In this paper we describe a new approach to sampling-based motion planning with Probabilistic Roadmap Planner (PRM) methods. Our aim is to compute good quality roadmaps which encode the multiple connectedness of the configuration space inside small but yet representative graphs which capture the different varieties of free paths well. The proposed Path Deformation Roadmaps (PDRs) rely on a notion of path deformability indicating whether or not a given path can be continuously deformed into another existing path. By considering a simpler form of deformation than that allowed between homotopic paths, we propose a method that extends the Visibility-PRM technique to construct compact roadmaps which encode richer and more suitable information than representative paths of the homotopy classes. PDRs contain additional useful cycles between paths in the same homotopy class that can be hardly deformed into each other. Experimental results show that the technique enables small roadmaps to reliably capture the multiple connectedness of complex spaces in various problems involving free-flying and articulated robots in both two- and three-dimensional environments.
Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C. and Vallejo, D. (1998). OBPRM: an obstacle-based PRM for 3D workspaces. Robotics: The Algorithmic Perspective (WAFR1998), Agarwal, P., Kavraki, L. E. and Mason, M. (eds). Wellesley, MA, A.K. Peters, pp. 155-168.
2.
Bohlin, R. and Kavraki, L.E. (2000). Path planning using lazy PRM. Proceedings IEEE Internatiortal Conference on Robotics and Automation, pp. 521-528.
3.
Boor, V., Overmars, M.H. and van der Stappen, A.F. (1999). The Gaussian sampling strategy for probabilistic roadmap planners. Proceedings IEEE Internatiortal Conference on Robotics and Automation, pp. 1018-1023.
4.
Bums, B. and Brock, O. (2005). Toward optimal configuration space sampling. Proceedings of Robotics: Science and Systems.
5.
Cheng, H.-L., Hsu, D., Latombe, J.-C. and Sanchez-Ante, G. (2006). Multi-level free-space dilation for sampling narrow passages in PRM planning. Proceedings IEEE International Conference on Robotics and Automation, pp. 1255-1260.
6.
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E. and Thrun, S. (2005). Principles of Robot Motion. Cambridge, MA, MIT Press.
7.
Geraerts, R. and Overmars, M.H. (2006). Creating high-quality roadmaps for motion planning in virtual environments. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
8.
Hatcher, A. (2002). Algebraic Topology. Cambridge, Cambridge University Press. Available at http://www.math.cornell.edu/~hatcher/AT/ATpage.html.
9.
Holleman, C. and Kavraki, L.E. (2000). A framework for using the workspace medial axis in PRM planners. Proceedings IEEE Internatiortal Conference on Robotics and Automation, pp. 1408-1413.
10.
Hsu, D., Jiang, T., Reif, J. and Sun, Z. (2003). The bridge test for sampling narrow passages with probabilistic roadmap planners. Proceedings IEEE International Conference on Robotics and Automation.
11.
Huang, Y. and Gupta, K. (2004). A Delaunay triangulation based node connection strategy for probabilistic roadmap planners. Proceedings IEEE International Conference on Robotics and Automation, pp. 908-913.
12.
Jaillet, L. (2005). Methodes Probabilistes Pour La Planification Reactive de Mouvements. PhD Thesis, Paul Sabatier University. Available at http://robotics.cs.umass.edu/tc-apc/Main/Theses .
13.
Kavraki, L.E., Svestka, P., Latombe, J.-C. and Overmars, M.H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
14.
Koenig, S. and Furcy, D. (2004). Lifelong planning A. Artificial Intelligence, 155: 93-146.
15.
Kurniawati, H. and Hsu, D. (2006). Workspace-based connectivity Oracle: an adaptive sampling strategy for PRM planning. Algorithmic Foundations of Robotics VII , Akella, S. et al. (eds). Berlin, Springer.
LaValle, S.M. (2004). Planning Algorithms. Cambridge, Cambridge University Press. Available at http://msl.cs.uiuc.edu/planning/.
18.
Lien, J.-M., Thomas, S.L. and Amato, N.M. (2003). A general framework for sampling on the medial axis of the free space. Proceedings IEEE International Conference on Robotics and Automation.
19.
Nieuwenhuisen, D. and Overmars, M.H. (2004). Useful cycles in probabilistic roadmap graphs . Proceedings IEEE International Conference on Robotics and Automation, pp. 446-452.
20.
Rodriguez, S., Shawna, S., Pearce, R. and Amato, N.M. (2006). Resampl: a region-sensitive adaptive motion planner . Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
21.
Saha, M. and Latombe, J.C. (2005). Finding narrow passages with probabilistic roadmaps: the small-step retraction method. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
22.
Schmitzberger, E., Bouchet, J.L., Dufaut, M., Didier, W. and Husson, R. (2002). Capture of homotopy classes with probabilistic road map. Proceedings of the IEEE/RSJ International Conference on Robots and Systems.
23.
Sekhavat, S., Svestka, P., Laumond, J.-P. and Overmars, M.H. (1998). Multi-level path planning for nonholonomic robots using semi-holonomic subsystems. The International Journal of Robotics Research, 17(8): 840-857.
24.
Simeon, T., Laumond, J.-P. and Nissoux, C. (2000). Visibility-based probabilistic roadmaps for motion planning. Advanced Robotics Journal, 14(6): 477-494.
25.
Simeon, T., Laumond, J.-P. and Lamiraux, F. (2001). Move3D: a generic platform for path planning. Proceedings IEEE International Symposium on Assembly and Task Planning.
26.
Sanchez, 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.
van den Berg, J.P., Nieuwenhuisen, D., Jaillet, L. and Overmars, M.H. (2005). Creating robust toadmaps for motion planning in changing environments. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
28.
van den Berg, J.P. and Overmars, M.H. (2007). Kinodynamic motion planning on roadmaps in dynamic environments. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
29.
Wilmarth, S., Amato, N.M. and Stiller, P. (1999). MAPRM: a probabilistic roadmap planner with sampling on the medial axis of the free space. Proceedings IEEE International Conference on Robotics and Automation, pp. 1024-1031.
