{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T16:02:10Z","timestamp":1784131330938,"version":"3.55.0"},"reference-count":83,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T00:00:00Z","timestamp":1454457600000},"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,4]]},"abstract":"<jats:p>Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, STABLE_SPARSE_RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.<\/jats:p>","DOI":"10.1177\/0278364915614386","type":"journal-article","created":{"date-parts":[[2016,2,3]],"date-time":"2016-02-03T22:10:20Z","timestamp":1454537420000},"page":"528-564","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":219,"title":["Asymptotically optimal sampling-based kinodynamic planning"],"prefix":"10.1177","volume":"35","author":[{"given":"Yanbo","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zakary","family":"Littlefield","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kostas E.","family":"Bekris","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2016,2,3]]},"reference":[{"key":"bibr1-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ISMA.2013.6547379"},{"key":"bibr2-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980286"},{"key":"bibr3-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"bibr4-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891837"},{"key":"bibr5-0278364915614386","volume-title":"First International Symposium on Search Techniques in Artificial Intelligence and Robotics (STAIR)","author":"Bekris K","year":"2008"},{"key":"bibr6-0278364915614386","doi-asserted-by":"publisher","DOI":"10.2514\/2.4231"},{"key":"bibr7-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/027836498500400301"},{"key":"bibr8-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1049\/ip-cta:20050152"},{"key":"bibr9-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5651-9_2"},{"key":"bibr10-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574702"},{"key":"bibr11-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1302404"},{"key":"bibr12-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2001.973334"},{"key":"bibr13-0278364915614386","volume-title":"Principles of Robot Motion","author":"Choset H","year":"2005"},{"key":"bibr14-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BF01450011"},{"key":"bibr15-0278364915614386","unstructured":"Coumans E (2012) Bullet Physics Engine. http:\/\/bulletphysics.org."},{"key":"bibr16-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913498292"},{"key":"bibr17-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696508"},{"key":"bibr18-0278364915614386","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Dobson A","year":"2012"},{"key":"bibr19-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BF01586637"},{"key":"bibr20-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1145\/174147.174150"},{"key":"bibr21-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2006.282100"},{"key":"bibr22-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3176-0_10"},{"key":"bibr23-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1080\/00207179508921959"},{"key":"bibr24-0278364915614386","doi-asserted-by":"publisher","DOI":"10.2514\/2.4856"},{"key":"bibr25-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509718"},{"key":"bibr26-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630907"},{"key":"bibr27-0278364915614386","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and Random Processes","author":"Grimmett G","year":"2001","edition":"3"},{"key":"bibr28-0278364915614386","first-page":"150","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Heinzinger G","year":"1989"},{"key":"bibr29-0278364915614386","first-page":"141","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Hsu D","year":"1998"},{"key":"bibr30-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556421"},{"key":"bibr31-0278364915614386","volume-title":"International Symposium of Robotics Research (ISRR)","author":"Janson L","year":"2013"},{"key":"bibr32-0278364915614386","first-page":"188","volume-title":"American Control Conference (ACC)","author":"Jeon JH","year":"2013"},{"key":"bibr33-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2011.6161521"},{"key":"bibr34-0278364915614386","author":"Karaman S","year":"2010","journal-title":"Robotics: Science and Systems (RSS)"},{"key":"bibr35-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr36-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631297"},{"key":"bibr37-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980479"},{"key":"bibr38-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"bibr39-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr40-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr41-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907230"},{"key":"bibr42-0278364915614386","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Kunz T","year":"2014"},{"key":"bibr43-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"bibr44-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/10991541_21"},{"key":"bibr45-0278364915614386","first-page":"233","author":"Ladd AM","year":"2005","journal-title":"Robotics: Science and Systems (RSS)"},{"key":"bibr46-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308894"},{"key":"bibr47-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0036069"},{"key":"bibr48-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr49-0278364915614386","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"LaValle S","year":"2001"},{"key":"bibr50-0278364915614386","volume-title":"Optimal Control","author":"Lewis FL","year":"1995"},{"key":"bibr51-0278364915614386","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Li Y","year":"2010"},{"key":"bibr52-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980427"},{"key":"bibr53-0278364915614386","volume-title":"Workshop on Algorithmic Foundations of Robotics (WAFR)","author":"Li Y","year":"2014"},{"key":"bibr54-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/0278364909340445"},{"key":"bibr55-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696590"},{"key":"bibr56-0278364915614386","volume-title":"International Symposium on Robotic Research (ISRR)","author":"Littlefield Z","year":"2015"},{"key":"bibr57-0278364915614386","volume-title":"International Symposium of Robotics Research (ISRR)","author":"Marble JD","year":"2011"},{"key":"bibr58-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2012.2234312"},{"key":"bibr59-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17452-0_17"},{"key":"bibr60-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840370"},{"key":"bibr61-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022066833"},{"key":"bibr62-0278364915614386","volume":"1405","author":"Papadopoulos G","year":"2014","journal-title":"Preprint"},{"key":"bibr63-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696773"},{"key":"bibr64-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1308890"},{"key":"bibr65-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2047820"},{"key":"bibr66-0278364915614386","volume-title":"International Symposium of Robotics Research (ISRR)","author":"Richter C","year":"2013"},{"key":"bibr67-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1985.1087233"},{"key":"bibr68-0278364915614386","first-page":"403","volume-title":"International Symposium of Robotics Research (ISRR)","author":"Sanchez G","year":"2001"},{"key":"bibr69-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914528132"},{"key":"bibr70-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631155"},{"key":"bibr71-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1988.12076"},{"key":"bibr72-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/70.105387"},{"key":"bibr73-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2009.5152874"},{"key":"bibr74-0278364915614386","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/BFb0015081","volume-title":"Control problems in robotics and automation","volume":"230","author":"Spong MW","year":"1997"},{"key":"bibr75-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2013.6760219"},{"key":"bibr76-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2160466"},{"key":"bibr77-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1137\/0325011"},{"key":"bibr78-0278364915614386","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.003"},{"key":"bibr79-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1248805"},{"key":"bibr80-0278364915614386","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","author":"Wang W","year":"2013"},{"key":"bibr81-0278364915614386","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Webb D","year":"2013"},{"key":"bibr82-0278364915614386","volume-title":"IEEE International Conference on Robotics and Automation (ICRA)","author":"Zucker M","year":"2007"},{"key":"bibr83-0278364915614386","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913488805"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915614386","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364915614386","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364915614386","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:19Z","timestamp":1777457719000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364915614386"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,3]]},"references-count":83,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["10.1177\/0278364915614386"],"URL":"https:\/\/doi.org\/10.1177\/0278364915614386","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,3]]}}}