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

4.2.1 Constraints

In many domains, not all possible assignments of values to variables are permissible. A hard constraint, or simply constraint, specifies legal combinations of assignments of values to the variables.

A scope or scheme is a set of variables. A tuple on scope S is an assignment of a value to each variable in S. A constraint c on a scope S is a set of tuples on S. A constraint is said to involve each of the variables in its scope.

If S' is a set of variables such that S⊆S', and t is a tuple on S', constraint c is said to satisfy t if t, restricted to S, is in c.

Constraints can be defined using the terminology of relational databases. The main difference between constraints and database relations is that a constraint specifies legal values, whereas a database relation specifies what happens to be true in some situation. Constraints are also often defined intensionally, in terms of predicates (Boolean functions), to recognize legal assignments rather than extensionally by representing each assignment explicitly in a table. Extensional definitions can be implemented either by representing the legal assignments or by representing the illegal assignments.

Example 4.7: Consider a constraint on the possible dates for three activities. Let A, B, and C be variables that represent the date of each activity. Suppose the domain of each variable is {1,2,3,4}.

The constraint could be written as a table that gives the legal combinations:

A B C
2 2 4
1 1 4
1 2 3
1 2 4

which has scope {A,B,C}. Each row is a tuple that specifies a legal assignment of a value to each variable in the scope of the constraint. The first tuple is

{A=2,B=2,C=4}.

This tuple, which assigns A the value of 2, B the value of 2, and C the value of 4, specifies one of the four legal assignments of the variables.

This constraint satisfies the tuple {A=1,B=2,C=3,D=3,E=1}, because that tuple assigns legal values to the variables in the scope.

This constraint could also be described intensionally by using a predicate - a logical formula - to specify the legal assignments. The preceding constraint could be specified by

(A ≤ B) ∧(B<3) ∧(B<C) ∧¬(A=B ∧C=3),

where ∧ means and, and ¬ means not. This formula says that A is on the same date or before B, and B is before 3, and B is before C, and it cannot be that A and B are on the same date and C is on day 3.

A unary constraint is a constraint on a single variable (e.g., X≠4). A binary constraint is a constraint over a pair of variables (e.g., X≠Y). In general, a k-ary constraint has a scope of size k.

A possible world w satisfies a set of constraints if, for every constraint, the values assigned in w to the variables in the scope of the constraint satisfy the constraint. In this case, we say that the possible world is a model of the constraints. That is, a model is a possible world that satisfies all of the constraints.

Example 4.8: 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
dom(A)={1,2,3,4},dom(B)={1,2,3,4},dom(C)={1,2,3,4},
dom(D)={1,2,3,4},dom(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)}

The aim is to find a model, an assignment of a value to each variable, such that all the constraints are satisfied.

Example 4.9: Consider the constraints for the two representations of crossword puzzles of Example 4.4.
  1. For the case in which the domains are words, the constraint is that the letters where a pair of words intersect must be the same.
  2. For the representation in which the domains are the letters, the constraint is that contiguous sequences of letters must form legal words.
Example 4.10: In Example 4.6, consider some typical constraints. It may be that certain activities have to be on different days or that other activities have to be in the same town on the same day. There may also be constraints that some activities must occur before other activities, or that there must be a certain number of days between two activities, or that there cannot be three activities on three consecutive days.