Third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including the full text).
4.6 Domain Splitting
Another method for simplifying the network is domain splitting or case analysis. The idea is to split a problem into a number of disjoint cases and solve each case separately. The set of all solutions to the initial problem is the union of the solutions to each case.
In the simplest case, suppose there is a binary variable X with domain {t,f}. All of the solutions either have X=t or X=f. One way to find them is to set X=t, find all of the solutions with this assignment, and then assign X=f and find all solutions with this assignment. Assigning a value to a variable gives a smaller reduced problem to solve.
If the domain of a variable has more than two elements, for example if the domain of A is {1,2,3,4}, there are a number of ways to split it:
- Split the domain into a case for each value. For example, split A into the four cases A=1, A=2, A=3, and A=4.
- Always split the domain into two disjoint subsets. For example, split A into the two cases A∈{1,2} and the case A∈{3,4}.
The first approach makes more progress with one split, but the second may allow for more pruning with fewer steps. For example, if the same values for B can be pruned whether A is 1 or 2, the second case allows this fact to be discovered once and not have to be rediscovered for each element of A. This saving depends on how the domains are split.
Recursively solving the cases using domain splitting, recognizing when there is no solution based on the assignments, is equivalent to the search algorithm of Section 4.4. We can be more efficient by interleaving arc consistency with the search.
One effective way to solve a CSP is to use arc consistency to simplify the network before each step of domain splitting. That is, to solve a problem,
- simplify the problem using arc consistency; and,
- if the problem is not solved, select a variable whose domain has more than one element, split it, and recursively solve each case.
One thing to notice about this algorithm is that it does not require a restart of the arc consistency from scratch after domain splitting. If the variable X has its domain split, TDA can start with just the arcs that are possibly no longer arc consistent as a result of the split; these are only the arcs of the form ⟨Y,r⟩, where X appears in r and Y is a variable, other than X, that appears in constraint r.
- B=2. In this case A=2 is pruned. Splitting on C produces two of the answers.
- B=3. In this case C=3 is pruned. Splitting on A produces the other two answers.
This search tree should be contrasted with the search tree of Figure 4.1. The search space with arc consistency is much smaller, and it was not as sensitive to the selection of variable orderings. [Figure 4.1 would be much bigger with different variable orderings.]
One other enhancement can make domain splitting much more efficient. If assigning values to the variables disconnects the graph, each disconnected component can be solved separately. The solution to the complete problem is the cross product of the solutions to each component. This can save much computation when one is counting the number of solutions or finding all solutions. For example, if one component has 100 solutions and the other component has 20 solutions, there are 2,000 solutions. This is a more efficient way to count than finding each of the 2,000 solutions separately.
