Search is the most common tool for finding solutions in artificial intelligence. That being true, the most common work in the AI smithery is aimed at refining that tool. Such work can be classified into two main areas:
The hunter is savage. She kills without mercy to serve the needs of
the clan. The gatherer is gentle. He takes in all that supply the
needs of the group.
Much work has been done with regard to the hunters. Finding and using ``heuristics'' to guide search intelligently 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. Such a methodology is almost always combined with some concept of ``satisficing'' (Newell & Simon, 1972), a determination of whether a given answer is ``good enough,'' regardless of the fact that other ``better'' solutions may still be present in the search space.
Discovering appropriate heuristics for any given problem is another matter. Often ``experts'' in the field must be consulted, their methods for finding solutions analyzed, and means of implementing those methods computationally invented. MYCIN (Buchanan & Shortliffe, 1984) is a typical ``expert system'' whose search is based upon heuristic medical knowledge.
This research does not address heuristic search. Heuristics, by definition, are guesses, and thus can only lead to the most probable answers. In contrast, this work claims that by using the modified CSP techniques presented below, the most optimal solution can be guaranteed for computational semantic problems, even under reasonable time constraints. This is not to say that heuristics cannot be valuable in computational semantics, and in fact, heuristics could be easily added to the methods described here.
Some further clarifications regarding heuristics must be made. Heuristics can be used more conservatively as a method to order the search, without resorting to ``satisficing'' determinations which may leave optimal solutions undiscovered. Combined with other methods (namely branch-and-bound and solution synthesis), these ordering heuristics may potentially provide substantial pruning of the search space. There are several general ordering heuristics that are common in constraint satisfaction algorithms. These heuristics are discussed below in the ``Other Strategies for CSPs'' section. In addition, knowledge sources which evaluate solutions can also be seen as heuristics. For example, the fact that the Mikrokosmos lexicon constrains the AGENT of a SPEAK event to be a HUMAN is simply a heuristic. Metonymic speech, such as The White House said today ... often overrides the basic constraint. In all that follows, we assume a given knowledge source with all of its inherent heuristics. The control mechanisms developed here then find the best solution, given that knowledge.
The ``hunting'' techniques applied in this research are most closely related to the field of CSPs; a detailed summary of this work is given below. ``Branch-and-bound'' methods have been modified and adapted for work with CSPs, and are thus also described below. The recent work of Steve Minton and colleagues also provides an interesting comparison and will be summarized, along with techniques in linear programming and the related field of nonserial dynamic programming.
``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. Optimization problems, for instance, either need to examine all correct answers and select the most optimal, or they must utilize certain techniques such as branch-and-bound which allow them to ignore certain sections of the search space which can be guaranteed not to contain optimal answers. ``Solution synthesis'' addresses the need to determine all correct answers to a constraint satisfaction problem. Solution Synthesis techniques (Freuder, 1978; Tsang & Foster, 1990) iteratively combine (gather) partial answers together 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. Solution synthesis methods will be described below.
In sections 3 and following, the modifications and interactions of these ``hunter-gatherers'' utilized in this project will be developed. In particular, it will be shown that by combining branch-and-bound techniques with a novel solution synthesis method, the best solution for a computational semantic problem can be found in near-linear time. Also, the conversion of a means-end type text planner to a CSP will be described.