A Framework for Planning withIncrementally Created Graphs in Attributed Problem SpacesProblem Spaces

Published

January 1, 2003

Author(s)

Stephen B. Balakirsky

Abstract

In this thesis, a framework for parallel planning agents is developed and applied to planningproblems ranging from domain independent planning to planning for autonomous vehiclesystems. This general purpose framework combines both logic-based and cost-basedplanning approaches in order to allow for the creation of logic-constrained cost optimalplans with respect to possibly dynamic environments, user objectives, and constraints.In order to fully understand the requirements for planning agents, the state-of-the-artin agent architectures is presented. In addition, the state-of-the-art in planning is examinedin order to provide basis for the development of the general purpose framework.This novel general purpose planning framework plans on incrementally createdplanning graphs and is proven to be capable of generating logic-constrained, cost optimalplans. The framework is then further elaborated upon in order to apply it to partitionedproblem spaces where it is proven to be capable of generating logic-constrained, costoptimal plans with parallel planning agents.The general purpose framework is also shown to include the ability to implementboth hard and soft constraints. It is demonstrated that hard constraints based on deriveddomain feature predicates may be used to incrementally construct a planning graph. Theseconstraints are shown to eliminate classes of state transitions from the planner s vocabulary,thus constraining possible behaviors. Soft constraints allow the system to exhibit apreference for one form of state transition over another. These preferences are controlledthrough the use of a cost function during the incremental construction of the planning graphand lead to favoring certain system behaviors over others.Experiments are performed in rule-based and cost-based planning domains. Thesedomains range from simple to complex, with examples from the literature such as thetowers of Hanoi, and domain independent planning (flat tire domain and elevator domain)[20] as well as current state-of-the-art real-time autonomous vehicle applications such ason- and off-road driving. These experimental results show that this incremental techniqueproduces smaller planning graphs with higher quality planning results than standard graphbasedplanning techniques: for a high-resolution off-road driving domain, the incrementaltechnique constructed graphs that contained ~3% as many nodes, ~14% as many edges, andproduced paths that were ~9% shorter (when plan optimality was judged by path length).One sample path from the experiments contained ~1% as many nodes and ~2% as manyedges while constructing a plan that was ~71% shorter. These improvements are the resultof the incremental graph construction approach and the application of hard and softconstraints that are also shown to elicit a variety of different driving behaviors in theautonomous vehicle domain and different problem solving approaches in the towers ofHanoi domain.Finally, real-time operation capabilities are demonstrated through the developmentof an any-time approach to planning in partitioned problem spaces. The ability of thegeneral purpose planning framework to construct plans in real-time, resource constrainedenvironments is also demonstrated through the graceful degradation of performance whenresource usage is constrained.

Citation

Submitted in partial fulfillment of the requirements for the degree of Dr.-ing. to the Department of Mathematics and Computer Science University of Bremen

Pub Type

Journals

Keywords

optimal plan, Planning graph, robotic planning, world model

Citation

Balakirsky, S. (2003), A Framework for Planning withIncrementally Created Graphs in Attributed Problem SpacesProblem Spaces, Submitted in partial fulfillment of the requirements for the degree of Dr.-ing. to the Department of Mathematics and Computer Science University of Bremen (Accessed April 25, 2024)