Bang-Bang Boosting of RRTs

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

Published: 2022 (Conference Paper)

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

Algorithm: BB-RRT

arXiv: 2210.01744

DOI: 10.1109/IROS55552.2023.10341760

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.

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.

Links

Primary

Paper arxiv.org

Standard

arXiv Abstract 2210.01744 arXiv PDF 2210.01744 arXiv HTML 2210.01744 DOI 10.1109/IROS55552.2023.10341760

Alternate

ieeexplore.ieee.org ieeexplore.ieee.org

Tags

• Kinodynamic planning

• RRT

• Bang-bang control

• Steering function

• Double integrator

• Time-optimal control