next up previous
Next: 3.4.2 Facilitating Algorithmic Plan Construction Up: 3.4 Initial Plan Generation Previous: 3.4 Initial Plan Generation

3.4.1 Biased Generative Planners

There are a variety of ways in which to control the search of a generic planner. Some planners accept search control rules, others accept heuristic functions, and some have built-in search control. We present examples of these techniques.

A very general way of efficiently constructing plans is to use a domain-independent generative planner that accepts search control rules. For example, Prodigy [21], UCPOP [65] and Sage [48] are such planners. By setting the type of search and providing a strong bias by means of the search control rules, the planner can quickly generate a valid, although possibly suboptimal, initial plan. For example, in the manufacturing domain of [54], analyzed in detail in Section 4.1, depth-first search and a goal selection heuristic based on abstraction hierarchies [46] quickly generates a feasible plan, but often the quality of this plan, which is defined as the time required to manufacture all objects, is suboptimal.

TLPlan [10,11] is an efficient forward-chaining planner that uses search control expressed in temporal logic. Because in forward chaining the complete state is available, much more refined domain control knowledge can be specified. The preferred search strategy used by TLPlan is depth-first search, so although it finds plans efficiently, the plans may be of low quality. Note that because it is a generative planner that explores partial sequences of steps, it cannot use sophisticated quality measures.

HSP [18,17] is a forward search planner that performs a variation of heuristic search applied to classical AI planning. The built-in heuristic function is a relaxed version of the planning problem: it computes the number of required steps to reach the goal disregarding negated effects in the operators. Such metric can be computed efficiently. Despite its simplicity and that the heuristic is not admissible, it scales surprisingly well for many domains. Because the plans are generated according to the fixed heuristic function, the planner cannot incorporate a quality metric.

These types of planners are quite efficient in practice although they often produce suboptimal plans. They are excellent candidates to generate the initial plans that will be subsequently optimized by PbR.


next up previous
Next: 3.4.2 Facilitating Algorithmic Plan Construction Up: 3.4 Initial Plan Generation Previous: 3.4 Initial Plan Generation
Jose-Luis Ambite 2001-08-09