3.2 Selection of Next Plan: Search Strategies

Although the space of rewritings can be explored systematically, the Planning by Rewriting framework is better suited to the local search techniques typical of combinatorial optimization algorithms. The characteristics of the planning domain, the initial plan generator, and the rewriting rules determine which local search method performs best. First, we discuss how the initial plan generator affects the choice of local search methods. Second, we consider the impact of the rewriting rules. Third, we discuss the role of domain knowledge in the search process. Finally, we describe how several local search methods work in PbR.

An important difference between PbR and traditional combinatorial
algorithms is the generation of feasible solutions.
Usually, in combinatorial optimization problems there exists an
effective procedure to generate *all* feasible solutions (e.g.,
the permutations of a schedule). Thus, even if the local search graph
is disconnected, by choosing an appropriate initial solution generator
(e.g., random) we could fall in a component of the graph that contains
the global optimum.
In PbR we cannot assume such powerful initial plan generators.
Even in optimization domains, which have efficient initial plan
generators, we may not have guarantees on the coverage of the solution
space they provide.
Therefore, the optimal plan may not be reachable by applying the
rewriting rules when starting from the initial plans available from
the generator.
Nevertheless, for many domains an initial plan generator that provides
a good sample of the solution space is sufficient for multiple-restart
search methods to escape from low-quality local minima and provide
high-quality solutions.

The plan-rewriting rules define the neighborhood function, which may
be *exact* (cf. Section 2.3) or not. For example,
in the query planning domain we can define a set of rules that
completely generate the space of solution plans (because of the
properties of the relational algebra). In other domains it may be hard
to prove that we have an exact set of rules.
Both the limitations on initial plan generation and the plan-rewriting
rules affect the possibility of theoretically reaching the global
optimum. This is not surprising since many problems, regardless of
whether they are cast as planning or in other formalisms, do not have
converging local search algorithms (e.g., [63]).
Nevertheless, in practice, good local optima can still be obtained for
many domains.

Many local search methods, such as first and best improvement, simulated annealing, tabu search, or variable-depth search, can be applied straightforwardly to PbR. In our experiments in Section 4 we have used first and best improvement, which have performed well. Next, we describe some details of the application of these two methods in PbR. In Section 6, we discuss our ideas for using variable-depth plan rewriting.

*First improvement* generates the rewritings incrementally and
selects the first plan of better cost than the current one. In order
to implement this method efficiently we can use a tuple-at-a-time
evaluation of the rule antecedent, similarly to the behavior of
Prolog. Then, for that rule instantiation, generate one embedding,
test the cost of the resulting plan, and if it is not better that the
current plan, repeat. We have the choice of generating another
embedding of the same rule instantiation, generate another
instantiation of the same rule, or generate a match for a different
rule.

*Best improvement* generates the complete set of rewritten plans
and selects the best. This method requires computing all matches and
all embeddings for each match. All the matches can be obtained by
evaluating the rule antecedent as a set-at-a-time database query. As
we discussed in Section 3.1.4 such query evaluation can be
quite efficient. In our experience, computing the plan embeddings was
usually more expensive than computing the rule matches.

In Planning by Rewriting the choice of the initial plan generator, the rewriting rules, and the search methods is intertwined. Once the initial plan generator is fixed, it determines the shape of the plans that would have to be modified by the rewriting rules, then according to this neighborhood, the most appropriate search mechanism can be chosen. PbR has a modular design to facilitate experimentation with different initial plan generators, sets of rewriting rules, and search strategies.