# Asymptotically near-optimal RRT for fast, high-quality, motion planning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Aug 2013.

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

- [NeuPAN: Direct Point Robot Navigation with End-to-End Model-based Learning](https://mlsanity.com/paper/2403.06828/) (2024)
- [ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Exploration](https://mlsanity.com/paper/2312.13385/) (2023)
- [Unified Control Framework for Real-Time Interception and Obstacle Avoidance of Fast-Moving Objects with Diffusion Variational Autoencoder](https://mlsanity.com/paper/2209.13628/) (2022)
- ["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)
- [T*varepsilon -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems](https://mlsanity.com/paper/2204.01673/) (2022)
- [CBAGAN-RRT: Convolutional Block Attention Generative Adversarial Network for Sampling-Based Path Planning](https://mlsanity.com/paper/2305.10442/) (2023)

## Abstract (arXiv)

We present Lower Bound Tree-RRT (LBT-RRT), a single-query sampling-based algorithm that is asymptotically near-optimal. Namely, the solution extracted from LBT-RRT converges to a solution that is within an approximation factor of 1+epsilon of the optimal solution. Our algorithm allows for a continuous interpolation between the fast RRT algorithm and the asymptotically optimal RRT* and RRG algorithms. When the approximation factor is 1 (i.e., no approximation is allowed), LBT-RRT behaves like RRG. When the approximation factor is unbounded, LBT-RRT behaves like RRT. In between, LBT-RRT is shown to produce paths that have higher quality than RRT would produce and run faster than RRT* would run. This is done by maintaining a tree which is a sub-graph of the RRG roadmap and a second, auxiliary graph, which we call the lower-bound graph. The combination of the two roadmaps, which is faster to maintain than the roadmap maintained by RRT*, efficiently guarantees asymptotic near-optimality. We suggest to use LBT-RRT for high-quality, anytime motion planning. We demonstrate the performance of the algorithm for scenarios ranging from 3 to 12 degrees of freedom and show that even for small approximation factors, the algorithm produces high-quality solutions (comparable to RRG and RRT*) with little running-time overhead when compared to RRT.