The work most closely related to our plan-rewriting algorithm is plan merging [33]. Foulser et al. provide a formal analysis and algorithms for exploiting positive interactions within a plan or across a set of plans. However, their work only considers the case in which a set of operators can be replaced by one operator that provides the same effects to the rest of the plan and consumes the same or fewer preconditions. Their focus is on optimal and approximate algorithms for this type of operator merging. Plan rewriting in PbR can be seen as a generalization of operator merging where a subplan can replace another subplan. A difference is that PbR is not concerned with finding the optimal merge (rewritten plan) in a single pass of an optimization algorithm as their approach does. In PbR we are interested in generating possible plan rewritings during each rewriting phase, not the optimal one. The optimization occurs as the (local) search progresses.
Case-based planning (e.g., [41,80,61,39,59]) solves a problem by modifying a previous solution. There are two phases in case-based planning. The first one identifies a plan from the library that is most similar to the current problem. In the second phase this previous plan is adapted to solve the new problem. PbR modifies a solution to the current problem, so there is no need for a retrieval phase nor the associated similarity metrics. Plan rewriting in PbR can be seen as a type of adaptation from a solution to a problem to an alternate solution for the same problem. That is, a plan rewriting rule in PbR identifies a pair of subplans (the replaced and replacement subplans) that may be interchangeable.
Veloso [80] describes a general approach to case-based planning based on derivational analogy. Her approach works in three steps. First, the retrieval phase selects a similar plan from the library. Second, the parts of this plan irrelevant to the current problem are removed. Finally, her system searches for a completion of this plan selecting as much as possible the same decisions as the old plan did. In this sense the planning knowledge encoded in the previous solution is transferred to the generation of the new solution plan. The plan-rewriting algorithm for partially-specified rules of PbR can be seen as a strongly constrained version of this approach. In PbR the subplan in the rule consequent fixes the steps that can be added to repair the plan. We could use her technique of respecting previous choice points when completing the plan as a way of ensuring that most of the structure of the plan before and after the repair is maintained. This could be useful to constrain the number of rewritten plans for large rewriting rules.
Nebel and Koehler [61] present a computational analysis of case-based planning. In this context they show that the worst-case complexity of plan modification is no better than plan generation and point to the limitations of reuse methods. The related problem in the PbR framework is the embedding of the replacement subplan for partially specified rules. As we explained in Section 3.1.4 there may be pathological cases in which the number of embeddings is exponential in the size of the plan or deciding if the embedding exists is NP-hard. However, often we are not interested in finding all rewritings, for example when following a first improvement search strategy. In our experience the average case behavior seems to be much better as was presented in Section 4.
Systematic algorithms for case-based planning (such as [39]) invert the decisions done in refinement planning to find a path between the solution to a similar old problem and the new problem. The rewriting rules in PbR indicate how to transform a solution into another solution plan based on domain knowledge, as opposed to the generic inversion of the refinement operations. Plan rewriting in PbR is done in a very constrained way instead of an open search up and down the space of partial plans. However, the rules in PBR may search the space of rewritings non systematically. Such an effect is ameliorated by using local search.