This paper describes the foundations and algorithms of a new probabilistic roadmap (PRM) planner that is: single-query—instead of pre-computing a roadmap covering the entire free space, it uses the two input query configurations to explore as little space as possible; bi-directional—it explores the robot's free space by building a roadmap made of two trees rooted at the query configurations; and lazy in checking collisions—it delays collision tests along the edges of the roadmap until they are absolutely needed. Several observations motivated this strategy: (1) PRM planners spend a large fraction of their time testing connections for collision; (2) most connections in a roadmap are not on the final path; (3) the collision test for a connection is most expensive when there is no collision; and (4) any short connection between two collision-free configurations has high prior probability of being collision-free. The strengths of single-query and bi-directional sampling techniques and those of delayed collision checking reinforce each other. Experimental results show that this combination reduces planning time by a large factor, making it possible to efficiently handle difficult planning problems, such as problems involving multiple robots in geometrically complex environments. This paper specifically describes the application of the planner to multi-robot planning and compares results obtained when the planner uses a centralized planning approach (PRM planning is then performed in the joint configuration space of the robots) and when it uses a decoupled approach (the PRM planner is invoked several times, first to compute a path of each robot independent of the others, and then to coordinate those paths). On a simulated six-robot welding station combining 36 degrees of freedom, centralized planning has proven to be a much more effective approach than decoupled planning.
Agarwal, P.K.1997. Range searching. In Handbook of Discrete and Computational Geometry, ed. J. E. Goodman and J. O'Rourke, 575-598. CRC Press.
2.
Ahuactzin, J.M.1994. Le Fil d'Ariane. Une méthode de planification générale. Application à la planification de trajectoires. PhD Thesis, National Polytechnic Institute of Grenoble, France.
3.
Ahuactzin, J.M., and Gupta, K.K.1999. The kinematic roadmap: A motion planning based global approach for inverse kinematics of redundant robots. IEEE Tr. On Robotics and Automation15(4):653-669.
4.
Alami, R., Robert, F., Ingrand, F.F., and Suzuki, S.1995. Multi-robot cooperation through incremental plan-merging . Proc. IEEE Int. Conf. on Robotics and Automation , Nagoya, Japan, pp. 2573-2578.
5.
Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D.1998. OBPRM: An obstacle-based PRM for 3D workspace. In Robotics: The Algorithmic Perspective, eds. P.K. Agarwal et al., 155-168. Natick, MA: A. K. Peters.
6.
Amato, N.M., Bayazit, O.B., Dale, L.K., Jones, C., and Vallejo, D.2000. Choosing good distance metrics and local planners for probabilistic roadmap methods. IEEE Tr. on Robotics and Automation16(4):442-447.
7.
Amato, N.M., and Wu, Y.1996. A randomized roadmap method for path and manipulation planning. Proc. IEEE Int. Conf. on Robotics and Automation, Minneapolis, MN, pp. 113-120.
8.
Apaydin, M.S., Brutlag, D., Guestrin, C., Hsu, D., and Latombe, J.C.2002. Stochastic roadmap simulation: An efficient representation and algorithm for analyzing molecular motion. Proc. 6th Annual Conf. on Research in Computational Molecular Biology (RECOMB'02) , Washington D.C., pp. 12-21.
9.
Aronov, B., De Berg, M., Van der Stappen, A.F., S vestka, P., and Vleugels, J.1999. Motion planning for multiple robots. Discrete and Computational Geometry22:505-525.
10.
Baginski, B.1996. The Z3-method for fast path planning in dynamic environments . Proc. IASTED Conf. Applications of Control and Robotics, Orlando, FL, pp. 47-52.
11.
Baginski, B.1997. Local motion planning for manipulators based on shrinking and growing geometry models. Proc. IEEE Int. Conf. on Robotics and Automation, Minneapolis, MN , pp. 3303-3308.
12.
Baraff, D.1990. Curved surfaces and coherence of non-penetrating rigid body simulation. ACM Computer Graphics24(4):19-28.
13.
Barraquand, J., Kavraki, L.E., Latombe, J.C., Li, T.Y., Motwani, R., and Raghavan, P.1997. A random sampling scheme for path planning. International Journal of Robotics Research16(6):759-774.
14.
Barraquand, J., and Latombe, J.C.1991. Robot motion planning: A distributed representation approach . International Journal of Robotics Research10(6):628-649.
15.
Barraquand, J., Langlois, B., and Latombe, J.C.1992. Numerical potential field techniques for robot path planning . IEEE Tr. on Systems, Man, and Cybernetics22(2):224- 241.
16.
Bohlin, R., and Kavraki, L.E.2000. Path planning using lazy PRM. Proc. IEEE International Conf. Robotics and Automation, San Francisco, CA.
17.
Bonert, M., Shu, L.H., and Benhabib, B.1999. Motion planning for multi-robot assembly systems . Proc. ASME Design Engineering Technical Conf , Las Vegas, NE.
18.
Boor, V., Overmars, M.H., van der Strappen, A.F.1999. The Gaussian sampling strategy for probabilistic roadmap planners. Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, pp. 1018-1023.
19.
Buckley, S.J.1989. Fast motion planning for multiple moving robots . Proc. IEEE Int. Conf. on Robotics and Automation , Scottsdale, AZ, pp. 1419-1424.
20.
Casal, A.2001. Reconfiguration Planning for Modular Self-Reconfigurable Robots. PhD Thesis and Aeronautics & Astronautics Dept., Stanford University, Stanford, CA.
21.
Chang, H., and Li, T.Y.1995. Assemblability maintainability study with motion planning . Proc. IEEE Int. Conf. on Robotics and Automation , pp. 1012-1019.
22.
Choi, M.G., Lee, J., and Shin, S.Y.2000. A Probabilistic Approach to Planning Biped Locomotion with Prescribed Motions. Tech. Rep. CS-TR-2000-162, Computer Science Dept., Korea Advanced Institute of Science & Technology.
23.
Cohen, J., Lin, M., Manocha, D., and Ponamgi, M.1995. I-collide: An interactive and exact collision detection system for large scale environments. Proc. ACM Interactive 3D Graphics Conf, pp. 189-196.
24.
Erdmann, M.A., and Lozano-Perez, T.1987. On multiple moving objects . Algorithmica2(4):477-521.
25.
Faverjon, B.1989. Hierarchical object models for efficient anti-collision algorithms. Proc. IEEE Int. Conf. on Robotics and Automation, Scottsdale, AZ, pp. 333-340.
26.
Frazzoli, E., Dahleh, M.A., and Feron, E.2000. Real-time motion planning for agile autonomous vehicles . Proc. 2000 AIAA Conf. on Guidance, Navigation and Control, Paper AIAA 2000-4056, Denver, CO.
27.
Gottschalk, S., Lin, M., and Manocha, D.1996. OBB-tree: A hierarchical structure for rapid interference detection. Proc. ACM SIGGRAPH'96, pp. 171-180.
28.
Guibas, L., Holleman, C., and Kavraki, L.1999. A probabilistic roadmap planner for flexible objects with a workspace medial-axis based sampling approach. Proc. IEEE International Conf. on Intelligent Robots and Systems.
29.
Han, L., and Amato, N.M.2001. A kinematics-based probabilistic roadmap method for closed chain systems. In Algorithmic and Computational Robotics: New Directions, eds. B. R. Donald , K. M. Lynch, and D. Rus, pp. 233-246. Natick, MA: A. K. Peters.
30.
Hoff III, K.E., Culver, T., Keyser, J., Lin, M., and Manocha, D.2000. Interactive motion planning using hardware-accelerated computation of generalized voronoi diagrams. Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA.
31.
Holleman, C., and Kavraki, L.2000. A framework for using the workspace medial axis in PRM planners, Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, pp. 1408-1413.
32.
Holleman, C., Kavraki, L., and Warren, J.1998. Planning paths for a flexible surface patch. Proc. IEEE Int. Conf. on Robotics and Automation, pp. 21-26.
33.
Horsch, T., Schwarz, F., and Tolle, H.1994. Motion planning for many degrees of freedom-random reflections at Cspace obstacles. Proc. IEEE Int. Conf. on Robotics and Automation, pp. 3318-3323.
34.
Hsu, D.2000. Randomized Single-Query Motion Planning in Expansive Spaces. PhD Thesis, Computer Science Dept., Stanford University , Stanford, CA.
35.
Hsu, D., Kavraki, L., Latombe, J.C., Motwani, R., and Sorkin, S.1998. On finding narrow passages with probabilistic roadmap planners. In Robotics: The Algorithmic Perspective, eds. P. K. Agarwal et al., 151-153. Natick, MA: A. K. Peters.
36.
Hsu, D., Latombe, J.C., and Motwani, R.1997, 1999. Path planning in expansive configuration spaces. Proc. IEEE Int. Conf. Robotics and Automation, pp. 2719-2726. A revised version of this paper can be found in Int. J. of Computational Geometry and Applications9(4-5):495-512.
37.
Hsu, D., Latombe, J.C., Motwani, R., and Kavraki, L.E.1999. Capturing the connectivity of high-dimensional geometric spaces by parallelizable random sampling techniques. In Advances in Randomized Parallel Computing, eds. P. M. Pardalos and S. Rajasekaran, pp. 159-182, Combinatorial Optimization Series, Boston, MA: Kluwer.
38.
Hsu, D., Latombe, J.C., and Sorkin, S.1999. Placing a robot manipulator amid obstacles for optimized execution. Proc. IEEE Int. Symp. on Assembly and Task Planning (ISATP'99), Porto, Portugal, pp. 280-285.
39.
Hwang, Y.K., Xavier, P.G., Chen, P.C., and Wattergerg, P.A.1998. Motion planning with SANDROS and the configuration space toolkit. In Practical Motion Planning in Robotics, eds. K. K. Gupta and A. P. del Pobil, pp. 55-77, John Wiley & Sons.
40.
Hubbard, P.M.1995. Collision Detection for Interactive Graphics Applications . PhD Thesis, Computer Science Dept., Brown University , Providence, RI.
41.
Ji, X., and Xiao, J.2001. Planning motion compliant to complex contact states . Proc. 2001 IEEE Int. Conf. on Robotics and Automation , Seoul, Korea.
42.
Kant, K.G., and Zucker, S.W.1986. Toward efficient trajectory planning: path velocity decomposition . International Journalof Robotics Research5:72-89.
43.
Kavraki, L.E.1994. Random Networks in Configuration Space for Fast Path Planning. PhD Thesis, Computer Science Dept., Stanford University , Stanford, CA.
44.
Kavraki, L.E., Kolountzakis, M., and Latombe, J.C.1998. Analysis of probabilistic roadmaps for path planning . IEEE Tr. on Robotics and Automation14(1):166-171.
45.
Kavraki, L.E., Svestka, P., Latombe, J.C., and Overmars, M.H.1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Tr. on Robotics and Automation12(4):566-580.
46.
Kindel, R.2001. Motion Planning for Free-Flying Robots in Dynamic and Uncertain Environments. PhD Thesis, Aeronautics & Astronautics Dept ., Stanford University, Stanford, CA.
47.
Kindel, R., Hsu, D., Latombe, J.C., Rock, S.2000. Kinodynamic motion planning amidst moving obstacles . Proc. IEEE Int. Conf. on Robotics and Automation , San Francisco, CA, pp. 537-543.
48.
Klosowski, J., Held, M., Mitchell, J.S.B., Sowizral, H., and Zikan, K.1998. Efficient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. On Visualization and Computer Graphics4(1): 21-37.
49.
Koga, Y., Kondo, K., Kuffner, J., and Latombe, J.C.1994. Planning motions with intentions. Proc. SIGGRAPH'94, pp. 395-408.
50.
Koga, Y., and Latombe, J.C.1994. On multi-arm manipulation planning. Proc. IEEE Int. Conf on Robotics and Automation, San Diego, CA, pp. 945-952.
51.
Krishnan, S., Pattekar, A., Lin, M., and Manocha, D.1998. Spherical shell: A higher order bounding volume for fast proximity queries. In Robotics: The Algorithmic Perspective , eds. P. K. Agarwal et al., pp. 177-190. Natick, MA: A. K. Peters.
52.
Kuffner, J.J. Jr.1999. Autonomous Agents for Real-Time Animation. PhD Thesis , Computer Science Dept., Stanford University, Stanford, CA.
53.
Kuffner, J.J., Nishiwaki, K., Kagami, S., Inaba, M., and Inoue, H.2001. Motion planning for humanoid robots under obstacle and dynamic balance constraints. Proc. IEEE 2001 Int. Conf. on Robotics and Automation, Seoul, Korea.
54.
Ladd, A., and Kavraki, L.E.2002. A Measure Theoretic Analysis of PRM. Manuscript.
55.
Lamiraux, F., and Kavraki, L.E.2001. Planning paths for elastic objects under manipulation constraints, International Journal of Robotics Research20(3):188-208.
Laumond, J.P., and Siméon, T.2001. Notes on visibility roadmaps and path planning . In Algorithmic and Computational Robotics: New Directions , eds. B. R. Donald, K. M. Lynch, and D. Rus, pp. 317-328. Natick, MA: A. K. Peters.
58.
LaValle, S.M., and Kuffner, J.J.1999. Randomized kinodynamic planning. Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, pp. 473-479.
59.
LaValle, S.M., and Kuffner, J.J.2001. Randomized kinodynamic planning. International Journal of Robotics Research20(5):278-300.
60.
LaValle, S.M., Yakey, J., and Kavraki, L.1999. A probabilistic roadmap approach for systems with closed kinematic chains. Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, pp. 151-156.
61.
Leroy, S., Laumond, J.P., and Siméon, T.1999. Multiple path coordination for mobile robots: A geometric algorithm. Proc. 16th Int. Joint Conf. on Artificial Intelligence, Stockholm, Sweden.
62.
Lin, M.C.2000. Fast and accurate collision detection for virtual environments . Proc. IEEE Scientific Visualization Conf.
63.
Lin, M.C., and Canny, J.1991. A fast algorithm for incremental distance calculation . Proc. IEEE Int. Conf. on Robotics and Automation , pp. 1008-1014.
64.
Mirtich, B.1998. V-clip: Fast and robust polyhedral collision detection . ACM Tr. on Graphics17(3):177-208.
65.
Nielsen, C., and Kavraki, L.2000. A two-level fuzzy PRM for manipulation planning . Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems.
66.
Nissoud, C., Simeon, T., and Laumond, J.P.1999. Visibility based probabilistic roadmaps. Proc. IEEE Int. Conf. on Intelligent Robors and Systems, Detroit, MI, pp. 1316-1321.
67.
O'Donnell, P.A., and Lozano-Perez, T.1989. Deadlock-free and collision-free coordination of two robot manipulators. Proc. IEEE Int. Conf. Robotics and Automation, pp. 484- 489.
68.
Overmars, M.1992. A Random Approach to Motion Planning. Tech. Rep. RUU-CS-92-32 . Computer Science Dept., TB Utrecht , The Netherlands.
69.
Palmer, L.J., and Grimsdale, R.L.1995. Collision detection for animation using sphere-trees . Computer Graphics Forum14(2):105-116.
70.
del Pobil, A.P., Serna, M.A., and Iovet, J.1992. A new representation for collision avoidance and detection . Proc. IEEE Int. Conf. On Robotics and Automation , pp. 246- 251.
71.
Quinlan, S.1994. Efficient distance computation between non-convex objects . Proc. IEEE Int. Conf. On Robotics and Automation , pp. 3324-3329.
Sánchez-Ante, G., and Latombe, J.C.2001. Single-query bi-directional motion planning with lazy collision checking. Proc. 10th Int. Symp. On Robotics Research, Lorne, Australia.
74.
Sánchez-Ante, G., and Latombe, J.C.2002. Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. Proc. IEEE Int. Conf. on Robotics and Automation, Washington D.C.
75.
Schwartz, J.T., and Sharir, M.1983. In the piano mover's problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. International Journal of Robotics Research2(3):46-75.
76.
Sekhavat, S., S vetska, P., Laumond, J.P., and Overmars , M.1998. Multilevel path planning for nonholonomic robots using semiholonomic subsystems . International Journal of Robotics Research17:840-857.
77.
Simeon, T., Laumond, J.P., and Lamiraux, F.2001. Move3D: A generic platform for motion planning . Proc. IEEE Int. Symp. on Assembly and Task Planning .
78.
Singh, A.P., Latombe, J.C., and Brutlag, D.L.1999. A motion planning approach to flexible ligand binding . Proc. 7th Int. Conf. on Intelligent Systems for Molecular Biology (ISMB) pp. 252-261. Menlo Park, CA: AAAI Press.
79.
Song, G., and Amato, N.M.2001. Using motion planning to study protein folding pathways . Proc. 5th International Conf. on Computational Molecular Biology (RE-COMB'01), pp. 287-296.
80.
Song, G., Miller, S., and Amato, N.2001. Customizing PRM roadmaps at query time. Proc. IEEE Int. Conf. On Robotics and Automation, Seoul, Korea.
81.
Spitz, S.N., and Requicha, A.A.G.2000. Multiple-goals path planning for coordinate measuring machines. Proc. IEEE Int. Conf. On Robotics and Automation, San Francisco, CA.
82.
van der Stappen, A.F., Halperin, D., and Overmars, M.H.1993. The complexity of the free space for a robot moving amidst fat obstacles. Computational Geometry: Theory and Applications3:353-373.
83.
Sundaram, S., Remmler, I., and Amato, N.M.2001. Disassembly sequencing using a motion planning approach . Proc. IEEE Int. Conf. on Robotics and Automation , pp. 1475-1480.
84.
S vetska, P.1997. Robot Motion Planning Using Probabilistic Roadmaps , PhD Thesis, Utrecht University.
85.
S vetska, P., and Overmars, M.1995. Coordinated motion planning for multiple car-like robots using probabilistic roadmaps. Proc. IEEE Int. Conf. Robotics and Automation, Nagoya, Japan, pp. 1631-1636.
86.
Tombropoulos, R.Z., Adler, J.R., and Latombe, J.C.1999. CARABEAMER : A treatment planner for a robotic radio-surgical system with general kinematics. Medical Image Analysis3(3):237-264.
87.
Tournassoud, P.1986. A strategy for obstacle avoidance and its application to multi-robot systems. Proc. IEEE Int. Conf. on Robotics and Automation, San Francisco, CA, pp. 1224-1229.
88.
Vallejo, D., Remmler, I., Amato, N.M.2001. An adaptive framework for "single shot" motion planning: A self-tuning system for rigid and articulated robots. Proc. IEEE Int. Conf. on Robotics and Automation, Seoul , Korea, pp. 21-26.
89.
Warren, C.W.1990. Multiple robot path coordination using artificial potential fields, Proc. IEEE Int. Conf. on Robotics and Automation , Cincinnati, OH, pp. 500-505.
90.
Wilmarth, S.A., Amato, N.M., and Stiller, P.F.1999. MAPRM: A probabilistic roadmap planner with sampling on the medial axis of the free space. Proc. IEEE Int. Conf. on Robotics and Automation, Detroit, MI, pp. 1024-1031.
91.
Wuril, C., Henrich, D., and Worn, H.1999. Multi-goal path planning for industrial robots . Proc. Int. Conf. Robotics and Application, Santa Barbara, CA.
