# Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space

arXiv: https://arxiv.org/abs/1909.05569 · HTML: https://mlsanity.com/paper/1909.05569/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Sep 2019.

## Built on by (most cited first, 2 of 2)

- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [Train-Once Plan-Anywhere Kinodynamic Motion Planning via Diffusion Trees](https://mlsanity.com/paper/2508.21001/) (2025)

## Abstract (arXiv)

We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm---a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AO-RRT. We also discuss practical aspects of AO-RRT and present experimental comparisons of variants of the algorithm.