{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T09:52:10Z","timestamp":1777715530070,"version":"3.51.4"},"reference-count":47,"publisher":"SAGE Publications","issue":"6","license":[{"start":{"date-parts":[[1997,12,1]],"date-time":"1997-12-01T00:00:00Z","timestamp":880934400000},"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":[[1997,12]]},"abstract":"<jats:p>Several randomized path planners have been proposed dur ing the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empir ically observed success. In this article, we attempt to present a unifying view of these planners and to theoretically explain their success. First, we introduce a general planning scheme that consists of randomly sampling the robot 's configuration space. We then describe two previously developed planners as instances of planners based on this scheme, but applying very different sampling strategies. These planners are probabilis tically complete: if a path exists, they will find one with high probability, if we let them run long enough. Next, for one of the planners, we analyze the relation between the probability of failure and the running time. Under assumptions characteriz ing the \"goodness\" of the robot's free space, we show that the<\/jats:p>","DOI":"10.1177\/027836499701600604","type":"journal-article","created":{"date-parts":[[2007,3,4]],"date-time":"2007-03-04T20:24:06Z","timestamp":1173039846000},"page":"759-774","source":"Crossref","is-referenced-by-count":178,"title":["A Random Sampling Scheme for Path Planning"],"prefix":"10.1177","volume":"16","author":[{"given":"J\u00e9r\u00f4me","family":"Barraquand","sequence":"first","affiliation":[{"name":"Salomon Brothers Int. Ltd. Victoria Plaza 111 Buckingham Palace Road London SWIW 0SB, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lydia","family":"Kavraki","sequence":"additional","affiliation":[{"name":"Department of Computer Science Rice University Houston, TX 77005-1892"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jean-Claude","family":"Latombe","sequence":"additional","affiliation":[{"name":"Department of Computer Science Stanford University Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajeev","family":"Motwani","sequence":"additional","affiliation":[{"name":"Department of Computer Science Stanford University Stanford, CA 94305, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsai-Yen","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science National Chengchi University Wenshan, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prabhakar","family":"Raghavan","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center San Jose, CA 95120, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[1997,12,1]]},"reference":[{"key":"atypb1","volume-title":"Le Fil d'Ariane: Une M\u00e9thode de Planification G\u00e9n\u00e9rale. Application \u00e0 la Planification Automatique de Trajectoires. Thesis Dissertation","author":"Ahuactzin, J.M.","year":"1994"},{"key":"atypb2","volume-title":"Proceedings of the ACM Symposium on Computational Geometry","author":"Arya, S."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/21.148426"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1177\/027836499101000604"},{"key":"atypb5","unstructured":"Bessi\u00e8re, P., Mazer, E., and Ahuactzin, J.M. 1995. Planning in a continuous space with forbidden regions: the Ariadne's clew algorithm. In Goldberg, K. et al. (eds.) Algorithmic Foundations of Robotics. Wellesley, MA: A. K. Peters, pp. 39-47."},{"key":"atypb6","volume-title":"The Complexity of Robot Motion Planning","author":"Canny, J.F.","year":"1988"},{"key":"atypb7","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Challou, D."},{"key":"atypb8","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Chang, H."},{"key":"atypb9","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Chen, P.C."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"atypb11","volume-title":"Aerospace Automated Fastening Conference and Exposition","author":"Graux, L."},{"key":"atypb12","unstructured":"Halperin, D., Latombe, J.C., and Motwani, R. 1997. Dynamic maintenance of kinematic structures. In Laumond, J. P., and Overmars, M. (eds.) Algorithmic Foundations of Robotics . Wellesley, MA: A.K. Peters, pp. 155-170."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/0215055"},{"key":"atypb15","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Horsch, T."},{"key":"atypb16","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Hwang, Y.K."},{"key":"atypb17","volume-title":"Proceedings of the First ACM Symposium on Computational Geometry","author":"Joseph, D.A."},{"key":"atypb18","volume-title":"Random networks in configuration space for fast path planning. Technical Report STAN-CS-TR-95-1535","author":"Kavraki, L.","year":"1995"},{"key":"atypb19","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Kavraki, L."},{"key":"atypb20","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Kavraki, L."},{"key":"atypb21","volume-title":"Proceedings of the IEEE Conference on Intelligent Robots and Systems","author":"Kavraki, L."},{"key":"atypb22","volume-title":"Randomized query processing in robot motion planning. Technical Report STAN-CS-TR-94-1533","author":"Kavraki, L.","year":"1994"},{"key":"atypb23","volume-title":"Proceedings of the 27th Annual ACM Symposium on Theory of Computing","author":"Kavraki, L."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb25","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Koditschek, D.E."},{"key":"atypb26","volume-title":"Proceedings of SIGGRAPH'94","author":"Koga, Y."},{"key":"atypb27","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Koga, Y."},{"key":"atypb28","volume-title":"On the expected complexity of random path planning. Technical Report 95087","author":"Lamiraux, F."},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"atypb30","volume-title":"Proceedings of the 36th Annual Symposium on Foundations of Computer Science","author":"Latombe, J.C."},{"key":"atypb31","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Li, T.Y."},{"key":"atypb32","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Lin, M.C."},{"key":"atypb33","volume-title":"Lecture Notes on Evasiveness of Graph Properties. Technical Report CS-TR-317-91","author":"Lov\u00e1sz, L.","year":"1991"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"atypb35","volume-title":"A random approach to motion planning. Technical Report RUU-CS-92-32","author":"Overmars, M.","year":"1992"},{"key":"atypb36","unstructured":"Overmars, M., and \u0160vestka, P. 1995. A probabilistic learning approach to motion planning. In Goldberg, K. et al. (eds.) Algorithmic Foundations of Robotics. Wellesley, MA: A. K. Peters, pp. 19-37."},{"key":"atypb37","volume-title":"Proceedings of the 3rd ACM Symposium on Solid Modeling and Applications","author":"Ponamgi, M."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"atypb39","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Quinlan, S."},{"key":"atypb40","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science","author":"Reif, J."},{"key":"atypb41","volume-title":"Proceedings of the 25th IEEE Symposium on Foundations of Computer Science","author":"Reif, J."},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"atypb43","volume-title":"Probabilistic path planning for tractor-trailer robots. Technical Report 96007","author":"Sekhavat, S.","year":"1995"},{"key":"atypb44","volume-title":"A probabilistic approach to motion planning for car-like robots. Technical Report RUU-CS-93-18","author":"\u0160vestka, P.","year":"1993"},{"key":"atypb45","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Thomas, F."},{"key":"atypb46","volume-title":"Proceedings of SIGGRAPH'95","author":"Veach, E."},{"key":"atypb47","volume-title":"On local minima and random search in robot motion planning. Technical Report. Vancouver, Canada","author":"Zhu, X.","year":"1993"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499701600604","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499701600604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:25Z","timestamp":1777457725000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499701600604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,12]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1997,12]]}},"alternative-id":["10.1177\/027836499701600604"],"URL":"https:\/\/doi.org\/10.1177\/027836499701600604","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,12]]}}}