Skip to the lesson
FixTheRobot Explore Robotics / Navigation / M4 Sampling-Based and Kinodynamic Planning / M4-T4

Navigation · Theory · M4

M4-T4 — RRT*, Informed RRT* and BIT*

RRT finds a path and keeps it. RRT* keeps improving it: every new node may shorten what is already there.

  • Lesson 4 of 6
  • Module 4: Sampling-Based and Kinodynamic Planning
  • Theory
  • About 10 minutes to read

A plain RRT never changes an edge. Whatever branch first reached the goal sets the route, wiggles included. RRT* adds two small steps to each iteration, pick the best parent among the neighbours and let the new node shorten its neighbours’ routes, and the cost of the best path converges to the optimum as samples are added. Informed RRT* and BIT* then spend those samples where they can still help.

Learning objectives

After this lesson, you should be able to:

  • Describe the choose-parent and rewire steps of RRT* and why they only ever lower costs.
  • Compute the cost-to-come of a node and the effect of a rewire on its descendants.
  • State what asymptotic optimality means and what role the shrinking radius plays.
  • Explain how Informed RRT* restricts sampling to an ellipse and how BIT* batches the idea.

The intuition

Picture the tree as a road network built outwards from the start. A plain RRT connects each new junction to the nearest existing junction, however long the road to that junction is. RRT* asks a better question: among all the junctions nearby, which one gives the new junction the shortest drive from the start? The nearest junction can be on a long detour while one slightly farther away is on a direct road.

Then it asks a second question the other way round: would any nearby junction be reached more quickly by driving through the new one? If so, it rebuilds that road. Every road below the rebuilt junction gets shorter by the same amount, for free, because costs are read from the chain of parents.

The effect, repeated for thousands of samples, is that the tree untangles itself towards shortest paths. The price is that each sample now looks at many neighbours instead of one.

Choosing a parent and rewiring a neighbourTwo panels of the same small tree. Left: the new node x is joined to its parent A and the tree has a long route to node C through B. Right: after rewiring, C hangs from x and its cost falls from 6.5 to 5.2.New node x joins the cheapest parent A startA 3.0B 5.0 C 6.5new x 4.2Then C is rewired to hang from x startA 3.0B 5.0 C 5.2new x 4.2
Left: the new node x chooses A as parent because A gives the lowest cost, 4.2. Right: C is cheaper through x (5.2) than through B (6.5), so it is rewired. The edge from B to C is dropped.

The mathematics

Cost-to-come

The cost of a node v is the length of the tree path from the root: c(root) = 0 and c(v) = c(parent(v)) + |parent(v) → v|. It is never stored as a separate truth: change a parent and the costs below it change with it.

One iteration of RRT*

  1. Sample and extend exactly as RRT: nearest node, steer by at most η, check the edge. Call the result x.
  2. Neighbours. Find Xnear, all nodes within the radius r of x.
  3. Choose parent. Among the nodes of Xnear with a free edge to x, choose the one minimising c(v) + |v → x|. Add x with that parent.
  4. Rewire. For each v in Xnear with a free edge from x: if c(x) + |x → v| < c(v), make x the parent of v.
Choose parent and rewire
parent⁡(x)=arg min⁡ over v in Xnear, edge v→x free of[c(v)+∣v→x∣]\operatorname{parent}(x)=\operatorname*{arg\,min}\,\text{over}\,v\,\text{in}\,X_{\text{near}},\,\text{edge}\,v\to x\,\text{free of}[c(v)+\lvert v\to x\rvert ]
rewire v if c(x)+∣x→v∣<c(v)\text{rewire}\,v\,\text{if}\,c(x)+\lvert x\to v\rvert <c(v)

Compare totals, not edge lengths: a short edge to a node on a bad route is no improvement. Because a rewire only happens when it strictly lowers c(v), and any descendant of v costs more than v, no cycle can form.

The radius and asymptotic optimality

Karaman and Frazzoli showed that RRT* is asymptotically optimal: the cost of the best path converges to the optimal cost almost surely as the number of samples n tends to infinity, provided the neighbourhood radius shrinks slowly enough, as

Shrinking radius
r(n)=γ⋅(log⁡ nn)(1d)  withr(n)=\gamma \cdot (\frac{\log \,n}{n})^{(\frac{1}{d})}\;\mathrm{with}
γ>2⋅(1+1d)(1d)⋅(μ(Xfree)ζd)(1d)\gamma >2\cdot (1+\frac{1}{d})^{(\frac{1}{d})}\cdot (\frac{\mu (X_{\text{free}})}{\zeta _{d}})^{(\frac{1}{d})}
d
dimension of the space.
μ(Xfree)
volume (area, in 2D) of the free space.
ζd
volume of the unit ball in d dimensions (π in 2D).
γ
the constant; the formula gives its lower bound.

The radius shrinks so that the number of neighbours per sample grows only like log n, while the graph of neighbours stays connected enough to contain near-optimal paths. A fixed radius works in practice on small problems, as in lab M4-L3. Plain RRT is not asymptotically optimal; the cost it converges to is above the optimum.

Informed RRT*

Once a path of cost cbest exists, a point x can be on a better path only if the shortest imaginable route through x is shorter than cbest. The straight-line bound gives

Informed set
∣start−x∣+∣x−goal∣<cbest\lvert \text{start}-x\rvert +\lvert x-\text{goal}\rvert <c_{\text{best}}

In the plane this is the inside of an ellipse with the start and the goal as foci and major axis cbest. With cmin the straight-line distance, its semi-axes are a = cbest / 2 and b = sqrt(cbest² − cmin²) / 2. Informed RRT* draws samples uniformly from that ellipse (Gammell, Srinivasa and Barfoot, 2014). As cbest falls, the ellipse shrinks towards the straight line.

BIT*

Batch Informed Trees treat the samples as an implicit random geometric graph and search it with an A*-like order. Samples come in batches drawn from the informed set; edges are processed in the order of an estimate of the total path cost through them, and an edge is collision-checked only when it is about to be used. A new batch with a denser graph (and a smaller ellipse) is added when the search of the current one is exhausted. It finds a first path quickly and improves it (Gammell, Srinivasa and Barfoot, 2015).

A worked example

Choose parent and rewire. The tree has A at cost 3.0, B at cost 5.0 and C at cost 6.5, reached from B. A new node x lands near all three, with distances |A x| = 1.2, |B x| = 0.9 and |C x| = 1.0, and all edges free.

via A
3.0+1.2=4.23.0+1.2=4.2
via B
5.0+0.9=5.95.0+0.9=5.9
B is the nearest, A is cheaper
parent⁡(x)=A,\operatorname{parent}(x)=A,
c(x)=4.2c(x)=4.2
rewire C?4.2+1.0=5.2<6.5\text{rewire}\,C?4.2+1.0=5.2<6.5
yes
parent⁡(C)=x\operatorname{parent}(C)=x
rewire B?4.2+0.9=5.1>5.0  no\text{rewire}\,B?4.2+0.9=5.1>5.0\;\mathrm{no}

RRT would have used B (the nearest) and left x at 5.9 and C at 6.5. RRT* ends with x at 4.2 and C at 5.2, a saving of 1.3 for C and for every node below it. In lab M4-L3 stages 1 and 2 are exactly these two decisions.

The radius. In the 10 m × 6 m dock the free area is about 54 m². The lower bound for γ in 2D is

Radius for the dock
γ∗=2⋅(1.5)0.5⋅(54π)0.5=2⋅1.2247⋅4.146=10.16\gamma ^{*}=2\cdot (1.5)^{0}.5\cdot (\frac{54}{\pi })^{0}.5=2\cdot 1.2247\cdot 4.146=10.16
r(100)=10.16⋅(ln⁡ 100100)0.5=2.18 mr(100)=10.16\cdot (\frac{\ln \,100}{100})^{0}.5=2.18\,\mathrm{m}
r(500)=10.16⋅(ln⁡ 500500)0.5=1.13 mr(500)=10.16\cdot (\frac{\ln \,500}{500})^{0}.5=1.13\,\mathrm{m}

The bound is a sufficient condition for the proof, and small in practice; the lab uses a fixed 1.4 m with 0.7 m steps.

The ellipse. The dock’s start (0.8, 1.0) and goal (9.2, 4.8) are cmin = sqrt(8.4² + 3.8²) = 9.22 m apart. After a first path of cbest = 10.5 m the informed ellipse has

Informed ellipse
a=10.52=5.25 ma=\frac{10.5}{2}=5.25\,\mathrm{m}
b=10.52−9.2222=2.51 mb=\frac{\sqrt{10.5^{2}-9.22^{2}}}{2}=2.51\,\mathrm{m}
area=π⋅5.25⋅2.51=41.4 m2\text{area}=\pi \cdot 5.25\cdot 2.51=41.4\,\mathrm{m}^{2}

about 69% of the 60 m² dock, ignoring the walls. At cbest = 10.0 m it is a = 5.0, b = 1.94, area 30.4 m² (51%). Every sample outside it is wasted.

What the lab shows. With the same 500 samples on the same dock, plain RRT gives paths 1.26 to 1.8 times the shortest route; RRT* with a 1.4 m radius gives 1.02 to 1.18 times (16 generated docks). The RRT* curve falls with every batch of samples while the RRT curve stays flat.

Engineering implications and limitations

Cost per sample

Each RRT* sample does a neighbour search and up to one collision check per neighbour, for parent choice and for rewiring. With radius r the number of neighbours is roughly the density of nodes times πr². A larger radius gives better paths and costs more time; a smaller one is cheaper and converges slowly. Edge checks are the main cost (lesson M4-T2); reuse the edge-validity results between the choose-parent and rewire steps.

Anytime use

RRT* is an anytime planner: run it until a deadline, or until the cost stops improving, and execute the best path. Keep the tree if the goal is only slightly moved or the map has barely changed, and repair it instead of starting again.

Choosing between them

If you need the first solution fast and do not care about its length, RRT or RRT-Connect. If length matters and time is available, RRT* with informed sampling. For highly constrained problems BIT* or FMT* often reach a good path with fewer collision checks. For vehicles with turning constraints, exact rewiring needs a steering function that connects any two poses (lesson M4-T5); without it, kinodynamic RRT* variants are needed.

Paths still need smoothing

Even a nearly optimal tree path is a polyline with corners made of random directions. Shortcut and smooth it before it goes to a controller (module 5).

Common misconceptions

“RRT* is just RRT with more samples.”

The difference is not the number of samples but two extra steps. RRT converges to a suboptimal path with unlimited samples; RRT* converges to the optimal one.

“Asymptotically optimal means the path is optimal.”

It means the cost converges to the optimum in the limit of infinitely many samples. After 500 samples the path is better, not best, and no finite number of samples is certain to be optimal.

“Rewiring needs a loop check.”

It does not if costs are compared as totals: a rewire to x requires c(x) + |x → v| < c(v), and a descendant of v always costs more than v. Only a buggy comparison creates a loop (lab M4-L3 stage 2).

“The step size and the radius are the same parameter.”

The step η limits how far one sample moves the tree; the radius r decides which nodes may be parents or be rewired. Setting r to η leaves the new node with almost no choices and makes RRT* behave like RRT.

Engineering takeaways

  1. RRT* adds choose-parent (minimise cost-to-come plus edge) and rewire (shorten neighbours) to every iteration.
  2. Compare total costs, not edge lengths; costs of descendants follow from parents automatically.
  3. It is asymptotically optimal when the radius shrinks like (log n / n)^(1/d) with a large enough constant.
  4. Informed RRT* samples only inside the ellipse with the start and goal as foci and major axis cbest.
  5. BIT* searches batches of informed samples in A*-like order and checks edges lazily.

References and further reading

The papers that introduced RRT*, informed sampling and BIT*.

  • S. Karaman and E. Frazzoli, “Sampling-based Algorithms for Optimal Motion Planning”, The International Journal of Robotics Research, 30(7), 2011.
  • J. D. Gammell, S. S. Srinivasa and T. D. Barfoot, “Informed RRT*: Optimal Sampling-based Path Planning Focused via Direct Sampling of an Admissible Ellipsoidal Heuristic”, IEEE/RSJ IROS, 2014.
  • J. D. Gammell, S. S. Srinivasa and T. D. Barfoot, “Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs”, IEEE ICRA, 2015.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

Question 1

A new node has neighbours P (cost 4.0, distance 1.0) and Q (cost 2.5, distance 2.0). Which is the parent, and what is the new node’s cost?

Explanation

Via P: 4.0 + 1.0 = 5.0. Via Q: 2.5 + 2.0 = 4.5. Q is the parent, c = 4.5, even though P is nearer.

Question 2

A neighbour R has cost 6.0 and the new node has cost 4.5 at distance 1.2 from R. What happens to R and to a child of R at distance 0.8?

Explanation

4.5 + 1.2 = 5.7 < 6.0, so R is rewired to the new node and its cost falls by 0.3 to 5.7. Its child falls by the same 0.3, from 6.8 to 6.5.

Question 3

The start and goal are 8 m apart and the best path so far is 10 m. What are the semi-axes of the informed ellipse?

Explanation

a = 10 / 2 = 5 m and b = sqrt(10² − 8²) / 2 = 6 / 2 = 3 m.

What’s next

Next: vehicles that cannot turn on the spot, and the shortest curves they can drive: Dubins and Reeds-Shepp.

Practice this lesson

Rewire to a Better Path with RRT*

Improve the RRT path by rewiring, and watch the cost fall as samples are added.

Next lesson

M4-T5 — Dubins and Reeds-Shepp Curves

Build the shortest paths for a car that turns with a minimum radius, with and without reversing.

Nothing below is required to finish this lesson.