{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T21:54:58Z","timestamp":1786139698751,"version":"3.56.0"},"reference-count":55,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2016,1,28]],"date-time":"2016-01-28T00:00:00Z","timestamp":1453939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2016,6]]},"abstract":"<jats:p>Collision checking is considered to be the most expensive computational bottleneck in sampling-based motion planning algorithms. We introduce a simple procedure that theoretically eliminates this bottleneck and significantly reduces collision-checking time in practice in several test scenarios. Whenever a point is collision checked in the normal (expensive) way, we store a lower bound on that point\u2019s distance to the nearest obstacle. The latter is called a \u201csafety certificate\u201d and defines a region of the search space that is guaranteed to be collision-free. New points may forgo collision checking whenever they are located within a safety certificate of an old point. Testing the latter condition is accomplished during the nearest-neighbor search that is already part of most sampling-based motion planning algorithms. As more and more points are sampled, safety certificates asymptotically cover the search space and the amortized complexity of (normal, expensive) collision checking becomes negligible with respect to the overall runtime of sampling-based motion planning algorithms. Indeed, the expected fraction of points requiring a normal collision check approaches zero, in the limit, as the total number of points approaches infinity. A number of extensions to the basic idea are presented. Experiments with a number of proof-of-concept implementations demonstrate that using safety certificates can improve the performance of sampling-based motion planning algorithms in practice.<\/jats:p>","DOI":"10.1177\/0278364915625345","type":"journal-article","created":{"date-parts":[[2016,1,28]],"date-time":"2016-01-28T22:44:09Z","timestamp":1454021049000},"page":"767-796","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":46,"title":["Efficient collision checking in sampling-based motion planning via safety certificates"],"prefix":"10.1177","volume":"35","author":[{"given":"Joshua","family":"Bialkowski","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Otte","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sertac","family":"Karaman","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emilio","family":"Frazzoli","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2016,1,28]]},"reference":[{"key":"bibr1-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"bibr2-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"bibr3-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/304893.305004"},{"key":"bibr4-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"bibr5-0278364915625345","author":"Bialkowski J","year":"2013","journal-title":"Optimizations for sampling-based motion planning algorithms"},{"key":"bibr6-0278364915625345","unstructured":"Bialkowski J, Otte M, Frazzoli E (2013a) Fast collision checking: from single robots to multi-robot teams. (Technical Report). http:\/\/arxiv.org\/abs\/1305.2299."},{"key":"bibr7-0278364915625345","volume-title":"IEEE international conference on robotics and automation: crossing the reality gap \u2013 from single to multi- to many robot systems","author":"Bialkowski J","year":"2013"},{"key":"bibr8-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696513"},{"key":"bibr9-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36279-8_22"},{"key":"bibr10-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr11-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.772447"},{"key":"bibr12-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932817"},{"key":"bibr13-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1986.4767773"},{"key":"bibr14-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_7"},{"key":"bibr15-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/56.2083"},{"key":"bibr16-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/1198555.1198788"},{"key":"bibr17-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2006.29"},{"key":"bibr18-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/971697.602266"},{"key":"bibr19-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00003-7"},{"key":"bibr20-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-050753-8.50089-9"},{"key":"bibr21-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.88"},{"key":"bibr22-0278364915625345","first-page":"141","volume-title":"Robotics: The Algorithmic Perspective (WAFR \u201998)","author":"Hsu D","year":"1998"},{"key":"bibr23-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-8493(00)00130-8"},{"key":"bibr24-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr25-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_32"},{"key":"bibr26-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2005.00861.x"},{"key":"bibr27-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr28-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781612"},{"key":"bibr29-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336219"},{"key":"bibr30-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01377.x"},{"key":"bibr31-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01611.x"},{"key":"bibr32-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr33-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr34-0278364915625345","author":"Lin M","year":"1993","journal-title":"Efficient collision detection for animation and robotics"},{"key":"bibr35-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1007\/BF02716580"},{"key":"bibr36-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/285857.285860"},{"key":"bibr37-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594679."},{"key":"bibr38-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"bibr39-0278364915625345","first-page":"211","volume-title":"Algorithmic Foundations of Robotics IX, Springer Tracts in Advanced Robotics","volume":"68","author":"Pan J","year":"2011"},{"key":"bibr40-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911429335"},{"key":"bibr41-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/2945.582346"},{"key":"bibr42-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.845313"},{"key":"bibr43-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1111\/1467-8659.t01-1-00587"},{"key":"bibr44-0278364915625345","first-page":"145","volume-title":"Proceedings of the ninth ACM symposium on solid modeling and applications","author":"Redon S","year":"2004"},{"key":"bibr45-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1115\/1.1884133"},{"key":"bibr46-0278364915625345","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet H","year":"2006"},{"key":"bibr47-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45058-0_3"},{"key":"bibr48-0278364915625345","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920994"},{"key":"bibr49-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2010.01.001"},{"key":"bibr50-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.1991.174431"},{"key":"bibr51-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844110"},{"key":"bibr52-0278364915625345","first-page":"254","volume-title":"Proceedings of the international conference on robotics and automation","author":"Yang L","year":"2002"},{"key":"bibr53-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824640"},{"key":"bibr54-0278364915625345","first-page":"4405","volume-title":"Proceedings of the international conference on robotics and automation","author":"Yang Y","year":"2013"},{"key":"bibr55-0278364915625345","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276396"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915625345","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915625345","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915625345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:21Z","timestamp":1777457721000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915625345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1,28]]},"references-count":55,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["10.1177\/0278364915625345"],"URL":"https:\/\/doi.org\/10.1177\/0278364915625345","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1,28]]}}}