# Planning By Rewriting

## José Luis Ambite

Craig A. K noblock Information Sciences Institute and Department of Computer Science, University of Southern California, 4676 Admiralty Way, Marina del Rey, CA 90292, USA
A M BIT E Q I S I . E D U
KNOBLOCK QISI. EDU

## 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.

## 1. Introduction

Planning is the process of generating a network of actions, a plan, that achieves a desired goal from an initial state of the world. Many problems of practical importance can be cast as planning problems. Instead of crafting an individual planner to solve each specific problem, a long line of research has focused on constructing domain-independent planning algorithms. Domain-independent planning accepts as input, not only descriptions of the initial state and the goal for each particular problem instance, but also a declarative domain specification, that is, the set of actions that change the properties of the state. Domainindependent planning makes the development of planning algorithms more efficient, allows for software and domain reuse, and facilitates the principled extension of the capabilities of the planner. Unfortunately, domain-independent planning (like most planning problems)
is computationally hard (Bylander, 1994; Erol, Nau, & Subrahmanian, 1995; Bäckström
& Nebel, 1995).  Given the complexity limitations, most of the previous work on domainindependent planning has focused on finding any solution plan without careful consideration of plan quality.  Usually very simple cost functions, such as the length of the plan, have been used. However, for many practical problems plan quality is crucial. In this paper we present a new planning paradigm, Planning by Rewriting (PbR), that addresses both planning efficiency and plan quality while maintaining the benefits of domain independence. The framework is fully implemented and we present empirical results in several planning domains.