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

Estimation, Search, and Planning (ESP) Research Group

Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search

Authors
  1. Jonathan D. Gammell
  2. Timothy D. Barfoot
  3. Siddhartha S. Srinivasa
Publication Date
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.

Informed graph-based searches, such as A*, 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.

Anytime sampling-based planners, such as RRT*, 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.

This article unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* 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*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.

Publication Details
Type
Journal Paper
Journal
The International Journal of Robotics Research (IJRR)
Volume
39
Number
5
Pages
543–567
Digital Object IdentifierDOI
10.1177/0278364919890396
arXiv Identifier
1707.01888 [cs.RO]
Manuscript
Google ScholarGoogle Scholar
Google Scholar
BibTeX Entry
@article{gammell_ijrr20,
author = {Jonathan D Gammell and Timothy D Barfoot and Siddhartha S Srinivasa},
title = {Batch {Informed} {Trees} ({BIT*}): Informed asymptotically optimal anytime search},
journal = {The International Journal of Robotics Research ({IJRR})},
year = {2020},
volume = {39},
number = {5},
pages = {543--567},
month = apr,
doi = {10.1177/0278364919890396},
}