Matt Strong

Matt Strong

CS PhD at Stanford University

← Paper Digest

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

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

Seminal May 2014

TL;DR BIT* treats batches of random samples as an implicit graph and searches it in heuristic order like A*, reusing the tree as each batch adds samples. On a hard 14-DOF two-arm problem on HERB it found a solution in 68% of trials within 2.5 minutes, against 36% for FMT* and 8% for Informed RRT*.

What they do

A* searches in order of solution quality but needs a fixed discretization; RRT* scales to high dimensions but searches in random order. BIT* treats a batch of random samples as an implicit random geometric graph, searches it with a heuristic, then adds more samples and reuses the tree. With one sample per batch it reduces to a version of Informed RRT; with one batch and a zero heuristic, to a version of FMT.

How it works

  • Batches. Each batch adds uniform samples (100 in the experiments) and shrinks the connection radius as the graph grows. Once a solution exists, new samples come only from the region that could hold a better one (an ellipse for path length), and states that cannot improve it are pruned.
  • Ordered edge queue. Edges are processed by the estimated cost of a solution through them; a batch ends when the best queued edge cannot beat the current solution.
  • Lazy collision checking. Only edges whose heuristic cost could still improve the solution are collision-checked.
  • Incremental updates. New samples join the existing tree LPA*-style. The paper proves probabilistic completeness and almost-sure asymptotic optimality.

Results

  • Random worlds in R^2 and R^8 (10 worlds, 50 seeds each): BIT* was more likely to have a solution at a given time and converged faster than RRT, RRT, Informed RRT and FMT*. Only RRT-Connect, which does not converge to the optimum, found solutions faster.
  • HERB two-arm problem (14 DOF, 2.5 min, 25 trials): BIT* succeeded 68% of the time with median cost 17.4; FMT* 36% (17.2), Informed RRT* 8% (25.3), RRT 8% (31.1), RRT-Connect 100% (22.1).
  • HERB one-arm problem (7 DOF, 5 s): BIT* and RRT-Connect solved all 25 trials, with median costs 6.8 and 10.6; FMT* solved 52% (9.0), Informed RRT* and RRT 88% (10.6, 11.2).

Limitations

BIT* never removes samples whose connections fail, so edges known to be unusable stay in the graph; tracking failed edges proved too expensive in initial attempts. The benefit depends on the heuristic, and conservative heuristics help less.

Videos

Full video (YouTube)

Figures

From Figure 1: Composite of a BIT* trajectory for a 14-DOF two-arm manipulation problem on HERB. In this trial BIT* f...
From Figure 1: Composite of a BIT* trajectory for a 14-DOF two-arm manipulation problem on HERB. In this trial BIT* found a solution in 4 seconds and spent 2.5 minutes refining it.
From Figure 3: The BIT* search, from start (green) to goal (red). (a) The first batch is searched outwards from the s...
From Figure 3: The BIT* search, from start (green) to goal (red). (a) The first batch is searched outwards from the start; (b) it ends when a solution (magenta) is found. (c) After pruning and adding a second batch inside the region that could hold a better solution (black dashed), the search restarts on the denser graph; (d) it ends with an improved solution.
From Figure 4: RRT*, FMT* (2500 samples), Informed RRT* and BIT* on a random 2D world, each run until it matched the ...
From Figure 4: RRT*, FMT* (2500 samples), Informed RRT* and BIT* on a random 2D world, each run until it matched the FMT* solution cost of 1.39. BIT* got there in 0.072 s, against 0.487 s for RRT*, 0.141 s for FMT* and 0.144 s for Informed RRT*.
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 $\mathbb{R}^2$ and $\mathbb{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.

Summaries are written automatically from each paper's text. Figures and videos come from the paper and its project page; all credit goes to the authors.