RRT* Motion Planning — Rapidly-Exploring Random Trees

Planner

Step size (extend length) 0.9

Goal bias 8%

Rewire radius 1.6

Obstacle count 7

Live Stats

Tree nodes

Iterations

Best path cost

—

Rewires done

How it works

RRT (Rapidly-exploring Random Tree) solves motion planning in continuous, high-dimensional configuration space without a grid. Each iteration:

1. x_rand  ~ Uniform(space)     (or x_goal with prob. p_bias)
2. x_near  = arg min_{v in T} dist(v, x_rand)
3. x_new   = x_near + step * normalize(x_rand - x_near)
4. if segment(x_near, x_new) is collision-free:
       T.addEdge(x_near, x_new)

Plain RRT never revisits a decision — the first path found is kept even if a shorter one appears later. RRT* adds two optimality steps around a radius r:

choose parent: among neighbours within r,
  pick the one minimizing cost(x_near) + dist(x_near, x_new)
rewire: for each neighbour v within r,
  if cost(x_new) + dist(x_new, v) < cost(v):
     reparent v under x_new   (edge is redrawn)

As iterations → ∞, RRT* converges to the optimal path (probabilistic completeness + asymptotic optimality), which is why it underlies real motion planners in robotic arms, self-driving cars and drone navigation stacks (e.g. OMPL, MoveIt).

Grow Tree — runs the sampling loop continuously, one extension per frame.
Step ×50 — advances 50 iterations instantly, useful to watch rewiring converge fast.
RRT / RRT* — toggles whether the "choose parent" + "rewire" optimality steps run at all.
Rewire radius — the neighbourhood r searched for a cheaper parent / rewire candidates; too small misses improvements, too large costs more per iteration.
Goal bias — probability the random sample is the goal itself instead of a uniform point, which speeds convergence toward it.

Tree edge Best path so far Obstacle Start / Goal

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.