Overview
RRT* is a sampling-based motion planning method for motion planning. It works by rewiring a rapidly-exploring random tree to improve path cost over time.
ExtendedSource checked
RRT*
RRT* addresses motion planning by rewiring a rapidly-exploring random tree to improve path cost over time.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Pathfinding
- Difficulty
- Intermediate
- Family
- Sampling-Based Motion Planning
- Tier
- Extended
- Status
- Verified
- Review
- Source Checked
- Sources
- 2
- Formulas
- 0
- Relationships
- 6
- Code example
- Ready
- Visualization
- Ready
- Aliases
- RRT star
Core Concepts
motion planningsampling-based motion planningrandom samplingpathfinding
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n)
Average
O(n log n)
Worst
O(n^2)
Space
O(n)
When to Use
- Use RRT* when solving motion planning and you want to benefit from rewiring a rapidly-exploring random tree to improve path cost over time.
- Choose it when O(n log n) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over Lazy PRM or RRT-Connect when the problem structure favors motion planning.
When Not to Use
- Avoid when path costs or obstacles change in ways the method cannot update efficiently.
- Avoid when approximate paths are unacceptable and the method does not guarantee optimality.
What It Does
- Computes motion planning within Sampling-Based Motion Planning workloads (O(n log n) time, O(n) space).
- Works by rewiring a rapidly-exploring random tree to improve path cost over time.
- Maintains key invariants across motion planning, sampling-based motion planning, random sampling.
Use Cases
- Production and research workloads requiring motion planning via rewiring a rapidly-exploring random tree to improve path cost over time.
- Sampling-Based Motion Planning pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against Lazy PRM and RRT-Connect when tuning motion planning.
Inputs
- Start state q_init, goal region Q_goal, and collision-check oracle in configuration space
Outputs
- Collision-free trajectory or roadmap connecting q_init to Q_goal
Pseudocode
- 1.Initialize the search space, start/goal states, and cost/priority tables for RRT*.
- 2.Insert the initial state into the open frontier or roadmap with its baseline cost and heuristic estimate.
- 3.Expand or sample candidate transitions by rewiring a rapidly-exploring random tree to improve path cost over time.
- 4.Update path costs, parent pointers, or conflict constraints whenever an improved trajectory is found.
- 5.Reconstruct and return the collision-free path from start to goal once the termination criterion holds.
Canonical Example
- Input
- Start state q_init, goal region Q_goal, and collision-check oracle in configuration space configured for a representative motion planning test case
- Output
- Collision-free trajectory or roadmap connecting q_init to Q_goal satisfying RRT* invariants
- Explanation
- RRT* processes the input by rewiring a rapidly-exploring random tree to improve path cost over time, tracking motion planning and sampling-based motion planning to produce the verified motion planning result.
Implementation Notes
- Separate search state from world state so changes can be tested.
- Use small maps with known optimal answers before large scenarios.
- Track whether returned paths are optimal, bounded, or heuristic.
Common Pitfalls
- Using an inadmissible heuristic where optimality is expected.
- Ignoring dynamic obstacles, time-dependent costs, or changing edge weights.
- Testing only open grids and missing narrow-passage cases.
Interactive Mechanism Walkthrough
2D Grid Wavefront & TrajectoryShow rewiring a rapidly-exploring random tree to improve path cost over time on a small motion planning example.
S
#
#
#
#
#
#
#
G
Step 1 of 5: Initialize the search space, start/goal states, and cost/priority tables for RRT*.
pathfinding-mechanismNotes
RRT* operates in O(n log n) time and O(n) space within the Sampling-Based Motion Planning family. Often compared with Lazy PRM and RRT-Connect.
Sources (2)
What each reference supports for this entry.
Sampling-Based Algorithms for Optimal Motion Planning
PaperOriginal RRT* reference for asymptotically optimal rewiring in sampling-based planning.
Open sourcePlanning Algorithms
BookMotion-planning reference supporting RRT* roadmap construction, sampling, visibility, or configuration-space search.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Alternative toLazy PRM
Pathfinding · Extended
RRT* and Lazy PRM are practical alternatives within motion planning, with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toLazy PRM
RRT* and Lazy PRM are practical alternatives within motion planning, with different assumptions and tradeoffs.
Alternative toRRT-Connect
RRT* and RRT-Connect are practical alternatives within motion planning, with different assumptions and tradeoffs.
Alternative toConfiguration-Space Obstacle Construction
RRT* and Configuration-Space Obstacle Construction are practical alternatives within motion planning, with different assumptions and tradeoffs.
Related Algorithms
Tags
PathfindingGraphRandomness