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-fullfixes 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.

(define-rule :name avoid-move-twice-full
:if (:operators ((?n1 (unstack ?b1 ?b2))
(?n2 (stack ?b1 ?b3 Table)))
:links ((?n4 (clear ?b1) ?n1)
(?n5 (on ?b1 ?b2) ?n1)
(?n1 (clear ?b2) ?n6) (?n1 (on ?b1 Table) ?n2) (?n7 (clear ?b1) ?n2)
(?n8 (clear ?b3) ?n2)
(?n2 (on ?b1 ?b3) ?n9))
:constraints ((possibly-adjacent ?n1 ?n2)
(:neq ?b2 ?b3)))
:replace (:operators (?n1 ?n2))
:with (:operators ((?n3 (stack ?b1 ?b3 ?b2)))
:links ((?n4 (clear ?b1) ?n3)
(?n8 (clear ?b3) ?n3)
(?n5 (on ?b1 ?b2) ?n3) (?n3 (on ?b1 ?b3) ?n9))))
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
(define-rule :name avoid-move-twice iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiittttt    iiiinnnntttt    iiinnntttt     iiinnntttt      iiinnntttt       
(?n1 (unstack ?b1 ?b2))
(?n2 (stack ?b1 ?b3 Table)))
:links (?n1 (on ?b1 Table) ?n2) : c o n s t r a i n t s
(possibly-adjacent ?n2)
(:neq ?b2 ?b3)))
:replace (:operators (?n1 ?n2))
: w i t h  ( : oper at or s

$$\Pi\,{\mathcal{L}}$$

(?n3 (stack ?b1 ?b3 ?b2)))