Skip to content
Lab
motion planning hybrid A* · reeds-shepp · curvature-continuous smoothing · path tracking

Parking Planner

Automated parking does not end with a search. Hybrid A* explores position and heading together, chaining forward and reverse arcs, and near the goal a Reeds-Shepp curve closes the gap in one shot. The path is then smoothed to continuous curvature, given a speed profile, and driven by a tracking controller on a bicycle model with a lagging steering actuator. Change the heuristic, gear-change cost, steering lock and slot size and compare node counts, paths and tracking errors.

Presets
t 0.0 s PLANNING
Lot · 34 × 20 m drive reverse RS shot (raw) grid A* search tree
expanded · generated—
search time—
length · cusps—
cost J—
gear · v—
δ · δcmd—
ey—
sensor gap—

Drag a body to move the start or goal, its front handle to turn it. Parked cars move too; the plan updates as you drag.

Profiles vs. station executed path raw Hybrid A* command / plan limit reverse
Execution · raw vs. post-processed —
MetricRawSmoothedΔ
Path length L———
Gear changes cusps———
Peak curvature rate max |dκ/ds|———
Peak steering rate max |δ̇|———
Manoeuvre time t———
Peak tracking error max |ey|———
Final pose error Δp · Δψ———
Closest approach min gap———

Both are driven by the same tracker on the same bicycle model (actuator 40°/s, τ = 0.12 s). The speed profile slows the car wherever the path would need more than 20°/s of steering, half the actuator's limit, so the lag has room to catch up.

Planner comparison · this scene queued
PlannerExpandedTimeLengthCostCuspsRmin
Grid A* (x, y only)8-connected ——————
Hybrid A* · Euclideanh = ‖p − g‖ ——————
Hybrid A* · 2D Dijkstraobstacles, no heading ——————
Hybrid A* · Reeds-Sheppheading, no obstacles ——————
Hybrid A* · max of bothdefault ——————
… without RS shotanalytic off ——————

Same vehicle, costs and 30 000-node budget. Grid A* counts cells and needs turns of radius Rmin far below the car's; click a Hybrid A* row to drive with that heuristic.

Minimum parallel slot vs. steering lock queued

One-move bound: the gap a car needs to leave in a single arc at full lock, b + √(ro² − (R − w/2)²), Blackburn's geometry with the safety margin.

Hybrid A*: binary search on the gap, feasible = solved within 12 000 expansions. Extra cusps buy a shorter slot; the budget makes each point an upper bound on the true minimum.

Uses the current margin, costs, bins and the planning lock (92 %).

Search

state (x, y, ψ) · key ⌊x/0.5⌋, ⌊y/0.5⌋, ⌊ψ/(2π/Nψ)⌋

primitives: δ ∈ {−δ̄, −δ̄/2, 0, δ̄/2, δ̄} × {D, R}, 1 m exact arcs, δ̄ = 0.92 δmax

g += ℓ·(wR if R) + 0.5|δ|ℓ + |Δδ| + csw[gear change]

Collision: 10 cm Euclidean distance transform; bounding circle → 3 covering discs → exact OBB test.

Heuristic & analytic shot

h = max(hRS, h2D)

hRS: shortest Reeds-Shepp length at Rplan, obstacles ignored (48 words)

h2D = (D16 − 2√2 Δ) / 1.0275: Dijkstra from the goal, 16-connected, heading ignored

Both are lower bounds on the length still to drive, and cost ≥ length, so h is admissible; the test suite checks it along every solved path. Near the goal each expansion tries the six shortest RS words; the first collision-free one ends the search.

Post-processing & tracking

c(s) = tan δ / L ← moving average, |c| ≤ c̄, + Σk=1..3 ak sin(kπs/S), ℓ(1+ε): Gauss-Newton to the segment's end pose

v ≤ min(vmax, √(alat/|κ|), δ̇plan/|dδ/ds|), δ̇plan = 20°/s, stop at every cusp

κcmd = κ cos eψ/(1 − κey) − kψeψ − ke sinc(eψ) ey

Rear-wheel feedback (ke = 1.2, kψ = 2.4) or pure pursuit, both on the mirrored car in reverse; the car steers at standstill before each segment.

What is modelled

What runs in your browser

Every plan is searched from scratch in a Web Worker. Collisions are checked on a 10 cm distance transform, bounding circle first, then three covering discs, then an exact OBB test. The heuristic is the larger of the obstacle-free Reeds-Shepp distance and a 16-connected Dijkstra distance that ignores heading; both are corrected to stay below the distance still to drive, and the test script checks that along every solved path. Post-processing filters each segment's curvature profile with a moving average, re-solves its end pose by Gauss-Newton and re-checks collisions. Execution runs rear-wheel feedback or pure pursuit on a kinematic bicycle with a first-order, rate-limited steering actuator.

state
(x, y, ψ)
cells
0.5 m · 5°
primitives
5 × D/R
RS words
48
Scope & limits

What is simplified

Hybrid A* keeps one state per cell and stops at the first Reeds-Shepp shot that is collision-free, so it is neither optimal nor complete. A search over budget counts as a failure, and each point in the minimum-slot sweep is an upper bound found within that budget. The car is a kinematic model without slip, and the controllers see the true state with no noise. Where a curvature-continuous version does not fit, post-processing keeps that segment raw. Real automated parking also has to deal with perception, localisation error, slopes and kerbs.