{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,11]],"date-time":"2026-06-11T16:09:03Z","timestamp":1781194143645,"version":"3.54.1"},"reference-count":91,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>This paper describes the foundations and algorithms of a new probabilistic roadmap (PRM) planner that is: single-query \u2014instead 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 \u2014it explores the robot's free space by building a roadmap made of two trees rooted at the query configurations; and lazy in checking collisions \u2014it 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.<\/jats:p>","DOI":"10.1177\/027836402320556458","type":"journal-article","created":{"date-parts":[[2003,7,19]],"date-time":"2003-07-19T01:53:44Z","timestamp":1058579624000},"page":"5-26","source":"Crossref","is-referenced-by-count":190,"title":["On Delaying Collision Checking in PRM Planning: Application to Multi-Robot Coordination"],"prefix":"10.1177","volume":"21","author":[{"given":"Gildardo","family":"S\u00e1nchez","sequence":"first","affiliation":[{"name":"ITESM Campus Cuernavaca Cuernavaca, M\u00e9xico"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Computer Science Department Stanford University Stanford, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2002,1,1]]},"reference":[{"key":"atypb1","unstructured":"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."},{"key":"atypb2","volume-title":"Le Fil d'Ariane. Une m\u00e9thode de planification g\u00e9n\u00e9rale. Application \u00e0 la planification de trajectoires","author":"Ahuactzin, J.M.","year":"1994"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/70.781970"},{"key":"atypb4","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Alami, R."},{"key":"atypb5","unstructured":"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."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/70.864240"},{"key":"atypb7","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Amato, N.M."},{"key":"atypb8","volume-title":"Proc. 6th Annual Conf. on Research in Computational Molecular Biology (RECOMB'02)","author":"Apaydin, M.S."},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009476"},{"key":"atypb10","volume-title":"Proc. IASTED Conf. Applications of Control and Robotics","author":"Baginski, B."},{"key":"atypb11","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Baginski, B."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/97880.97881"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600604"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1109\/21.148426"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1080\/095119200407660"},{"key":"atypb18","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Boor, V."},{"key":"atypb19","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Buckley, S.J."},{"key":"atypb20","volume-title":"Reconfiguration Planning for Modular Self-Reconfigurable Robots. PhD Thesis and Aeronautics & Astronautics Dept","author":"Casal, A.","year":"2001"},{"key":"atypb21","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Chang, H."},{"key":"atypb22","volume-title":"A Probabilistic Approach to Planning Biped Locomotion with Prescribed Motions","author":"Choi, M.G.","year":"2000"},{"key":"atypb23","volume-title":"Proc. ACM Interactive 3D Graphics Conf","author":"Cohen, J."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840371"},{"key":"atypb25","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Faverjon, B."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.2514\/6.2000-4056"},{"key":"atypb27","first-page":"171","volume":"96","author":"Gottschalk, S.","year":"1996","journal-title":"Proc. ACM SIGGRAPH'"},{"key":"atypb28","volume-title":"Proc. IEEE International Conf. on Intelligent Robots and Systems","author":"Guibas, L."},{"key":"atypb29","unstructured":"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."},{"key":"atypb30","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Hoff III, K.E."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844795"},{"key":"atypb32","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Holleman, C."},{"key":"atypb33","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Horsch, T."},{"key":"atypb34","volume-title":"Randomized Single-Query Motion Planning in Expansive Spaces. PhD Thesis","author":"Hsu, D.","year":"2000"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1201\/9781439863886-18"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.619371"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-3282-4_8"},{"key":"atypb38","volume-title":"Proc. IEEE Int. Symp. on Assembly and Task Planning (ISATP'99)","author":"Hsu, D."},{"key":"atypb39","unstructured":"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."},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.1109\/2945.466717"},{"key":"atypb41","volume-title":"Proc. 2001 IEEE Int. Conf. on Robotics and Automation","author":"Ji, X."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500304"},{"key":"atypb43","volume-title":"Random Networks in Configuration Space for Fast Path Planning. PhD Thesis","author":"Kavraki, L.E.","year":"1994"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb46","volume-title":"Motion Planning for Free-Flying Robots in Dynamic and Uncertain Environments. PhD Thesis, Aeronautics & Astronautics Dept","author":"Kindel, R.","year":"2001"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844109"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1109\/2945.675649"},{"key":"atypb49","first-page":"395","volume":"94","author":"Koga, Y.","year":"1994","journal-title":"Proc. SIGGRAPH'"},{"key":"atypb50","volume-title":"Proc. IEEE Int. Conf on Robotics and Automation","author":"Koga, Y."},{"key":"atypb51","unstructured":"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."},{"key":"atypb52","volume-title":"Autonomous Agents for Real-Time Animation. PhD Thesis","author":"Kuffner, J.J. Jr.","year":"1999"},{"key":"atypb53","volume-title":"Proc. IEEE 2001 Int. Conf. on Robotics and Automation","author":"Kuffner, J.J."},{"key":"atypb54","volume-title":"A Measure Theoretic Analysis of PRM","author":"Ladd, A.","year":"2002"},{"key":"atypb55","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067354"},{"key":"atypb56","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb57","unstructured":"Laumond, J.P., and Sim\u00e9on, 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."},{"key":"atypb58","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"LaValle, S.M."},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"atypb60","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"LaValle, S.M."},{"key":"atypb61","volume-title":"Proc. 16th Int. Joint Conf. on Artificial Intelligence","author":"Leroy, S."},{"key":"atypb62","volume-title":"Proc. IEEE Scientific Visualization Conf","author":"Lin, M.C."},{"key":"atypb63","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Lin, M.C."},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1145\/285857.285860"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2000.895219"},{"key":"atypb66","volume-title":"Proc. IEEE Int. Conf. on Intelligent Robors and Systems","author":"Nissoud, C."},{"key":"atypb67","volume-title":"Proc. IEEE Int. Conf. Robotics and Automation","author":"O'Donnell, P.A."},{"key":"atypb68","volume-title":"A Random Approach to Motion Planning. Tech. Rep. RUU-CS-92-32","author":"Overmars, M.","year":"1992"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.1420105"},{"key":"atypb70","volume-title":"Proc. IEEE Int. Conf. On Robotics and Automation","author":"del Pobil, A.P."},{"key":"atypb71","volume-title":"Proc. IEEE Int. Conf. On Robotics and Automation","author":"Quinlan, S."},{"key":"atypb72","volume-title":"Single-Query Bi-Directional Motion Planning with Lazy Collision Checking, PhD Thesis, ITESM","author":"S\u00e1nchez-Ante, G.","year":"2002"},{"key":"atypb73","volume-title":"Proc. 10th Int. Symp. On Robotics Research","author":"S\u00e1nchez-Ante, G."},{"key":"atypb74","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"S\u00e1nchez-Ante, G."},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1177\/027836498300200304"},{"key":"atypb76","doi-asserted-by":"publisher","DOI":"10.1177\/027836499801700803"},{"key":"atypb77","volume-title":"Proc. IEEE Int. Symp. on Assembly and Task Planning","author":"Simeon, T."},{"key":"atypb78","volume-title":"Proc. 7th Int. Conf. on Intelligent Systems for Molecular Biology (ISMB)","author":"Singh, A.P."},{"key":"atypb79","volume-title":"Proc. 5th International Conf. on Computational Molecular Biology (RE-COMB'01)","author":"Song, G."},{"key":"atypb80","volume-title":"Proc. IEEE Int. Conf. On Robotics and Automation","author":"Song, G."},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.846373"},{"key":"atypb82","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(93)90007-S"},{"key":"atypb83","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Sundaram, S."},{"key":"atypb84","volume-title":"Robot Motion Planning Using Probabilistic Roadmaps","author":"S vetska, P.","year":"1997"},{"key":"atypb85","volume-title":"Proc. IEEE Int. Conf. Robotics and Automation","author":"S vetska, P."},{"key":"atypb86","doi-asserted-by":"publisher","DOI":"10.1016\/S1361-8415(99)80022-X"},{"key":"atypb87","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Tournassoud, P."},{"key":"atypb88","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2000.895220"},{"key":"atypb89","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Warren, C.W."},{"key":"atypb90","volume-title":"Proc. IEEE Int. Conf. on Robotics and Automation","author":"Wilmarth, S.A."},{"key":"atypb91","volume-title":"Proc. Int. Conf. Robotics and Application","author":"Wuril, C."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836402320556458","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836402320556458","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:39Z","timestamp":1777457799000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836402320556458"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":91,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1177\/027836402320556458"],"URL":"https:\/\/doi.org\/10.1177\/027836402320556458","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}