Jump to Content
  1. Queen's
  2. Smith Eng.
  3. ECE

Estimation, Search, and Planning (ESP) Research Group

Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning

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

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.

VideoVideo
PlaylistPlaylist
Publication Details
Type
Journal Paper
Journal
The International Journal of Robotics Research (IJRR)
Volume
41
Number
4
Pages
390–417
Digital Object IdentifierDOI
10.1177/02783649211069572
arXiv Identifier
2111.01877 [cs.RO]
Manuscript
Google ScholarGoogle Scholar
Google Scholar
BibTeX Entry
@article{strub_ijrr22,
author = {Marlin P Strub and Jonathan D Gammell},
title = {Adaptively {Informed} {Trees} ({AIT*}) and {Effort} {Informed} {Trees} ({EIT*}): Asymmetric bidirectional sampling-based path planning},
journal = {The International Journal of Robotics Research ({IJRR})},
year = {2022},
volume = {41},
number = {4},
pages = {390--417},
month = apr,
doi = {10.1177/02783649211069572},
}