# Asymptotically Optimal Sampling-based Kinodynamic Planning

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2014.

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

- [Motion Planning Transformers: A Motion Planning Framework for Mobile Robots](https://mlsanity.com/paper/2106.02791/) (2021)
- [Fast Kinodynamic Planning on the Constraint Manifold with Deep Neural Networks](https://mlsanity.com/paper/2301.04330/) (2023)
- [MPC-MPNet: Model-Predictive Motion Planning Networks for Fast, Near-Optimal Planning under Kinodynamic Constraints](https://mlsanity.com/paper/2101.06798/) (2021)
- [Constrained Stein Variational Trajectory Optimization](https://mlsanity.com/paper/2308.12110/) (2023)
- [Model-free Neural Lyapunov Control for Safe Robot Navigation](https://mlsanity.com/paper/2203.01190/) (2022)
- [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)
- [Informed sampling-based trajectory planner for automated driving in dynamic urban environments](https://mlsanity.com/paper/2210.02335/) (2022)
- [Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization](https://mlsanity.com/paper/2407.05511/) (2024)
- ["Don't Do That!": Guiding Embodied Systems through Large Language Model-based Constraint Generation](https://mlsanity.com/paper/2506.04500/) (2025)
- [Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities](https://mlsanity.com/paper/2603.24318/) (2026)
- [Learning Continuous Cost-to-Go Functions for Non-holonomic Systems](https://mlsanity.com/paper/2103.11168/) (2021)
- [Accelerating db-A* for Kinodynamic Motion Planning Using Diffusion](https://mlsanity.com/paper/2503.05539/) (2025)
- [ActivePusher: Active Learning and Planning with Residual Physics for Nonprehensile Manipulation](https://mlsanity.com/paper/2506.04646/) (2025)
- [GRACE: A Unified 2D Multi-Robot Path Planning Simulator & Benchmark for Grid, Roadmap, And Continuous Environments](https://mlsanity.com/paper/2603.10858/) (2026)

## Abstract (arXiv)

Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.