RRT* stands for Rapidly-exploring Random Tree Star.
It is a motion-planning algorithm used to find a path from a start state to a goal state, usually in a space with obstacles.
It is an improved version of RRT.
The main difference is:
- RRT tries to find a feasible path quickly
- RRT* tries to keep improving that path over time
So RRT* is not just trying to reach the goal. It is trying to reach the goal with a better path cost.
Main idea
RRT* builds a tree outward from the start by repeatedly sampling random points in the space.
Each new sample gives the algorithm a chance to:
- expand into unexplored space
- connect a new node in a cheap way
- rewire nearby nodes if the new node gives them a better route
That last step is what makes RRT* special.
Intuition
The best mental model is:
RRT grows a messy tree quickly. RRT* keeps reorganizing the tree so the routes get cleaner and cheaper.
So RRT* is like exploring a city by building temporary roads.
At first, you are just happy to connect places somehow.
Later, when you discover a shorter road through the middle, you reroute traffic through that better connection.
That is exactly what rewiring is doing.
Basic steps of RRT*
At each iteration, RRT* does something like this:
- Sample a random point
- Find a nearby existing node in the tree
- Move a small step toward the random point to create a new node
- Reject it if the path collides with an obstacle
- Look at nearby nodes around
- Choose the parent that gives the lowest cost-to-come
- Add
to the tree - Rewire nearby nodes if going through
makes their path cheaper
So the algorithm is doing both:
- exploration
- local path improvement
What “cost” means
Usually the cost is just path length, but it could also mean:
- travel time
- energy usage
- smoothness penalty
- risk
So when we say RRT* finds a better path, we really mean:
It finds a path with lower total cost according to the objective we care about.
Important pieces
1. Random sampling
Sampling random points helps the tree spread into open space without needing an explicit grid.
This is why RRT-style methods work well in high-dimensional spaces where a grid would become too expensive.
2. Nearest or nearby nodes
Plain RRT usually picks the nearest node and attaches the new point there.
RRT* does more work:
- it looks at a neighborhood of candidate parents
- it picks the one that gives the cheapest path to the new node
So the parent is chosen by cost, not just by geometric closeness.
3. Rewiring
After adding the new node, RRT* checks whether nearby existing nodes would be better off using this new node as their parent.
If yes, it changes their parent.
This is the optimization step.
Without rewiring, the tree keeps a lot of bad early decisions.
With rewiring, those bad early decisions can be corrected.
A simple example
Imagine the start is on the left side of a room and the goal is on the right side, with a box-shaped obstacle in the middle.
Early on, RRT* might discover a path that goes awkwardly around the obstacle with lots of zig-zags.
That path is valid, so great, the algorithm already has a solution.
But as more samples appear near the obstacle boundary, RRT* may discover a smoother shortcut around one corner.
Then it can:
- attach new nodes through that shortcut
- rewire old nodes to also use that shortcut
So over time the path becomes less ugly and more direct.
This is the key difference from RRT:
- RRT often finds a weird but valid path
- RRT* gradually improves that path
Another intuition: bad first drafts
RRT* behaves a bit like writing.
The first draft just needs to exist.
After that, you revise it:
- remove unnecessary detours
- connect ideas more cleanly
- shorten the route from start to finish
RRT is mostly the first draft.
RRT* includes revision.
Why RRT* is better than RRT
RRT is good at quickly finding a feasible path.
RRT* is better when path quality matters, because it is asymptotically optimal.
That means:
As the number of samples goes to infinity, the solution found by RRT* approaches the optimal one under mild assumptions.
So RRT* may be slower than RRT at first, but it has a much better long-term guarantee.
Why RRT* can be slower
RRT* usually does more work per iteration because it:
- checks a neighborhood of nodes
- compares costs
- rewires the tree
So you are paying extra computation in exchange for better path quality.
Connection to trees in graph search
RRT* is still building a tree, not an arbitrary graph.
Each node has one parent, which makes it easy to define:
- the path from the start to that node
- the cost-to-come for that node
This is similar in spirit to shortest-path thinking in graphs, except the graph is being built incrementally by random sampling.
Connection to configuration space
RRT* usually works in configuration space rather than plain physical space.
That matters because for a robot arm, a “point” in the planning space might not mean a location in the room.
It might mean:
- joint angle 1
- joint angle 2
- joint angle 3
- …
So RRT* is often exploring a high-dimensional state space, not just drawing lines in 2D.
This is one reason random-sampling methods are useful.
Connection to obstacle checking
RRT* does not just check whether a node is valid.
It also has to check whether the edge from one node to another is collision-free.
So even if two endpoints are valid, the path between them might cross an obstacle.
That edge-checking step is critical.
Summary
RRT* works by:
- sampling random states
- growing a tree from the start
- attaching new nodes using the cheapest nearby parent
- rewiring nearby nodes when a better route is found
So the real mental model is:
RRT* is a tree-based planner that explores randomly but optimizes locally.
That combination is why it can both find a path and keep improving it over time.