4.1 Possible Worlds, Variables, and Constraints

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

4.1.3 Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) consists of

  • •

    a set of variables,

  • •

    a domain for each variable, and

  • •

    a set of constraints.

A finite CSP has a finite set of variables and a finite domain for each variable. Some of the methods considered in this chapter only work for finite CSPs, although some are designed for infinite, even continuous, domains.

Example 4.9.

Suppose the delivery robot must carry out a number of delivery activities, a, b, c, d, and e. Suppose that each activity happens at any of times 1, 2, 3, or 4. Let A be the variable representing the time that activity a will occur, and similarly for the other activities. The variable domains, which represent possible times for each of the deliveries, are

𝑑𝑜𝑚⁢(A)={1,2,3,4},𝑑𝑜𝑚⁢(B)={1,2,3,4},𝑑𝑜𝑚⁢(C)={1,2,3,4},
𝑑𝑜𝑚⁢(D)={1,2,3,4},𝑑𝑜𝑚⁢(E)={1,2,3,4}.

Suppose the following constraints must be satisfied:

{ (B≠3),(C≠2),(A≠B),(B≠C),(C<D),(A=D),
(E<A),(E<B),(E<C),(E<D),(B≠D)}

It is instructive for you to try to find a model for this example; try to assign a value to each variable that satisfies these constraints.

Given a CSP, a number of tasks are useful:

  • •

    Determine whether or not there is a model.

  • •

    Find a model.

  • •

    Count the number of models.

  • •

    Enumerate all of the models.

  • •

    Find a best model, given a measure of how good models are.

  • •

    Determine whether some statement holds in all the models.

The multidimensional aspect of CSPs, where each variable is a separate dimension, makes these tasks difficult to solve, but also provides structure that can be exploited.

This chapter mostly considers the problem of finding a model. Some of the methods can also determine if there is no model, and can be adapted to finding all models. What may be more surprising is that some of the methods can find a model if one exists, but they cannot determine that there is no model if none exists.

CSPs are very common, so it is worth trying to find relatively efficient ways to solve them. Determining whether there is a model for a CSP with finite domains is NP-complete (see box) and no known algorithms exist to solve such problems that do not use exponential time in the worst case. However, just because a problem is NP-complete does not mean that all instances are difficult to solve. Many instances have structure to exploit.