José Luis Ambite and Craig A. Knoblock
We present the application of the Planning by Rewriting (PbR) framework to query planning in distributed and heterogeneous environments. PbR is 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 high-quality plan. The resulting planner is scalable, flexible, has anytime behavior, and, applied to query planning, yields a novel combination of traditional query optimization with heterogeneous information source selection. Query planners are the core component of mediator systems, which are becoming increasingly important in a world of interconnected information, and constitute excellent testbeds for planning technology.