PaperlayerView exact revision on arXiv

Source-linked AI summary

Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search

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

arXiv:1707.01888v4cs.RO

TL;DR

Continuous and high-dimensional path planning requires approximations, but graph methods depend on a priori resolution while sampling-based methods depend on random approximation order. The paper introduces BIT*, which combines heuristic ordering with batch-based incremental sampling; it is analytically almost-surely asymptotically optimal and experimentally outperforms existing planners, especially in high dimensions. The paper also identifies tuning and approximation choices as practical scope boundaries.

  • Problem

    Path planning must handle continuous and high-dimensional spaces, while graph-based methods depend on chosen resolution and sampling-based methods can waste effort through random search order.

  • Method

    BIT* uses heuristics and batches of random samples to incrementally build and search continuous-space approximations in order of potential solution quality.

  • Results

    BIT* is almost-surely asymptotically optimal and experimentally outperforms other almost-surely asymptotically optimal planners, with results indicating stronger performance as the RGG becomes denser.

  • Takeaways & Limitations

    BIT* directly unifies informed graph search and sampling-based planning while retaining anytime approximation and heuristic search.

  • Takeaways & Limitations

    Performance depends on tuning the maximum edge length and batch size for problem size, dimension, and obstacle characteristics.

Abstract

from arXiv · show

Path planning in robotics often requires finding high-quality solutions to continuously valued and/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as respectively used by informed graph-based searches and anytime sampling-based planners. Informed graph-based searches, such as A*, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient but leaves their performance dependent on the chosen approximation. If its resolution is too low then they may not find a (suitable) solution but if it is too high then they may take a prohibitively long time to do so. Anytime sampling-based planners, such as RRT*, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously and but may be prohibitively inefficient at containing a solution. This paper unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.

1 Introduction

BIT* unifies informed graph search with anytime sampling-based planning by alternately improving a continuous-space approximation and searching it in potential-solution-quality order. This avoids unnecessary computation while retaining asymptotic convergence and improving solutions faster, especially in high-dimensional spaces.

  • Planning challenge: Continuous and high-dimensional path planning is difficult because graph approximations must balance resolution against search cost, with graph size growing exponentially with state dimension.Sparse graphs may miss suitable solutions, whereas dense graphs may be prohibitively expensive to search.
  • Sampling-based planning: Sampling-based planners improve resolution incrementally and can be probabilistically complete and almost-surely asymptotically optimal, but random sample order wastes effort across the domain.Their space-filling search may consider states not used to find a solution.
  • BIT* approach: BIT* combines incremental sampling with heuristic search, approximating continuous problems in batches while ordering search by potential solution quality.The approximation improves as samples increase, and heuristics focus search on promising states.
  • BIT* approach: BIT* avoids unnecessary computational costs while almost-surely converging asymptotically to the optimum and finding better solutions faster than existing algorithms, especially in high state dimensions.Its batch size, heuristic, and RGG-connection parameter are user-defined options, and the framework relates to established graph and sampling planners.
  • Extensions and evidence: The paper presents extensions including SORRT*, which applies ordered-search concepts to incremental sampling while retaining RRT*’s algorithmic simplicity.The paper also reports expanded proofs of probabilistic completeness and almost-sure asymptotic optimality.
  • Extensions and evidence: Experiments show that BIT* finds better solutions faster than existing almost-surely asymptotically optimal planners, while only non-asymptotically optimal RRT-Connect finds worse solutions faster.The reported advantage is especially pronounced in high dimensions.

2 Prior Work Ordering Sampling-based Planners

Prior work combines informed graph search with sampling-based planning, but existing approaches sacrifice either anytime resolution or search efficiency. BIT* instead orders the entire sampling-based search by potential solution quality while retaining anytime behavior and asymptotic convergence.

  • The Optimal Path Planning Problem: Optimal path planning searches for a feasible path minimizing a chosen cost function between start and goal states.
  • A*-based Approaches: A*-style methods efficiently search discretized representations, but their performance depends on the chosen a priori approximation.
  • Combining Approaches: Earlier hybrids either sacrifice anytime resolution or order search using metrics beyond solution cost, reducing efficiency.
  • RRT-based Approaches: Sampling-based planners avoid a priori discretization and can run indefinitely, but their search depends on the random sample sequence and may waste effort on unnecessary states.
  • BIT*: BIT* orders its entire search by potential solution quality, returns incrementally better solutions, and almost-surely converges asymptotically to the optimum.

3 Batch Informed Trees (BIT*)†

BIT* alternates between improving a random geometric approximation and searching it in order of potential solution quality. Incremental search, informed sets, and batches let it run indefinitely while converging almost surely toward optimal paths.

  • Core algorithm: BIT* builds an increasingly dense edge-implicit random geometric graph from batches of random samples in the informed set.
  • Search: BIT* expands the best possible edge from a potential-cost queue and resumes searching after adding a new batch when no current edge can improve the solution.
  • Informed set: The informed set contains states whose admissible estimated path cost could improve the current best solution cost.
  • Search: Heuristics order the initial search by estimated solution quality, while incremental techniques reuse information when the approximation improves.
  • Efficiency: BIT* can reject edges without calculating their true cost, reducing unnecessary edge evaluation.

2 Xunconn

BIT* prunes states that cannot improve the current solution and recycles disconnected states that may become useful in later batches. This preserves informed-set sampling density while avoiding repeated consideration of irrelevant vertices.

  • Batch processing: Each vertex is expanded or pruned in every batch, preventing reconsideration by the expansion procedure.
  • Pruning: BIT* removes unconnected states outside the informed set and incrementally prunes connected vertices that cannot improve the current solution.
  • Recycling: Disconnected vertices that could provide a better solution are reused as samples in the next batch.
  • Recycling: Recycling maintains uniform sample density in the informed set and allows future reconnection when improvements make vertices useful.
  • Implementation: Pruning is computationally expensive and should occur only after a new solution or significant solution-cost change.

4 Analysis

BIT* combines heuristic ordering with batch-based sampling to search an increasingly dense approximation of continuous planning problems. Its analysis establishes probabilistic completeness and almost-sure asymptotic optimality.

  • Guarantees: BIT* is probabilistically complete and almost-surely asymptotically optimal.The proofs connect BIT*’s considered edges and cost-improving selections to RRT*’s asymptotic guarantees.
  • Relation to graph search: BIT*’s queue ordering is equivalent to the vertex ordering used by LPA* and TLPA* under a lazy approximation of incoming edge costs.The search itself is not fully equivalent because BIT* does not propagate rewirings from rewired vertices.
  • Batched approximation: BIT* batches samples and considers connections from the same or earlier batches within a connection limit.For batch size m ≥ 1, its connection limit satisfies rBIT* ≥ rRRT*, so it considers at least the same edges as RRT*.
  • Search ordering: BIT* searches an implicit random geometric graph in order of potential solution quality using an edge queue.The queue combines estimated cost-to-go, estimated edge cost, and current cost-to-come.
  • Cost evaluation: BIT* combines minimum-cost calculations for individual vertices into one edge queue while expanding vertices in increasing order.This reduces the need to calculate true costs for every possible incoming edge before ordering expansions.

5 Modifications and Extensions

The extensions modify BIT* to prioritize solution discovery, avoid unnecessary sampling, and support difficult or unbounded planning domains. They preserve asymptotic guarantees while adapting search and approximation effort to the problem.

  • Just-in-time sampling: Just-in-time sampling generates samples only when needed by vertex expansion while maintaining uniform sample density.It expands the informed set incrementally and samples only the new prolate hyperspheroidal shell required by the search.
  • Sample removal: Removing unconnected samples avoids repeated connection attempts to infeasible states while maintaining almost-sure asymptotic optimality.The modification is useful when many free-space regions are unreachable.
  • Sorted RRT*: SORRT* orders batches by potential solution quality but uses a steer function and one connection attempt per sample.This extension reduces the number of connections attempted during ordered search.
  • Delayed rewiring: Delayed rewiring prioritizes finding an initial solution by considering edges to new samples before rewiring existing vertices.Rewirings are performed after a solution is found and this modification does not affect almost-sure asymptotic optimality.
  • Just-in-time sampling: JIT sampling avoids approximating unused regions and allows BIT* to operate on large or unbounded planning problems.It removes the need to define a priori limits in unbounded problems.
  • Core extension framework: BIT* focuses its increasingly dense implicit RGG on the informed set, alternately adding samples and searching existing samples for better solutions.The resulting spanning tree contains states that could currently improve the solution but need not use every RGG state.

6 Experiments

Experiments across abstract problems and HERB manipulation tasks show that BIT* is competitive in low dimensions and generally stronger than other anytime asymptotically optimal planners as dimension increases. Its advantage is especially evident in difficult high-dimensional settings, although RRT-Connect can find solutions faster in some cases.

  • Many homotopy classes: BIT* finds solutions faster than other tested planners except RRT-Connect on the many-homotopy-class problem and outperforms other asymptotically optimal planners in R16.RRT*-based planners did not find solutions in the available high-dimensional time.
  • Many homotopy classes: In lower dimensions, informed RRT*-based planners can achieve better median solution costs, while BIT* becomes the only anytime asymptotically optimal planner that always solves the R16 problem within the allotted time.The results associate the higher-dimensional advantage with processing multiple connections or samples per iteration.
  • Random obstacles: Across the tested randomly obstructed problems, BIT* generally finds better solutions faster and its relative improvement increases with state dimension.RRT-Connect was the only tested planner that found solutions faster than BIT* in these experiments.
  • HERB experiments: On HERB manipulation problems, BIT* found solutions more often and improved to better final paths than other tested asymptotically optimal planners.For the reported two-armed problem, BIT* found initial solutions faster than all tested algorithms, including RRT-Connect.

7 Discussion & Conclusion

BIT* unifies informed graph search with anytime sampling by ordering increasingly dense approximations according to potential solution quality. Experiments show strong performance, while tuning sensitivity and the absence of formal search-efficiency guarantees remain important qualifications.

  • Method: BIT* combines heuristic ordering with batches of random samples to search increasingly dense implicit RGGs.This preserves A*-like ordering while allowing indefinite approximation improvement, as in RRT*.
  • Theory: BIT* is probabilistically complete and almost-surely asymptotically optimal.
  • Efficiency: Heuristics focus approximation on regions that could provide better solutions, while delayed edge evaluation avoids unnecessary computational costs.BIT* also reuses information when searching denser approximations.
  • Experiments: BIT* generally finds better solutions faster than other almost-surely asymptotically optimal planners as state dimension increases.The benefits were demonstrated on abstract planning problems and simulated HERB experiments.
  • Limitations: RRT-style planner performance depends heavily on maximum edge length, whereas BIT* batch-size tuning could still improve problem-specific performance.The experiments used the same batch size across tested problems, despite Fig. 16 indicating further tuning may help.
  • Future Work: Future work includes variable and adaptive batch sizes, different anytime approximations, and probabilistic search-efficiency statements analogous to those for A*.

Funding

The research received support from Canadian and U.S. research organizations and programs.

  • Funding: The research was supported by the Natural Sciences and Engineering Research Council of Canada.
  • Funding: Support was provided through the NSERC Canadian Field Robotics Network and Ontario’s Early Researcher Award Program.
  • Funding: The Office of Naval Research Young Investigator program also supported the research.
Loading 1707.01888v4…