# Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Sep 2018.

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

- [Train-Once Plan-Anywhere Kinodynamic Motion Planning via Diffusion Trees](https://mlsanity.com/paper/2508.21001/) (2025)
- [Lazy Rearrangement Planning in Confined Spaces](https://mlsanity.com/paper/2203.10379/) (2022)
- [Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms](https://mlsanity.com/paper/2104.04768/) (2021)
- [Provably Efficient Long-Horizon Exploration in Monte Carlo Tree Search through State Occupancy Regularization](https://mlsanity.com/paper/2407.05511/) (2024)
- [Perception Helps Planning: Facilitating Multi-Stage Lane-Level Integration via Double-Edge Structures](https://mlsanity.com/paper/2407.11644/) (2024)
- [Motion Planning with Model-Based Diffusion via Constraint Optimization and Adaptive Scheduling](https://mlsanity.com/paper/2607.14455/) (2026)
- [Learning Continuous Cost-to-Go Functions for Non-holonomic Systems](https://mlsanity.com/paper/2103.11168/) (2021)
- [Learning from Demonstration without Demonstrations](https://mlsanity.com/paper/2106.09203/) (2021)
- [Sampling-based Reactive Synthesis for Nondeterministic Hybrid Systems](https://mlsanity.com/paper/2304.06876/) (2023)

## Abstract (arXiv)

The Rapidly-exploring Random Tree (RRT) algorithm has been one of the most prevalent and popular motion-planning techniques for two decades now. Surprisingly, in spite of its centrality, there has been an active debate under which conditions RRT is probabilistically complete. We provide two new proofs of probabilistic completeness (PC) of RRT with a reduced set of assumptions. The first one for the purely geometric setting, where we only require that the solution path has a certain clearance from the obstacles. For the kinodynamic case with forward propagation of random controls and duration, we only consider in addition mild Lipschitz-continuity conditions. These proofs fill a gap in the study of RRT itself. They also lay sound foundations for a variety of more recent and alternative sampling-based methods, whose PC property relies on that of RRT. Our original publication contains an error in the analysis of the case of the kinodynamic RRT. Here, we rectify the problem by modifying the proof of Theorem 2, which, in particular, necessitated a revision of Lemma 3. Briefly, the original (and erroneous) proof of Theorem 2 used a sequence of equal-size balls. The correction uses a sequence of balls of increasing radii. We emphasize that the correction is in Lemma 3 and the proof of Theorem 2 only. The main results remain unchanged.