Constraint propagation on interval bounds for dealing with geometric backtracking
- 1 October 2012
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21530858,p. 957-964
Abstract
The combination of task and motion planning presents us with a new problem that we call geometric backtracking. This problem arises from the fact that a single symbolic state or action may be geometrically instantiated in infinitely many ways. When a symbolic action cannot be geometrically validated, we may need to backtrack in the space of geometric configurations, which greatly increases the complexity of the whole planning process. In this paper, we address this problem using intervals to represent geometric configurations, and constraint propagation techniques to shrink these intervals according to the geometric constraints of the problem. After propagation, either (i) the intervals are shrunk, thus reducing the search space in which geometric backtracking may occur, or (ii) the constraints are inconsistent, indicating the non-feasibility of the sequence of actions without further effort. We illustrate our approach on scenarios in which a two-arm robot manipulates a set of objects, and report experiments that show how the search space is reduced.Keywords
This publication has 6 references indexed in Scilit:
- Sampling-Based Motion and Symbolic Action Planning with geometric and differential constraints2010
- A Hybrid Approach to Intricate Motion, Manipulation and Task PlanningThe International Journal of Robotics Research, 2009
- Capturing robot workspace structure: representing robot capabilities2007
- A Humanoid Two-Arm System for Dexterous Manipulation2006
- Planning Algorithms2006
- Analysis of probabilistic roadmaps for path planning2002