Shortest parking route · Case 11 · tandem carport, rear position
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.
Record comparison
the length of the route · Lower is better| Record | Value / interval | Author / holder | Source |
|---|---|---|---|
| External best known | — | — | No reference listed |
| Site record | 5.88045935 | NUE_13 | Record details ↓ |
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