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.
Akinc, M., Bekris, K.E., Chen, B.Y., Ladd, A.M., Plaku, E. and Kavraki, L.E. ( 2003). Probabilistic roadmaps of trees for parallel computation of multiple query roadmaps. International Symposium on Robotics Research, Siena, Italy.
2.
Alami, R., Laumond, J.-P. and Siméon, T. ( 1995). Two manipulation planning algorithms. Algorithmic Foundations of Robotics, Goldberg, K., Halperin, D., Latombe, J.-C. and Wilson, R. (eds). Wellesley, MA, A K Peters, pp. 109-125.
3.
Boor, V., Overmars, M. and van der Stappen, A. ( 1999). The Gaussian sampling strategy for probabilistic roadmap planners. International Conference on Robotics and Automation, pp. 1018-1023.
4.
Bretl, T., Lall, S., Latombe, J.-C. and Rock, S. ( 2004). Multi-step motion planning for free-climbing robots. Workshop on the Algorithmic Foundations of Robotics, Zeist, the Netherlands.
5.
Chaudhuri, S. and Koltun, V. ( 2007). Smoothed analysis of probabilistic roadmaps. Fourth SIAM Conference of Analytic Algorithms and Computational Geometry.
6.
Choset, H., Lynch, K., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L. and Thrun, S. ( 2005). Principles of Robot Motion: Theory, Algorithms, and Implementations . Cam-bridge, MA, MIT Press.
7.
Cortés, J. and Siméon, T. ( 2004). Sampling-based motion planning under kinematic loop-closure constraints. Workshop on the Algorithmic Foundations of Robotics, Zeist, the Netherlands.
8.
Hauser, K., Bretl, T. and Latombe, J.-C. ( 2005a). Learning-assisted multi-step planning. IEEE International Conference on Robotics and Automation, Barcelona, Spain.
9.
Hauser, K., Bretl, T. and Latombe, J.-C. ( 2005b). Non-gaited humanoid locomotion planning. IEEE International Conference on Humanoid Robots, Tsukuba, Japan.
10.
Hauser, K., Bretl, T., Latombe, J.-C., Harada, K. and Wilcox, B. ( 2006). Motion planning for legged robots on varied terrain. The International Journal of Robotics Research, 27(11-12): 1325-1349.
11.
Hauser, K., Ng-Thow-Hing, V. and Nos, H.G.-B. ( 2007). Multi-modal planning for a humanoid manipulation task . International Symposium on Robotics Research , Hiroshima, Japan.
12.
Hoeffding, W. ( 1996). Probability inequalities for sums of bounded random variables . Journal of the American Statistical Association, 58(301): 13-30.
13.
Hsu, D., Kavraki, L.E., Latombe, J.-C., Motwani, R. and Sorkin, S. ( 1998). On finding narrow passages with probabilistic roadmap planners. Workshop on the Algorithmic Foundations of Robotics, Natick, MA, pp. 141-153.
14.
Hsu, D., Kindel, R., Latombe, J.-C. and Rock, S.(Mar 2002). Kinodynamic motion planning amidst moving obstacles. The International Journal of Robotics Research, 21(3): 233-255.
15.
Hsu, D., Latombe, J. and Kurniawati, H. ( 2006). On the probabilistic foundations of probabilistic roadmap planning. The International Journal Robotics Research, 25(7): 627- 643.
16.
Hsu, D., Latombe, J.-C. and Motwani, R. ( 1997). Path planning in expansive configuration spaces. IEEE International Conference on Robotics and Automation, pp. 2219-2226.
17.
Hsu, D., Latombe, J.-C. and Motwani, R. ( 1999). Path planning in expansive spaces. The International Journal of Computational Geometry and Applications, 9(4-5): 495- 512.
18.
Kavraki, L., Latombe, J., Motwani, R. and Raghavan, P. ( 1998). Randomized query processing in robot motion planning . Journal of Computer and System Sciences, 57(1): 50-60.
19.
Kavraki, L., Svetstka, P., Latombe, J. and Overmars, M. ( 1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
20.
Koga, Y. and Latombe, J.-C. ( 1994). On multi-arm manipulation planning. IEEE International Conference on Robotics and Automation, San Diego, CA, pp. 945-952.
21.
LaValle, S.M. and Kuffner, Jr, J.J. ( 2001). Randomized kinodynamic planning. The International Journal of Robotics Research, 20(5): 379-400.
22.
LaValle, S.M., Yakey, J.H. and Kavraki, L.E. ( 1999). A probabilistic roadmap approach for systems with closed kinematic chains. IEEE International Conference on Robotics and Automation, Detroit, MI.
23.
Nielsen, C.L. and Kavraki, L.E. ( 2000). A two level fuzzy PRM for manipulation planning. IEEE/RSJ International Conference on Intelligent Robots and Systems , pp. 1716- 1721.
24.
Nieuwenhuisen, D., van der Stappen, A.F. and Overmars, M.H. ( 2006). An effective framework for path planning amidst movable obstacles. Workshop on the Algorithmic Foundations of Robotics, New York, NY.
25.
Sahbani, A., Cortés, J. and Siméon, T. ( 2002). A probabilistic algorithm for manipulation planning under continuous grasps and placements. IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne , Switzerland, pp. 1560-1565.
26.
Sánchez, G. and Latombe, J.-C. ( 2002). On delaying collision checking in PRM planning: Application to multi-robot coordination. The International Journal of Robotics Research, 21(1): 5-26.
27.
Stilman, M. ( 2007). Navigation Among Movable Obstacles. PhD thesis, Carnegie Mellon University.
28.
van den Berg, J., Stilman, M., Kuffner, J., Lin, M. and Manocha, D. ( 2008). Path planning among movable obstacles: A probabilistically complete approach. Workshop on the Algorithmic Foundations of Robotics.
29.
Wilcox, B.H., Litwin, T., Biesiadecki, J., Matthews, J., Heverly, M., Morrison, J., Townsend, J., Ahmad, N., Sirota, A. and Cooper, B. ( 2007). Athlete: A cargo handling and manipulation robot for the Moon. Journal of Field Robotics, 24(5): 421-434.
