Rapidly-Exploring Random Tree
Also known as: RRT, Incremental Sampling-based Algorithm
The Rapidly-Exploring Random Tree (RRT) is a motion planning algorithm that builds a tree of feasible paths by iteratively sampling random configurations in the workspace and connecting them to the nearest existing node in the tree. Introduced by LaValle in 1998, RRT is a breakthrough for high-dimensional motion planning, enabling robots to find collision-free paths in complex environments with obstacles, joint limits, and kinematic constraints.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Use RRT for motion planning in high-dimensional configuration spaces with complex obstacles (robotic arms, mobile manipulators). It is ideal for finding a single feasible path quickly, especially when the environment is cluttered and classical grid-based methods fail. RRT shines in scenarios like warehouse automation, surgical robot pathway planning, and UAV trajectory generation through 3D obstacle fields. Avoid RRT if you need optimal paths (use RRT* instead), if real-time replanning is needed (look ahead and replan can slow down), or if your configuration space has low-dimensional structure (grid-based methods may be faster).
Strengths & limitations
- Solves motion planning in high-dimensional spaces efficiently; works well in 10D-50D+ configurations.
- Probabilistically complete; if a solution exists, RRT finds one (with probability approaching 1 as iterations increase).
- No need for explicit map discretization; implicitly samples the configuration space.
- Handles kinematic constraints (joint limits, non-holonomic constraints) naturally through the extend operator.
- Simple to implement and computationally efficient; millions of samples feasible in seconds.
- Paths found are typically not optimal; often longer and more jerky than manual hand-crafted paths.
- Bias introduced by goal-biasing parameter p_goal and step size delta_q affects both convergence and path quality.
- Nearest-neighbor queries in high dimensions can become slow (curse of dimensionality for KD-trees).
- Sensitive to step size and goal probability; poor parameter choices cause slow exploration or failures.
- Does not handle dynamic obstacles; purely offline planner.
Frequently asked
How do I choose the step size delta_q?
Step size should be a balance: too small (e.g., 0.01) causes slow tree growth; too large (e.g., 10) causes many collisions and rejection. A practical heuristic is 5-10% of the configuration space range per dimension. For robotic arms, delta_q = 0.1-0.5 radians is typical. Adaptive step sizing (increasing step size in unexplored regions) can improve performance.
What is goal-biasing and how does it affect RRT?
Goal-biasing is sampling the goal configuration with probability p_goal (e.g., 0.05) instead of a random sample. This biases the tree toward the goal, speeding up path discovery. Too much goal-biasing (p_goal > 0.5) causes the tree to converge prematurely without exploring alternative paths. Typical choice: p_goal = 0.05-0.2.
Can RRT handle non-holonomic constraints (e.g., car-like robots)?
Yes, RRT naturally handles non-holonomic constraints through the extend operator. Instead of linear interpolation from q_near to q_new, use the system's dynamics or steering law to compute feasible paths. For example, use Dubins curves for a car-like robot with bounded curvature.
Why is RRT not optimal?
RRT is not optimal because it terminates upon finding the first feasible path. The first path found is usually longer and more circuitous than necessary. RRT* addresses this by maintaining a radius of neighboring nodes and rewiring the tree to improve path cost, asymptotically converging to optimal solutions.
Sources
- LaValle, S. M. (1998). Rapidly-exploring random trees: A new tool for path planning. Technical Report TR 98-11, Iowa State University. link ↗
- Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research, 30(7), 846-894. DOI: 10.1177/0278364911406761 ↗
- LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press. link ↗
How to cite this page
ScholarGate. (2026, June 3). Rapidly-Exploring Random Tree. ScholarGate. https://scholargate.app/en/control-theory/rapidly-exploring-random-tree
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Feedback LinearizationControl Theory↔ compare
- Model Predictive ControlControl Theory↔ compare
- Probabilistic RoadmapControl Theory↔ compare