foundations of computational agents
Although depth-first search over the search space of assignments is usually a substantial improvement over generate and test, it still has various inefficiencies that can be overcome.
In Example 4.12, the variables and are related by the constraint . The assignment is inconsistent with each of the possible assignments to because . In the course of the backtrack search (see Figure 4.1), this fact is rediscovered for different assignments to and . This inefficiency can be avoided by the simple expedient of deleting from , once and for all. This idea is the basis for the consistency algorithms.
The consistency algorithms are best thought of as operating over the network of constraints formed by the CSP:
There is a node for each variable. These nodes are drawn as circles or ovals.
There is a node for each constraint. These nodes are drawn as rectangles.
Associated with each variable, , is a set of possible values. This set of values is initially the domain of the variable.
For every constraint , and for every variable in the scope of , there is an arc .
Such a network is called a constraint network.
Consider Example 4.12. There are three variables , , and , each with domain . The constraints are and . In the constraint network, shown in Figure 4.2, there are four arcs:
The constraint has one arc:
The constraint has three arcs:
In the simplest case, when a constraint has just one variable in its scope, the arc is domain consistent if every value of the variable satisfies the constraint.
The constraint has scope . With this constraint, and with , the arc is not domain consistent because violates the constraint. If the value 3 were removed from the domain of , then it would be domain consistent.
Suppose constraint has scope . Arc is arc consistent if, for each value , there are values where , such that is satisfied. A network is arc consistent if all its arcs are arc consistent.
Consider the network of Example 4.14 shown in Figure 4.2. None of the arcs are arc consistent. The first arc is not arc consistent because for there is no corresponding value for for which . If were removed from the domain of , then it would be arc consistent. The second arc is not arc consistent because there is no corresponding value for when .
If an arc is not arc consistent, there are some values of for which there are no values for for which the constraint holds. In this case, all values of in for which there are no corresponding values for the other variables can be deleted from to make the arc consistent. When a value is removed from a domain, this may make some other arcs that were previously consistent no longer consistent.
The generalized arc consistency (GAC) algorithm is given in Figure 4.3. It makes the entire network arc consistent by considering a set to_do of potentially inconsistent arcs, the to-do arcs. The set to_do initially consists of all the arcs in the graph. While the set is not empty, an arc is removed from the set and considered. If the arc is not arc consistent, it is made arc consistent by pruning the domain of variable . All of the previously consistent arcs that could, as a result of pruning , have become inconsistent are placed back into the set to_do. These are the arcs , where is a constraint different from that involves , and is a variable involved in other than .
Consider the algorithm GAC operating on the network from Example 4.14, with constraints , . Initially, all of the arcs are in the to_do set. Here is one possible sequence of selections of arcs.
Suppose the algorithm first selects the arc . For , there is no value of that satisfies the constraint. Thus, is pruned from the domain of . Nothing is added to to_do because there is no other arc not in to_do.
Suppose that is selected next. The value is pruned from the domain of . Again no arc is added to to_do.
Suppose that is selected next. The value is removed from the domain of . Because the domain of has been reduced, the arc must be added back into the to_do set because the domain of could potentially be reduced further now that the domain of is smaller.
If the arc is selected next, the value is pruned from the domain of .
The remaining arc on to_do is . The values and are removed from the domain of . No arcs are added to to_do because is not involved in any other constraints, and to_do becomes empty.
The algorithm then terminates with , , . Although this has not fully solved the problem, it has greatly simplified it. For example, depth-first backtrackingsearch would now solve the problem more efficiently.
Consider applying GAC to the scheduling problem of Example 4.9. The network shown in Figure 4.4 has already been made domain consistent (the value 3 has been removed from the domain of and has been removed from the domain of ). Suppose arc is considered first. The arc is not arc consistent because is not consistent with any value for in , so 1 is deleted from . becomes and arcs , and could be added to to_do but they are in to_do already.
Suppose arc is considered next; then is reduced to and arc goes back into the to_do set to be reconsidered.
Suppose arc is next; then is further reduced to the singleton . Processing arc prunes to . Making arc consistent reduces to . Processing reduces to . Then arc reduces to . Finally, arc reduces to . All arcs remaining in the queue are consistent, and so the algorithm terminates with the to_do set empty. The set of reduced variable domains is returned. In this case, the domains all have size 1 and there is a unique solution: , , , , .
Regardless of the order in which the arcs are considered, the algorithm will terminate with the same result, namely, an arc consistent network and the same set of reduced domains. Three cases are possible, depending on the state of the network upon termination:
In the first case, one domain becomes empty, indicating there is no solution to the CSP. Note that, as soon as any one domain becomes empty, all the domains of connected nodes will become empty before the algorithm terminates.
In the second case, each domain has a singleton value, indicating that there is a unique solution to the CSP, as in Example 4.19.
In the third case, every domain is non-empty and at least one has multiple values left in it. In this case, we do not know whether there is a solution or what the solutions look like (unless just a single domain has multiple values). Methods to solve the problem in this case are explored in the following sections.
The following example shows that it is possible for a network to be arc consistent even though there is no solution.
Suppose there are three variables, , and , each with the domain . Consider the constraints , , and . This is arc consistent: no domain can be pruned using any single constraint. However, there are no solutions. There is no assignment to the three variables that satisfies the constraints.
Consider the time complexity of the generalized arc consistency algorithm for binary constraints. Suppose there are binary constraints, and the domain of each variable is of size . There are arcs. Checking an arc involves, in the worst case, iterating through each value in the domain of for each value in the domain of , which takes time. This arc may need to be to be checked once for every element in the domain of , thus GAC for binary variables can be done in time , which is linear in , the number of constraints. The space used is where is the number of variables and is the domain size. Exercise 4 explores the complexity of more general constraints.
Various extensions to arc consistency are also possible. The domains need not be finite; they may be specified using intensions, not just lists of their values. It is also possible to prune the constraints if the constraints are represented extensionally: if a value has been pruned for a variable , this value can be pruned from all constraints that involve . Higher-order consistency techniques, such as path consistency, consider -tuples of variables at a time, not just pairs of variables that are connected by a constraint. For example, by considering all three variables, you can recognize that there is no solution in Example 4.20. These higher-order methods are often less efficient for solving a problem than using arc consistency augmented with the methods described below.