Rapidly-exploring random tree
- Also called: RRT
- Category: Planning & manipulation › Motion planning
- Tags: motion-planning, sampling-based-planning, path-planning, kinodynamic-planning, collision-avoidance
A sampling-based motion planner that grows a tree from the start state by repeatedly sampling a random state and extending the nearest tree node toward it, quickly exploring large spaces.
Definition
The rapidly-exploring random tree (RRT) is a sampling-based algorithm for finding a feasible path from a start state to a goal region. It was introduced by Steven LaValle in 1998. The algorithm grows a tree rooted at the start: at each iteration it samples a random state in the configuration or state space, finds the nearest node in the tree, and extends from that node a short distance toward the sample. If the extension is collision-free, the new state is added to the tree. The search ends when the tree reaches the goal region, and the path is read back through each node's parent.
The key property is the Voronoi bias. Nodes on the frontier of the tree have the largest Voronoi regions, so they are the most likely to be nearest to a random sample, and the tree is pulled toward unexplored space instead of filling regions it has already covered. This makes RRT effective in high-dimensional spaces such as the joint space of a robot arm. RRT is probabilistically complete: if a solution exists, the probability of finding it approaches one as the number of samples grows. Common improvements include goal biasing, where a fraction of the samples are drawn at the goal, and RRT-Connect, which grows trees from both the start and the goal and tries to join them greedily.
Because the extend step only needs a way to move from one state toward another, RRT also handles kinodynamic planning, where the robot cannot move in straight lines through its state space. The extend step then applies sampled or optimized controls and simulates the dynamics forward, as in LaValle and Kuffner's kinodynamic RRT, or chains precomputed motion primitives. This makes it useful for vehicles, legged robots and contact-rich manipulation, where the distance metric and extend step must be designed around the dynamics. RRT's paths are typically jagged and not optimal, and adding more samples does not improve a path once found. RRT\ adds a choose-parent step and a rewiring step that reconnects nearby nodes whenever a cheaper route exists, which makes it asymptotically optimal at the cost of more computation per sample. When a feasible path is needed quickly, plain RRT or RRT-Connect followed by shortcutting and smoothing remains a common choice.
Why it matters
RRT made motion planning practical for robots with many degrees of freedom and for systems with dynamics, and it remains a default planner in libraries such as OMPL and MoveIt. Many later planners, including RRT*, are built on its structure.
Key applications
- Manipulator motion planning in cluttered workspaces
- Kinodynamic planning for cars, drones and legged robots
- Contact-rich manipulation planning with custom distance metrics
- Planning over motion primitive graphs for locomotion
- Exploration of unknown environments
In practice
A team configuring MoveIt for a seven-axis arm that picks items from shelves uses OMPL's RRT-Connect as the default planner. Collision checking uses the robot model and an octree built from a depth camera. They set the planning time limit and the extension step size relative to the clearance of the shelf openings, then post-process each path with shortcutting and time parameterization so the arm moves smoothly. When planning struggles to reach deep into narrow shelf bins, they increase goal biasing or try a planner with better narrow-passage behavior, and for repeated queries in a static cell they consider a probabilistic roadmap instead.
Common misconceptions
- RRT finds the shortest path — it finds a feasible path; RRT* or post-processing is needed for good path quality
- RRT is guaranteed to find a path within a set time — it is probabilistically complete, so it finds a path with probability approaching one as sampling continues, and narrow passages can take a long time
- RRT* is always the better choice — it improves paths over time but is slower to a first solution; RRT-Connect with smoothing is often preferred when speed matters
Who should know this
- Motion planning engineers
- Manipulation and mobile robot developers using MoveIt or OMPL
- Autonomous vehicle and drone planning engineers
- Robotics students
Related technologies
- OMPL
- MoveIt
- RRT-Connect
- Kinodynamic RRT
- Informed RRT*
- Path Shortcutting
Related terms
Related projects
- Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
- ROS Motion Planning: One repo implementing 40+ classic and learning-based robot path planners as ROS plugins
- OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
- MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
- PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
- mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Videos
- Motion Planning: Rapidly Exploring Random Trees (RRT): Algorithm Implementation Step by Step!: VDEngineering