Shortest parking route
A front-steered car (the kinematic bicycle, with a rectangular body) drives from a given start into a given parking slot without touching an obstacle. Find the run whose rear-axle midpoint travels the least distance. Each instance is one scene.
Formal definition
- CarThe body is a rectangle and its position is the middle of the rear axle: the nose lies wheelbase + front overhang ahead of it, the tail one rear overhang behind, and the width is split evenly. All twelve scenes use one car: wheelbase 2.8 m, front overhang 0.96 m, rear overhang 0.929 m, width 1.942 m. The state is (x, y, θ, v, φ): position, heading, signed speed (negative in reverse) and the steering angle of the front wheels
- MotionThe kinematic bicycle, with L the wheelbase. During a control the acceleration a and the steering rate ω are constant, so the speed and the steering angle are piecewise linear in time. The turning radius is at least L / tan(the largest steering angle), about 3.32 m for this car; the car may go forward, go backward, and turn its wheels while standing
- Limits|v| ≤ 2.5 m/s, |a| ≤ 1 m/s², |φ| ≤ 0.7 rad, |ω| ≤ 0.5 rad/s (the instance's parameters are what counts). a and ω are checked on every control, v and φ at the end of every control; they are linear in between, so that covers the whole run
- ContainerThe whole plane, with no outer boundary: anywhere outside the obstacles is open ground. Every obstacle is a convex polygon given in the instance's parameters: a parked car, a curb, a wall or a column. The car's rectangle coming within 0.1 mm of an obstacle is a collision
- Submissioncontrols: between 1 and 1200 controls [duration, acceleration, steering rate], every duration positive and the whole run at most 600 s; every number has at most nine decimals
- EndsThe car leaves the instance's start with v = 0 and φ = 0. At the end v = 0 and φ = 0, the middle of the rear axle is within 0.01 m of the slot's position on each axis and the heading within 1°. A speed or steering angle of at most 10⁻⁶ in absolute value at the end of a control counts as zero, so a submission written to nine decimals can still come to rest
- Verification ruleIntegers throughout. Durations are whole nanoseconds and a and ω whole multiples of 10⁻⁹, so v and φ are exact at every instant that is checked, and so are the limits and the length. The position and heading have no closed form and are defined by this rule: classical fourth-order Runge–Kutta steps in 10⁻¹⁸ fixed point, with sine and cosine from truncated Taylor series. Each step is the largest whole number of nanoseconds that stays within the time left in the control, within 2.5 cm at the control's fastest speed, within 0.005 rad of steering at the control's rate, and, nearer than 4.3 cm to an obstacle, short enough that no point of the car can cover the room it has. The distance from the car to the obstacles is checked after every step, and a submission may take at most 60000 steps. The same submission gives the same result on every machine; the rule's distance from the differential equation is measured in tests to be far below the tolerances of the problem, but it is not proved, and a submission is held to the rule
- ScoreThe distance the middle of the rear axle travels, forward and reverse alike, in metres; computed exactly from the stated speed and rounded up to 10⁻⁹ m; smaller is better
- ObjectiveMinimise the length over all runs that end in the slot without a collision
Getting a feel for it
Why length
The parking literature usually races the clock, and the fastest run steers while it moves, which rewards fine control. Length looks only at the route: any pace will do, and turning the wheels while standing costs nothing. That leaves a problem of geometry: a rectangle moving among polygonal obstacles, with a turning radius of at least 3.32 m and reversals allowed, by the shortest route. With no obstacles this is the Reeds–Shepp problem (1990), whose shortest routes are full-lock arcs and straight segments with a closed form; among obstacles there is no formula to reach for.
Where the scenes come from
The twelve scenes are the complete case set of Bai Li's CommonParking 1.0 benchmark for parking planners, with its scene geometry and vehicle parameters unchanged. The benchmark ranks parking time and publishes no lengths, so this problem has no external record: each instance starts from a route found by this site's planner, bylined MinMax Arena.
SourceWhat the starting routes leave
The starting routes come from a Hybrid A* search: full-lock arcs and straights only, a stop to turn the wheels at every reversal, and a few centimetres kept from every obstacle. They are sure to park, and they are not the shortest. A shorter route may pass closer to the obstacles, use arcs that are not at full lock, or save a reversal; the goal's 1 cm and 1° may be used in full as well.
Current best solutions by n
Each parameter n is an independently scored sub-problem. Select any card to inspect the current record construction or submit a stronger solution.
Discussion (2) ↓Data and citation
All sub-problems in this family — authoritative scores, proof status, coordinates, and sources — are published at the stable URL below under CC BY 4.0. Because scores update as records fall, please cite the file's generatedAt timestamp.
GET https://minmaxarena.com/data/shortest-parking-route.json
Cite the frozen 2026-10 edition: live records change, whereas a frozen edition stays fixed and reproducible.
GET https://minmaxarena.com/data/editions/2026-10/shortest-parking-route.json
BibTeX (click to copy)
@misc{minmaxarena-shortest-parking-route-2026-10,
title = {{Shortest parking route} (P98)},
author = {{MinMax Arena}},
year = {2026},
note = {Machine-verified records, 2026-10 edition},
url = {https://minmaxarena.com/data/editions/2026-10/shortest-parking-route.json},
license = {CC BY 4.0}
}Discussion
Discuss strategies, share construction methods, or ask questions. Any signed-in user can post under their public byline and unique #UID. New posts appear after moderation.
Grouped by player and sub-problem, showing the latest note first. Earlier versions and replies are preserved; click any note to read or reply. Notes can be published alongside record-breaking submissions.
No solver notes yet.