Carnegie Mellon University
The
Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs

Jonathan Gammell, Siddhartha Srinivasa, and Timothy Barfoot
2015 IEEE International Conference on Robotics and Automation (ICRA), May, 2015.


Download
  • Adobe portable document format (pdf) (3MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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 R2 and R8 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.

Keywords
motion planning, manipulation, sampling-based planning, optimal motion planning, robotics

Notes
Sponsor: ONR
Grant ID: ONR-YIP
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Personal Robotics

Text Reference
Jonathan Gammell, Siddhartha Srinivasa, and Timothy Barfoot, "Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs," 2015 IEEE International Conference on Robotics and Automation (ICRA), May, 2015.

BibTeX Reference
@inproceedings{Srinivasa_2015_7946,
   author = "Jonathan Gammell and Siddhartha Srinivasa and Timothy Barfoot",
   editor = "IEEE",
   title = "Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs",
   booktitle = "2015 IEEE International Conference on Robotics and Automation (ICRA)",
   address = "6341 Burchfield Avenue",
   month = "May",
   year = "2015",
}