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 and 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. 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 seek to constrain and 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 speach, 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.
``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 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 the section 3, ``Hunters and Gatherers in Computational Semantics,'' 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.