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.