{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T18:50:27Z","timestamp":1735584627121},"reference-count":62,"publisher":"SAGE Publications","issue":"5","license":[{"start":{"date-parts":[[2021,1,27]],"date-time":"2021-01-27T00:00:00Z","timestamp":1611705600000},"content-version":"vor","delay-in-days":366,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/501100003400","name":"Ministry of Research and Innovation","doi-asserted-by":"publisher","award":["Early Researcher Award Program"],"id":[{"id":"10.13039\/501100003400","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["NSERC Canadian Field Robotics Network (NCFRN)"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["Young Investigator Program"],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2020,4]]},"abstract":" Path planning in robotics often requires finding high-quality solutions to continuously valued and\/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as used by informed graph-based searches and anytime sampling-based planners, respectively. <\/jats:p> Informed graph-based searches, such as A*<\/jats:sup>, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient, but leaves their performance dependent on the chosen approximation. If the resolution of the chosen approximation is too low, then they may not find a (suitable) solution, but if it is too high, then they may take a prohibitively long time to do so. <\/jats:p> Anytime sampling-based planners, such as RRT*<\/jats:sup>, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found, but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously, but may be prohibitively inefficient at containing a solution. <\/jats:p> This article unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT*<\/jats:sup> solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*<\/jats:sup>, and its approximation improves indefinitely with additional computational time, as in RRT*<\/jats:sup>. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems. <\/jats:p>","DOI":"10.1177\/0278364919890396","type":"journal-article","created":{"date-parts":[[2020,1,27]],"date-time":"2020-01-27T13:11:52Z","timestamp":1580130712000},"page":"543-567","update-policy":"http:\/\/dx.doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":96,"title":["Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search"],"prefix":"10.1177","volume":"39","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-1034-3889","authenticated-orcid":false,"given":"Jonathan D","family":"Gammell","sequence":"first","affiliation":[{"name":"University of Oxford, Oxford, UK"}]},{"given":"Timothy D","family":"Barfoot","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Siddhartha S","family":"Srinivasa","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]}],"member":"179","published-online":{"date-parts":[[2020,1,27]]},"reference":[{"key":"bibr1-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.01.009"},{"key":"bibr2-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594029"},{"key":"bibr3-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095077"},{"key":"bibr4-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"bibr5-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139869"},{"key":"bibr6-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799034"},{"key":"bibr7-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1954-09848-8"},{"volume-title":"Dynamic Programming","year":"1957","author":"Bellman RE","key":"bibr8-0278364919890396"},{"key":"bibr9-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1975.1100984"},{"key":"bibr10-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr11-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932820"},{"key":"bibr12-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487615"},{"key":"bibr13-0278364919890396","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2014.X.033"},{"key":"bibr14-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2007.4399557"},{"key":"bibr15-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"bibr16-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009293"},{"key":"bibr17-0278364919890396","first-page":"36","volume":"5","author":"Euler L","year":"1738","journal-title":"Commentarii academiae scientiarum Petropolitanae"},{"key":"bibr18-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2006.282100"},{"volume-title":"Informed Anytime Search for Continuous Planning Problems","year":"2017","author":"Gammell JD","key":"bibr19-0278364919890396"},{"key":"bibr20-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2830331"},{"key":"bibr21-0278364919890396","unstructured":"Gammell JD, Srinivasa SS, Barfoot TD (2014a) BIT*: Batch informed trees for optimal sampling-based planning via dynamic programming on implicit random geometric graphs. Technical Report TR-2014-JDG006, Autonomous Space Robotics Lab, University of Toronto."},{"volume-title":"The Information-based Grasp and Manipulation Planning Workshop, Robotics: Science and Systems (RSS)","year":"2014","author":"Gammell JD","key":"bibr22-0278364919890396"},{"key":"bibr23-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942976"},{"key":"bibr24-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"bibr25-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1137\/0109045"},{"key":"bibr26-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"bibr27-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139603"},{"key":"bibr28-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1705"},{"key":"bibr29-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000285"},{"key":"bibr30-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917714338"},{"volume-title":"Proceedings of the International Symposium on Robotics Research (ISRR)","year":"2013","author":"Janson L","key":"bibr31-0278364919890396"},{"key":"bibr32-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"bibr33-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr34-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980479"},{"key":"bibr35-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"bibr36-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"volume-title":"Proceedings of the Fifth Annual Symposium on Combinatorial Search (SoCS)","year":"2012","author":"Kiesel S","key":"bibr37-0278364919890396"},{"key":"bibr38-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139608"},{"volume-title":"Proceedings of the International Workshop on the Algorithmic Foundations of Robotics (WAFR)","year":"2016","author":"Kleinbort M","key":"bibr39-0278364919890396"},{"key":"bibr40-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2003.12.001"},{"key":"bibr41-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr42-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487120"},{"key":"bibr43-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr44-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.11.009"},{"key":"bibr45-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"bibr46-0278364919890396","first-page":"989","volume-title":"Proceedings of the Sixteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms","author":"Muthukrishnan S","year":"2005"},{"volume-title":"International Workshop on the Algorithmic Foundations of Robotics (WAFR)","year":"2014","author":"Otte M","key":"bibr47-0278364919890396"},{"key":"bibr48-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594679"},{"key":"bibr49-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"bibr50-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6094994"},{"key":"bibr51-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914547786"},{"key":"bibr52-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1016\/0094-5765(94)00158-I"},{"key":"bibr53-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139773"},{"key":"bibr54-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2539377"},{"key":"bibr55-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556458"},{"key":"bibr56-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2012.2200561"},{"key":"bibr57-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"bibr58-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696588"},{"key":"bibr59-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1248805"},{"key":"bibr60-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139776"},{"key":"bibr61-0278364919890396","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915602958"},{"key":"bibr62-0278364919890396","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\/0278364919890396","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364919890396","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364919890396","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364919890396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T08:10:23Z","timestamp":1728979823000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364919890396"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,27]]},"references-count":62,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["10.1177\/0278364919890396"],"URL":"https:\/\/doi.org\/10.1177\/0278364919890396","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2020,1,27]]}}}