Overview
RRT-Connect is a sampling-based motion planning method for motion planning. It works by growing two random trees toward each other until they connect.
ExtendedSource checked
RRT-Connect
RRT-Connect addresses motion planning by growing two random trees toward each other until they connect.
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
- 5
- Code example
- Ready
- Visualization
- Ready
- Aliases
- RRT Connect
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-Connect when solving motion planning and you want to benefit from growing two random trees toward each other until they connect.
- Choose it when O(n log n) average/worst-case time and O(n) memory match your workload profile.
- Prefer it over RRT* or Lazy PRM 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 growing two random trees toward each other until they connect.
- Maintains key invariants across motion planning, sampling-based motion planning, random sampling.
Use Cases
- Production and research workloads requiring motion planning via growing two random trees toward each other until they connect.
- Sampling-Based Motion Planning pipelines where O(n log n) time and O(n) space fit system constraints.
- Engineering comparisons against RRT* and Lazy PRM 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-Connect.
- 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 growing two random trees toward each other until they connect.
- 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-Connect invariants
- Explanation
- RRT-Connect processes the input by growing two random trees toward each other until they connect, 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 growing two random trees toward each other until they connect 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-Connect.
pathfinding-mechanismNotes
RRT-Connect operates in O(n log n) time and O(n) space within the Sampling-Based Motion Planning family. Often compared with RRT* and Lazy PRM.
Sources (2)
What each reference supports for this entry.
RRT-Connect
PaperOriginal RRT-Connect reference for bidirectional rapidly-exploring random-tree planning.
Open sourcePlanning Algorithms
BookMotion-planning reference supporting RRT-Connect 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-Connect and Lazy PRM are practical alternatives within motion planning, with different assumptions and tradeoffs.
Compare with thisRelationships
View full relationship pageAlternative toRRT*
RRT-Connect and RRT* are practical alternatives within motion planning, with different assumptions and tradeoffs.
Alternative toLazy PRM
RRT-Connect and Lazy PRM are practical alternatives within motion planning, with different assumptions and tradeoffs.
Alternative toConfiguration-Space Obstacle Construction
RRT-Connect and Configuration-Space Obstacle Construction are practical alternatives within motion planning, with different assumptions and tradeoffs.
Related Algorithms
Tags
PathfindingGraphRandomness