{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T13:54:14Z","timestamp":1769176454689,"version":"3.49.0"},"reference-count":54,"publisher":"SAGE Publications","issue":"2-3","license":[{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100010690","name":"toyota physical and chemical research institute","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100010690","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["825\/15"],"award-info":[{"award-number":["825\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Blavatnik Computer Science Research Fund","award":["Blavatnik Computer Science Research Fund"],"award-info":[{"award-number":["Blavatnik Computer Science Research Fund"]}]},{"name":"Fulbright United States-Israel Educational Foundation"},{"name":"Blavatnik Interdisciplinary Cyber Research Center at Tel Aviv University"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:p> We develop a new analysis of sampling-based motion planning in Euclidean space with uniform random sampling, which significantly improves upon the celebrated result of Karaman and Frazzoli and subsequent work. In particular, we prove the existence of a critical connection radius proportional to [Formula: see text] for n samples and d dimensions: below this value the planner is guaranteed to fail (similarly shown by Karaman and Frazzoli). More importantly, for larger radius values the planner is asymptotically (near-)optimal. Furthermore, our analysis yields an explicit lower bound of [Formula: see text] on the probability of success. A practical implication of our work is that asymptotic (near-)optimality is achieved when each sample is connected to only [Formula: see text] neighbors. This is in stark contrast to previous work that requires [Formula: see text] connections, which are induced by a radius of order [Formula: see text]. Our analysis applies to the probabilistic roadmap method (PRM), as well as a variety of \u201cPRM-based\u201d planners, including RRG, FMT*, and BTT. Continuum percolation plays an important role in our proofs. Lastly, we develop similar theory for all the aforementioned planners when constructed with deterministic samples, which are then sparsified in a randomized fashion. We believe that this new model, and its analysis, is interesting in its own right. <\/jats:p>","DOI":"10.1177\/0278364919859627","type":"journal-article","created":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T09:07:18Z","timestamp":1561972038000},"page":"266-285","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":21,"title":["The critical radius in sampling-based motion planning"],"prefix":"10.1177","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0254-0572","authenticated-orcid":false,"given":"Kiril","family":"Solovey","sequence":"first","affiliation":[{"name":"Department of Aeronautics and Astronautics, Stanford University, Stanford, CA, USA"}]},{"given":"Michal","family":"Kleinbort","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv University, Israel"}]}],"member":"179","published-online":{"date-parts":[[2019,7,1]]},"reference":[{"key":"bibr1-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2015.2470096"},{"key":"bibr2-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980286"},{"key":"bibr3-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1039639377"},{"key":"bibr4-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"bibr5-0278364919859627","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2017.XIII.020"},{"key":"bibr6-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139167383"},{"key":"bibr7-0278364919859627","volume-title":"The complexity of robot motion planning","author":"Canny J","year":"1988"},{"key":"bibr8-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913498292"},{"key":"bibr9-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139775"},{"key":"bibr10-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511619632"},{"key":"bibr11-0278364919859627","first-page":"1","volume-title":"Encyclopedia of Systems and Control","author":"Frazzoli E","year":"2013"},{"key":"bibr12-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9710-y"},{"key":"bibr13-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"bibr14-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.67.036101"},{"key":"bibr15-0278364919859627","volume":"321","author":"Grimmett GR","year":"1999","journal-title":"Percolation (Comprehesive Studies in Mathematics"},{"key":"bibr16-0278364919859627","volume-title":"Handbook of Discrete and Computational Geometry","author":"Halperin D","year":"2016","edition":"3"},{"key":"bibr17-0278364919859627","volume-title":"Handbook of Discrete and Computational Geometry","author":"Halperin D","year":"2016","edition":"3"},{"key":"bibr18-0278364919859627","author":"Holladay RM","year":"2017","journal-title":"CoRR"},{"issue":"4","key":"bibr19-0278364919859627","volume":"9","author":"Hsu D","year":"1999","journal-title":"International Journal of Computational Geometry and Applications"},{"key":"bibr20-0278364919859627","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2018.XIV.061"},{"key":"bibr21-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917714338"},{"key":"bibr22-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"bibr23-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr24-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"bibr25-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr26-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918802957"},{"key":"bibr27-0278364919859627","volume-title":"International Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Kleinbort M","year":"2016"},{"key":"bibr28-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"bibr29-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr30-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915614386"},{"key":"bibr31-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004978"},{"issue":"2","key":"bibr32-0278364919859627","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1109\/LRA.2018.2888628","volume":"4","author":"Michal K","year":"2019","journal-title":"(IEEE) Robotics and Automation Letters"},{"key":"bibr33-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_17"},{"key":"bibr34-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"bibr35-0278364919859627","doi-asserted-by":"publisher","DOI":"10.2307\/1427912"},{"key":"bibr36-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.10"},{"key":"bibr37-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139773"},{"key":"bibr38-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2539377"},{"key":"bibr39-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914556517"},{"key":"bibr40-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2015.7402604"},{"key":"bibr41-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139514"},{"key":"bibr42-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-019-09832-9"},{"key":"bibr43-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364916672311"},{"key":"bibr44-0278364919859627","first-page":"76:1","volume-title":"European Symposium on Algorithms","author":"Solovey K","year":"2016"},{"key":"bibr45-0278364919859627","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Solovey K","year":"2017"},{"key":"bibr46-0278364919859627","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2018.XIV.017"},{"key":"bibr47-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915615688"},{"key":"bibr48-0278364919859627","author":"Solovey K","year":"2015","journal-title":"Robotics: Science and Systems"},{"key":"bibr49-0278364919859627","first-page":"2072","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Starek JA","year":"2015"},{"key":"bibr50-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/AERO.2016.7500704"},{"key":"bibr51-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"bibr52-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1063\/1.4742750"},{"key":"bibr53-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.001"},{"key":"bibr54-0278364919859627","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.87.052107"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364919859627","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364919859627","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364919859627","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T23:59:29Z","timestamp":1740873569000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364919859627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,1]]},"references-count":54,"journal-issue":{"issue":"2-3","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["10.1177\/0278364919859627"],"URL":"https:\/\/doi.org\/10.1177\/0278364919859627","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,1]]}}}