3 Planning by Rewriting as Local Search

Planning by Rewriting can be viewed as a domain-independent framework for local search. PbR accepts arbitrary domain specifications, declarative plan-rewriting rules that generate the neighborhood of a plan, and arbitrary (local) search methods. Therefore, assuming that a given combinatorial problem can be encoded as a planning problem, PbR can take it as input and experiment with different neighborhoods and search methods.

We will describe the main issues in Planning by Rewriting as an instantiation of the local search idea typical of combinatorial optimization algorithms:

• Selection of an initial feasible point: In PbR this phase consists of efficiently generating an initial solution plan.

• Generation of a local neighborhood: In PbR the neighborhood of a plan is the set of plans obtained from the application of a set of declarative plan-rewriting rules.

• Cost function to minimize: This is the measure of plan quality that the planner is optimizing. The plan quality function can range from a simple domain-independent cost metric, such as the number of steps, to more complex domain-specific ones, such as the query evaluation cost or the total manufacturing time for a set of parts.

• Selection of the next point: In PbR, this consists of deciding which solution plan to consider next. This choice determines how the global space will be explored and has a significant impact on the efficiency of planning. A variety of local search strategies can be used in PbR, such as steepest descent, simulated annealing, etc. Which search method yields the best results may be domain or problem specific.

In the following subsections we expand on these issues. First, we discuss the use of declarative rewriting rules to generate a local neighborhood of a plan, which constitutes the main contribution of this paper. We present the syntax and semantics of the rules, the plan-rewriting algorithm, the formal properties and a complexity analysis of plan rewriting, and a rule taxonomy. Second, we address the selection of the next plan and the associated search techniques for plan optimization. Third, we discuss the measures of plan quality. Finally, we describe some approaches for initial plan generation.