Parking Planner
자동주차는 탐색 하나로 끝나지 않습니다. Hybrid A*가 위치와 방향을 함께 탐색해 전진·후진 원호를 잇고, 목표 근처에서는 Reeds-Shepp 곡선으로 남은 구간을 한 번에 닫습니다. 그 경로를 곡률이 연속이 되도록 다듬고, 속도 프로파일을 붙이고, 조향 지연이 있는 자전거 모델 위에서 추종 제어기로 실제로 주차해봅니다. 휴리스틱, 기어 전환 비용, 조향 한계, 주차 공간 크기를 바꾸며 탐색 노드 수와 경로, 추종 오차가 어떻게 달라지는지 비교해보세요.
차체를 끌어 시작·목표를 옮기고, 앞쪽 핸들로 방향을 돌리세요. 주차된 차도 옮길 수 있고, 놓는 즉시 다시 계획합니다.
| 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.
브라우저 안에서 실제로 계산하는 것
탐색은 매번 Web Worker에서 처음부터 돕니다. 충돌 검사는 10 cm 거리 변환 지도 위에서 경계원, 덮개 원 세 개, 정확한 OBB 순서로 판정하고, 휴리스틱은 장애물을 무시한 Reeds-Shepp 거리와 방향을 무시한 16-연결 Dijkstra 거리 중 큰 값입니다. 둘 다 남은 주행 거리의 하한이 되도록 보정했고, 테스트 스크립트가 모든 시나리오의 해 경로를 따라 이를 확인합니다. 후처리는 세그먼트별 곡률 프로파일을 이동평균으로 펴고 Gauss-Newton으로 끝 자세를 다시 맞춘 뒤 충돌을 재검사합니다. 실행은 1차 지연·조향속도 제한이 있는 운동학 자전거 모델에서 rear-wheel feedback 또는 pure pursuit로 추종합니다.
단순화한 부분
Hybrid A*는 셀마다 하나의 상태만 남기고 처음 성공한 Reeds-Shepp 샷에서 멈추므로 최적도, 완전성도 보장하지 않습니다. 탐색 예산을 넘으면 실패로 처리하고, 최소 슬롯 스윕의 점들도 그 예산 안에서 찾은 상한값입니다. 차량은 미끄럼 없는 운동학 모델이고, 제어기는 잡음 없는 상태를 그대로 받습니다. 곡률 연속 후처리는 여유 공간이 없으면 해당 세그먼트를 원래 경로로 남깁니다. 실제 자동주차는 센서 인식, 측위 오차, 경사와 연석을 함께 다뤄야 합니다.