Jonathan Gammell, Siddhartha Srinivasa, and Timothy Barfoot
2015 IEEE International Conference on Robotics and Automation (ICRA), May, 2015.
|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.
|motion planning, manipulation, sampling-based planning, optimal motion planning, robotics|
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
|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.|
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",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions