Journal of Artificial Intelligence Research 15 (2001), pp. 207-261. Submitted 5/00; published 9/01.
© 2001 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.
Postscript and PDF versions of this document are available from here.

Planning by Rewriting

José Luis Ambite (ambite@isi.edu)
Craig A. Knoblock (knoblock@isi.edu)
Information Sciences Institute and Department of Computer Science,
University of Southern California,
4676 Admiralty Way, Marina del Rey, CA 90292, USA

Abstract:

Domain-independent planning is a hard combinatorial problem. Taking into account plan quality makes the task even more difficult. This article introduces Planning by Rewriting (PbR), a new paradigm for efficient high-quality domain-independent planning. PbR exploits declarative plan-rewriting rules and efficient local search techniques to transform an easy-to-generate, but possibly suboptimal, initial plan into a high-quality plan. In addition to addressing the issues of planning efficiency and plan quality, this framework offers a new anytime planning algorithm. We have implemented this planner and applied it to several existing domains. The experimental results show that the PbR approach provides significant savings in planning effort while generating high-quality plans.