RRT*

• Also called: RRT star, RRT-star, optimal RRT
• Category: Planning & manipulation › Motion planning
• Tags: motion-planning, sampling-based-planning, path-planning, optimization, manipulation

An asymptotically optimal version of the Rapidly-exploring Random Tree planner that rewires its tree as it grows, so the path it returns keeps improving toward the lowest-cost one.

Definition

RRT\ (pronounced "RRT star") is a sampling-based motion planning algorithm that finds collision-free paths and, given enough samples, converges toward an optimal one. It was introduced by Sertac Karaman and Emilio Frazzoli in 2011 as an extension of the Rapidly-exploring Random Tree (RRT) algorithm proposed by Steven LaValle in 1998.

The original RRT grows a tree from the start configuration by repeatedly sampling a random point in the configuration space, finding the nearest node in the tree and extending a short step toward the sample if that motion is collision-free. RRT finds feasible paths quickly, even in high-dimensional spaces such as the joint space of a robot arm, but its paths are usually jagged and far from the shortest, and they do not improve as more samples are added.

RRT* changes two things. When a new node is added, it examines all tree nodes within a neighborhood radius and connects to the one that gives the lowest cost from the start, not simply to the nearest one. It then rewires: for each neighbor, if passing through the new node gives a cheaper path, that neighbor's parent is changed. Karaman and Frazzoli showed that with a neighborhood radius that shrinks appropriately as the tree grows, the solution cost converges to the optimum as the number of samples goes to infinity, a property called asymptotic optimality.

The price is extra computation per sample, so RRT is slower than RRT to find a first solution. Variants such as Informed RRT and BIT* focus the sampling to speed up convergence.

Why it matters

Many robots need not just any path but a good one: shorter, smoother or cheaper in energy. RRT* gives sampling-based planners, which scale to high-dimensional configuration spaces, a principled route to path quality, and it is a standard baseline in motion planning research and software.

Key applications

• Collision-free motion planning for robot arms in cluttered workspaces
• Global path planning for mobile robots and drones
• Planning in high-dimensional configuration spaces where grid search is impractical
• Generating reference paths for trajectory optimization

In practice

Robotics teams usually reach RRT through a planning library rather than writing it themselves. The Open Motion Planning Library (OMPL), which MoveIt uses for robot arms, includes RRT and several of its variants alongside RRT, RRT-Connect and PRM. A common pattern is to run RRT with a fixed time budget, take the best path found when time runs out, and then shortcut and smooth it before converting it into a time-parameterized trajectory. For mobile robots and drones, teams also use RRT on a 2D or 3D occupancy map as a global planner, choosing the planning time and step size to trade path quality against response time.

Common misconceptions

• RRT* returns the optimal path — it is asymptotically optimal, so the path cost approaches the optimum only as the number of samples grows without bound
• RRT* paths are smooth — they are piecewise linear and usually need shortcutting and smoothing before execution
• RRT* is always better than RRT — when only a feasible path is needed quickly, plain RRT or RRT-Connect is often the better choice

Who should know this

• Motion planning engineers
• Robot arm and manipulation software developers
• Autonomous drone and mobile robot developers
• Robotics students studying planning algorithms

Related technologies

• OMPL
• MoveIt
• RRT-Connect
• Informed RRT*
• BIT*
• Collision Checking

Related terms

• Motion Planning
• Probabilistic Roadmap
• Configuration Space
• Trajectory Planning

Related projects

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim
• NVIDIA Isaac GR00T: NVIDIA open foundation model for humanoid robot reasoning and skills
• OpenVLA: 7B-parameter Vision-Language-Action model for robotic manipulation
• Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
• Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design

Videos

• Path Planning with A* and RRT | Autonomous Navigation, Part 4: MATLAB