Constraints: The Key Questions
Department of Computer Science - 30th anniversary year (1997-98)

Wednesday 6 May 1998

Constraints Day was the third of a series of one-day colloquia organised by the research groups in the Department. The programme included invited lectures on key research topics in this rapidly developing field from Peter van Beek and Bernhard Nebel, as well as a panel session exploring different perspectives on constraints within the UK research community.

Speakers:
Prof Peter van Beek, Department of Computing Science, University of Alberta:
Formulating a constraint satisfaction problem

Abstract: Constraint satisfaction problems (CSPs) are a simple representation and reasoning framework. A problem is represented as a set of variables, a domain of values for each variable, and a set of constraints between the variables. A solution is an instantiation of the variables that satisfies the constraints. In spite of the simplicity of the framework, many interesting problems have been formulated as CSPs, ranging from ones that are simple for humans, such as vision and language comprehension, to ones that are difficult for humans, such as scheduling.

As in all problem solving, there are three stages to solving a problem using the CSP framework: model the problem (by specifying the variables, their domains, and the constraints), solve the model, and verify and analyze the solution. Although widely applicable and elegant in theory, there are difficulties with applying the CSP framework in practice. One difficulty is in setting up the model itself. A second difficulty is that, once the model is set up, it might not be solvable in a reasonable amount of time. Sometimes the unreasonable time requirement is inherent in the problem. However, at times it is due to an unfortunate choice of model. It is well known within the constraint programming and operations research fields that often the key to effectively solving, for example, a difficult scheduling problem, is to hit upon the right model of the problem. For some problems, adding redundant constraints is crucial and for other problems the quality of the formulation depends on the choice of variables and their domains. In this talk, I will review the techniques for formulating and solving CSPs and then discuss my recent work on understanding what makes a good CSP model for a problem.
Prof Dr Bernhard Nebel, Institut für Informatik, University of Freiburg:
Constraints on time and space

Abstract: Qualitative temporal and spatial reasoning is usually treated as a particular form of constraint reasoning. In my talk, I will introduce three different qualitative calculi, contrast them with finite-domain CSPs, and describe the theoretical results that enable us to solve large temporal and spatial CSPs. In the last part of the talk, I will describe an application in the area of document interpretation, which uses qualitative spatial reasoning for identifying recipient addresses.
Dr Peter Jeavons and Dr David Cohen, Royal Holloway:
An anthropologist's view of constraints research

Abstract: Studying variations in culture is a central idea in anthropology - and can also be applied to any research community.

Following an exhaustive programme of investigation, involving numerous study visits to the jungles of South America, and remote university campuses in Europe and North America, we have discovered the existence of a number of academic "tribes" whose culture is based around the worship of "constraints". Each tribe has its own customs and language, and some are completely isolated from the real world.

One of the tribes can only count up to two, and insists that constraints are "logical" and must be "satisfied". Another tribe has a very visual culture, in which "colours" have a mysterious significance. Another worships only very large constraints, and sees all questions as "queries". Finally, there is a small group who appear to be continually generating new constraints at random, seeking some kind of "phase transition".

This talk presents a serious attempt to unify constraint research. It is our view that cross-fertilisation, not only between the different constraint areas, but between different areas of Computer Science and Mathematics, can be hampered by too parochial a viewpoint. On many occasions people end up solving the same problem using different terminology. In this talk we attempt to translate between these different cultures, and discuss what they might be able to learn from each other.
Panel session: So, what are the key questions?

Dr Patrick Prosser, Dept of Computer Science, Strathclyde University
Dr Barbara Smith, School of Computer Studies, University of Leeds
Dr Edward Tsang, Dept of Computer Science, University of Essex
Dr Mark Wallace, IC-Parc, Imperial College, London

back