Section 1 : Constraint satisfaction problems

Commentary

Section Goals

• To discuss the definition and representation of constraint satisfaction problems.
• To introduce the two different formulations of CSPs, and the features of constraints.

Section Notes

• The focus of this section is on the formal definition of CSP, and the representation of constraints.

Learning Objectives

Learning Objective 1

• Explain the following concepts or terms:
  • Constraint satisfaction problem
  • Constraints
  • Incremental formulation
  • Complete-state formulation
  • Linear and nonlinear constraints
  • Auxiliary variables
  • Preference constraints
• Describe and draw a sample constraint graph.
• Summarize the difference in problem representation between CSPs and state-space search.

Objective Readings

Required Readings

Reading topics:

Constraint Satisfaction Problems (see Section 6.1 of AIMA3ed)

Bistarelli, S., Montanari, U., and Rossi, F. (1997). Semiring-based constraint satisfaction and optimization. Journal of the Association for Computing Machinery, 44(2), 201-236.

(Note: this article is related to CSP preferences)

Objective Questions

• What do the arcs mean in the context of the constraint graph representing the map-colouring problem (Section 6.1 of AIMA3ed)?
• What are the differences between the incremental formulation of CSP and the state-space search?

Objective Activities

• Find some more examples, either from your field or from publications that can be represented as CSPs.
• Explore the code for CSP class in either Java or Python from the textbook's website.
• Browse the books listed in Supplemental Unit Readings to gain a better understanding of CSP and its application.
• Complete Exercise 6.1 of AIMA3ed.