Unit 2: Constraint Satisfaction Problems (CSP) and Distributed CSP

Commentary

This unit discusses constraint satisfaction problems (CSPs), a class of problems that consist of variables with constraints on them, which are represented in a simple, standardized, and structured way, such as a constraint graph. CSPs are prevalent in many different application fields, and thus draw lot of attention from the AI and computing science community. This unit focuses on the definition of CSP, and backtracking and intelligent backtracking search for CSPs. This unit also discusses the CSP problem structure and local search. Finally, distributed CSP is introduced in the required readings.

Unit Purpose

When you complete this unit, you will be able to

• Describe the representation and formation of CSPs.
• Analyse and design backtracking and local search algorithms for CSPs.
• Take advantage of the structure of problems to solve CSPs.
• Explain the recent progress in CSP research and application.

Section 1: Constraint satisfaction problems
Section 2: Backtracking and intelligent backtracking search for CSPs
Section 3: Local search and problem structures of CSPs
Section 4: Distributed CSPs

Readings

Required readings:

Browse through some of the papers from Faltings, B., and Yokoo, M. (eds.). (2005). Special issue: Distributed constraint satisfaction. Artificial Intelligence, 161(1-2), 1-250.

Supplemental Unit Readings

Bordeaux, L., Hamadi, Y., and Zhang, L. (2006). Propositional satisfiability and constraint programming: A comparative survey. ACM Computing Surveys. 38(4), Article 12. https://doi.acm.org/10.1145/1177352.1177354

Books:

Marriott, K., and Stuckey, P. J. (1998). Programming with Constraints: An Introduction. Cambridge, MA: MIT Press,.

Dechter, R. (2003). Constraint Processing. San Francisco, CA: Morgan Kaufmann.

Related journals: Artificial Intelligence, and Constraints

Related conferences: International Conference on Principles and Practice of Constraint Programming. (See: https://link.springer.com/conference/cp/). Note that the full-text proceedings from 2000 to 2009 are available via AU Library.

Note: The journals and conference papers can be accessed through the AU Library links to Elsevier or Springer

Activities

• Explore the list of supplemental unit readings, and track the frontiers of research and application of CSP.
• Analyse the potential application of CSP in areas you are familiar with.