Jump to Content
  1. Oxford
  2. MPLS
  3. Eng. Sci.
  4. ORI

Estimation, Search, and Planning (ESP) Research Group

Adaptively Informed Trees (AIT*): Fast asymptotically optimal path planning through adaptive heuristics

Authors
  1. Marlin P. Strub
  2. Jonathan D. Gammell
Publication Date
Abstract

Informed sampling-based planning algorithms exploit problem knowledge for better search performance. This knowledge is often expressed as heuristic estimates of solution cost and used to order the search. The practical improvement of this informed search depends on the accuracy of the heuristic.

Selecting an appropriate heuristic is difficult. Heuristics applicable to an entire problem domain are often simple to define and inexpensive to evaluate but may not be beneficial for a specific problem instance. Heuristics specific to a problem instance are often difficult to define or expensive to evaluate but can make the search itself trivial.

This paper presents Adaptively Informed Trees (AIT*), an almost-surely asymptotically optimal sampling-based planner based on BIT*. AIT* adapts its search to each problem instance by using an asymmetric bidirectional search to simultaneously estimate and exploit a problem-specific heuristic. This allows it to quickly find initial solutions and converge towards the optimum. AIT* solves the tested problems as fast as RRT-Connect while also converging towards the optimum.

VideoVideo
PresentationPresentation
Publication Details
Type
Full-Paper-Refereed Conference Paper
Conference
IEEE International Conference on Robotics and Automation (ICRA)
Pages
3191–3198
Digital Object Identifier DOI
10.1109/ICRA40945.2020.9197338
arXiv Identifier arXiv
2002.06599 [cs.RO]
Manuscript
Google Scholar Google Scholar
Google Scholar
BibTeX Entry
@inproceedings{strub_icra20b,
author = {Marlin P Strub and Jonathan D Gammell},
title = {Adaptively {Informed} {Trees} ({AIT*}): {Fast} asymptotically optimal path planning through adaptive heuristics},
booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation ({ICRA})},
year = {2020},
pages = {3191--3198},
month = {31 } # may #{ -- 31 } # aug,
doi = {10.1109/ICRA40945.2020.9197338},
}