foundations of computational agents
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 is a function from assignments on to . That is, it specifies whether each assignment is true or false. A constraint is a scope and a relation on . 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 on . Assignment on , where , satisfies if , restricted to , is mapped to true by the relation. Otherwise, the constraint is violated by the assignment.
A possible world satisfies a set of constraints if, for every constraint, the values assigned in 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., ). A binary constraint is a constraint over a pair of variables (e.g., ). In general, a -ary constraint has a scope of size . For example, is a 3-ary (ternary) constraint.
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 to represent the start time for the drilling, for the start time of the bolting, and the start time for the casting. Some constraints are that drilling must start before bolting, which translates into the constraint . If casting and drilling must not start at the same time, this corresponds to the constraint . If bolting must start exactly 3 time units after casting starts this corresponds to the constraint .
Consider a constraint on the possible dates for three activities. Let , , and be variables that represent the date of each activity. Suppose the domain of each variable is .
A constraint with scope could be described by its intension, using a logical formula to specify the legal assignments, such as
where means and, and means not. This formula says that is on the same date or before , and is before day , is before , and it cannot be that and are on the same date and is on or before day 3.
This constraint could instead have its relation defined its extension, as a table specifying the legal assignments:
The first assignment is , which assigns the value 2, the value 2, and the value 4. There are four legal assignments of the variables.
The assignment satisfies this constraint because that assignment restricted to the scope of the relation, namely , is one of the legal assignments in the table.
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.