PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:1405.5848v7cs.RO

TL;DR

Continuous path planners must balance the ordered efficiency of graph search against the anytime scalability of sampling-based methods, especially in high-dimensional spaces. BIT* unifies them by heuristically searching increasingly dense implicit random geometric graphs while reusing information across batches. Across simulated and HERB manipulation problems, it found better solutions faster and converged toward the optimum faster than the compared planners.

  • Problem

    Graph search faces discretization and high-dimensionality costs, while sampling-based planning is probabilistic and often unordered.

  • Method

    BIT* combines heuristic graph search, incremental information reuse, and batches of samples to search increasingly dense implicit RGGs.

  • Results

    BIT* consistently outperformed RRT, RRT*, Informed RRT*, and FMT* in solution likelihood, solution quality, and convergence speed across simulated and manipulation problems.

  • Takeaways & Limitations

    BIT* demonstrates that incremental graph-search techniques and RGG theory can produce anytime sampling-based planners with ordered search and asymptotic optimality.

  • Takeaways & Limitations

    BIT* does not remove samples whose connection attempts fail, leaving known unusable edges in the implicit RGG.

Abstract

from arXiv · show

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.

I. INTRODUCTION

Graph-search methods provide ordered, resolution-optimal searches but suffer from discretization and dimensionality costs, while sampling-based methods scale better continuously but search probabilistically. BIT* combines these paradigms through heuristic, batch, and incremental search, improving performance across simulated and manipulation problems.

  • Graph-search methods: Graph-search algorithms such as A* efficiently find resolution-optimal solutions by ordering vertices with admissible heuristics.Their guarantees apply to the chosen discrete approximation.
  • Graph-search methods: Finer discretization improves continuous-solution quality but increases computation dramatically, especially in high-dimensional manipulation spaces.The discrete state space grows exponentially with dimensionality.
  • Sampling-based methods: Sampling-based planners avoid discretization by randomly sampling continuous domains, providing probabilistic completeness and anytime resolution.Their search becomes increasingly reliable as the number of samples increases.
  • Prior combinations: Existing heuristic sampling methods improve solutions or convergence, but RRT-based searches remain unordered, while FMT* sacrifices anytime resolution.FMT* must restart when higher resolution is needed.
  • BIT*: BIT* orders searches over batches of samples, reuses incremental-search information, and focuses later searches on regions that may contain better solutions.This combines A*-like ordering, RRT*-like anytime scalability, LPA*-style reuse, and Informed RRT*-style focusing.
  • BIT*: Across random R2 and R8 experiments and HERB manipulation problems, BIT* more often found solutions and converged faster than tested optimal planners.RRT-Connect found solutions faster in the reported comparison but does not converge toward the optimum.

II. BACKGROUND

The paper formulates optimal planning over continuous free space and models random samples as implicit random geometric graphs. BIT* applies incremental search to increasingly dense graphs to combine ordered search with anytime, asymptotically optimal planning.

  • Problem formulation: The optimal planning problem seeks a minimum-cost path from the start state to a goal state through collision-free space.The optimal path cost is denoted s*.
  • Random geometric graphs: Randomly sampled states define an implicit graph whose properties can be modeled using random geometric graph theory.Edges are determined algorithmically from sampled states and their geometry.
  • Random geometric graphs: RGG edges may connect nearest neighbors or all states within a specified distance, with theory relating sampling and graph parameters to connectivity and cost.These relationships support controlling graph complexity while preserving planning properties.
  • Planner interpretation: Sampling-based planners construct implicit RGGs and explicit spanning trees in free space, so performance depends on both representation quality and search efficiency.This provides the conceptual bridge between sampling-based planning and graph search.
  • Existing planners: RRT* produces randomly ordered anytime searches, whereas FMT* produces ordered searches over a fixed sample set without anytime solution or resolution improvement.These contrasting properties motivate a method that combines ordering with progressive refinement.
  • BIT*: BIT* uses incremental search on increasingly dense RGGs, balancing heuristic ordering, anytime performance, and asymptotic optimality.It generalizes existing planners: one-sample batches resemble Informed RRT*, while a single zero-heuristic batch resembles FMT*.

III. BATCH INFORMED TREES (BIT*)

BIT* builds and searches implicit RGGs in batches, using admissible cost estimates to prioritize promising edges and paths. It reuses existing search information while adding samples and restricting later searches to regions that could improve the current solution.

  • Batch construction: BIT* begins with uniformly sampled free-space states, start and goal states, and an RGG connection parameter selected for graph complexity and asymptotic optimality.The initial explicit tree grows from the start toward the goal using heuristic search.
  • Batch construction: Each new batch adds samples, densifies the implicit RGG, and updates its connection parameter before restarting the search.When a solution exists, sampling is restricted to a subproblem that could contain a better solution.
  • Heuristic guidance: Admissible cost-to-come and cost-to-go estimates lower-bound the true costs and support informed prioritization.These estimates are denoted b_g(x) and b_h(x).
  • Heuristic guidance: The path estimate b_f(x) = b_g(x) + b_h(x) identifies states that could yield a solution better than the current best cost.This defines the informed subset used to focus search.
  • Cost evaluation: The tree’s current cost-to-come g_T(x) bounds the unknown optimal cost together with the admissible lower bound b_g(x).For every state, b_g(x) ≤ g(x) ≤ g_T(x).
  • Cost evaluation: Admissible edge-cost estimates delay expensive true-cost evaluations, including collision detection and differential-constraint checks.Edges intersecting obstacles are assigned infinite true cost.

B. Algorithm

BIT* grows a collision-free tree through an implicitly defined RGG using heuristic queues, delayed edge-cost evaluation, and incremental batch updates. Its ordered search prioritizes edges that could improve the current solution.

  • Batch creation: BIT* initializes an implicit RGG and grows an explicit tree from the start toward the goal using a heuristic search.The initial batch contains uniformly distributed samples, the start, and the goal; edges are considered only when collision-free.
  • Batch creation: Each new batch adds m samples, prunes states that cannot improve the solution, updates the RGG radius, and requeues tree vertices.Sampling can use rejection sampling or direct informed sampling for some cost functions.
  • Edge selection: Edges are selected by increasing estimated solution cost, gT(v)+bc(v,x)+bh(x), with ties favoring lower current cost-to-come.This ordering focuses processing on edges that appear most promising under the current tree and heuristic.
  • Edge selection: BIT* delays edge-queue construction by expanding vertices only when their lower-bound queue value is below the best edge-queue value.Each vertex is expanded once per batch, so each resulting edge is processed at most once per batch.
  • Edge processing: Before expensive collision checks and differential-constraint calculations, BIT* discards edges that cannot improve the current solution.Edges that pass this test are checked against the target vertex’s cost-to-come and added only when they improve it.
  • Performance illustration: In a representative R2 comparison, BIT* found a solution with cost c = 1.39 in t = 0.072s, faster than RRT*, FMT*, and Informed RRT*.The comparison used FMT*’s solution cost as the target, regardless of homotopy class.
  • Edge processing: Improving edges either rewire existing tree vertices or expand unconnected samples, after which the edge queue is pruned.Vertex expansion adds outgoing RGG edges, while graph pruning removes states unable to yield a solution better than the given cost.

C. Practical Considerations

The paper identifies implementation choices that reduce BIT*’s practical overhead without changing its behavior. These include conditional pruning, indexed data structures, and approximate queue sorting.

  • Pruning: Pruning is expensive, so it should occur only after finding a new solution or after significant solution-cost changes.The paper states that limiting pruning to significant cost changes does not alter behavior.
  • Data structures: k-d trees or indexed containers can implement searches without exhaustive global scans.These structures are suggested for searches used in vertex expansion, rewiring, and pruning.
  • Queue management: An approximately sorted edge queue showed little experimental difference from a strictly sorted queue despite rewiring-induced order changes.Ordered containers are used to maintain the edge queue efficiently.

IV. ANALYSIS

BIT* is analyzed as an incremental, heuristic extension of RRT* and LPA* over increasingly dense implicit RGGs. The analysis establishes almost-sure asymptotic optimality and relates the edge queue to incremental graph search.

  • Theoretical guarantees: The paper presents a proof of almost-sure asymptotic optimality and notes that this implies probabilistic completeness.The analysis also discusses the relationship between BIT*’s edge queue and LPA*’s vertex queue.
  • Theoretical guarantees: BIT* asymptotically converges almost surely to the optimal solution when the total number of samples q goes to infinity, if a solution exists.best,q denotes the cost of BIT*’s best solution from q samples.
  • Theoretical guarantees: BIT* considers all same- or earlier-batch edges within rq, containing the edges RRT* considers for the same sample sequence and radius.Uniform sample density in the subproblem containing all better solutions, together with the RGG radius condition, supports the asymptotic-optimality argument.
  • Relation to LPA*: BIT*’s edge queue extends LPA*’s vertex queue by incorporating a heuristic estimate of edge cost.The queue simultaneously computes minimum cost-to-come values while expanding vertices by increasing estimated solution cost.
  • Relation to LPA*: Using admissible edge-cost estimates lets BIT* calculate the running minimum incrementally while delaying expensive true edge-cost evaluations.True costs can involve collision checking and differential constraints.

V. EXPERIMENTAL RESULTS

BIT* was evaluated against sampling-based planners in simulated R2 and R8 random-obstacle worlds and on real-world HERB manipulation problems. The experimental setup used common RGG parameters, 100-sample batches, Euclidean heuristics, and informed sampling.

  • Evaluation setup: Experiments used publicly available OMPL implementations to compare BIT* with existing algorithms in simulated and real-world planning problems.The evaluation included random worlds in R2 and R8 and manipulation problems on HERB.
  • Evaluation setup: BIT* used graph pruning only when solution cost changed by more than 1% and used an approximately sorted queue.These settings reflect the practical implementation choices described for the experiments.

A. Simulated Random Worlds

In simulated random planning problems in R^2 and R^8, BIT* generally found better solutions faster than the other tested planners and converged faster toward the optimum.

  • The evaluation used 10 random worlds per dimension, 50 pseudo-random seeds per world, and solution-cost recording every millisecond.
  • BIT* generally found better solutions faster than other sampling-based optimal planners and RRT in both R^2 and R^8.
  • BIT* had a higher likelihood of finding a solution at a given computational time than the compared planners.
  • BIT* converged faster toward the optimum than the compared planners.
  • RRT-Connect was the only tested planner that found solutions faster than BIT*; it is nonasymptotically optimal.

B. Motion Planning for Manipulation

On HERB manipulation problems, BIT* outperformed the tested planners on a challenging dual-arm task and achieved the lowest median cost on an easier one-arm task.

  • HERB evaluation: BIT* outperformed every planner except RRT-Connect on HERB manipulation problems.
  • Dual-arm planning: The dual-arm task was challenging because a narrow passage around the table was combined with a 14-DOF configuration space.
  • Dual-arm planning: 68% of dual-arm trials succeeded for BIT* in 2.5 minutes, versus 36% for FMT*, 8% for RRT and Informed RRT*, and 100% for RRT-Connect.BIT* had median solution cost 17.4; RRT-Connect had 22.1, RRT 31.1, Informed RRT* 25.3, and FMT* 17.2.
  • One-arm planning: In the easier one-arm task, BIT* and RRT-Connect succeeded in all 25 trials, while BIT* had the lower median solution cost of 6.8 versus 10.6.

VI. DISCUSSION & FUTURE WORK

BIT* combines incremental graph search with RGG theory to support anytime planning, while the discussion identifies efficiency analysis and failed-edge handling as open improvement areas.

  • BIT* combines incremental graph-search techniques with RGG theory to design an anytime sampling-based planner.
  • Heuristic estimates guide cost-to-come, edge cost, and solution cost to reduce unnecessary checks and focus the search.
  • BIT* reuses information differently from LPA*: reconsidering all descendant cost-to-come values becomes prohibitively expensive as graph size grows.
  • Open questions: The efficiency of graph-search techniques for sampling-based planners remains understudied, and probabilistic efficiency evaluation is ongoing.
  • Potential improvements: BIT* retains samples after failed connection attempts, leaving known unusable edges in the implicit RGG.
  • Potential improvements: Tracking failed edges was initially too computationally expensive, while removing repeatedly failing samples would require RGG theory for nonuniform distributions.
  • Future work: The authors are investigating adaptive batch sizes and extensions for large, unbounded, or changing planning problems.

VII. CONCLUSION

BIT* unifies graph-search and sampling-based planning through implicit random geometric graphs, combining efficient heuristic search with anytime scalability. Experiments show it outperforms existing planners, particularly in high-dimensional problems.

  • BIT* recognizes samples as an implicit random geometric graph and applies incremental-search techniques to continuous planning.This unifies graph-search and sampling-based planning techniques through RGG theory.
  • Heuristics prioritize high-quality paths and focus the search on improvements.The heuristic applies to all aspects of path cost.
  • BIT* combines the efficient search of A* with the anytime scalability of sampling-based planners such as RRT*.
  • BIT* outperforms existing sampling-based optimal planners and RRT, especially in high dimensions.Across simulated and real-world experiments, it generally finds solutions of equivalent quality sooner and converges toward the optimum faster.
Loading 1405.5848v7…