|
Informally, the problem of generalized planning is to find plans that
can solve a set of problem instances. In one form or another, this
problem has been studied since the earliest work on STRIPS
planning (Fikes et al. 1972). A generalized plan can be viewed as an object with a method for instantiation, which yields a concrete sequence of operations when given a problem instance. GP: S → π An implementation of the method for instantiation may be interleaved with the execution of π, so that any generated observations can be taken into account. In such situations, the problem is revealed incrementally through the observations. A greater discussion of such problems with partial observability can be found in the section on contingent planning under approaches. This definition of generalized plans unifies various approaches to "efficiently" producing "good" plans for "broad" classes of problems. Trivially, a classical planner also addresses this objective: it uses heuristic search to generate (or instantiate) a plan for a given problem instance. Using the definition above, we can understand the requirement of efficiency as one of decreasing the overall cost of instantiation, with the worst-case exponential cost of instantiation of classical planners as a baseline. Approaches for macro tabulation such as Triangle Tables, or plan compilation such as case-based planning (CBP) essentially aim to do this. More recent approaches like KPLANNER (Levesque 2005), loopDISTILL (Winner and Veloso, 2007) and ARANDA (Srivastava et al., 2007) aim to lower the cost of instantiation while extending the generality of plans by including loops of actions for handling various problem instances. In the context of this definition of generalized plans, we can break down the desirable requirements of any approach for generalized planning into the following five factors:
|