PbR gives the user total flexibility in defining rewriting rules. In this section we describe two approaches to guaranteeing that a rewriting rule specification preserves plan correctness, that is, produces a valid rewritten plan when applied to a valid plan.
In the full-specification approach the rule specifies all steps and links involved in a rewriting. The rule antecedent identifies all the anchoring points for the operators in the consequent, so that the embedding of the replacement subplan is unambiguous and results in a valid plan. The burden of proving the rule correct lies upon the user or an automated rule defining procedure (cf. Section 6). These kind of rules are the ones typically used in graph rewriting systems [73].
In the partial-specification approach the rule defines the operators and links that constitute the gist of the plan transformation, but the rule does not prescribe the precise embedding of the replacement subplan. The burden of producing a valid plan lies upon the system. PbR takes advantage of the semantics of domain-independent planning to accept such a relaxed rule specification, fill in the details, and produce a valid rewritten plan. Moreover, the user is free to specify rules that may not necessarily be able to compute a rewriting for a plan that matches the antecedent because some necessary condition was not checked in the antecedent. That is, a partially-specified rule may be overgeneral. This may seem undesirable, but often a rule may cover more useful cases and be more naturally specified in this form. The rule may only fail for rarely occurring plans, so that the effort in defining and matching the complete specification may not be worthwhile. In any case, the plan-rewriting algorithm ensures that the application of a rewriting rule either generates a valid plan or fails to produce a plan (Theorem 1, Section 3.1.3).
As an example of these two approaches to rule specification, consider Figure 12 that shows the avoid-move-twice-full rule, a fully-specified version of the avoid-move-twice rule (of Figure 6, reprinted here for convenience). The avoid-move-twice-full rule is more complex and less natural to specify than avoid-move-twice. But, more importantly, avoid-move-twice-full is making more commitments than avoid-move-twice. In particular, avoid-move-twice-full fixes the producer of (clear ?b1) for ?n3 to be ?n4 when ?n7 is also known to be a valid candidate. In general, there are several alternative producers for a precondition of the replacement subplan, and consequently many possible embeddings. A different fully-specified rule is needed to capture each embedding. The number of rules grows exponentially as all permutations of the embeddings are enumerated. However, by using the partial-specification approach we can express a general plan transformation by a single natural rule.
|
In summary, the main advantage of the full-specification rules is that the rewriting can be performed more efficiently because the embedding of the consequent is already specified. The disadvantages are that the number of rules to represent a generic plan transformation may be very large and the resulting rules quite lengthy; both of these problems may decrease the performance of the match algorithm. Also, the rule specification is error prone if written by the user. Conversely, the main advantage of the partial-specification rules is that a single rule can represent a complex plan transformation naturally and concisely. The rule can cover a large number of plan structures even if it may occasionally fail. Also, the partial specification rules are much easier to specify and understand by the users of the system. As we have seen, PbR provides a high degree of flexibility for defining plan-rewriting rules.