Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs
Share
- 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.
- Video
- 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 Identifier
- 10.1109/ICRA.2015.7139620
- arXiv Identifier
- 1405.5848 [cs.RO]
- Manuscript
- Open-Access PDF
- https://arxiv.org/pdf/1405.5848
- Google 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},
}