{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T23:30:01Z","timestamp":1782948601113,"version":"3.54.5"},"reference-count":105,"publisher":"SAGE Publications","issue":"4","license":[{"start":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T00:00:00Z","timestamp":1648771200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"UK Research and Innovation and EPSRC","award":["EP\/R026084\/1, EP\/S030832\/1"],"award-info":[{"award-number":["EP\/R026084\/1, EP\/S030832\/1"]}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:p>Optimal path planning is the problem of finding a valid sequence of states between a start and goal that optimizes an objective. Informed path planning algorithms order their search with problem-specific knowledge expressed as heuristics and can be orders of magnitude more efficient than uninformed algorithms. Heuristics are most effective when they are both accurate and computationally inexpensive to evaluate, but these are often conflicting characteristics. This makes the selection of appropriate heuristics difficult for many problems. This paper presents two almost-surely asymptotically optimal sampling-based path planning algorithms to address this challenge, Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*). These algorithms use an asymmetric bidirectional search in which both searches continuously inform each other. This allows AIT* and EIT* to improve planning performance by simultaneously calculating and exploiting increasingly accurate, problem-specific heuristics. The benefits of AIT* and EIT* relative to other sampling-based algorithms are demonstrated on 12 problems in abstract, robotic, and biomedical domains optimizing path length and obstacle clearance. The experiments show that AIT* and EIT* outperform other algorithms on problems optimizing obstacle clearance, where a priori cost heuristics are often ineffective, and still perform well on problems minimizing path length, where such heuristics are often effective.<\/jats:p>","DOI":"10.1177\/02783649211069572","type":"journal-article","created":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T21:42:02Z","timestamp":1656711722000},"page":"390-417","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":69,"title":["Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning"],"prefix":"10.1177","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2185-5852","authenticated-orcid":false,"given":"Marlin P","family":"Strub","sequence":"first","affiliation":[{"name":"Jet Propulsion Laboratory, California Institute of Technology, Pasadena, CA, USA, Work performed at the University of Oxford"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1034-3889","authenticated-orcid":false,"given":"Jonathan D","family":"Gammell","sequence":"additional","affiliation":[{"name":"Estimation, Search, and Planning (ESP) research group, University of Oxford, Oxford, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"bibr1-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1145\/3230650"},{"key":"bibr2-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2016.01.009"},{"key":"bibr3-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2011.6095077"},{"key":"bibr4-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630906"},{"key":"bibr5-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139869"},{"key":"bibr6-02783649211069572","unstructured":"Bekris KE, Kavraki LE (2008) Informed and probabilistically complete search for motion planning under differential constraints. In: Proceedings of the international symposium on search techniques in artificial intelligence and robotics, 13-14 July 2008, Chicago, Illinois, pp. 3\u201310."},{"key":"bibr7-02783649211069572","volume-title":"Dynamic Programming","author":"Bellman R","year":"1957"},{"key":"bibr8-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr9-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2001.932820"},{"key":"bibr10-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759547"},{"key":"bibr11-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"bibr12-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61291-2_68"},{"key":"bibr13-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1111\/0824-7935.00065"},{"key":"bibr14-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2020.2974094"},{"key":"bibr140-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3830"},{"key":"bibr15-02783649211069572","doi-asserted-by":"crossref","unstructured":"Dellin CM, Srinivasa SS (2016) A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors. In: Proceedings of the AAAI international conference on automated planning and scheduling (ICAPS), 12-17 June 2016, London, UK, pp. 459\u2013467.","DOI":"10.1609\/icaps.v26i1.13788"},{"key":"bibr16-02783649211069572","volume-title":"Automated Construction of Robotic Manipulation Programs","author":"Diankov R","year":"2010"},{"key":"bibr17-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"bibr18-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6696508"},{"key":"bibr19-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1480"},{"key":"bibr20-02783649211069572","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2021.XVII.081"},{"key":"bibr21-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2830331"},{"key":"bibr22-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919890396"},{"key":"bibr23-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942976"},{"key":"bibr24-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139620"},{"key":"bibr25-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-061920-093753"},{"key":"bibr26-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"bibr27-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1016\/0968-0160(96)00208-6"},{"key":"bibr28-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/tssc.1968.300136"},{"key":"bibr29-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139603"},{"key":"bibr30-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2602363"},{"key":"bibr31-02783649211069572","first-page":"530","volume":"1","author":"Holte RC","year":"1996","journal-title":"Proceedings of the AAAI national conference on artificial intelligence"},{"key":"bibr32-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364917714338"},{"key":"bibr33-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28872-7_38"},{"key":"bibr34-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"bibr35-02783649211069572","volume-title":"Optimal Bidirectional Rapidly-Exploring Random Trees. Technical Report MIT-CSAIL-TR-2013-021, Computer Science and Artificial Intelligence Laboratory (CSAIL)","author":"Jordan M","year":"2013"},{"key":"bibr36-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793933"},{"key":"bibr37-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1613\/jair.460"},{"key":"bibr38-02783649211069572","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2010.VI.034"},{"key":"bibr39-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr40-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr41-02783649211069572","doi-asserted-by":"crossref","unstructured":"Kiesel S, Burns E, Ruml W (2012) Abstraction-guided sampling for motion planning. In: Proceedings of the Symposium on Combinatorial Search (SOCS), 19-21 July 2012, Niagara Falls, Canada, pp. 162\u2013163.","DOI":"10.1609\/socs.v3i1.18265"},{"key":"bibr42-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206118"},{"key":"bibr43-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8463181"},{"key":"bibr44-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197236"},{"key":"bibr45-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43089-4_40"},{"key":"bibr46-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-43089-4_40"},{"key":"bibr47-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBIO.2015.7419012"},{"key":"bibr48-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1145\/1082473.1082748"},{"key":"bibr49-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2003.12.001"},{"key":"bibr50-02783649211069572","unstructured":"Korf RE (1997) Finding optimal solutions to Rubik\u2019s cube using pattern databases. In: Proceedings of the AAAI National Conference on Artificial Intelligence, 27-31 July 1997, Rhode Island, USA, pp. 700\u2013705."},{"key":"bibr51-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844730"},{"key":"bibr52-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487120"},{"key":"bibr53-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.845311"},{"key":"bibr54-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"bibr55-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1999.770022"},{"key":"bibr56-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr57-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942563"},{"key":"bibr58-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980427"},{"key":"bibr59-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915614386"},{"key":"bibr60-02783649211069572","unstructured":"Likhachev M, Gordon G, Thrun S (2004) ARA*: anytime A* with provable bounds on sub-optimality. In: Proceedings of the Advances in Neural Information Processing Systems (NIPS), British Columbia, Canada, 8-13 December 2003, pp. 767\u2013774."},{"key":"bibr61-02783649211069572","unstructured":"Likhachev M, Koenig S (2005) A generalized framework for lifelong planning A* search. In: Proceedings of the AAAI international conference on automated planning and scheduling (ICAPS), 5-10 June 2005, Monterey, CA, USA, pp. 99\u2013108."},{"key":"bibr62-02783649211069572","doi-asserted-by":"crossref","unstructured":"Mandalika A, Choudhury S, Salzman O, et al (2019) Generalized lazy search for robot motion planning: interleaving search and edge evaluation via event-based toggles. In: Proceedings of the AAAI international conference on automated planning and scheduling (ICAPS), 11-15 July 2019, Berkeley, California, USA, pp. 745\u2013753.","DOI":"10.1609\/icaps.v29i1.3543"},{"key":"bibr63-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v28i1.13931"},{"key":"bibr64-02783649211069572","doi-asserted-by":"crossref","unstructured":"Natarajan R, Saleem MS, Aine S, et al (2019) A-MHA*: anytime multi-heuristic A*. In: Proceedings of the symposium on combinatorial search (SoCS), 16-17 July 2019, Napa, California, USA, pp. 192\u2013193.","DOI":"10.1609\/socs.v10i1.18486"},{"key":"bibr65-02783649211069572","unstructured":"Nayak S, Otte M (2021) Bidirectional sampling-based motion planning without two-point boundary value solution. arXiv preprint ArXiv:2010.14692."},{"key":"bibr66-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2000.895219"},{"key":"bibr68-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8593554"},{"key":"bibr69-02783649211069572","unstructured":"Orthey A, Toussaint M (2019) Rapidly-exploring quotient-space trees: motion planning using sequential simplifications. In: Proceedings of the international symposium of robotics research (ISRR), Germany, 24 Aug 2019, pp. 1\u201316."},{"key":"bibr70-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16595-0_27"},{"key":"bibr71-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915594679"},{"key":"bibr72-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225337"},{"key":"bibr73-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1016\/j.knee.2009.10.007"},{"key":"bibr74-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1982.4767270"},{"key":"bibr75-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"bibr76-02783649211069572","doi-asserted-by":"publisher","DOI":"10.2172\/4785039"},{"key":"bibr77-02783649211069572","first-page":"12","volume-title":"Proceedings of the international joint conference on artificial intelligence","author":"Pohl I","year":"1973"},{"key":"bibr78-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2015.02.007"},{"key":"bibr79-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-019-09830-x"},{"key":"bibr80-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/LCSYS.2019.2922166"},{"key":"bibr81-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907543"},{"key":"bibr82-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139773"},{"key":"bibr83-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2539377"},{"key":"bibr84-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36460-9_27"},{"key":"bibr85-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9560836"},{"key":"bibr86-02783649211069572","doi-asserted-by":"crossref","unstructured":"Silver D (2005) Cooperative pathfinding. In: Proceedings of the AAAI conference on artificial intelligence and interactive digital entertainment (AIIDE), 1-2 June 2005, Marina Del Rey, CA, USA, pp. 117\u2013122.","DOI":"10.1609\/aiide.v1i1.18726"},{"key":"bibr87-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919859627"},{"key":"bibr88-02783649211069572","volume-title":"Leveraging Multiple Sources of Information to Search Continuous spaces","author":"Strub MP","year":"2021"},{"key":"bibr89-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197338"},{"key":"bibr90-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9196580"},{"key":"bibr91-02783649211069572","volume-title":"Admissible Heuristics for Obstacle Clearance Optimization Objectives","author":"Strub MP","year":"2021"},{"key":"bibr92-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1145\/1402383.1402451"},{"key":"bibr93-02783649211069572","doi-asserted-by":"crossref","unstructured":"Thayer JT, Benton J, Helmert M (2012) Better parameter-free anytime search by minimizing time between solutions. In: Proceedings of the symposium on combinatorial search (SOCS), 19-21 July 2012, Niagara Falls, Canada, pp. 120\u2013128.","DOI":"10.1609\/socs.v3i1.18242"},{"key":"bibr94-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v21i1.13474"},{"key":"bibr95-02783649211069572","doi-asserted-by":"crossref","unstructured":"Thayer JT, Ruml W (2009) Using distance estimates in heuristic search. In: Proceedings of the AAAI international conference on automated planning and scheduling (ICAPS), 19-23 September 2009, Thessaloniki, Greece, pp. 382\u2013385.","DOI":"10.1609\/icaps.v19i1.13390"},{"key":"bibr96-02783649211069572","unstructured":"Thayer JT, Ruml W (2011) Bounded suboptimal search: a direct approach using inadmissible estimates. In: Proceedings of the AAAI international conference on automated planning and scheduling (ICAPS), 11-16 June 2011, Freiburg, Germany, pp. 674\u2013679."},{"key":"bibr97-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9196917"},{"key":"bibr98-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1248805"},{"key":"bibr99-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908097213"},{"key":"bibr100-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341349"},{"key":"bibr101-02783649211069572","doi-asserted-by":"crossref","unstructured":"Wilt C, Ruml W (2012) When does weighted A* fail? In: Proceedings of the symposium on combinatorial search (SOCS), 19-21 July 2012, Niagara Falls, Canada, pp. 137\u2013144.","DOI":"10.1609\/socs.v3i1.18250"},{"key":"bibr102-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v27i1.8662"},{"key":"bibr103-02783649211069572","doi-asserted-by":"publisher","DOI":"10.29007\/jbv7"},{"key":"bibr104-02783649211069572","unstructured":"Yang I, Gammell JD, Murray DW, et al. (2021) The Oxford domed lateral implant: increasing tibial component wall height reduces the risk of medial dislocation of the mobile bearing. In: Proceedings of the annual meeting of the British orthopedic research society (BORS), 13-14 September 2021, held virtually, p. 1069."},{"key":"bibr105-02783649211069572","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8460188"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069572","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649211069572","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069572","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:54Z","timestamp":1777457814000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649211069572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4]]},"references-count":105,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["10.1177\/02783649211069572"],"URL":"https:\/\/doi.org\/10.1177\/02783649211069572","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4]]}}}