Skip to content

RRT* Algorithm (Rapidly-exploring Random Tree Star)

◀ Go to RRT

Go to Q-Learning ▶

RRT* is a sampling-based path planning algorithm that keeps the exploration behavior of RRT, but continuously improves path quality by optimizing local tree connections.

Review RRT First

If you want a quick refresher before continuing, review the RRT module here:

Review RRT

Quick Review: Core RRT Idea

RRT builds a tree by repeating these steps:

  1. Randomly sample a point in free space.
  2. Find the nearest existing tree node.
  3. Steer from that node toward the sample by a fixed step.
  4. Add the new node if the edge is collision-free.

This process is very good at rapidly exploring complicated spaces and finding a feasible path.

Why Move From RRT to RRT*?

RRT is great at quickly finding a feasible path in complex spaces, but it does not explicitly optimize path cost.
In basic RRT, each new node is typically attached to the nearest node, which can lock in a poor local choice early.

As a result, RRT often returns a valid route that is:

  1. Longer than needed.
  2. Not smooth.
  3. Not close to minimum cost.

RRT* addresses this limitation with local cost optimization using rewiring:

  1. Choose a better parent for the new node (not just nearest).
  2. Re-check nearby nodes and reconnect them if the new node gives a lower-cost path.

In practice:

  1. RRT: finds a path quickly.
  2. RRT*: keeps improving that path as more samples are added.

RRT* is asymptotically optimal, meaning that with enough samples, the solution converges toward the optimal path.

The Core Difference: Rewire

When a new node \(x_{new}\) is added to our tree, RRT* additionally performs two checks in a local neighborhood.

Step 1: Find the Best Parent for the New Node

For a sampled node \(x_{new}\), consider nearby nodes \(x_i\) in a radius \(r_n\).
Among collision-free candidates, select the parent that minimizes:

\[ J(x_i) + \text{dist}(x_i, x_{new}) \]

where \(J(x_i)\) is the current cost-to-come from start to node \(x_i\).

This is different from basic RRT, which always connects \(x_{new}\) to the nearest node only.

Step 2: Rewire Nearby Nodes Through the New Node

After choosing the parent of \(x_{new}\), check each nearby node \(x_{near}\) within radius \(r_n\).
If routing through \(x_{new}\) is cheaper, then change its parent:

\[ J(x_{new}) + \text{dist}(x_{new}, x_{near}) < J(x_{near}) \]

If true (and collision-free), rewire \(x_{near}\) to \(x_{new}\).

This is the key reason RRT* improves path quality over time.

Cost Function and Radius (Used by Rewire)

Rewiring decisions depend on two things:

  1. A path cost function to compare alternatives.
  2. A near-node radius to decide which nodes are candidates for parent selection and rewiring.

Defining the Cost Function in RRT*

In RRT, each node stores a *cost-to-come** from the start:

\[ J(x) = J(\text{parent}(x)) + c(\text{parent}(x), x) \]

Here, \(c(a,b)\) is the edge cost from node \(a\) to node \(b\).
The total path cost is the sum of all edge costs along the branch.

How to Choose the Near-Node Update Radius

RRT* uses a neighborhood radius when selecting parent and rewiring.
A common theoretical form is:

\[ r_n = \min\left\{\eta,\ \gamma\left(\frac{\log n}{n}\right)^{1/d}\right\} \]

where:

  1. \(n\): number of nodes currently in the tree.
  2. \(d\): planning space dimension.
  3. \(\gamma\): scaling constant (controls neighbor count).
  4. \(\eta\): upper bound radius (often tied to steering step size).

Why this helps:

  1. Early in planning (small \(n\)), \(r_n\) is larger, so the algorithm explores broadly.
  2. Later (large \(n\)), \(r_n\) shrinks, so rewiring becomes more local and refined.

Pseudocode (RRT* Loop)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
for k in range(max_iterations):
    x_rand = sample_free()
    x_nearest = nearest(tree, x_rand)
    x_new = steer(x_nearest, x_rand, step_size)

    if collision_free(x_nearest, x_new):
        n = len(tree.nodes)
        r_n = min(eta, gamma * (log(n) / n) ** (1.0 / d))
        X_near = near(tree, x_new, r_n)

        # 1) Choose parent for x_new
        x_parent = argmin_over_collision_free(
            J(x) + dist(x, x_new) for x in X_near
        )
        add_node(tree, x_new, parent=x_parent)

        # 2) Rewire neighbors through x_new
        for x_near in X_near:
            if collision_free(x_new, x_near):
                if J(x_new) + dist(x_new, x_near) < J(x_near):
                    change_parent(x_near, x_new)

Rewire Intuition Example

Assume node 9 is newly added and the yellow circle is its neighborhood.

RRT star rewiring neighborhood example
RRT* local neighborhood: choose best parent for node 9, then rewire neighbors if cost improves.

In this example, RRT* first computes the best parent for node 9, then checks if 4, 5, or 8 become cheaper when connected through 9.

Quick Check Quiz 1 (Best Parent Selection)

Use the same figure above. Assume all dashed candidate edges are collision-free and edge labels are edge costs.

Which node should be selected as the parent of node 9?
Answer explanation
Compare total cost-to-come to node 9 through each candidate:

Through 6: \(0 \rightarrow 2 \rightarrow 6 \rightarrow 9 = 3 + 5 + 3 = 11\)
Through 8: \(0 \rightarrow 2 \rightarrow 6 \rightarrow 8 \rightarrow 9 = 3 + 5 + 1 + 3 = 12\)
Through 5: \(0 \rightarrow 5 \rightarrow 9 = 19 + 4 = 23\)
Through 4: \(0 \rightarrow 5 \rightarrow 4 \rightarrow 9 = 19 + 5 + 1 = 25\)

Minimum cost is through node 6.

Quick Check Quiz 2 (Rewire Decision)

After selecting node 6 as parent of node 9, which neighbors should be rewired to 9?

Which option is correct?
Answer explanation
From Quiz 1, \(J(9)=11\). Now compare each nearby node's current cost with the cost through 9:

Node 4 current: \(24\). Through 9: \(11 + 1 = 12\) -> improve, so rewire.
Node 5 current: \(19\). Through 9: \(11 + 4 = 15\) -> improve, so rewire.
Node 8 current: \(9\). Through 9: \(11 + 3 = 14\) -> no improvement, keep current parent.

So only nodes 4 and 5 are rewired.

Demo Notebook (Colab)

Open In Colab