|
The definition of generalized plans captures many different approaches to improving the efficiency of planning. Program-like plans such as the following can also be treated as generalized plans: while (∃b: clear(b) ∧ ¬onTable(b)) { mvToTable(b) } This plan for unstacking blocks solves all block-world problems where the goal is to have all blocks on the table. During instantiation, this program like data structure needs to be converted into a sequence of concrete mvToTable(_) actions with object names as arguments. For problems that require observations such as those of conditional planning, instantiation can be interleaved with its execution. In this form of plan instantiation, successive actions in π are generated by the generalized plan after taking the available observations into account. Complexity of Plan InstantiationApproaches such as Case Based Planning (CBP; Spalzzi 2001) incur significant computational effort during the process of instantiation. If it is acceptable for plan instantiation to require considerable computation, even classical planners can be thought of as generalized plan objects: they possess no data-structures and their method for plan instantiation amounts to a direct search for a plan from scratch. This makes the amount of computational effort required during plan instantiation a significant factor for any generalized plan, and the key distinguishing factor between plans such as the one for unstacking, above, and classical planners which offer broad generality, but suffer with worst-case exponential instantiation costs.Complexity of Checking ApplicabilityA generalized plan can be designed to proceed in one of two ways when given an input problem instance: (1) conduct a pre-designed applicability test to determine if an instantiation will be possible, and if so, proceed to find it, or, (2) directly attempt an instantiation. The problem with the second approach is that instantiation can be an expensive and wasteful operation if the generalized plan cannot actually solve the given problem instance. While the first approach is desirable, it is often very difficult to construct an applicability test; the ideal situation would be to have a linear time applicability test.Approaches for finding generalized plans seldom offer applicability tests. KPLANNER (Levesque, 2005), as an exception, provides a partial test: within the user-requested bounds on a unique parameter that its input problem instances are allowed to vary over, its generalized plans are guaranteed to produce a correct instantiation. Approaches like case-based planning (Spalzzi, 2001) incur large costs of applicability and instantiation while retrieving and adapting potentially applicable previously observed plans; modern approaches like DISTILL (Winner and Veloso, 2001) also do not provide applicability tests. Domain CoverageSolving broad classes of problems is the most commonly addressed, and one of the original motivations (Fikes, Hart and Nilsson, 1972) behind existing approaches for generalized planning. We define the domain coverage of a plan as a measure of the size of the set of problem instances of interest that are solved by a generalized plan. Concrete plans produced by classical planners actually score very well as generalized plans on all the factors discussed so far, except that they typically work for only one problem instance. Conditional plans cover larger sets of problem instances than classical plans. However, as discussed below, their utility is limited because their inherently large sizes make conditional plans too difficult to find.Complexity of Computing a Generalized PlanConditional planning produces generalized plans with clear applicability tests (by definition, they solve all instances of the provided initial belief state) and are easy to instantiate. However, the decision tree structured representations that they use for expressing solutions can grow exponentially with every unknown predicate tuple, making plans inherently more difficult to find. Plan representation thus becomes an important factor when considering the complexity of deriving a generalized plan itself. Approaches like DISTILL (Winner and Veloso, 2001), KPLANNER (Levesque, 2005), and BAGGER2 (Shavlik, 1990) mitigate this cost by constructing plans with loops that can instantiate into much larger concrete plans.Quality of the Instantiated PlanThe quality of instantiated plans produced determines the relative usability of a generalized plan. Ideally, instantiated plans should be optimal according to a measure like the number of actions in the plan or its makespan. Again, determining how well or poorly a generalized plan's instantiations perform is not always easy to determine, and most approaches focus on finding any working instantiation. |