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.
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.
Topics: Pre-processing to reduce problems. Arc consistency. Path consistency. Strong k-consistency. Some consistency algorithms.
Topics: General search strategies. Chronological backtracking. Forward checking (lookahead). Dependency directed backtracking. Backjumping/backmarking. Dynamic search ordering. Incomplete search techniques.
Topics: Acyclic graphs - trees. Tree width. Minimal cut-sets. Local to global consistency. The relational/graph separation. Problem decomposition. Some tractable constraint classes.
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
Back to MSc by Research in Computer Science Home Page