Multi-modal Motion Planning in Non-expansive Spaces
- 22 October 2009
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 29 (7) , 897-915
Abstract
Motion planning problems encountered in manipulation and legged locomotion have a distinctive multi-modal structure, where the space of feasible configurations consists of intersecting submanifolds, often of different dimensionalities. Such a feasible space does not possess expansiveness, a property that characterizes whether planning queries can be solved efficiently with traditional probabilistic roadmap (PRM) planners. In this paper we present a new PRM-based multi-modal planning algorithm for problems where the number of intersecting manifolds is finite. We also analyze the completeness properties of this algorithm. More specifically, we show that the algorithm converges quickly when each submanifold is individually expansive and establish a bound on the expected running time in that case. We also present an incremental variant of the algorithm that has the same convergence properties, but works better for problems with a large number of submanifolds by considering subsets of submanifolds likely to contain a solution path. These algorithms are demonstrated in geometric examples and in a legged locomotion planner.Keywords
This publication has 10 references indexed in Scilit:
- Athlete: A cargo handling and manipulation robot for the moonJournal of Field Robotics, 2007
- On the Probabilistic Foundations of Probabilistic Roadmap PlanningThe International Journal of Robotics Research, 2006
- Randomized Kinodynamic Motion Planning with Moving ObstaclesThe International Journal of Robotics Research, 2002
- On Delaying Collision Checking in PRM Planning: Application to Multi-Robot CoordinationThe International Journal of Robotics Research, 2002
- Randomized Kinodynamic PlanningThe International Journal of Robotics Research, 2001
- A two level fuzzy PRM for manipulation planning2000
- PATH PLANNING IN EXPANSIVE CONFIGURATION SPACESInternational Journal of Computational Geometry & Applications, 1999
- Randomized Query Processing in Robot Path PlanningJournal of Computer and System Sciences, 1998
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963