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

Estimation, Search, and Planning (ESP) Research Group

Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs

Authors
  1. Jonathan D. Gammell
  2. Siddhartha S. Srinivasa
  3. Timothy D. Barfoot
Publication Date
Abstract

In this paper, we present Batch Informed Trees (BIT*), a planning algorithm based on unifying graph- and sampling-based planning techniques. By recognizing that a set of samples describes an implicit random geometric graph (RGG), we are able to combine the efficient ordered nature of graph-based techniques, such as A*, with the anytime scalability of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT).

BIT* uses a heuristic to efficiently search a series of increasingly dense implicit RGGs while reusing previous information. It can be viewed as an extension of incremental graph-search techniques, such as Lifelong Planning A* (LPA*), to continuous problem domains as well as a generalization of existing sampling-based optimal planners. It is shown that it is probabilistically complete and asymptotically optimal.

We demonstrate the utility of BIT* on simulated random worlds in ℝ2 and ℝ8 and manipulation problems on CMU’s HERB, a 14-DOF two-armed robot. On these problems, BIT* finds better solutions faster than RRT, RRT*, Informed RRT*, and Fast Marching Trees (FMT*) with faster anytime convergence towards the optimum, especially in high dimensions.

VideoVideo
Publication Details
Type
Full-Paper-Refereed Conference Paper
Conference
IEEE International Conference on Robotics and Automation (ICRA)
Location
Seattle, WA, USA
Pages
3067–3074
Digital Object IdentifierDOI
10.1109/ICRA.2015.7139620
arXiv Identifier
1405.5848 [cs.RO]
Manuscript
Google ScholarGoogle Scholar
Google Scholar
BibTeX Entry
@inproceedings{gammell_icra15,
author = {Jonathan D Gammell and Siddhartha S Srinivasa and Timothy D Barfoot},
title = {Batch {Informed} {Trees} ({BIT*}): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs},
booktitle = {Proceedings of the {IEEE} International Conference on Robotics and Automation ({ICRA})},
year = {2015},
pages = {3067--3074},
address = {Seattle, WA, USA},
month = {26--30 } # may,
doi = {10.1109/ICRA.2015.7139620},
}