This paper has presented Planning by Rewriting, a new paradigm for efficient high-quality domain-independent planning. PbR adapts graph rewriting and local search techniques to the semantics of domain-independent partial-order planning. The basic idea of PbR consists in transforming an easy-to-generate, but possibly suboptimal, initial plan into a high-quality plan by applying declarative plan-rewriting rules in an iterative repair style.
There are several important advantages to the PbR planning approach. First, PbR is a declarative domain-independent framework, which brings the benefits of reusability and extensibility. Second, it addresses sophisticated plan quality measures, while most work in domain-independent planning has not addressed quality or does it in very simple ways. Third, PbR is scalable because it uses efficient local search methods. Finally, PbR is an anytime planning algorithm that allows balancing planning effort and plan quality in order to maximize the utility of the planning process.
Planning by Rewriting provides a domain-independent framework for local search. PbR accepts declarative domain specifications in an expressive operator language, declarative plan-rewriting rules to generate the neighborhood of a plan, complex quality metrics, interchangeable initial plan generators, and arbitrary (local) search methods.
Planning by Rewriting is well suited to mixed-initiative planning. In mixed-initiative planning, the user and the planner interact in defining the plan. For example, the user can specify which are the available or preferred actions at the moment, change the quality criteria of interest, etc. In fact, some domains can only be approached through mixed-initiative planning. For example, when the quality metric is very expensive to evaluate, such as in geometric analysis in manufacturing, the user must guide the planner towards good quality plans in a way that a small number of plans are generated and evaluated. Another example is when the plan quality metric is multi-objective or changes over time. Several characteristics of PbR support mixed-initiative planning. First, because PbR offers complete plans, the user can easily understand the plan and perform complex quality assessment. Second, the rewriting rule language is a convenient mechanism by which the user can propose modifications to the plans. Third, by selecting which rules to apply or their order of application the user can guide the planner.
Our framework achieves a balance between domain knowledge, expressed as plan-rewriting rules, and general local-search techniques that have proved useful in many hard combinatorial problems. We expect that these ideas will push the frontier of solvable problems for many practical domains in which high quality plans and anytime behavior are needed.
The planning style introduced by PbR opens several areas for future research. There is great potential for applying machine learning techniques to PbR. An important issue is the generation of the plan-rewriting rules. Conceptually, plan-rewriting rules arise from the chosen plan equivalence relation. All valid plans that achieve the given goals in a finite number of steps, i.e. all solution plans, are (satisfiability) equivalent. Each rule arises from a theorem that states that two subplans are equivalent for the purposes of achieving some goals, with the addition of some conditions that indicate in which context that rule can be usefully applied. The plan-rewriting rules can be generated by automated procedures. The methods can range from static analysis of the domain operators to analysis of sample equivalent plans that achieve the same goals but at different costs. Note the similarity with methods to automatically infer search control and domain invariants [55,29,35,34,68], and also the need to deal with the utility problem. Ambite, Knoblock, & Minton [6] present some results on learning plan rewriting rules based on comparing initial and optimal plans for sample problems.
Beyond learning the rewriting rules, we intend to develop a system that can automatically learn the optimal planner configuration for a given planning domain and problem distribution in a manner analogous to Minton's Multi-TAC system [57]. Our system would perform a search in the configuration space of the PbR planner proposing candidate sets of rewriting rules and different search methods. By testing each proposed configuration against a training set of simple problems, the system would hill-climb in the configuration space in order to arrive at the most useful rewriting rules and search strategies for the given planning domain and distribution of problems.
There are many advanced techniques in the local search literature that can be adapted and extended in our framework. In particular, the idea of variable-depth rewriting leads naturally to the creation of rule programs, which specify how a set of rules are applied to a plan. We have already seen how in query planning we could find transformations that are better specified as a program of simple rewriting rules. For example, a sequence of Join-Swap transformations may put two retrieve operators on the same database together in the query tree and then Remote-Join-Eval would collapse the explicit join operator and the two retrieves into a single retrieval of a remote join. Cherniack & Zdonik [22,23] present more complex examples of this sort of programs of rewriting rules in the context of a query optimizer for object-oriented databases.
As we discussed in Sections 3.1.3 and 3.1.4 the language of the antecedent of the rewriting rules can be more expressive than conjunctive queries while still remaining computationally efficient. For example, Figure 32 shows a rule from the manufacturing domain of Section 4.1 with a relationally-complete antecedent. This rule matches a subplan that contains a spray-paint operator, but does not contain either punch or drill-press operators that create holes of diameter smaller than 1 millimeter. In such case, the rule replaces the spray-paint operator by an immersion-paint operator. This rule would be useful in a situation in which painting by immersion could clog small holes.
Another area for further research is the interplay of plan rewriting and plan execution. Sometimes the best transformations for a plan may only be known after some portion of the plan has been executed. This information obtained at run-time can guide the planner to select the appropriate rewritings. For example, in query planning the plans may contain information gathering actions [7] and depend on run-time conditions. This yields a form of dynamic query optimization. Interleaved planning and execution is also necessary in order to deal effectively with unexpected situations in the environment such as database or network failures.
An open area of research is to relax our framework to accept incomplete plans during the rewriting process. This expands the search space considerably and some of the benefits of PbR, such as its anytime property, are lost. But for some domains the shortest path of rewritings from the initial plan to the optimal may pass through incomplete or inconsistent plans. This idea could be embodied as a planning style that combines the characteristics of generative planning and Planning by Rewriting. This is reminiscent of the plan critics approach [70,79]. The resulting plan-rewriting rules can be seen as declarative specifications for plan critics. The plan refinements of both partial order planning [42] and Hierarchical Task Network Planning [26] can be easily specified as plan-rewriting rules.
Applying PbR to other domains will surely provide new challenges and the possibility of discovering and transferring general planning techniques from one domain to another. We hope that the local-search methods used by PbR will help planning techniques to scale to large practical problems and conversely that the domain-independent nature of PbR will help in the analysis and principled extension of local search techniques.
