Efficiently combining task and motion planning using geometric constraints
- 13 October 2014
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 33 (14) , 1726-1747
Abstract
We propose a constraint-based approach to address a class of problems encountered in combined task and motion planning (CTAMP), which we call kinematically constrained problems. CTAMP is a hybrid planning process in which task planning and geometric reasoning are interleaved. During this process, symbolic action sequences generated by a task planner are geometrically evaluated. This geometric evaluation is a search problem per se, which we refer to as geometric backtrack search. In kinematically constrained problems, a significant computational effort is spent on geometric backtrack search, which impairs search at the task level. At the basis of our approach to address this problem, is the introduction of an intermediate layer between task planning and geometric reasoning. A set of constraints is automatically generated from the symbolic action sequences to evaluate, and combined with a set of constraints derived from the kinematic model of the robot. The resulting constraint network is then used to prune the search space during geometric backtrack search. We present experimental evidence that our approach significantly reduces the complexity of geometric backtrack search on various types of problem.Keywords
This publication has 23 references indexed in Scilit:
- Answer set programming for collaborative housekeeping robotics: representation, reasoning, and executionIntelligent Service Robotics, 2012
- A Hybrid Approach to Intricate Motion, Manipulation and Task PlanningThe International Journal of Robotics Research, 2009
- Planning Among Movable Obstacles with Artificial Constraints2008
- Tractable Structures for Constraint Satisfaction Problems2006
- Manipulation Planning with Probabilistic RoadmapsThe International Journal of Robotics Research, 2004
- A Global Filtering Algorithm for Handling Systems of Quadratic Equations and Inequations2002
- Interval constraint propagation with application to bounded-error estimationAutomatica, 2000
- Motion planning in the presence of movable obstacles1988
- Constraint propagation with interval labelsArtificial Intelligence, 1987
- On the complexity of linear programming1987