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.

## 3.3  Plan Quality

In most practical planning domains the quality of the plans is crucial. This is one of the motivations for the Planning by Rewriting approach. In PbR the user defines the measure of plan quality most appropriate for the application domain. This quality metric could range from a simple domain-independent cost metric, such as the number of steps, to more complex domain-specific ones. For example, in the query planning domain the measure of plan quality usually is an estimation of the query execution cost based on the size of the database relations, the data manipulation operations involved in answering a query, and the cost of network transfer. In a decentralized environment, the cost metric may involve actual monetary costs if some of the information sources require payments. In the jobshop scheduling domain some simple cost functions are the schedule length (that is, the parallel time to finish all pieces), or the sum of the times to finish each piece.  A more ssssse reliability, and precision of each operator/process, the costs of resources and materials used by the operators, the utilization of the machines, etc. The reader will find more detailed examples of quality metrics in these domains in Sections 4.1 and 4.4.

A significant advantage of PbR is that the complete plan is available to assess its quality.

In generative planners the complete plan is not available until the sear for a solution is completed, so usually only very simple plan quality metrics, such as the number of steps, can be used. Some work does incorporate quality concerns into generative planners (Estlin & Mooney, 1997; Borrajo & Veloso, 1997; Pérez, 1996).  These systems automatically learn search control rules to improve both the efficiency of planning and the quality of the resulting plans. In PbR the rewriting rules can be seen as "post facto" optimization search control. As opposed to guiding the search of a generative planner towards high-quality solutions based only on the information available in partial plans, PbR improves the quality of complete solution plans without any restriction on the types of quality metrics.  Moreover, if the plan cost is not additive, a plan refinement strategy is impractical since it may need to exhaustively explore the search space to find the optimal plan. An example of nonadditive cost function appears in the UNIX planning domain (Etzioni & Weld, 1994) where a plan to transfer files between two machines may be cheaper if the files are compressed initially (and uncompressed after arrival). That is, the plan that includes the compression (and the necessary uncompression) operations is more cost effective, but a plan refinement sseerch would not naturally lead to it. By using complete plans, PbR can accurately assess arbitrary measures of quality.