CSP techniques can be used in conjunction with many other AI search
strategies. The most basic of these strategies is called
``lookahead.'' In fact, lookahead is not an additional strategy, but
simply a full, dynamic application of consistency checking. At each decision
point in a search, a value is assigned to a variable. This implicitly
removes the other possible values of that variable; thus, other
variables that depend on those values can be affected. By applying
the consistency algorithm,
these effects can be automatically propagated at each
decision point.
There are various strategies used to handle backtracking. The most advantageous of these, used in conjunction with constraint analysis, is called ``dependency-directed backtracking.'' When the need for backtracking arises, constraint analyses can help indicate what the source of the current conflict is. The search can then be backtracked directly to the source of the problem. This can potentially eliminate large areas of search that will not ``fix'' the current bottleneck. Because backtracking is eliminated in solution synthesis methods, the various backtracking strategies are not relevant to this research.
Heuristics can be used to great advantage in search. At any branching point, each choice can be analyzed using heuristic knowledge to estimate how much closer to a solution the choice brings the search. Choices with higher heuristic value can be followed first, a technique generally referred to as ``best-first'' search. Optimal solutions cannot be guaranteed with heuristic search, however, because local optima can obscure longer-term solutions. For instance, turning south seems like a bad choice when your goal is north, unless there is a freeway one block to the south that can speedily take you on your way. Some types of problems require heuristic search to make them tractable. Any problem with an exponentially growing search space that is irreducible with CSP techniques will quickly become unmanageable. Prior to the current research, the Mikrokosmos project relied on heuristic search in its analysis of natural language semantics. It is the thesis of this report, however, that CSP techniques in combination with branch-and-bound and solution synthesis can deliver guaranteed optimal solutions in near-linear time for computational semantic problems. Therefore, heuristic search is not necessary. On the other hand, even with near-linear time speed, large problems, especially those involving discourse, are nowhere near ``real-time.'' Best-first techniques can be added to those described below to improve this situation.
A different kind of heuristic can be used to optimally order the instantiations of variables and their values. These heuristics can be labeled more accurately as ``strategies,'' because they involve general principles rather than world knowledge. These types of strategies are closely connected to constraint analysis; a good discussion of them can be found in [Tsang, 1993]. The first is called ``minimal width ordering'' (MWO). In general terms, this strategy seeks to instantiate more highly constrained variables first, in hopes that backtracking will be reduced. For example, if variable A constrains variable B to value X and variable C to Y, it would be advantageous to instantiate variable A first. This would reduce the number of choices in B and C, which in turn might restrict choices elsewhere. If variable C was instantiated first, values for it might be tried that conflict with variable A.
Alternatively, a ``minimal bandwidth ordering'' (MBO) can be used. This ordering seeks to place constrained variables close together so that when backtracking is necessary, only a small distance will have to be backtracked, minimizing the amount of work that might have to be repeated. For example, if variable A constrains B to X, but B is instantiated first, followed by C, D, E and F, then when A is finally instantiated, the search will need to backtrack to B and then recalculate values for C, D, E and F as well. If, on the other hand, A was instantiated directly after B, backtracking would proceed directly to B, with no intervening variables affected.
Of course, a dynamic
implementation of arc consistency reduces the importance of these
types of orderings. First of all, before search even began,
conflicting values will be removed from any variables domain. In
addition, during search, when a value for a variable is
chosen, all variables affected by the choice can be dynamically
processed, with all those effects recursively propagated, etc.. Thus, a
dynamic implementation of arc-consistency inherently gives the
benefits of MWO and MBO. This notwithstanding, these techniques can
still give some advantage. If two or more variable instantiations
work together to eliminate certain values of other
variables, it would
be advantageous to process these ``partners'' early. Since ordering
more constrained variables first maximizes this potential, a minimal
width ordering would be helpful.
Solution synthesis, however, alters the picture somewhat. Solution synthesis combines small sub-solutions together to form larger and larger solutions. Interactions outside of the subsets being combined are not noticed. Because of this, it would be helpful to group variables together in such a way as to minimize the amount of ambiguity carried along in the sub-solutions. By grouping variables (and later sub-solutions) together that constrain each other maximally, ambiguity can be eliminated as early as possible. This type of variable grouping is an outgrowth of MBO. This project uses MBO concepts to group variables and synthesized solutions together in order to minimize ambiguity within the sub-solution. This goes well beyond a simple linear ordering of variables on which an SS-TSANG-like algorithm would work.
MWO and MBO help determine which order to instantiate variables. There are also techniques which help decide, given a variable, which values to try first. While variable ordering techniques seek to maximally constrain so that backtracking can be identified early, value ordering techniques seek to eliminate backtracking by trying the most likely values first. For problems in which all possible solutions are required (or the most optimal), these techniques are not helpful. All values that result in solutions must be attempted; it does not matter which order they are found.