The Mikrokosmos project utilizes an efficient, constraint-directed control architecture called Hunter-Gatherer (HG). [Beale et al. 1996] overviews how it enables semantic analysis to be performed in near linear-time. Its use in generation is quite similar. [Beale1997] describes HG in detail.
Figure 8: Problem Decomposition
Consider Figure 8, a representation of the constraint interactions present in a section of Figure 1. Each label, such as DIVIDE, is realizable by the set of choices specified in the lexicon. Each solid line represents an instance of one of the above constraint types. For example, DIVIDE and ORG-INVOLVED-IN are connected because of the structural constraint described above (they both cannot set up a structure which nests the realization of CONGLOMERATE-32 into different subject positions).
The key to the efficient constraint-based planner Hunter-Gatherer is its
ability to identify constraints and partition the overall problem into
relatively independent subproblems. These subproblems are tackled
independently and the results are combined using solution synthesis
techniques. This ``divide-and-conquer'' methodology substantially reduces the
number of combinations that have to be tested, while guaranteeing an
optimal answer. For example, in Figure 8, if we assume that each
node had 5 possible choices (a conservative assumption), there would be
, or almost 10 million combinations of choices to examine. Using the
partitions shown in dotted lines, however, HG only examines
1200 combinations. In general, HG is able to process semantic
analysis and generation problems for natural language in near linear-time
[Beale et al. 1996] (pp. 1060-61).
While a detailed explanation of Hunter-Gatherer is beyond the scope of this paper, it is fairly easy to explain the source of its power. Consider Figure 9, a single subproblem from Figure 8. The key thing to note is that, of the three nodes, BUY, LOCATION and STOCK-MARKET, only BUY is connected by constraints to entities outside the subproblem. This tells us that by looking only at this subproblem we will not be able to determine the optimal global choice for BUY, since there are constraints we cannot take into account. What we can do, however, is, for each possible choice for BUY, pick the choices for LOCATION and STOCK-MARKET that optimize it. Later, when we combine the results of this subproblem with other subproblems and thus determine which choice for BUY is optimal, we will already have determined the choices for LOCATION and STOCK-MARKET that go best with it.
There are two distinct types of constraints that HG deals with. The first are hard binary constraints. If such a constraint is not met while considering a candidate combination of realizations, that combination is simply eliminated. Most of the constraints discussed above are hard constraints. HG utilizes constraint satisfaction techniques to keep track of hard constraints. On the other hand, soft constraints set up preferences that can be overridden. These ``fuzzy'' constraints cannot be handled by straightforward constraint satisfaction techniques; however, the partitioning methodology described above combined with simple branch-and-bound methods allows HG to determine optimal local combinations.
The following sums up the advantages Hunter-Gatherer has for text generation:
