How to Learn RRT and RRT*: Configuration Spaces, Voronoi Bias, Rewiring and Asymptotically Optimal Motion Planning

Wait, What?

A planner can explore a huge continuous space by repeatedly aiming at random points—and the randomness can create useful direction rather than chaos.

Rapidly-exploring Random Trees, usually called RRTs, are a landmark family of sampling-based motion-planning algorithms. They are especially useful when the search space is continuous, high-dimensional, constrained by obstacles, or difficult to grid finely enough for ordinary graph search.

The important lesson is not “random search works.” The lesson is that geometry, nearest-neighbour selection and incremental extension combine to create a strong exploration bias toward regions that have not yet been covered.

Quick Answer

Learn RRT in this order: configuration space → free versus obstructed states → random sampling → nearest node → steering/extension → collision checking → Voronoi bias → probabilistic completeness → RRT-Connect → RRT* parent choice → rewiring → asymptotic optimality → production bottlenecks.

1. First Decide What a “Point” Means

For a mobile robot on a flat floor, a state might be position and heading: (x, y, θ). For a robot arm, a state may be a vector of joint angles. For a dynamic system, the state may also include velocity or other variables.

The set of all possible states is the configuration space or, more generally, the state space. Motion planning then becomes a geometric search problem: find a continuous path from a start state to a goal state while remaining in the valid region.

2. Obstacles Live in Configuration Space Too

A robot does not move as a mathematical point in the physical world. Its shape matters. Collision checking therefore asks whether a configuration places any part of the robot in collision. Conceptually, planning divides the space into:

• C-free: valid configurations.
• C-obstacle: invalid or colliding configurations.

This is one reason motion planning becomes difficult. Even when the physical scene looks simple, the corresponding configuration-space obstacles may be high-dimensional and geometrically complicated.

3. The Basic RRT Loop Is Surprisingly Small

tree = {start}

repeat:
    q_rand = sample_state()
    q_near = nearest(tree, q_rand)
    q_new  = steer(q_near, q_rand, step_size)

    if motion_is_collision_free(q_near, q_new):
        add q_new to tree with parent q_near

    if q_new reaches goal condition:
        return path by following parents

The algorithm is simple enough to code quickly. Understanding why it explores well takes more thought.

4. Random Sampling Does Not Mean Random Motion

A random sample is used as a directional target. The tree does not usually jump directly to it. Instead, the nearest existing tree node is selected, and the tree extends a controlled distance toward the sample.

This distinction matters. RRT is an incremental search structure, not a bag of random disconnected points.

5. Voronoi Bias Explains the Rapid Exploration

Imagine partitioning the search space according to which existing tree node is nearest. Nodes on the frontier often own large Voronoi regions because fewer other nodes are nearby. A uniformly random sample is therefore more likely to fall into those large regions, causing frontier nodes to be selected more often.

That creates an implicit exploration pressure toward unvisited space. No explicit frontier score is needed. The geometry of nearest-neighbour sampling does the work.

6. “Steer” Is a Contract, Not Always a Straight Line

For a holonomic point robot, steering may simply interpolate along a straight segment. For a car-like robot, aircraft, drone or dynamically constrained system, the local motion must obey kinematics or dynamics.

Professional implementations therefore separate the planner from the state-propagation and collision-checking machinery. If the steering operation invents physically impossible motion, the planner can return a path that is mathematically connected but operationally meaningless.

7. Collision Checking Often Dominates Runtime

A beginner may look at the nearest-neighbour search and assume it is the expensive part. In many real planning systems, collision or validity checking consumes a very large fraction of the time. A planner may need to test many intermediate states along every attempted edge.

This leads to a broader algorithm-engineering lesson: asymptotic complexity of the visible data structure does not automatically identify the practical bottleneck.

8. Step Size Changes the Personality of the Search

A very small extension step explores carefully but may require many nodes. A very large step can reduce node count but may repeatedly collide with obstacles or miss narrow passages. There is no universally best step size independent of geometry, scale and dynamics.

A useful learning experiment is to hold the random seed fixed, vary only the step size, and compare number of nodes, collision checks, time to first solution and path quality.

9. Goal Bias Is Helpful but Easy to Overuse

Instead of sampling uniformly every time, an implementation may sometimes sample the goal directly. This can accelerate convergence when progress toward the goal is possible. But too much goal bias can make the search repeatedly attack a blocked region instead of exploring alternatives.

The principle is general: a heuristic should guide exploration without erasing the diversity that made the search robust.

10. Probabilistic Completeness Is Not a Promise of Fast Success

Under suitable assumptions, RRT-style sampling can be probabilistically complete: if a feasible path exists, the probability that the planner eventually finds one approaches one as sampling continues.

That is not the same as deterministic completeness, and it does not tell you how long a difficult narrow-passage problem will take. Always distinguish the type of guarantee from the practical runtime distribution.

11. The Original RRT Does Not Optimise Path Cost

A basic RRT is very good at finding feasible motion, but the first route can be long or awkward. More importantly, simply allowing an ordinary RRT to grow indefinitely does not in general make its best path converge to the optimal path.

This limitation motivated the RRT* family.

12. RRT* Adds Two Essential Ideas

RRT* keeps the sampling-and-extension spirit of RRT but changes how a new node joins the tree:

1. Choose the best parent among nearby nodes, not merely the nearest node.
2. After adding the node, rewire nearby nodes through it when that reduces their path cost.

The tree therefore improves its structure as it becomes denser.

13. Parent Selection Turns Local Geometry Into Cost-Aware Search

q_near_set = nearby_nodes(tree, q_new)
parent = feasible node in q_near_set
         minimizing cost(node) + edge_cost(node, q_new)
add q_new with that parent

A node that is geometrically closest is not always the cheapest predecessor. If another nearby node already has a much better cost-to-come, connecting through it can lower the total path cost.

14. Rewiring Is the Key Structural Improvement

for q in nearby_nodes(tree, q_new):
    if edge(q_new, q) is collision-free
       and cost(q_new) + edge_cost(q_new, q) < cost(q):
        change q.parent to q_new
        update descendant costs

Rewiring lets later samples repair earlier choices. This is a profound difference from many one-pass tree searches: the tree is not merely growing; it is reorganising itself toward lower-cost paths.

15. Asymptotic Optimality Needs Precise Conditions

Karaman and Frazzoli introduced RRT* and proved asymptotic optimality under formal conditions: as the number of samples grows, the best path cost converges almost surely toward the optimum. Later work revisited technical details of the proof and refined the required connection-radius analysis.

For learners, the key point is not to recite a radius formula from memory. It is to understand why the neighbourhood must shrink slowly enough to preserve useful connections while the sample set becomes dense.

16. RRT-Connect Solves a Different Practical Job

RRT-Connect grows trees from both the start and the goal and aggressively tries to connect them. It is a widely used approach for quickly finding a feasible path in single-query planning problems.

Do not collapse RRT-Connect and RRT* into one idea. RRT-Connect emphasizes rapid feasible connection; RRT* emphasizes asymptotic path-quality improvement.

17. Nearest-Neighbour Search Becomes an Engineering Problem

The simple pseudocode scans every node to find the nearest one, costing O(n) per query. Larger planners commonly use spatial data structures or specialised nearest-neighbour libraries. But the best structure depends on state-space dimension, metric cost, update rate and whether approximate neighbours are acceptable.

High-dimensional nearest-neighbour search can itself become difficult. A data structure that is excellent in two dimensions may degrade badly as dimension rises.

18. Metrics Must Match the State Space

Euclidean distance is not automatically the right measure. Angles wrap around. Joint spaces have limits. Some dimensions may have different units or physical significance. Dynamic systems may need cost functions related to control effort or time rather than straight geometric distance.

A planner is only as meaningful as its definitions of distance, local motion, validity and cost.

19. Benchmark More Than “Did It Find a Path?”

For stochastic planners, one run can be misleading. Record distributions over repeated seeded trials:

• time to first feasible path,
• best path cost versus time,
• number of collision checks,
• number of states and edges,
• success rate within a fixed budget,
• memory use,
• sensitivity to step size, goal bias and neighbourhood settings.

Report the random seed and environment so that failures can be reproduced.

20. Professional Variants Are About Better Allocation of Search

Modern sampling-based planning includes informed sampling, batch methods, bidirectional methods and many other refinements. Once a solution exists, for example, an informed planner may concentrate sampling in regions that can still improve the current best cost.

Learn these only after ordinary RRT and RRT* are clear. Otherwise the learner sees a zoo of planner names without understanding the shared search machinery.

21. Common Failure States

• Thinking an RRT is just random points instead of an incrementally connected search tree.
• Using straight-line steering for a system that cannot execute straight-line state changes.
• Checking only endpoints for collision while the edge passes through an obstacle.
• Calling a planner “optimal” because its path looks short.
• Confusing probabilistic completeness with deterministic success within a deadline.
• Setting an extreme goal bias that destroys exploration.
• Using a distance metric that ignores state topology or scale.
• Comparing stochastic planners from a single run.
• Ignoring collision-check cost while optimising only tree operations.

22. Practice Ladder: Beginner to Professional

• Beginner: grow a 2D RRT by hand for ten samples and mark which existing node owns each sample as its nearest neighbour.
• Foundation: implement point-robot RRT with segment collision checking and a fixed random seed.
• Intermediate: add goal bias and measure how it changes search behaviour in open space and around barriers.
• Advanced: implement RRT* parent selection and rewiring; plot best path cost as the number of samples increases.
• Professional: separate sampler, metric, nearest-neighbour structure, steering, validity checking and cost model into explicit interfaces; benchmark repeated trials.
• Transfer: explain why RRT* can improve path cost over time while ordinary RRT may remain stuck with structurally poor parent choices.

Learning Hall Boundary

This article owns continuous and high-dimensional sampling-based motion planning with RRT, RRT-Connect and RRT*. It does not replace the site’s separate shortest-path, grid-pathfinding, dynamic-replanning, computational-geometry or general graph-search teaching jobs. In particular, discrete pathfinding algorithms answer a different problem from configuration-space motion planning.

Evidence Boundary

Steven M. LaValle introduced the RRT in the 1998 technical report Rapidly-Exploring Random Trees: A New Tool for Path Planning. LaValle’s open Planning Algorithms text develops sampling-based motion planning and configuration-space reasoning. Kuffner and LaValle’s RRT-Connect work addressed efficient bidirectional single-query planning. Karaman and Frazzoli’s 2011 paper, Sampling-based Algorithms for Optimal Motion Planning, introduced PRM* and RRT* and formalised asymptotic optimality. Solovey, Janson, Schmerling, Frazzoli and Pavone later revisited the RRT* optimality proof and refined its technical analysis. Current OMPL documentation includes production implementations of RRT-family planners and is useful for seeing how theoretical parameters become software interfaces.

Professional rule: you understand RRT-family planning when you can explain the exploration bias geometrically, separate feasibility from optimality, and identify which practical costs—collision checks, nearest neighbours, steering and metric design—control performance in the system you actually have.