(define-rule :name SP-by-IP-no-small-holes
:if (:and (:operator ?n1 (spray-paint ?x ?c ?s))
(: not (: and (: or (: operator ?n2 (punch ?x ?w ?o))
(:operator ?n3 (drill-press ?x ?w ?o)))
(:less ?w 1mm))))
:replace (:operators (?n1))
:with (:operator ?n4 (immersion-paint ?x ?c)))
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 (Ashish, Knoblock, & Levy, 1997) 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 (Sacerdoti, 1975; Sussman, 1975). The resulting plan-rewriting rules can be seen as declarative specifications for plan critics. The plan refinements of both partial order planning (Kambhampati et al., 1995) and Hierarchical Task Network Planning (Erol, Nau,
& Hendler, 1994) 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-sear 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.

## Acknowledgments

This paper is an extended version of (Ambite & Knoblock, 1997).

The research reported here was supported in part by a Fulbright/Ministerio of Educación y Ciencia of Spain scholarship, in part by the Defense Advanced Research Projects Agency
(DARPA) and Air Force Research Laboratory, Air Force Materiel Command, USAF, under agreement number F30602-00-1-0504, in part by the National Science Foundation under grant number IRI-9313993, in part by the Rome Laboratory of the Air Force Systems Command and the Defense Advanced Research Projects Agency (DARPA) under contract numbers F30602-94-C-0210, F30602-97-2-0352, F30602-97-2-0238, F30602-98-2-0109, in part by the United States Air Force under contract number F49620-98-1-0046, and in part by the Integrated Media Systems Center, a National Science Foundation Engineering Research