Constraint satisfaction is a major discipline in modern artificial intelligence. However, it is too advanced or specialised to be included in an undergraduate programme.

Clearly it is necessary for those attempting a project in constraint satisfaction to have a strong background in both the theoretical and practical aspects of the subject. This course aims to give the student sufficient understanding of, and practice with, constraint problems, and to successfully choose and deliver a good research project in the area.

At the end of this course the student will have an understanding of constraint satisfaction as a paradigm for general problem solving and will be able to formulate a problem as a Constraint Satisfaction Problem.

Students will understand some of the standard algorithms for pre-processing and solving constraint problems.

Students will understand the essential mathematical theory underpinning the subject - both as it relates to the underlying graphs of problems, and how it relates to the constraint structure.

Students will have an overview of the key current research areas.

The course will consist of four parts.

- What are constraints? This will begin with basic definitions and introduce the student to the problems associated with constraint formulation. Through practical examples the student will see alternative models and why they are important. The section will include a short introduction to the area of complexity of constraint problems.
- Consistency Techniques. In this section students will be shown
how pre-processing can lead to simplified but equivalent problems.
Different kinds of problem reduction will be covered. The section will
end with an in depth look at some of the best consistency algorithms in
use today.
**Topics:**Pre-processing to reduce problems. Arc consistency. Path consistency. Strong k-consistency. Some consistency algorithms. - Basic Algorithms. In this section all basic types of constraint
solving algorithms will be covered. This will include traditional
methods as well as recent research developments.
**Topics:**General search strategies. Chronological backtracking. Forward checking (lookahead). Dependency directed backtracking. Backjumping/backmarking. Dynamic search ordering. Incomplete search techniques. - Underlying theory. Here students will cover essential
mathematical theory that underpins constraint satisfaction. This will
begin with notions from graph theory and relational algebra. Students
will apply this knowledge to constraint problem decomposition, complexity
bounding, and solution techniques.
**Topics:**Acyclic graphs - trees. Tree width. Minimal cut-sets. Local to global consistency. The relational/graph separation. Problem decomposition. Some tractable constraint classes.

Topics:Problems seen as assignments to constrained variables. A general framework. An alternative formulation. The problem of modelling. Different models for the same problems. Complexity. Model equivalence.

Dave Cohen

Mostly students will be referring to the book:

**Foundations of Constraint
Satisfaction**, Edward Tsang, Academic Press 1993

However, research papers will be covered as and when they are
appropriate.

Back to MSc by Research in Computer Science Home Page

Last updated
Fri, 23-Jan-2009 15:12
GMT / PS

•

•

Department of Computer Science,
University of London,
Egham,
Surrey TW20 0EX

Tel/Fax : +44 (0)1784 443421 /439786

Tel/Fax : +44 (0)1784 443421 /439786

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@

@@('' )@@