Meeting 07: Constraint Satisfaction

Reading: AIAMA 6.1-6.2

This section is an example of how a richer representation of the problem can lead to improvements in agents, specifically agents whose models use a factored representation. A class of problems that can be solved efficiently in this fashion are the Constraint Satisfaction Problems or CSPs. Section 6.1 defined formally what a CSP is and provides some examples. Section 6.2 defines our first set of inference algorithms, those that operate on CSPs, i.e. arc, node, and path consistency.

Questions you should be able to answer after reading are:

  1. What are the three components of a CSP?
  2. What is the difference between a complete and partial assignment?
  3. What are some examples of CSPs including each component?
  4. What complications do infinite domains bring to a CSP?
  5. What are the different types of constraints in a CSP?
  6. What does it mean for a variable to be node consistent?
  7. What does it mean for a variable to be arc consistent?
  8. What is the most popular algorithm for ensuring arc consistency?
  9. What does it mean for three variables to be path consistent?