HUNTER-GATHERER is complete
because it guarantees
the same results as an exhaustive planner. The solution synthesizer,
at every step, exhaustively calculates all of the valid combinations
of plans for that synthesis. The only combinations that are removed
are:
Exhaustive planners are obviously complete, so HUNTER-GATHERER must be as well.
Two exceptions exist, however. The first has to do with the types of constraints allowed by HUNTER-GATHERER. One of the drawbacks inherent in a text generator like Penman is the inability of the modules to communicate with each other. One of the main characteristics of driving this project is the inter-action of choices available at different levels. HUNTER-GATHERER specifically allows for these inter-actions. There is, however, a class of constraints that this system cannot at present address. It is not able to use constraints that arise from the combination of plan effects. Thus a constraint such as ``if the clause is already 30 words long, make a sentence boundary'' cannot be used. This limitation exists because simple precondition-effect pairs cannot be set up. A precondition like ``sentence 30 words long?'' is satisfied by combining the effects of many plans together. Section 3.5 addresses this problem and suggests a number of possible alternative methods for handling it.
The second limitation with regards to completeness has already been mentioned. Non-monotonic plans are not allowed. Non-monotonic plans are those which at intermediate stages contain constraint conflicts which are later resolved in the overall plan. While we recognize that this may be a severe limitation in generalized AI planning, we do not feel it presents much of a problem for computational semantics, where preconditions and effects are generally fairly simple. As we look into using HUNTER-GATHERER in other applications, we plan on investigating this limitation further.