3.1.3 Plan-Rewriting Algorithm

In this section, first we describe the basic plan-rewriting algorithm in PbR. Second, we prove this algorithm sound and discuss some formal properties of rewriting. Finally, we discuss a family of algorithms for plan rewriting depending on parameters such as the language for defining plan operators, the specification language for the rewriting rules, and the requirements of the search method.

The plan-rewriting algorithm is shown in Figure 13. The algorithm takes two inputs: a valid plan $P$, and a rewriting rule $R~=~(q_{m},~p_{r},~p_{c}$) ($q_{m}$ is the antecedent query, $p_{r}$ is the replaced subplan, and $p_{c}$ is the replacement subplan). The output is a valid rewritten plan $P'$. The matching of the antecedent of the rewriting rule ($q_{m}$) determines if the rule is applicable and identifies the steps and links of interest (line 1). This matching can be seen as subgraph isomorphism between the antecedent subplan and the current plan (with the results then filtered by applying the :constraints). However, we take a different approach. PbR implements rule matching as conjunctive query evaluation. Our implementation keeps a relational representation of the steps and links in the current plan similar to the node and link specifications of the rewriting rules. For example, the database for the plan in Figure 4 contains one table for the unstack steps with schema (?n1 ?b1 ?b2) and tuples (4 C A) and (5 B D), another table for the causal links involving the clear condition with schema (?n1 ?n2 ?b) and tuples (0 1 C), (0 2 B), (0 2 C), (0 3 B), (0 4 C), (0 5 B), (4 3 A) and (5 1 D), and similar tables for the other operator and link types. The match process consists of interpreting the rule antecedent as a conjunctive query with interpreted predicates, and executing this query against the relational view of the plan structures. As a running example, we will analyze the application of the avoid-move-twice rule of Figure 6 to the plan in Figure 4. Matching the rule antecedent identifies steps 1 and 4. More precisely, considering the antecedent as a query, the result is the single tuple (4 C A 1 D) for the variables (?n1 ?b1 ?b2 ?n2 ?b3).

Figure 13: Plan-Rewriting Algorithm

After choosing a match $\sigma_{i}$ to work on (line 3), the algorithm instantiates the subplan specified by the :replace field ($p_{r}$) according to such match (line 4) and removes the instantiated subplan $p_{r}^{i}$ from the original plan $P$ (line 5). All the edges incoming and emanating from nodes of the replaced subplan are also removed. The effects that the replaced plan $p_{r}^{i}$ was achieving for the remainder of the plan ($P - p_{r}^{i}$), the UsefulEffects of $p_{r}^{i}$, will now have to be achieved by the replacement subplan (or other steps of $P - p_{r}^{i}$). In order to facilitate this process, the AddFlaws procedure records these effects as open conditions.¹⁰ The result is the partial plan $P_{r}^{i}$ (line 5). Continuing with our example, Figure 14(a) shows the plan resulting from removing steps 1 and 4 from the plan in Figure 4.

Finally, the algorithm embeds the instantiated replacement subplan $p_{c}^{i}$ into the remainder of the original plan (lines 6-9). If the rule is completely specified, the algorithm simply adds the (already instantiated) replacement subplan to the plan, and no further work is necessary. If the rule is partially specified, the algorithm computes the embeddings of the replacement subplan into the remainder of the original plan in three stages. First, the algorithm adds the instantiated steps and links of the replacement plan $p_{c}^{i}$ (line 6) into the current partial plan $P_{r}^{i}$ (line 7). Figure 14(b) shows the state of our example after $p_{c}^{i}$, the new stack step (6), has been incorporated into the plan. Note the open conditions (clear A) and on(C D). Second, the FindThreats procedure computes the possible threats, both operator threats and resource conflicts, occurring in the $P_{r}^{i} \cup p_{c}^{i}$ partial plan (line 7); for example, the threat situation on the clear(C) proposition between step 6 and 2 in Figure 14(b). These threats and the preconditions of the replacement plan $p_{c}^{i}$ are recorded by AddFlaws resulting in the partial plan $P_{c}^{i}$. Finally, the algorithm completes the plan using rPOP, a partial-order causal-link planning procedure restricted to only reuse steps (i.e., no step addition) (line 8). rPOP allows us to support our expressive operator language and to have the flexibility for computing one or all embeddings. If only one rewriting is needed, rPOP stops at the first valid plan. Otherwise, it continues until exhausting all alternative ways of satisfying open preconditions and resolving conflicts, which produces all valid rewritings. In our running example, only one embedding is possible and the resulting plan is that of Figure 14(c), where the new stack step (6) produces (clear A) and on(C D), its preconditions are satisfied, and the ordering (6 2) ensures that the plan is valid.

Figure 14: Plan Rewriting: Applying rule avoid-move-twice of Figure 6 to plan of Figure 4

The rewriting algorithm in Figure 13 is sound in the sense that it produces a valid plan if the input is a valid plan, or it outputs failure if the input plan cannot be rewritten using the given rule. Since this elementary plan-rewriting step is sound, the sequence of rewritings performed during PbR's optimization search is also sound.

Lemma 1 (Soundness of rPOP) Partial-order causal-link (POCL) planning without step addition ($rPOP$) is sound.

Proof: In POCL planning, a precondition of a step of a plan is achieved either by inserting a new step $s_{new}$ or reusing a step $s_{reuse}$ already present in the current plan (the steps having an effect that unifies with the precondition). Forbidding step addition decreases the set of available steps that can be used to satisfy a precondition, but once a step is found rPOP proceeds as general POCL. Since, the POCL completion of a partial-plan is sound [65], $rPOP$ is also sound. $\Box$

Theorem 1 (Soundness of Plan Rewriting) RewritePlan (Figure 13) produces a valid plan if the input $P$ is a valid plan, or outputs failure if the input plan cannot be rewritten using the given rewriting rule $R = (q_{m}, p_{r}, p_{c})$.

Proof: Assume plan $P$ is a solution to a planning problem with goals $G$ and initial state $I$. In POCL planning, a plan is valid iff the preconditions of all steps are supported by causal links (the goals $G$ are the preconditions of the goal step, and the initial state conditions $I$ are the effects of the initial step), and no operator threatens any causal link [53,65].

If rule $R$ does not match plan $P$, the algorithm trivially returns failure (line 2). Assuming there is a match $\sigma_{i}$, after removing from $P$ the steps and links specified in $p_{r}^{i}$ (including all links - causal and ordering - incoming and outgoing from steps of $p_{r}^{i}$), the only open conditions that exist in the resulting plan $P_{r}^{i}$ are those that $p_{r}^{i}$ was achieving (line 5). Adding the instantiated replacement subplan $p_{c}^{i}$ introduces more open conditions in the partial plan: the preconditions of the steps of $p_{c}^{i}$ (line 7). There are no other sources of open conditions in the algorithm.

Since plan $P$ is valid initially, the only (operator and/or resource) threats present in plan $P_{c}^{i}$ (line 7) are those caused by the removal of subplan $p_{r}^{i}$ (line 3) and the addition of subplan $p_{c}^{i}$ (line 7). The threats may occur between any operators and causal links of $P_{r}^{i} \cup p_{c}^{i}$ regardless whether the operator or causal link was initially in $P_{r}^{i}$ or in $p_{c}^{i}$. The threats in the combined plan $P_{r}^{i} \cup p_{c}^{i}$ can be effectively computed by finding the relative positions of its steps and comparing each causal link against the steps that may be ordered between the producer and the consumer of the condition in the causal link (FindThreats, line 7).

At this point, we have shown that we have a plan ($P_{c}^{i}$) with all the flaws (threats and open conditions) explicitly recorded (by AddFlaws in lines 5 and 7). Since $rPOP$ is sound (Lemma 1), we conclude that $rPOP$ will complete $P_{c}^{i}$ and output a valid plan $P'$, or output failure if the flaws in the plan cannot be repaired. $\Box$

Corollary 1 (Soundness of PbR Search) The optimization search of PbR is sound.

Proof: By induction. Assume an initial valid plan and a single step rewriting search. By Theorem 1, the output is either a valid rewritten plan or failure. If the output is failure, the search is trivially sound. Assume there is a valid plan $P_{n-1}$ after $n - 1$ rewriting steps. According to Theorem 1, applying a single rewriting rule to plan $P_{n-1}$ produces a valid plan $P_{n}$ or failure. Thus, an arbitrary number of rewritings produces a valid plan (or no plan), so PbR's search is sound. $\Box$

Although RewritePlan is sound, it may certainly produce plans that do not have the minimal number of steps when faced with arbitrary rules. For example, imagine that the consequent of a rewriting rule specified two identical steps s1 and s2 (both having as only effects e1 and e2) and that the only flaws in $P_{c}^{i}$ were exactly the open conditions e1 and e2. Then, a sound but non step-minimal plan would be using s1 to satisfy e1 and using s2 to satisfy e2 (although each step by itself could satisfy both open conditions). PbR does not discard this plan because we do not make any restriction on the types of acceptable cost functions. If we had a cost function that took the robustness of the plan into account, a plan with both steps may be desirable.

We cannot guarantee that PbR's optimization search is complete in the sense that the optimal plan would be found. PbR uses local search and it is well known that, in general, local search cannot be complete. Even if PbR exhaustively explores the space of plan rewritings induced by a given initial plan and a set of rewriting rules, we still cannot prove that all solution plans will be reached. This is a property of the initial plan generator, the set of rewriting rules, and the semantics of the planning domain. The rewriting rules of PbR play a similar role as traditional declarative search control where the completeness of the search may be traded for efficiency. Perhaps using techniques for inferring invariants in a planning domain [35,34,68] or proving convergence of term and graph rewriting systems [9], conditions for completeness of a plan-rewriting search in a given planning domain could be obtained.

The design of a plan-rewriting algorithm depends on several parameters: the language of the operators, the language of the rewriting rules, the choice of full-specification or partial-specification rewriting rules, and the need for all rewritings or one rewriting as required by the search method.

The language of the operators affects the way in which the initial and rewritten plans are constructed. Our framework supports the expressive operator definition language described in Section 2.1. We provide support for this language by using standard techniques for causal link establishment and threat checking like those in Sage [48] and UCPOP [65].

The language of the antecedents of the rewriting rules affects the efficiency of matching. Our system implements the conjunctive query language that was described in Section 3.1.1. However, our system could easily accommodate a more expressive query language for the rule antecedent, such as a relationally complete language (i.e., conjunction, disjunction, and safe negation) [2], or a recursive language such as datalog with stratified negation, without significantly increasing the computational complexity of the approach in an important way, as we discuss in Section 3.1.4.

The choice of fully versus partially specified rewriting rules affects the way in which the replacement plan is embedded into the current plan. If the rule is completely specified, the embedding is already specified in the rule consequent, and the replacement subplan is simply added to the current plan. If the rule is partially specified, our algorithm can compute all the valid embeddings.

The choice of one versus all rewritings affects both the antecedent matching and the embedding of rule consequent. The rule matches can be computed either all at the same time, as in bottom-up evaluation of logic databases, or one-at-a-time as in Prolog, depending on whether the search strategy requires one or all rewritings. If the rule is fully-specified only one embedding per match is possible. But, if the rule is partially-specified multiple embeddings may result from a single match. If the search strategy only requires one rewriting, it must also provide a mechanism for choosing which rule is applied, which match is computed, and which embedding is generated (rPOP can stop at the first embedding or compute all embeddings). Our implemented rewriting algorithm has a modular design to support different combinations of these choices.