Planning by Rewriting: Efficiently Generating High-Quality Plans

Abstract

Domain-independent planning is a hard combinatorial problem. Taking into account plan quality makes the task even more difficult. We introduce a new paradigm for efficient high-quality planning that exploits plan rewriting rules and efficient local search techniques to transform an easy-to-generate, but possibly suboptimal, initial plan into a low-cost plan. In addition to addressing the issues of efficiency and quality, this framework yields a new anytime planning algorithm. We have implemented this planner and applied it to several existing domains. The results show that this approach provides significant savings in planning effort while generating high-quality plans. Introduction Planning is the process of generating a network of actions that achieves a desired goal from an initial state of the world. Domain independent planning accepts as input, not only the initial state and the goal, but also the domain specification (i.e., the operators). This is a problem of considerable prac...