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 job-shop 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 sophisticated manufacturing domain may include a variety of concerns such as the cost, 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 search 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 [28,19,66]. 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 non-additive cost function appears in the UNIX planning domain [30] 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 search would not naturally lead to it. By using complete plans, PbR can accurately assess arbitrary measures of quality.