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.2 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 some of the variables.

A scope is a set of variables. A relation on a scope S is a function from assignments on S to {true,false}. That is, it specifies whether each assignment is true or false. A constraint c is a scope S and a relation on S. A constraint is said to involve each of the variables in its scope.

A constraint can be evaluated on any assignment that extends its scope. Consider constraint c on S. Assignment A on S′, where S⊆S′, satisfies c if A, restricted to S, is mapped to true by the relation. Otherwise, the constraint is violated by the assignment.

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.

Constraints are defined either by their intension, in terms of formulas, or by their extension, listing all the assignments that are true. Constraints defined extensionally can be seen as relations of legal assignments as in relational databases.

A unary constraint is a constraint on a single variable (e.g., B≤3). A binary constraint is a constraint over a pair of variables (e.g., A≤B). In general, a k-ary constraint has a scope of size k. For example, A+B=C is a 3-ary (ternary) constraint.

Example 4.6.

Suppose a robot needs to schedule a set of activities for a manufacturing process, involving casting, milling, drilling, and bolting. Each activity has a set of possible times at which it may start. The robot has to satisfy various constraints arising from prerequisite requirements and resource use limitations. For each activity there is a variable that represents the time that it starts. For example, it could use D to represent the start time for the drilling, B for the start time of the bolting, and C the start time for the casting. Some constraints are that drilling must start before bolting, which translates into the constraint D<B. If casting and drilling must not start at the same time, this corresponds to the constraint C≠D. If bolting must start exactly 3 time units after casting starts this corresponds to the constraint B=C+3.

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}.

A constraint with scope {A,B,C} could be described by its intension, using a logical formula to specify the legal assignments, such as

(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 day 3, B is before C, and it cannot be that A and B are on the same date and C is on or before day 3.

This constraint could instead have its relation defined its extension, as a table specifying the legal assignments:

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

The first assignment is {A=2,B=2,C=4}, which assigns A the value 2, B the value 2, and C the value 4. There are four legal assignments of the variables.

The assignment {A=1,B=2,C=3,D=3,E=1} satisfies this constraint because that assignment restricted to the scope of the relation, namely {A=1,B=2,C=3}, is one of the legal assignments in the table.

Example 4.8.

Consider the constraints for the two representations of crossword puzzles of Example 4.3:

  • •

    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.

  • •

    For the representation in which the domains are the letters, the constraint is that each contiguous sequence of letters must form a legal word.