PbR is designed to find a balance among the requirements of planning efficiency, high quality plans, flexibility, and extensibility. A great amount of work on AI Planning has focused on improving its average-case efficiency given that the general cases are computationally hard [27]. One possibility is to incorporate domain knowledge in the form of search control. A recent example is TLPlan [10,11], a forward-search planner that has shown a remarkable scalability using control knowledge expressed in temporal logic. Some systems automatically learn search control for a given planning domain or even specific problem instances. Minton [55] shows how to deduce search control rules for a problem solver by applying explanation-based learning to problem-solving traces. He also discusses the impact of the utility problem. The utility problem, simply stated, says that the (computational) benefits of using the additional knowledge must outweigh the cost of applying it. PbR plan-rewriting rules also are subject to the utility problem. The quality improvement obtained by adding more rewriting rules to a PbR-based planner may not be worth the performance degradation. Another approach to automatically generating search control is by analyzing statically the operators [29] or inferring invariants in the planning domain [35,34,68]. Abstraction provides yet another form of search control. Knoblock [46] presents a system that automatically learns abstraction hierarchies from a planning domain or a particular problem instance in order to speed up planning. plan-rewriting rules can be learned with techniques analogous to those used to learn search control. Ambite, Knoblock, & Minton [6] present an approach to automatically learn the plan-rewriting rules based on comparing initial and optimal plans for example problems. Alternatively, analyzing the planning operators and which combinations of operators are equivalent with respect to the achievement of some goals can also lead to the automatic generation of the rewriting rules.
Local search algorithms have also been used to improve planning efficiency although in a somewhat indirect way. Planning can be reduced to solving a series of propositional satisfiability problems [43]. Thus, Kautz & Selman [44] used an efficient satisfiability testing algorithm based on local search to solve the SAT encodings of a planning problem. Their approach proved more efficient than specialized planning algorithms. We believe that the power of their approach stems from the use of local search. PbR directly applies local search on the plan structures, as opposed to translating it first to a larger propositional representation.
Although all these approaches do improve the efficiency of planning, they do not specifically address plan quality, or else they consider only very simple cost metrics (such as the number of steps). Some systems learn search control that addresses both planning efficiency and plan quality [28,19,66]. However, from the reported experimental results, PbR appears to be more scalable. Moreover, PbR provides an anytime algorithm while other approaches must run to completion.