although they may differ on their cost or operators (that is, they are "equivalent" with respect to "satisfiability" as introduced above). However, we are not interested in using the rewriting rules to prove such "equivalence". Instead, our framework uses the rewriting rules to explore the space of solution plans.

Graph rewriting, akin to term rewriting, refers to the process of replacing a subgraph of a given graph, when some conditions are satisfied, by another subgraph. Graph rewriting has found broad applications, su as very high-level programming languages, database data description and query languages, etc.  Schiirr (1997) presents a good survey.  The main drawback of general graph rewriting is its complexity. Because graph matching can be reduced to (sub)graph isomorphism the problem is NP-complete. Nevertheless, under some restrictions graph rewriting can be performed efficiently (Dorr, 1995).

Planning by Rewriting adapts general graph rewriting to the semantics of partial-order planning with a STRIPS-like operator representation.  A plan-rewriting rule in PbR specifies the replacement, under certain conditions, of a subplan by another subplan. However, in our formalism the rule does not need to specify the completely detailed embedding of the consequent as in graph rewriting systems.  The consistent embeddings of the rule consequent, with the generation of edges if necessary, are automatically computed according to the semantics of partial-order planning. Our algorithm ensures that the rewritten plans always remain valid (Section 3.1.3). The plan-rewriting rules are intended to explore the space of solution plans to reach high-quality plans.

## 2.3  Local Search In Combinatorial Optimization

PbR is inspired by the local search techniques used in combinatorial optimization.  An instance of a combinatorial optimization problem consists of a set of feasible solutions and a cost function over the solutions. The problem consists in finding a solution with the optimal cost among all feasible solutions.  Generally the problems addressed are computationally intractable, thus approximation algorithms have to be used. One class of approximation algorithms that have been surprisingly successful in spite of their simplicity are local search methods (Aarts & Lenstra, 1997; Papadimitriou & Steiglitz, 1982).

Local search is based on the concept of a neighborhood. A neighborhood of a solution p is a set of solutions that are in some sense close to p, for example because they can be easily computed from p or because they share a significant amount of structure with p.

The neighborhood generating function may, or may not, be able to generate the optimal solution.  When the neighborhood function can generate the global optima, starting from any initial feasible point, it is called exact (Papadimitriou & Steiglitz, 1982, page 10).

Local search can be seen as a walk on a directed graph whose vertices are solutions points and whose arcs connect neighboring points. The neighborhood generating function determines the properties of this graph. In particular, if the graph is disconnected, then the nneeeiiiibbborhood is not exact since there exist feasible points that would lead to local optima but not the global optima. In PbR the points are solution plans and the neighbors of a plan are the plans generated by the application of a set of declarative plan rewriting rules.

The basic version of local search is iterative improvement. Iterative improvement starts with an initial solution and searches a neighborhood of the solution for a lower cost solution. If such a solution is found, it replaces the current solution and the search continues.