Advanced BIT* (ABIT*):
Sampling-Based Planning with Advanced Graph-Search Techniques

Path planning is the problem of finding a continuous sequence of valid states from a start to a goal specification. Popular approaches in robotics include graph-based searches, such as A* [1], and sampling-based planners, such as Rapidly-exploring Random Trees (RRT) [2].

Both graph- and sampling-based approaches have characteristic strengths and weaknesses. Advanced BIT* (ABIT*) continues previous work [3] to combine these strengths and mitigate these weaknesses using a unified planning paradigm. ABIT* achieves this by viewing the planning problem as the two subproblems of approximation and search. This perspective allows ABIT* to use advanced graph-search techniques on an anytime sampling-based approximation to quickly find initial solutions and almost-surely asymptotically converge to the global optimum.

Full details of ABIT* can be found in the paper (https://arxiv.org/abs/2002.06589).

Approximation

ABIT* approximates the state space of a planning problem by sampling multiple batches of states. Connections between these states are only considered if they are within a certain radius from each other. This results in an edge-implicit random geometric graph (RGG) [4] approximation of the problem’s state space with ever increasing density.

Once an initial solution is found, ABIT* only increases the density of its RGG approximation in the region of the state space that can possibly improve the current solution by using informed sampling [5].

Search

ABIT* searches paths in its RGG approximation with an informed graph-search algorithm. ABIT* initially prioritizes finding any solution quickly to being efficient in finding the optimal solution on its current approximation. This results in fast initial solution times.

Once an initial solution is found, ABIT* avoids wasting computational effort on finding the optimal solution on a given RGG approximation, knowing that it will change when the next batch of states is sampled. This promotes exploring the regions of the state space that can possibly improve the current solution, because it allows ABIT* to sample states without fully exploiting the current approximation.

Experimental Results

ABIT* outperforms state-of-the-art almost-surely asymptotically optimal planning algorithms on the tested problems. The only tested algorithm that found initial solutions faster than ABIT* is RRT-Connect [6], which is not an almost-surely asymptotically optimal algorithm and cannot improve its initial solution given more computational time.

One set of tested problems consists of axis-aligned hyperrectangles of random widths placed randomly in the state space in R^4 and R^8. Ten different random obstacle configurations were instantiated and each planner was run 100 times on each instantiation. The plots below show the achieved success rates and median path costs of all tested planners for the two problems that resulted in the best and worst performances of ABIT*, as defined by its initial solution time relative to RRT-Connect.

The plots show the best and worst instances of ten random rectangle experiments in R^4 and R^8. The squares in the cost plots show the median initial costs and times while the lines show the median cost over time for almost-surely asymptotically optimal planners (unsuccessful runs were taken as infinite costs). The error bars show a nonparametric 99% confidence interval on the solution cost and time.

ABIT* on NASA/JPL-Caltech’s Axel Rover System

The benefits of ABIT* were demonstrated on NASA/JPL-Caltech’s Axel Rover System [7] during a week-long field test in the Mojave Desert, California, USA. Axel is a tethered robotic platform designed for the exploration of challenging terrain that requires paths as sequences of SE(3) poses settled on the surface manifold of the terrain.

NASA/JPL-Caltech’s Axel Rover System autonomously navigating challenging terrain in the Mojave Desert, CA, USA.

ABIT* planning a path for Axel during a week-long field test in the Mojave Desert.

The complexity of the terrain and its interaction with the tether make for a challenging planning problem in which state evaluations are computationally expensive. ABIT* typically found solutions to the planning problems posed by Axel in under two seconds. This resulted in 95.12% autonomy by distance, despite the challenging terrain.

The top row shows DuAxel driving up to a ledge and separating into two modules connected by a thether. The middle row shows Axel driving over the ledge to access a steep slope with interesting science targets. The bottom row shows how Axel can take samples on steep slopes.

References

[1] P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.

[2] S. M. LaValle and J. J. Kuffner Jr., “Randomized kinodynamic planning,” The International Journal of Robotics Research, vol. 20, no. 5, pp. 378–400, 2001.

[3] J. D. Gammell, T. D. Barfoot, and S. S. Srinivasa, “Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search,” The International Journal of Robotics Research, 2020.

[4] M. Penrose, Random Geometric Graphs. Oxford University Press, 2003.

[5] J. D. Gammell, S. S. Srinivasa, and T. D. Barfoot, “Informed sampling for asymptotically optimal path planning,” IEEE Transactions on Robotics and Automation, vol. 34, no. 4, pp. 966–984, 2018.

[6] J. Kuffner and S. LaValle, “RRT-Connect: An efficient approach to single-query path planning,” in Proceedings of the International Conference on Robotics and Automation (ICRA), vol. 2, 2000, pp. 995–1001.

[7] I. A. D. Nesnas, J. B. Matthews, P. Abad-Manterola, J. W. Burdick, J. A. Edlund, J. C. Morrison, R. D. Peters, M. M. Tanner, R. N. Miyake, B. S. Solish, and R. C. Anderson, “Axel and DuAxel rovers for the sustainable exploration of extreme terrains,” Journal of Field Robotics, vol. 29, no. 4, pp. 663–685, 2012.