
## 1.1 Solution Approach

Two observations guided the present work. The first one is that there are two sources of complexity in planning:
- Satisfiability: the difficulty of finding any solution to the planning problem (regardless

of the quality of the solution).

- Optimization: the difficulty of finding the optimal solution under a given cost metric.
For a given domain, each of these facets may contribute differently to the complexity of planning. In particular, there are many domains in which the satisfiability problem is relatively easy and their complexity is dominated by the optimization problem. For example, there may be many plans that would solve the problem, so that finding one is efficient in practice, but the cost of each solution varies greatly, thus finding the optimal one is computationally hard. We will refer to these domains as optimization domains. Some optimization domains of great practical interest are query optimization and manufacturing process planning. 1 The second observation is that planning problems have a great deal of structure. Plans are a type of graph with strong semantics, determined by both the general properties of planning and each particular domain specification. This structure should and can be exploited to improve the efficiency of the planning process.

Prompted by the previous observations, we developed a novel approach for efficient planning in optimization domains: Planning by Rewriting (PbR). The framework works in two phases:

1. Generate an initial solution plan. Recall that in optimization domains this is efficient.

However, the quality of this initial plan may be far from optimal.

2. Iteratively rewrite the current solution plan improving its quality using a set of declarative plan-rewriting rules, until either an acceptable solution is found or a resource limit is reached.
As motivation, consider the optimization domains of distributed query processing and manufacturing process planning. 2 Distributed query processing (Yu & Chang, 1984) involves generating a plan that efficiently computes a user query from data that resides at different nodes in a network.  This query plan is composed of data retrieval actions at diverse information sources and operations on this data (such as those of the relational algebra: join, selection, etc).  Some systems use a general-purpose planner to solve this problem (Knoblock, 1996). In this domain it is easy to construct an initial plan (any parse of the query suffices) and then transform it using a gradient-descent search to reduce its cost.

The plan transformations exploit the commutative and associative properties of the (relational algebra) operators, and facts such as that when a group of operators can be executed together at a remote information source it is generally more efficient to do so.  Figure 1