P98 · Extremal configurations · Formed here · Applied frontier · Hard

Shortest parking route · Case 10 · wall-side bay at the aisle end

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.

InstanceCase 10 · wall-side bay at the aisle end
ObjectiveMinimize the length of the route

Record comparison

the length of the route · Lower is better
RecordValue / intervalAuthor / holderSource
External best known——No reference listed
Site record13.909990488Joost de WinterRecord 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 standingx′=vcosθ,y′=vsinθ,θ′=vtanφL,v′=a,φ′=ω
  • 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ℓ=∫|v|dt
  • ObjectiveMinimise the length over all runs that end in the slot without a collisionmincontrolsℓ
Open full editor ↗

Layout shown: site record

VERIFIED CONSTRUCTIONroute length 13.910 m

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.

Source

What 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.

The record-holding arrangement for Shortest parking route Case 10 · wall-side bay at the aisle end, 13.909990488
LAYOUT & HISTORY

Record details

Inspect the layout, solver notes and record history.

Record holderJoost de Winter
Solution methodAI · OpenAI: GPT Chat Latest
Challenge this record ↗Submit a proof / idea ↓Share a proof or bound argument in the discussion board. Accepted contributions earn proof points.
Record holder's solver noteNo solver note yet (expand)+

The record holder has not shared a solver note yet.

Record history (21 changes)
  1. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.910019372→13.909990488
  2. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.910051245→13.910019372
  3. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.910206863→13.910051245
  4. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.910257754→13.910206863
  5. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.910408634→13.910257754
  6. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.910427581→13.910408634
  7. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.9133635→13.910427581
  8. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.913616884→13.9133635
  9. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.914166197→13.913616884
  10. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.433010174→13.914166197
  11. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.433013071→14.433010174
  12. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.43305256→14.433013071
  13. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.433170211→14.43305256
  14. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    14.433202282→14.433170211
  15. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.433377639→14.433202282
  16. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    14.433606868→14.433377639
  17. Joost de WinterAI · OpenAI: GPT Chat Latest
    14.642307738→14.433606868
  18. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    14.700688713→14.642307738
  19. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    14.813236874→14.700688713
  20. qiboqiAI · OpenAI: GPT-6 Luna
    14.91848327→14.813236874
  21. qiboqiAI · OpenAI: GPT-6 Luna
    16.525088074→14.91848327
ANSWER FORMAT

How to write your answer

Coordinates are in metres and angles in radians, counter-clockwise positive, with the heading θ measured from the positive x axis. Positions are those of the middle of the rear axle. An instance's parameters give the body (car), the limits, the start and the goal (each [x, y, θ]), and the obstacles (each the corners of a convex polygon).

Submit controls: the controls in order, each [duration, acceleration, steering rate] in seconds, m/s² and rad/s, every number a decimal string of at most nine decimals. The car leaves the start at rest with its wheels straight; during a control the acceleration and the steering rate of the front wheels are constant. At the end the car must be at rest, its wheels straight, and in the slot (within 0.01 m in position and 1° in heading). The score is the length alone: any pace will do, and turning the wheels while standing adds nothing. The editor on the page can be driven with the keyboard, and Auto lets a planner finish the route; what it writes out is a controls list ready to submit.

The current leader's answer

{
  "controls": [
    [
      "1.399999984",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "24.459853203",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "2.799999980",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "54.438774105",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "24.923470001",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "35.067012485",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "2.799999992",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "35.067480273",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "52.119656704",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "43.271931623",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "52.058776238",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.681890636",
      "0",
      "-0.5"
    ],
    [
      "0.014147453",
      "-1",
      "0"
    ],
    [
      "0.014147453",
      "1",
      "0"
    ],
    [
      "2.081890632",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "25.977803783",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ]
  ]
}
Submission format and technical detailsOpen this when you are ready to prepare a JSON answer+

Instance parameters

{
  "car": {
    "wheelbase": "2.8",
    "frontOverhang": "0.96",
    "rearOverhang": "0.929",
    "width": "1.942"
  },
  "limits": {
    "speed": "2.5",
    "acceleration": "1",
    "steeringAngle": "0.7",
    "steeringRate": "0.5"
  },
  "start": [
    "-3.302902708",
    "6.015050598",
    "-0.13962634"
  ],
  "goal": [
    "-0.437413556",
    "-1.346220499",
    "1.256637061"
  ],
  "obstacles": [
    {
      "kind": "parked_car",
      "corners": [
        [
          "-2.462747433",
          "-1.535160682"
        ],
        [
          "-1.328375665",
          "3.014555979"
        ],
        [
          "-3.212689965",
          "3.4843683"
        ],
        [
          "-4.347061734",
          "-1.065348361"
        ]
      ]
    },
    {
      "kind": "parked_car",
      "corners": [
        [
          "-3.301382303",
          "8.953298201"
        ],
        [
          "1.046182791",
          "7.196767885"
        ],
        [
          "1.773668796",
          "8.99735893"
        ],
        [
          "-2.573896299",
          "10.753889247"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "-6.884204506",
          "-1.285584814"
        ],
        [
          "1.152223056",
          "-3.896778417"
        ],
        [
          "1.306731554",
          "-3.421250159"
        ],
        [
          "-6.729696009",
          "-0.810056556"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "1.306731554",
          "-3.421250159"
        ],
        [
          "4.118786202",
          "5.23336414"
        ],
        [
          "3.643257944",
          "5.387872637"
        ],
        [
          "0.831203295",
          "-3.266741661"
        ]
      ]
    }
  ]
}

The current leader's answer

{
  "controls": [
    [
      "1.399999984",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "24.459853203",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "2.799999980",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "54.438774105",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "24.923470001",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "35.067012485",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "2.799999992",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "35.067480273",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "52.119656704",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "43.271931623",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "52.058776238",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.681890636",
      "0",
      "-0.5"
    ],
    [
      "0.014147453",
      "-1",
      "0"
    ],
    [
      "0.014147453",
      "1",
      "0"
    ],
    [
      "2.081890632",
      "0",
      "0.5"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "0.020000000",
      "-1",
      "0"
    ],
    [
      "25.977803783",
      "0",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "0.020000000",
      "1",
      "0"
    ],
    [
      "1.399999996",
      "0",
      "-0.5"
    ]
  ]
}

Submit controls: the controls in order, each [duration, acceleration, steering rate] in seconds, m/s² and rad/s, every number a decimal string of at most nine decimals. The car leaves the start at rest with its wheels straight; during a control the acceleration and the steering rate of the front wheels are constant. At the end the car must be at rest, its wheels straight, and in the slot (within 0.01 m in position and 1° in heading). The score is the length alone: any pace will do, and turning the wheels while standing adds nothing. The editor on the page can be driven with the keyboard, and Auto lets a planner finish the route; what it writes out is a controls list ready to submit. · Verifier v1.0.0

DISCUSSION

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.