AORRTC: Almost-Surely Asymptotically Optimal Planning with RRT-Connect
Tyler S. Wilson, Wil Thomason, Zachary Kingston, Jonathan Gammell
AI summary
Problem
Satisficing planners find feasible paths quickly but lack optimality guarantees, whereas almost-surely asymptotically optimal planners guarantee optimal convergence but suffer from slow initial solution times and high computational overhead.
Approach
The method applies the AO-x meta-algorithm to RRT-Connect by iteratively searching a cost-augmented space with tightening upper bounds, enabling anytime convergence to optimal solutions without sacrificing initial speed.
Key results
- Matches RRT-Connect initial solution speed
- Converges to better solutions faster than state-of-the-art a.s.a.o. planners
- Solves difficult high-DoF problems in milliseconds where other optimal planners fail
- Effective in both standard and SIMD-accelerated implementations
Why it matters
Provides a practical, high-performance planning tool for real-time robotics applications requiring both speed and solution optimality.
Abstract
Finding high-quality solutions quickly is an impor- tant objective in motion planning. This is especially true for high- degree-of-freedom robots. Satisficing planners have traditionally found feasible solutions quickly but provide no guarantees on their optimality, while almost-surely asymptotically optimal (a.s.a.o.) planners have probabilistic guarantees on their convergence to- wards an optimal solution but are more computationally expensive. This paper uses the AO-x meta-algorithm to extend the sat- isficing RRT-Connect planner to optimal planning. The resulting Asymptotically Optimal RRT-Connect (AORRTC) finds initial so- lutions in similar times as RRT-Connect and uses additional plan- ning time to converge towards the optimal solution in an anytime manner. It is proven to be probabilistically complete and a.s.a.o. AORRTC was tested with the Panda (7 DoF) and Fetch (8 DoF) robotic arms on the MotionBenchMaker dataset. These experiments show that AORRTC finds initial solutions as fast as RRT-Connect and faster than the tested state-of-the-art a.s.a.o. algorithms while converging to better solutions faster. AORRTC finds solutions to difficult high-DoF planning problems in milliseconds where the other a.s.a.o. planners could not consistently find solutions in seconds. This performance was demonstrated both with and without single instruction/multiple data (SIMD) acceleration.