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.
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.
| Metric | Raw | Smoothed | Δ |
|---|---|---|---|
| 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 | Expanded | Time | Length | Cost | Cusps | Rmin |
|---|---|---|---|---|---|---|
| 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.
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 %).
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.
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.
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 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.
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.