To summarize, a means-end planner is used locally to set up possible sub-plans. The sub-plans are connected with a system of usage constraints that inhibit or allow usage depending on the other sub-plans being used. The HUNTER-GATHERER system can then efficiently process the collection of sub-plans to find the best overall plan. Constraint satisfaction techniques described in (Beale, 96) automatically control the combination of sub-plans. Constraint satisfaction also ensures the soundness of all preconditions used in the lexicon entries, including those which are not related to the ideas presented above. Efficiency is gained by restricting the means-end planning component to local sub-problems. Solutions to these sub-problems are then combined, utilizing solution synthesis, branch-and-bound and constraint satisfaction, by HUNTER-GATHERER.
The HUNTER-GATHERER control architecture has been used extensively in the Mikrokosmos semantic analyzer. The following table shows actual results of semantic analyses of various size problems (from sentences selected randomly from our corpus):
Sent A Sent B Sent C # plans 79 95 119 exhaustive 7.8 Mil 56.7 Mil 235 Bil HUNT-GATHER 179 254 327
It is interesting to note that a 20% increase in the number of total
plans
(79 to 95)
results in a 626% increase (7.8M to 56M) in the number of exhaustive
combinations possible, but only a 42% increase (179 to 254) in the
number of combinations considered by HUNTER-GATHERER. As one moves on to
even more complex problems, a 25% increase (95 to 119) in the number
of plans catapults the exhaustive complexity by 414,600% (56M to 235B)
and yet only increases the HUNTER-GATHERER complexity by 29% (254 to 327).
As the problem size increases, the minor effects of
non-local interactions diminish with respect to the size of the
problem. We expect, therefore, the behavior of this algorithm to move
even closer to linear with larger problems (for example, ones
involving discourse).
Generation in the Mikrokosmos project is a relatively new development. Currently we are developing methods to reverse multilingual analysis lexicons. PICARD has been used to back-translate the semantic analyses of the Mikrokosmos analyzer using these reversed lexicons. Efficiency results similar to those reported above were obtained.
The HUNTER-GATHERER algorithms are complete with respect to the set of monotonic solutions. Currently, solutions with plans that temporarily violate preconditions of other plans (with the ``violation'' corrected by a later plan) will not be allowed. Besides this limitation, HUNTER-GATHERER is guaranteed to find the same solution(s) as an exhaustive search. In addition, the constraint satisfaction component of HUNTER-GATHERER ensures soundness. By converting means-end planners into a format that can be used by HUNTER-GATHER, PICARD achieves efficient processing with guaranteed soundness and completeness without sacrificing the generality of means-end planning.