[Chapman 87] discusses precondition ``clobbering'', the state where a rule that had been instantiated previously on the basis of some precondition, later had that precondition removed, invalidating the rule. Previous text planners were not ``sound'', in that they did not detect this kind of situation. To prove more formally that this system is sound, let me state the soundness criterion which it claims to adhere to:
, have at
least one rule active that has a CONstraint
equal to the precondition if it is a ``check-con'', or have no rules active that have
a CONstraint equal to the precondition if it is a ``check-not-con''.
Thus, if rule 1 has a precondition that states that constraint A must be true, then whenever Rule 1 is not marked failed, there must be at least one other active rule that has a CONstraint that sets constraint A. On the other hand, if rule 1 has a precondition that states that precondition B must not be true, then there can be no rules active that set constraint B while rule 1 is not failed.
Note that this is slightly stronger than a general soundness condition, which might allow a planner to go through unsound states as long as the final result is sound. In practice, though, a planner that is guaranteed to be sound at the end most likely will be sound throughout.
This system meets the soundness criterion given above. After the DET precondition application, which removes any rules that do not meet DET preconditions, the dependencies between all the remaining rules are analyzed. The following information is recorded:
Before the recursive descent is initiated, every rule that has a precondition for which there were no rules found in number 3 above is failed. Every time a rule is failed, both during this initial process and during the subsequent recursive descent, all of the preconditions it can satisfy (from number 4 above) are retrieved. For each of these preconditions, all of the rules that could satisfy the precondition (from number 3 above) are retrieved, and it is checked that at least one of these rules is still active. If none are, then the rule corresponding to the precondition is failed. This process ensures that no rules are ever deleted that are the sole suppliers of preconditions of other active rules (or more accurately, that any such active rules are failed if their sole supplier is failed).
This does not yet fail preconditions that conflict with constraints. Whenever a node has
only one valid rule left, all of the preconditions that conflict
with the rule (from number 2 above) are retrieved and the corresponding rule(s) are failed.
The rules affected by these failures are then checked as described above.
During the recursive descent, at each node, one rule is chosen and the others are failed. The effects of failing the other nodes are checked, and the effects of instantiating the rule that is used are checked. In general, whenever a rule is failed, the rules for which it supplied preconditions are checked. Whenever an island is created, the rules that conflict with the island's rule are failed.
Backtracking is really irrelevant as far as this soundness issue is concerned. At every point in the recursive descent, the current active rule set is sound. If backtracking occurs, we simply return to a previous set of active rules that were earlier determined to be sound.
The fact that the system is sound is good in itself. But this is not where the benefits end. The whole process of ensuring soundness as described above, combined with island processing, creates a very efficient text planner. All conflicting rules and impossible rules are eliminated at the earliest point possible. A rule is not ever deleted, and then, after further processing, a different rule found to be invalid. As soon as a rule is failed or an island rule created, all the other rules that can no longer be valid are removed immediately. Removing these rules then may lead to further removals by the same process. This process feeds on itself to remove as many of the possible rules as possible.