RRT* Motion Planning in 2D — Informed Sampling

Planner

Step size (extend length) 0.7

Goal bias 8%

Rewire radius 1.3

Obstacle count 9

Live Stats

Tree nodes

Iterations

Best path cost

—

Rewires done

Sampling area

—

Mode

Uniform

How it works

This is RRT/RRT* worked entirely in a flat 2D configuration space — the classic textbook setting the algorithm was first published in — rather than a 3D scene viewed from above. 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)

RRT* adds a cheapest-parent choice and a rewire pass within a radius r, exactly as in 3D, but every distance and every obstacle test is 2D:

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

The 2D setting makes a second, genuinely 2D optimization visible: Informed RRT* (Gammell, Srinivasa & Lawrence, 2014). Once any path to the goal exists with cost c_best, further samples are drawn only inside the prolate ellipse whose foci are the start and goal and whose major axis equals c_best — every point strictly inside satisfies dist(x,start) + dist(x,goal) < c_best, so it can only ever improve on the current path. As c_best shrinks, the ellipse shrinks with it, and sampling converges from "everywhere" to a thin sliver around the direct line — visible on screen as the dashed ellipse contracting.

c_min   = dist(start, goal)
a       = c_best / 2
b       = sqrt(c_best² − c_min²) / 2
sample  = center + R(θ)·diag(a,b)·unit_disk_sample()

Grow Tree — runs the sampling loop continuously, one extension per frame.
Step ×50 — advances 50 iterations instantly.
RRT / RRT* — toggles whether the cheapest-parent + rewire optimality steps run at all.
Informed sampling — once RRT* has found a path, restrict new samples to the cost ellipse instead of the whole arena; turning it off reverts to uniform sampling even after a solution exists, so you can compare convergence speed directly.
Rewire radius — the neighbourhood r searched for a cheaper parent / rewire candidates.
Goal bias — probability the random sample is the goal itself.

Tree edge Best path so far Obstacle Start / Goal Informed sampling ellipse

⚠ Couldn't start the simulationSomething went wrong loading the canvas engine. Reload the page.