Bang-Bang Boosting of RRTs

Authors

Alexander J. LaValle, Basak Sakcak, Steven M. LaValle

Year

2022

Conference Paper

Algorithm

BB-RRT

Source

IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

Identifiers

arXiv 2210.01744 DOI 10.1109/IROS55552.2023.10341760

Abstract¶

This paper presents methods for dramatically improving the performance of sampling-based kinodynamic planners. The key component is the first-known complete, exact steering method that produces a time-optimal trajectory between any states for a vector of synchronized double integrators. This method is applied in three ways: 1) to generate RRT edges that quickly solve the two-point boundary-value problems, 2) to produce a (quasi)metric for more accurate Voronoi bias in RRTs, and 3) to iteratively time-optimize a given collision-free trajectory. Experiments are performed for state spaces with up to 2000 dimensions, resulting in improved computed trajectories and orders of magnitude computation time improvements over using ordinary metrics and constant controls.

Summary¶

Derives a complete, exact bang-bang time-optimal steering method for synchronized double integrators, using it to boost RRT performance via better BVP solving, improved Voronoi bias metrics, and post-hoc trajectory time-optimization.