It would be useful if we could divide text planning problems into relatively independent sub-problems and use HUNTER-GATHERER's solution synthesis to efficiently combine the smaller solutions. The problem is that solution synthesis requires an unchanging, orderly set of variables to start with. In Figure 3, there are 4 variables, A, B, C and D. Each one of these variables has a set of possible solutions. Three second order nodes are created, AB, BC and CD. From these, the ABC and BCD third order nodes are created and, finally, the answer, ABCD, is synthesized.
In text planning, as in all types of means-end planning systems, there is no fixed number of variables. ``Variable,'' in this context, refers to a set of possible plans from which one must be chosen. A variable can be set up for ACQUIRE, which has three possible plans. One of them must be chosen. On the other hand, sometimes a plan for instrument is needed, and sometimes not. For instance, if ACQUIRE-1 (Figure 22) is used, a separate sub-plan must be made for the instrument relation. Two ``variables'' would be needed, one for ACQUIRE and one for instrument. If the ACQUIRE-2 is used, the instrument plan and variable are unnecessary. Lexicon entries which have different set of VARS, different preconditions and/or contain more or fewer relations all create differing amounts of sub-plans. These differences are compounded as different paths through the space of possible plans are taken.
PICARD solves this problem in a simple way. Means-end planning is
carried out locally to determine, for each lexicon entry, the
additional sub-plans that are needed. Again, these sub-plans correspond
to VARs and missing relations or preconditions in the lexicon entry. For
instance, the ACQUIRE-1 entry requires a sub-plan for the missing
instrument relation. For each needed sub-plan, a ``usage
constraint'' is added to the lexicon entry that will ``request'' some
``non-dummy''
sub-plan
to be used that
fulfills the need. The ACQUIRE-1 entry,
for example, would receive a usage constraint that requires it to use
one of the sub-plans for instrument. In addition, for each of
the sub-plans that can fill the need, a usage constraint is added such
that those entries can only be used if ``requested'' by some other
plan.
For each semantic concept and relation that is included in the lexicon entry, a dummy sub-plan is created. For instance, in the ACQUIRE-2 entry, a dummy instrument sub-plan is created and added to the list of other instrument sub-plans. The ACQUIRE-2 entry then receives a usage constraint that ``requests'' the use of the dummy sub-plan. The dummy sub-plan receives a usage constraint that it be used only if ``requested.'' The fact that ACQUIRE-2 does not ``request'' one of the non-dummy instrument plans will prevent them from being used.
The main benefit this gives is that a stable set of ``variables'' can be created. There will be an ACQUIRE variable, from which one of the three lexicon entries must be selected. There will be an instrument variable, from which either the entry shown in Figure 23 will be used or the newly created dummy entry. These variables can then be processed by a solution synthesis algorithm. Whenever a choice is made, for instance selecting ACQUIRE-1 for AQUIRE, the constraint satisfaction mechanism in HUNTER-GATHERER will eliminate all conflicting sub-plans. Picking entry ACQUIRE-1 will eliminate the dummy entry for instrument. Choosing entry ACQUIRE-2 will eliminate all of the non-dummy instrument plans, as well as all the sub-plans that are created by the instrument plans. In this way, local means-end plans can be linked together, but can be processed globally by an efficient solution synthesis control. Figure 25 graphically displays the usage constraints for a portion of the example problem. The dotted lines connecting plans indicate compatible usage constraints.
Usage constraints are implemented by adding a series of preconditions and effects to each lexicon entry. For instance, for ACQUIRE-1 to ``request'' that an instrument slot be filled, the following effect is added to it:
EFFECT: (FILL (ACQUIRE instrument)) Each of the non-dummy plans for instrument - only one in this case - then receive a precondition:
PRECONDITION: (FILL (ACQUIRE instrument)) This precondition cannot be fulfilled unless another plan with the corresponding effect is used.
To request a dummy filler, an effect like this is added:
EFFECT: (FILL (ACQUIRE instrument-dummy)) The dummy instrument then is given this precondition:
PRECONDITION: (FILL (ACQUIRE instrument-dummy)) Each concept (like ACQUIRE) and relation (like instrument) is linked to actual, uniquely-named structures in the input semantic representation. For example, (FILL (ACQUIRE instrument)) would actually look like (FILL (ACQUIRE-21 instrument-23)). This prevents confusion when more than one of the same concepts or relations is present.
Effects and preconditions can also be added to prevent redundant planning. For instance, if there was a CORPORATION lexicon entry that had a ``built in'' instrument link, combining this with ACQUIRE-2 would over-generate the instrument meaning. Constraints can be added to ensure no input relation or concept is used twice.
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.
Generation in the Mikrokosmos project is a relatively new development. Currently we are developing methods to reverse multilingual analysis lexicons (Viegas & Beale, submitted). PICARD has been used to back-translate the semantic analyses of the Mikrokosmos analyzer using these reversed lexicons. Efficiency results similar to those reported for HUNTER-GATHERER 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.
