Planning by rewriting

Domain-independent planning is a hard combinatorial problem. Taking into account plan quality makes the task even more difficult. This thesis 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, with special emphasis on query planning in distributed and heterogeneous environments. Our PbR-based query planner is flexible, scalable, and yields a novel combination of traditional cost-based query optimization and source selection. The experimental results show that the PbR approach provides significant savings in planning effort while generating high-quality plans.