Search is the most common tool for finding solutions in artificial intelligence. The two paths to higher efficiency in search are
Much work has been done with regard to the hunters. Finding and using heuristics to guide search has been a major focus. Heuristics are necessary when other techniques cannot reduce the size of the search space to reasonable proportions. Under such circumstances, ``guesses'' have to be made to guide the search engine to the area of the search space most likely to contain acceptable answers. ``Best-first'' search (see, among many others, (Charniak et al. 1987)) is an example of how to use heuristics.
The ``hunting'' techniques applied in this research are most closely related to the field of constraint satisfaction problems (CSP). (Beale 1996) overviews this field and (Tsang 1993) covers it in depth. Further references include (Mackworth 1977), (Mackworth & Freuder 1985) and (Mohr & Henderson 1986).
``Gathering'' has been studied much less in AI. Most AI problems are content with a single ``acceptable'' answer. Heuristic search methods generally are sufficient. Certain classes of problems, however, demand all correct answers. ``Solution synthesis'' addresses this need. Solution synthesis techniques (Freuder 1978; see also Tsang & Foster 1990), iteratively combine (gather) partial answers to arrive at a complete list of all correct answers. Often, this list is then rated according to some separate criteria in order to pick the most suitable answer.
In a ``blocks'' world, CSP techniques and solution
synthesis are powerful mechanisms. Many ``real-world'' problems, however,
have a more complex semantics: constraints are not ``yes'' or ``no''
but ``maybe'' and ``sometimes.'' In NL, certain word-sense
combinations might make sense in one context but not in another. This
is the central problem with previous attempts at using constraint
analysis for NL disambiguation (Nagao 1992; Maruyama
1990).
We
need a method as powerful as CSP for
this more complex environment. Our proposal is to 1) use constraint
dependency information to partition problems into appropriate
sub-problems, 2) combine (gather) results from these sub-problems using a
new solution synthesis technique, and 3) prune (hunt) these results
using branch-and-bound techniques.
The rest of this paper addresses each of these issues in turn.