Many planning applications involve complex relationships defined on high-dimensional, continuous variables. For example, robotic manipulation requires planning with kinematic, collision, and motion constraints involving robot configurations, object transforms, and robot trajectories. These constraints typically require specialized procedures to sample satisfying values. We extend the STRIPS planning language to support a generic, declarative specification for these procedures while treating their implementation as blackboxes. We provide several domain-independent algorithms that reduce STRIPStream problems to a sequence of finite-domain STRIPS planning problems. Additionally, we describe cost-sensitive planning within this framework. Finally, we evaluate our algorithms on three robotic task and motion planning domains.
Several PDDL extensions such as PDDL2.1 @cite_10 and PDDL+ @cite_6 support planning with numeric variables that evolve as a function of time. Most planners are restricted to problems with linear or polynomial dynamics governing these variables @cite_22 @cite_9 @cite_16 ; however, some planners can handle non-polynomial dynamics by discretizing time @cite_20 @cite_8 . While it may be technically possible to analytically model, for example, collision constraints among three-dimensional meshes using PDDL+, the resulting encoding would be enormous, far exceeding the demonstrated capabilities of current numeric planners.
@cite_22 @cite_8 @cite_9 @cite_6 @cite_16 @cite_10 @cite_20
970972620 2512139417 2133517325 2119709400
PDDL+ planning involves reasoning about mixed discrete-continuous change over time. Nearly all PDDL+ planners assume that continuous change is linear. We present a new technique that accommodates nonlinear change by encoding problems as nonlinear hybrid systems. Using this encoding, we apply a Satisfiability Modulo Theories (SMT) solver to find plans. We show that it is important to use novel planning-specific heuristics for variable and value selection for SMT solving, which is inspired by recent advances in planning as SAT. We show the promising performance of the resulting solver on challenging nonlinear problems. Planning in hybrid systems is important for dealing with real-world applications. PDDL+ supports this representation of domains with mixed discrete and continuous dynamics, and supports events and processes modelling exogenous change. Motivated by numerous SAT-based planning approaches, we propose an approach to PDDL+ planning through SMT, describing an SMT encoding that captures all the features of the PDDL+ problem as published by Fox and Long (2006). The encoding can be applied on domains with nonlinear continuous change. We apply this encoding in a simple planning algorithm, demonstrating excellent results on a set of benchmark problems. In this paper we present PDDL+, a planning domain description language for modelling mixed discrete-continuous planning domains. We describe the syntax and modelling style of PDDL+, showing that the language makes convenient the modelling of complex time-dependent effects. We provide a formal semantics for PDDL+ by mapping planning instances into constructs of hybrid automata. Using the syntax of HAs as our semantic model we construct a semantic mapping to labelled transition systems to complete the formal interpretation of PDDL+ planning instances. An advantage of building a mapping from PDDL+ to HA theory is that it forms a bridge between the Planning and Real Time Systems research communities. One consequence is that we can expect to make use of some of the theoretical properties of HAs. For example, for a restricted class of HAs the Reachability problem (which is equivalent to Plan Existence) is decidable. PDDL+ provides an alternative to the continuous durative action model of PDDL2.1, adding a more flexible and robust model of time-dependent behaviour. In recent years research in the planning community has moved increasingly towards application of planners to realistic problems involving both time and many types of resources. For example, interest in planning demonstrated by the space research community has inspired work in observation scheduling, planetary rover exploration and spacecraft control domains. Other temporal and resource-intensive domains including logistics planning, plant control and manufacturing have also helped to focus the community on the modelling and reasoning issues that must be confronted to make planning technology meet the challenges of application. The International Planning Competitions have acted as an important motivating force behind the progress that has been made in planning since 1998. The third competition (held in 2002) set the planning community the challenge of handling time and numeric resources. This necessitated the development of a modelling language capable of expressing temporal and numeric properties of planning domains. In this paper we describe the language, PDDL2.1, that was used in the competition. We describe the syntax of the language, its formal semantics and the validation of concurrent plans. We observe that PDDL2.1 has considerable modelling power -- exceeding the capabilities of current planning technology -- and presents a number of important challenges to the research community.