We utilize an efficient, constraint-directed control architecture called Hunter-Gatherer (HG). (local-ref) overviews how it enables semantic analysis to be performed in near linear-time. Its use in generation is quite similar. (local-ref) describes the architecture in detail.
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 always guaranteeing an optimal answer.
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. HG utilizes traditional 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 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:
a) Its knowledge is fully declarative. This is also allowed by unification processors such as that used in [Elhadad et al. 1997], but HG gives the added benefits of speed and capability of ``fuzzy'' constraint processing; b) It allows ``exhaustive'' enumeration of local combinations; c) It eliminates the need to make early decisions; d) It facilitates interacting constraints, and accepts constraints from any source, while still utilizing modular, declarative knowledge; e) It guarantees optimal answers (as measured by preferences); f) It is very fast (near linear-time).