# Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2014.

## Built on by (most cited first, 30 of 50)

- [Habitat 2.0: Training Home Assistants to Rearrange their Habitat](https://mlsanity.com/paper/2106.14405/) (2021)
- [Creative Robot Tool Use with Large Language Models](https://mlsanity.com/paper/2310.13065/) (2023)
- [Potential Based Diffusion Motion Planning](https://mlsanity.com/paper/2407.06169/) (2024)
- [Motion Planning Diffusion: Learning and Adapting Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2412.19948/) (2024)
- [NTFields: Neural Time Fields for Physics-Informed Robot Motion Planning](https://mlsanity.com/paper/2210.00120/) (2022)
- [A Comprehensive Review of Digital Twin -- Part 2: Roles of Uncertainty Quantification and Optimization, a Battery Digital Twin, and Perspectives](https://mlsanity.com/paper/2208.12904/) (2022)
- [Neuro-algorithmic Policies enable Fast Combinatorial Generalization](https://mlsanity.com/paper/2102.07456/) (2021)
- [Motion Planning Transformers: A Motion Planning Framework for Mobile Robots](https://mlsanity.com/paper/2106.02791/) (2021)
- [Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning](https://mlsanity.com/paper/2508.20095/) (2025)
- [Progressive Learning for Physics-informed Neural Motion Planning](https://mlsanity.com/paper/2306.00616/) (2023)
- [Learning Sampling Dictionaries for Efficient and Generalizable Robot Motion Planning with Transformers](https://mlsanity.com/paper/2306.00851/) (2023)
- [Obstacle Aware Sampling for Path Planning](https://mlsanity.com/paper/2203.04075/) (2022)
- [Learning Forward Dynamics Model and Informed Trajectory Sampler for Safe Quadruped Navigation](https://mlsanity.com/paper/2204.08647/) (2022)
- [Recent Advancements in Deep Learning Applications and Methods for Autonomous Navigation: A Comprehensive Review](https://mlsanity.com/paper/2302.11089/) (2023)
- [VLM-RRT: Vision Language Model Guided RRT Search for Autonomous UAV Navigation](https://mlsanity.com/paper/2505.23267/) (2025)
- [SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots](https://mlsanity.com/paper/2108.01262/) (2021)
- [Neural Potential Field for Obstacle-Aware Local Motion Planning](https://mlsanity.com/paper/2310.16362/) (2023)
- [Non-differentiable Reward Optimization for Diffusion-based Autonomous Motion Planning](https://mlsanity.com/paper/2507.12977/) (2025)
- [Robot Motion Planning as Video Prediction: A Spatio-Temporal Neural Network-based Motion Planner](https://mlsanity.com/paper/2208.11287/) (2022)
- [Planning and Learning: Path-Planning for Autonomous Vehicles, a Review of the Literature](https://mlsanity.com/paper/2207.13181/) (2022)
- [Handling Long and Richly Constrained Tasks through Constrained Hierarchical Reinforcement Learning](https://mlsanity.com/paper/2302.10639/) (2023)
- [Discovering Multiple Algorithm Configurations](https://mlsanity.com/paper/2303.07434/) (2023)
- [Transformer-Enhanced Motion Planner: Attention-Guided Sampling for State-Specific Decision Making](https://mlsanity.com/paper/2404.19403/) (2024)
- [LLM-Advisor: An LLM Advisor for Cost-efficient Path Planning across Multiple Terrains](https://mlsanity.com/paper/2503.01236/) (2025)
- [aUToPath: Unified Planning and Control for Autonomous Vehicles in Urban Environments Using Hybrid Lattice and Free-Space Search](https://mlsanity.com/paper/2505.09475/) (2025)
- ["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)
- [DiffSlack: Learning under Nonlinear Inequality Constraints via Learnable Slack Variables](https://mlsanity.com/paper/2606.05247/) (2026)
- [qRRT: Quality-Biased Incremental RRT for Optimal Motion Planning in Non-Holonomic Systems](https://mlsanity.com/paper/2101.02635/) (2021)
- [Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions](https://mlsanity.com/paper/2205.04548/) (2022)

## Abstract (arXiv)

Rapidly-exploring random trees (RRTs) are popular in motion planning because they find solutions efficiently to single-query problems. Optimal RRTs (RRT*s) extend RRTs to the problem of finding the optimal solution, but in doing so asymptotically find the optimal path from the initial state to every state in the planning domain. This behaviour is not only inefficient but also inconsistent with their single-query nature. For problems seeking to minimize path length, the subset of states that can improve a solution can be described by a prolate hyperspheroid. We show that unless this subset is sampled directly, the probability of improving a solution becomes arbitrarily small in large worlds or high state dimensions. In this paper, we present an exact method to focus the search by directly sampling this subset. The advantages of the presented sampling technique are demonstrated with a new algorithm, Informed RRT*. This method retains the same probabilistic guarantees on completeness and optimality as RRT* while improving the convergence rate and final solution quality. We present the algorithm as a simple modification to RRT* that could be further extended by more advanced path-planning algorithms. We show experimentally that it outperforms RRT* in rate of convergence, final solution cost, and ability to find difficult passages while demonstrating less dependence on the state dimension and range of the planning problem.