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

By Jonathan D. Gammell, Siddhartha S. Srinivasa, T. Barfoot. 2014

548 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Mathematical Optimization

In Algorithms & Complexity

Citations in the corpus

Habitat 2.0: Training Home Assistants to Rearrange their Habitat (2021, background): “For instance, work in the area of motion planning has made several advancements with new sampling techniques [94, 95] and optimization based methods [86, 87, 89, 96], but largely operated on the assumption of a reliable perception stack.”
Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions (2016, methodology): “RABIT* was extended by an informed global technique called BIT* [69] by using a local optimization module to improve an initial sub-optimal path towards a local optimum.”
Path Planning for Autonomous Mobile Robots: A Review (2021, unknown): “[192] presented another improvement to this, called Batch Informed Trees (BIT*), together with a comparison demonstrating its better performance than RRT*, Informed RRT* and FMT*.”
Learning Sampling Distributions for Robot Motion Planning (2017, methodology): “Specifically, we consider the hybrid sampling strategy proposed in [28], and BIT∗ [3].”
Motion Planning Networks (2018, background): “Furthermore, the mean computational time of BIT* not only fluctuates but also increases significantly in the rigid-body planning problem.”