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. Unfortunately, heuristic search cannot guarantee optimal answers.
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). This paper assumes a basic working knowledge of CSP techniques, although absence of such knowledge should not be a major stumbling block.
``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; 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. Because of its importance to this work, a brief overview of solution synthesis is given below.
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 natural language semantics,
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 semantic disambiguation (Nagao, 1992; Maruyama,
1990).
In addition to ``fuzzy''
constraints, costs are often associated with decisions, and optimal
solutions must take these into account. 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.