 Research in AI plan generation was heavily influenced by the development of then-novel algorithms for partial-order causal link (POCL) planning, notably Chapman’s TWEAK and McAllister and Rosenblitt’s SNLP. These algorithms, and the systems based on them (notably Penberthy and Weld’s UCPOP), have been widely accepted as capturing the key insights of a host of earlier planners, in a framework that is more amenable to rigorous analysis.
In our work. we have shown how to incorporate action decomposition directly into the SNLP algorithm. The resulting algorithm, which we call DPOCL (Decompositional Partial-Order Causal-Link Planner) is clear and simple, and can readily be integrated with other SNLP extensions. In addition, DPOCL is specifically designed to handle partially specified action decompositions. Other approaches to formalizing action decomposition have tended to make overly strong assumptions about the completeness of decomposition specifications. Plan generation in DPOCL exploits the planner’s ability to fill in the missing pieces of a partially specified subplan in a way that uses the existing context of the larger plan being constructed. Standard POCL planners iterate through a loop in which they first check for a completed plan, then perform plan refinement by first adding causal links for open conditions and then resolving threats to existing causal links created by recent plan modifications. DPOCL differs from this approach by providing an additional option for the plan refinement phase: the planner may either do causal planning or may do decompositional planning. Either of these options is followed by a threat resolution phase. The algorithm terminates when there are no open conditions and when all abstract steps have been decomposed into primitive actions. DPOCL is both sound and satisfies a restricted but useful form of completeness called primitive completeness. That is, for every solution S to a planning problem A where S contains only primitive steps, DPOCL is guaranteed to produce a plan whose primitive steps are precisely S. Action decomposition is generally accepted as essential to effecient plan generation. Although many previous planning systems have employed action decomposition, the development of algorithms like SNLP make it possible for the first time to give a careful statement of the decomposition process. By incorporating decompositional planning directly into a POCL framework we have been able to specify a precise relationship between abstract steps and the subplans that achieve them. Furthermore, the constraints we place on the specification of decomposition schemata in DPOCL are less restrictive than previous formal models. By taking advantage of the context of the larger plan under construction during composite step expansion, DPOCL can generate plans that may be more efficient than those produced by planners that require more constrained specifications of decomposition schemata. Team members
DPOCL publicationsYoung, R. Michael, Martha E. Pollack and Johanna D. Moore, Decomposition and causality in partial-order planning, Intelligent Systems Program Technical Report 94-2, University of Pittsburgh, 1994. Young, R. Michael. A Developer’s Guide to the Longbow Discourse Planning System, Intelligent Systems Program Technical Report 94-4, University of Pittsburgh, 1994. [PDF] Young, R. Michael and Johanna D. Moore, DPOCL: A principled approach to discourse planning, inProceedings of the Seventh International Workshop on Natural Language Generation, Kennebunkport, ME, pages 13-20, July, 1994. [PDF] Young, R. Michael, Martha E. Pollack and Johanna D. Moore, Decomposition and causality in partial-order planning, in Proceedings of the Second International Conference on AI and Planning Systems, Chicago, IL, pages 188-193, July, 1994. [PDF] DPOCL video or image filesNone available. DPOCL in the newsNone available. DPOCL softwarePlease contact R. Michael Young (young at eae.utah.edu) DPOCL sponsorsThe US Office of Naval Research |
