Overview of Project

The following are the highlights of our experiment:

• GENERATION POTENTIAL: comparable to Penman and Diogenes 89, and, with extensions, to Diogenes 90. This system is designed to be a general purpose text planner along the lines of Penman and Diogenes 89. With an appropriate lexicon and rule set, it will be able to generate output that is at least as good as those systems. In addition, the opportunistic abilities of Diogenes 90 are also present here. In contrast to these planners, however, this system exhibits the characteristics listed below which enable it to perform more efficiently and, in some cases, produce higher quality output.

• ISLAND DRIVEN: takes advantage of ``islands of certainty'' in input, along with islands created as the planner further constrains problem. Takes advantage of the fact that much of language production is island-driven. By that we mean that within every utterance, whether it is large or small, there are generally ``islands'' of certainty; places where there is one and only one acceptable choice. Many such islands can be detected even BEFORE processing begins. As a result, certain rules will never be attempted. Rules that produce effects which conflict with preconditions of an island can also be eliminated. In addition to identifying islands before processing, islands that are created due to constraints imposed during processing are also detected. Again, their effects are instantiated and rules that lead to conflicts with their preconditions are eliminated.

• OPPORTUNISTIC: ``looks ahead'' for information as needed; prevents needless backtracking. To explain what we mean by ``look-ahead'', consider the types of preconditions that may be part of a rule:
  1. conditions that relate to the semantics of the immediate input
  2. conditions that relate to the semantics of the surrounding text
  3. conditions that relate to decisions made at other nodes
  4. conditions that relate to actual surface realizations

  For instance, a type 1 precondition might ask if the particular semantic structure being processed is a reason-result relation. A type 2 precondition might ask if the current structure is embedded in a reason-result relation. A type 3 precondition might ask whether the parent node is a passive or an active clause. Finally, a type 4 precondition might ask whether the containing clause is greater than 20 words long.

  In general, opportunistic planners work on type 2 and 3 preconditions. We have developed a method for identifying and determining whether such preconditions hold before processing begins. This look-ahead procedure can eliminate many possible rule applications before they are ever tried. Type 3 preconditions are systematically tracked to avoid instantiating conflicting rules or rules with impossible preconditions.

• SOUNDNESS: our system keeps track of preconditions, automatically detects when a rule's pre-conditions can no longer be satisfied, automatically detects pre-condition ``bashing''. The preconditions for each rule are determined before processing begins. In addition, each rule that could possible meet that precondition is also calculated. If, during (or before) processing, it can be determined that no more of these ``need-fillers'' are active for a particular rule's precondition, then that rule can be pruned out of the search tree, with any resulting new islands treated as described above. This feature relies on a constraint propagation algorithm developed for the system.

• OPTIMIZED: rule set dependencies are pre-analyzed to the point where all effects of instantiating a rule are known beforehand, and processing is reduced to a knowledge-free trip through a tree of 0's and 1's. The preconditions and effects of each rule that can be applied at a certain node are ``compiled'' into a very efficient format. For every possible rule application, we can tell immediately, for each node in the input semantic tree, which rules must be eliminated because their effects conflict with the present effect or conflict with the preconditions of the current effect, or because their preconditions conflict with the present effect. In practice, after optimization, we proceed through the ``recursive'' part of the planner without regard to the actual preconditions and effects. We simply instantiate a rule, which automatically eliminates all other conflicting rules. And keep in mind that every time a rule is eliminated, it is checked to see whether an island was created (in which case its island constraints are instantiated as described above), and whether any other rule's preconditions have become impossible to meet (in which case the rule in question is removed).

• MODIFIED RECURSIVE DESCENT ALGORITHM: takes advantage of above features to eliminate at least 80 percent of the processing in the experiment (compared to basic recursive descent algorithm).