# Asymptotically Optimal Planning by Feasible Kinodynamic Planning in State-Cost Space

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 May 2015.

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

- [Model Error Propagation via Learned Contraction Metrics for Safe Feedback Motion Planning of Unknown Systems](https://mlsanity.com/paper/2104.08695/) (2021)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [Trajectory Optimization of Chance-Constrained Nonlinear Stochastic Systems for Motion Planning Under Uncertainty](https://mlsanity.com/paper/2106.02801/) (2021)
- [Train-Once Plan-Anywhere Kinodynamic Motion Planning via Diffusion Trees](https://mlsanity.com/paper/2508.21001/) (2025)
- [L4KDE: Learning for KinoDynamic Tree Expansion](https://mlsanity.com/paper/2203.00975/) (2022)
- [The State of Robot Motion Generation](https://mlsanity.com/paper/2410.12172/) (2024)
- [Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization](https://mlsanity.com/paper/2407.05511/) (2024)
- [Learning Continuous Cost-to-Go Functions for Non-holonomic Systems](https://mlsanity.com/paper/2103.11168/) (2021)

## Abstract (arXiv)

This paper presents an equivalence between feasible kinodynamic planning and optimal kinodynamic planning, in that any optimal planning problem can be transformed into a series of feasible planning problems in a state-cost space whose solutions approach the optimum. This transformation gives rise to a meta-algorithm that produces an asymptotically optimal planner, given any feasible kinodynamic planner as a subroutine. The meta-algorithm is proven to be asymptotically optimal, and a formula is derived relating expected running time and solution suboptimality. It is directly applicable to a wide range of optimal planning problems because it does not resort to the use of steering functions or numerical boundary-value problem solvers. On a set of benchmark problems, it is demonstrated to perform, using the EST and RRT algorithms as subroutines, at a superior or comparable level to related planners.