ExtendedSource checked

Rapidly-Exploring Random Tree

Builds a tree of random feasible motions that quickly explores open space.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Pathfinding
Difficulty: Advanced
Family: Sampling-Based Planning
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 1
Relationships: 2
Code example: Ready
Visualization: Ready
Aliases: RRT

Overview

Rapidly-Exploring Random Tree samples states, connects each sample toward the nearest existing tree node, and stops when the tree reaches a goal region.

Core Concepts

random samplingnearest neighbormotion primitiveconfiguration space

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(n log n)

Worst

O(n^2)

Space

O(n)

When to Use

Use when route planning needs random sampling.
Use when the input matches the assumptions behind sampling-Based Planning.

When Not to Use

Avoid when edge costs or movement rules change faster than the search can update them.
Avoid when a simpler algorithm gives the required result with less setup.

What It Does

Builds a tree of random feasible motions that quickly explores open space
Uses random sampling and nearest neighbor to guide the work.
Produces path.

Use Cases

Route planning
Game navigation
Robotics motion planning

Inputs

Search graph or state space
Start state
Goal state or target set

Outputs

Path
Distance estimate
Search frontier state

Key Formulas (1)

Nearest extension

x_new = steer(nearest(tree, x_rand), x_rand)

x_new = steer(nearest(tree, x_rand), x_rand)

Adds a new state by moving from the nearest tree node toward a random sample.

Pseudocode

1.Prepare the inputs and state needed for Rapidly-Exploring Random Tree.
2.Apply the random sampling step while the stopping condition has not been met.
3.Update intermediate state and discard invalid candidates.
4.Return path.

Canonical Example

Input: Rapidly-Exploring Random Tree input with a small representative case
Output: Path
Explanation: Rapidly-Exploring Random Tree applies random sampling to produce path.

Implementation Notes

Store predecessor information separately from distance or priority values.
Keep the random sampling step separate enough to test independently.

Common Pitfalls

Using a heuristic or preprocessed data that does not match the actual cost model breaks path quality.
Forgetting to check edge cases can make Rapidly-Exploring Random Tree look correct on only ideal inputs.