Skip to content

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

Authors: Jonathan D. Gammell, Siddhartha S. Srinivasa, Timothy D. Barfoot

Published: 2014 (Conference Paper)

Source: IEEE International Conference on Robotics and Automation (ICRA)

Algorithm: BIT*

arXiv: 1405.5848

DOI: 10.1109/ICRA.2015.7139620

Summary

BIT* unifies graph- and sampling-based planning by treating a batch of random samples as an implicit random geometric graph (RGG) and searching it with an A*/LPA*-style ordered search focused on the informed ellipsoidal subset of states that can improve the current solution. Successive batches of increasing density are searched while reusing prior information, yielding a probabilistically complete, asymptotically optimal anytime planner that converges substantially faster than RRT* and FMT*, especially in high-dimensional spaces.

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 R^2 and R^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.

Primary

Paper arxiv.org

Standard

arXiv Abstract 1405.5848 arXiv PDF 1405.5848 arXiv HTML 1405.5848 DOI 10.1109/ICRA.2015.7139620

Alternate

ieeexplore.ieee.org ieeexplore.ieee.org arXiv PDF arxiv.org journals.sagepub.com journals.sagepub.com

Tags

  • Motion planning

  • Sampling-based planning

  • Asymptotic optimality

  • Anytime planning

  • Heuristic search

  • Random geometric graphs

  • Graph search

  • Informed sampling