Hunters and Gatherers in AI: An introduction to constraint-based AI techniques

  
Figure 1: Basic Constraint Satisfaction Problem

  
Figure 2: Backtracking

In recent years, Constraint Satisfaction Problems (CSP) have received a good deal of attention in the computer science world (see [Tsang 93] for a detailed look at CSP). Constraint satisfaction techniques enable search procedures to prune off substantial portions of the search tree by identifying solution sets/subsets that cannot meet input constraints. For example, in Figure 1, three variables, A, B and C, with the domains given, are to have values chosen subject to the two constraints: [A = B] and [A < C].

A naive parser would try every combination of A, B and C until it found one that met the constraints (Figure 2). If all correct answers are desired, an exhaustive search is required. Notice that certain combinations that always lead to failure (A=0, B=x) are tried again and again. Constraint satisfaction programming techniques can eliminate this unnecessary processing. For instance, it can reduce A's domain to {1,2}, since 0 as a value for A can never satisfy the [A = B] constraint. Actually, A's domain can be reduced to {1}, since 2 as a value for A can never satisfy the [A < C] constraint. Once A is reduced to {1}, then B can also be reduced to {1}, and C can be reduced to {2}. Only one choice for each variable is left; thus, the answer is achieved without search. In section 2.1, we will overview the algorithms used to achieve constraint ``consistency'' in a search and examine some of the applications which have benefited from this kind of treatment.

  
Figure 3: Solution Synthesis

Solution synthesis (section 2.2) is a method of generating all valid answers to a search problem. Instead of working from the top of the tree down, solution synthesis attempts to combine legal combinations of nodes from the bottom up. Figure 3 gives a graphical overview of the process. Used in conjunction with constraint satisfaction techniques, solution synthesis is a powerful method for avoiding exponential time requirements associated with conventional tree search.

Branch-and-bound techniques (section 2.3) can be used to find the optimal solution without resorting to heuristics. The basic idea is displayed in Figure 4. In that Figure, a graph is displayed with the cost of each arc listed. The order of arc traversal used in a branch-and-bound algorithm is marked by circled numbers. The shortest total path accumulated at any point is always expanded next. If there is a tie, as is the case at the start node when no paths have been chosen yet, then the shortest next arc is taken. Arcs without circled numbers in Figure 4 were not tested, because they were extensions of paths of length greater than the length of a valid solution. Branch-and-bound identifies and eliminates paths which can be guaranteed to have more costly solutions than some valid solution.

  
Figure 4: Branch-and-Bound

Each of these AI methods, constraint satisfaction, solution synthesis and branch-and-bound will be described, the appropriate literature reviewed, and the situations under which they can be applied advantageously will be noted.