{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T22:50:17Z","timestamp":1780095017812,"version":"3.54.0"},"reference-count":51,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"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":[[2006,7]]},"abstract":"<jats:p>Why is probabilistic roadmap (PRM) planning probabilistic? How does the probability measure used for sampling a robot\u2019s configuration space affect the performance of a PRM planner? These questions have received little attention to date. This paper tries to fill this gap and identify promising directions to improve future planners. It introduces the probabilistic foundations of PRM planning and examines previous work in this context. It shows that the success of PRM planning depends mainly and critically on favorable \u201cvisibility\u201d properties of a robot\u2019s configuration space. A promising direction for speeding up PRM planners is to infer partial knowledge of such properties from both workspace geometry and information gathered during roadmap construction, and to use this knowledge to adapt the probability measure for sampling. This paper also shows that the choice of the sampling source\u2014pseudo-random or deterministic\u2014has small impact on a PRM planner\u2019s performance, compared with that of the sampling measure. These conclusions are supported by both theoretical and empirical results.<\/jats:p>","DOI":"10.1177\/0278364906067174","type":"journal-article","created":{"date-parts":[[2006,6,20]],"date-time":"2006-06-20T07:01:21Z","timestamp":1150786881000},"page":"627-643","source":"Crossref","is-referenced-by-count":188,"title":["On the Probabilistic Foundations of Probabilistic Roadmap Planning"],"prefix":"10.1177","volume":"25","author":[{"given":"David","family":"Hsu","sequence":"first","affiliation":[{"name":"Department of Computer Science, National University of Singapore,                         Singapore, 117543,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stanford University, Stanford, CA 94305,                         USA,"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hanna","family":"Kurniawati","sequence":"additional","affiliation":[{"name":"Department of Computer Science, National University of Singapore,                         Singapore, 117543,"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2006,7,1]]},"reference":[{"key":"atypb1","first-page":"80","volume-title":"Algorithmic Foundations of Robotics VI","author":"Akinc, M.","year":"2004"},{"key":"atypb2","first-page":"155","volume-title":"Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics","author":"Amato, N. M."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"atypb4","first-page":"1018","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Boor, V."},{"key":"atypb5","volume-title":"Introduction to Protein Structure","author":"Branden, C.-I.","year":"1999"},{"key":"atypb6","volume-title":"Proceedings of Robotics: Science and Systems I","author":"Burns, B."},{"key":"atypb7","first-page":"246","volume-title":"Proceedings of SPIE Symposium on Intelligent Systems and Advanced Manufacturing","author":"Casal, A."},{"key":"atypb8","volume-title":"Smoothed analysis of probabilistic roadmaps","author":"Chaudhuri, S.","year":"2006"},{"key":"atypb9","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Cheng, H.-L."},{"key":"atypb10","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset, H.","year":"2005"},{"key":"atypb11","first-page":"55","volume-title":"Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Foskey, M."},{"key":"atypb12","first-page":"43","volume-title":"Algorithmic Foundations of Robotics V","author":"Geraerts, R.","year":"2002"},{"key":"atypb13","first-page":"531","volume-title":"IEEE International Confernece on Methods and Models in Automation and Robotics","author":"Geraerts, R."},{"key":"atypb14","first-page":"406","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Geraerts, R."},{"key":"atypb15","first-page":"254","volume-title":"Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Guibas, L."},{"key":"atypb16","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Hauser, K."},{"key":"atypb17","first-page":"239","volume-title":"Algorithmic Foundations of Robotics V","author":"Hirsch, S.","year":"2002"},{"key":"atypb18","first-page":"2931","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Hoff, K. E., III"},{"key":"atypb19","first-page":"4420","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb20","first-page":"141","volume-title":"Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics","author":"Hsu, D."},{"key":"atypb21","first-page":"2719","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb22","first-page":"3885","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1201\/9781420035315.ch39"},{"key":"atypb24","first-page":"2323","volume-title":"Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Isto, P."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"atypb26","first-page":"353","volume-title":"Proceedings of ACM Symposium on Theory of Computing","author":"Kavraki, L. E."},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"atypb29","volume-title":"Art of Computer Programming, Volume 2: Seminumerical Algorithms","author":"Knuth, D. VE.","year":"1997","edition":"3"},{"key":"atypb30","first-page":"375","volume-title":"Robotics: The Algorithmic Perspective: 1998 Workshop on the Algorithmic Foundations of Robotics","author":"Kotay, K."},{"key":"atypb31","first-page":"1618","volume-title":"Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Kurniawati, H."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"atypb34","first-page":"473","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"LaValle, S. M."},{"key":"atypb35","first-page":"2134","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Leven, P."},{"key":"atypb36","volume-title":"Handbook of Discrete and Computational Geometry","author":"Lin, M.","year":"2004"},{"key":"atypb37","first-page":"2920","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Lindemann, S. R."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03942-3"},{"key":"atypb39","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Morales A., M. A."},{"key":"atypb40","first-page":"361","volume-title":"Algorithmic Foundations of Robotics VI","author":"Morales A., M. A.","year":"2004"},{"issue":"2","key":"atypb41","first-page":"53","volume":"8","author":"Moro, B.","year":"1995","journal-title":"Risk"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970081"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1109\/70.611311"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-005-4748-1"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1163\/156855300741960"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"atypb48","volume-title":"On probabilistic completeness and expected complexity for probabilistic path planning","author":"\u0160vestka, P.","year":"1996"},{"key":"atypb49","doi-asserted-by":"publisher","DOI":"10.1177\/0278364905060132"},{"key":"atypb50","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Yang, Y."},{"key":"atypb51","first-page":"632","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Yershova, A."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906067174","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906067174","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:48Z","timestamp":1777457748000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906067174"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":51,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1177\/0278364906067174"],"URL":"https:\/\/doi.org\/10.1177\/0278364906067174","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]}}}