Approaches for Generalized PlanningApproaches Focusing on Domain CoverageThese approaches focus on increasing the domain coverage. Consequently, the generalized plans they produce are intended to work for very broad classes of problem instances. However, they incur high costs of instantiation which may even exceed the cost of planning from scratch.Triangle Tables (1972)Almost as soon as the problem of planning took its modern form in the STRIPS representation, it became clear that reusing plans or operator sequences would reduce significant amounts of repeated effort in while solving similar problem instances. Triangle tables (Fikes et al., 1972) were designed as lookup tables for operator sequences or macro operators, together with their overall effects and preconditions. These tables were used to monitor the execution of plans as well as provide short-cuts to the replanning process in case of an unexpected result.This compilation of plan segments forms one of the earliest approaches for generalized planning: the motivation was to obtain a large domain coverage with a cost of instantiation lower than that of planning from scratch. In the worst case however, inclusion of macro operators increases the search space of possible operators. Therefore, although the coverage of triangle tables would definitely be greater than that of the individual plans, they do not guarantee a lower cost of instantiation. Case Based Planning (1986)Triangle tables were difficult to maintain while avoiding multiple, subsuming versions of operator sequences. An alternate approach, case based planning (CBP), was developed as a model for ``planning from experience'' (Hammond, 1986; Spalzzi, 2001). Like triangle tables, the objective of CBP was to reduce the cost of instantiation while obtaining a wide domain coverage. CBP approaches directly addressed the problem of redundant operator sequences by developing specialized representations for storing plans in a database. This facilitated faster retrieval of plans relevant to the given problem. Approaches like CHEF (Hammond, 1986) relied upon a model of ``the causality of the domain'' to be able to repair these retrieved plans.In CBP approaches, subroutines for plan retrieval, adaptation, and efficient storage have to be executed on every problem instance. This increases the cost of instantiation; CBP approaches can also suffer from a lack of an efficient test of applicability: while triangle tables only increased the set of available operators and thus had the same applicability as the underlying action model, the applicability of a CBP database depends on the scope of its plan-memory and adaptation routines (although a classical planner invocation could always be incorporated with a CBP system to make it universally applicable). Approaches with Low Costs of InstantiationApproaches discussed in this section incur fewer overheads during plan instantiation. This is typically accompanied with trade-offs in the domain coverage of the produced generalized plans and absence of clear applicability tests.Explanation Based Planning (1990)Explanation based planning borrows ideas from explanation based learning (EBL), where the proof a given solution is generalized used to solve other, conceptually similar problem instances. Methods for EBL rely on complete domain theories to be able to generate these proofs. The BAGGER2 system (Shavlik, 1990) could generate plans with recursive structures for handling problems with unbounded numbers of objects. By using recursive structures, BAGGER2 significantly reduced the number of possible actions or rules to be attempted during plan instantiation.However, in order to do so, BAGGER2 used an a-priori hand-coded domain theory which included the recurrence relationships between recursive concepts that could be encountered in a solution. Although the use of a domain theory allowed BAGGER2 to make well-justified generalizations, it could not address the problem of designing an applicability test: BAGGER2 could generate (but not identify) non-terminating plans. Contingent PlanningThe problem of contingent planning addresses a version of the generalized planning problem where the agent does not have precise information about its environment and therefore needs to be prepared to solve any of the possible instances it might encounter. The agent's actions in contingent planning problems may allow it to gain new information about its state. A contingent plan, therefore, may consist of such sensing actions; the remainder of the plan after these actions can depend upon the results of these actions. At any stage, the set of possible states that the agent may be in constitutes its belief state. The contingent planning problem can thus be formulated as a search problem in the space of the agent's belief states (Bonet and Geffner, 2000), with the goal belief states consisting only of real goal states.Contingent plans are also generalized plans, with a key point of difference: in contingent planning the description of the problem instance is amortized. It is not known at the beginning of plan execution, but is revealed through the observable results of actions executed by the agent. Consequently, contingent plans can be completely instantiated only during plan execution, because parts of the plan may depend on the results of sensing actions. By definition, a contingent plan must solve every initial state represented by the initial belief state. The applicability test for contingent plans thus reduces to testing whether the current instance is captured by the initial belief state, which can typically be done in time linear in the size of the initial state. Contingent plans typically consist of fully instantiated operations, and can be easily instantiated into linear sequences of operations once the action observations become available. This makes contingent plans desirable from the point of view of applicability tests, domain coverage, and instantiation costs. However, contingent plans are typically represented using tree structured representations (Hoffmann and Brafman, 2005) that grow exponentially with the number of observations to be performed. This makes finding contingent plans computationally intractable. Contingent planning thus addresses most of the requirements of generalized planning -- except the complexity of computing a generalized plan. Effectively, this restricts the applicability of contingent planners to problems that require small solutions. Strong Cyclic Planning (2003)In strong cyclic planning (Cimatti et al., 2003), plans are represented as execution control tables mapping problem states to actions. These tables may incorporate cyclic flows of control if from every state in the cycle, there exists a path of actions leading to a goal state. With this structure, under the assumption that during execution every possible action outcome in the plan will have a non-zero probability, the plan will eventually terminate in the goal state.Strong cyclic planning allows us to represent compact contingent plans, and is particularly applicable in problems with temporally extended goals or situations where actions may fail and the only way to reach the goal is to repeat them until they succeed. However, in this approach plans with loops are are always less preferred than linear plans: a strong cyclic planner will create a plan with loops only if no acyclic plan can solve the given problem (for instance, when the goal is to stack a block on another, but the move action may drop a block back on to the table). Therefore, in some cases strong cyclic planning alleviates the problem caused due to representational constraints in contingent planning; some problems can only be solved by strong cyclic plans, and require loops of actions which make no measurable progress (such as a loop over the move action for the stacking problem with the possibility of the block being dropped). Because of these constraints, strong cyclic plans may execute an unbounded number of operations before termination and therefore have weaker applicability tests. |