This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Sánchez, G. Articles by Latombe, J.-C. Search for Related Content Social Bookmarking                         What's this?

On Delaying Collision Checking in PRM Planning: Application to Multi-Robot Coordination

ITESM Campus Cuernavaca Cuernavaca, México gsanchez{at}campus.gda.itesm.mx

Jean-Claude Latombe

Computer Science Department Stanford University Stanford, CA, USA latombe{at}cs.stanford.edu

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.

Key Words: motion planning • probabilistic roadmaps • lazy collision checking • multi-robot coordination

The International Journal of Robotics Research, Vol. 21, No. 1, 5-26 (2002)
DOI: 10.1177/027836402320556458


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This article has been cited by other articles:

				L. Jaillet and T. Simeon Path Deformation Roadmaps: Compact Graphs with Useful Cycles for Motion Planning The International Journal of Robotics Research, November 1, 2008; 27(11-12): 1175 - 1188. [Abstract] [PDF]

				K. Hauser, T. Bretl, J.-C. Latombe, K. Harada, and B. Wilcox Motion Planning for Legged Robots on Varied Terrain The International Journal of Robotics Research, November 1, 2008; 27(11-12): 1325 - 1349. [Abstract] [PDF]

				R. Geraerts and M. H. Overmars Creating High-quality Paths for Motion Planning The International Journal of Robotics Research, August 1, 2007; 26(8): 845 - 863. [Abstract] [PDF]

				D. Hsu, J.-C. Latombe, and H. Kurniawati On the Probabilistic Foundations of Probabilistic Roadmap Planning The International Journal of Robotics Research, July 1, 2006; 25(7): 627 - 643. [Abstract] [PDF]

				T. Bretl Motion Planning of Multi-Limbed Robots Subject to Equilibrium Constraints: The Free-Climbing Robot Problem The International Journal of Robotics Research, April 1, 2006; 25(4): 317 - 342. [Abstract] [PDF]

				M. Saha, T. Roughgarden, J.-C. Latombe, and G. Sanchez-Ante Planning Tours of Robotic Arms among Partitioned Goals The International Journal of Robotics Research, March 1, 2006; 25(3): 207 - 223. [Abstract] [PDF]

				E. J. Griffith and S. Akella Coordinating Multiple Droplets in Planar Array Digital Microfluidic Systems The International Journal of Robotics Research, November 1, 2005; 24(11): 933 - 949. [Abstract] [PDF]

				J. Peng and S. Akella Coordinating Multiple Robots with Kinodynamic Constraints Along Specified Paths The International Journal of Robotics Research, April 1, 2005; 24(4): 295 - 310. [Abstract] [PDF]

				D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock Randomized Kinodynamic Motion Planning with Moving Obstacles The International Journal of Robotics Research, March 1, 2002; 21(3): 233 - 255. [Abstract] [PDF]