P98 · 极值构型 · 本站原创 · 应用前沿

最短泊车路线

已验证构造路程 8.893 m
场景 1 · 侧方,宽车位当前纪录 · 打开子题

一辆前轮转向的汽车(运动学自行车模型,矩形车身)从给定起点开进给定车位,全程不碰障碍物。求后轴中点走过的路程最短的路线。每个子题是一个场景。

严格定义

  • 车车身是一个矩形,位置指后轴中点:车头在其前方「轴距 + 前悬」处,车尾在其后方「后悬」处,宽度左右各半。12 个场景用同一辆车:轴距 2.8 m,前悬 0.96 m,后悬 0.929 m,宽 1.942 m。状态为 (x, y, θ, v, φ):位置、车头方向、带符号的车速(倒车为负)和前轮转角
  • 运动运动学自行车模型,L 为轴距。每段控制期间加速度 a 和转向速度 ω 是常数,所以车速和前轮转角随时间分段线性变化。转弯半径不小于 L / tan(最大转角),这辆车约为 3.32 m;车可以前进、后退,也可以停着打方向x′=vcosθ,y′=vsinθ,θ′=vtanφL,v′=a,φ′=ω
  • 限制|v| ≤ 2.5 m/s,|a| ≤ 1 m/s²,|φ| ≤ 0.7 rad,|ω| ≤ 0.5 rad/s(以子题参数为准)。a 和 ω 在每段控制上检查,v 和 φ 在每段控制结束时检查;它们在一段之内线性变化,所以这就是全程的检查
  • 容器整个平面,没有外边界;障碍物以外的地方都可以走。每个障碍物是子题参数里给出的一个凸多边形:停着的车、路缘、墙或立柱。车身矩形与任何障碍物的距离小于 0.1 毫米即为碰撞
  • 提交controls:1 至 1200 段控制 [时长, 加速度, 转向速度],时长为正,全程不超过 600 秒;每个数最多九位小数
  • 始末车从子题给出的起点出发,v = 0,φ = 0。结束时 v = 0、φ = 0,后轴中点与车位位置在 x 和 y 上各相差不超过 0.01 m,车头方向相差不超过 1°。一段控制结束时绝对值不超过 10⁻⁶ 的车速或转角记为零,所以取到九位小数的提交也能停住
  • 判定规则全部用整数计算。时长是整数纳秒,a 和 ω 是 10⁻⁹ 的整数倍,所以 v 和 φ 在每个检查时刻都精确,限制和路程也都精确。位置和方向没有闭式解,由下面的规则定义:用 10⁻¹⁸ 定点数做经典四阶 Runge–Kutta 积分,正弦和余弦取截断的泰勒级数。每一步取满足下列条件的最大整数纳秒:不超过这段控制剩余的时间;按这段控制的最高车速不超过 2.5 cm;按这段控制的转向速度不超过 0.005 rad;离障碍物不足 4.3 cm 时,车上任何一点在这一步内走不完此刻的余量。每一步之后检查一次车身与障碍物的距离,一次提交至多 60000 步。同一份提交在任何机器上得到同一个结果;这条规则与微分方程的差距经测试远小于本题的容差,但没有证明,提交以这条规则为准
  • 分数后轴中点走过的路程,前进和倒车都计入,单位为米;按提交的车速精确计算,向上取整到 10⁻⁹ m;越小越好ℓ=∫|v|dt
  • 目标在所有停进车位且不碰障碍物的路线中使路程最短mincontrolsℓ

帮助理解

为什么比路程

泊车规划的文献通常比完成时间,而时间最短的走法要边走边打方向,考验的是控制的精细程度。路程只看路线本身:开得多慢都行,停下来打方向不计路程。于是问题变成几何的:一个矩形在多边形障碍物之间移动,转弯半径不小于 3.32 m,允许倒车换向,求最短路线。没有障碍物时这是 Reeds–Shepp 问题(1990),最短路线由满舵圆弧和直线段拼成,有闭式解;有了障碍物,就没有现成的公式了。

场景来源

12 个场景是 Bai Li 的 CommonParking 1.0 泊车规划基准的全部算例,场景几何和车辆参数原样采用。该基准比的是泊车用时,没有公布路程,所以这道题没有外部纪录:每个子题的起步路线由本站的规划器给出,署名 MinMax Arena。

查看来源

起步路线留下的空间

起步路线来自 Hybrid A* 搜索:只用满舵圆弧和直线,每次换向都停下来打方向,并与障碍物保持几厘米的余量。它保证能停进去,但不是最短的。更短的路线可以贴障碍物更近、用不满舵的弧、少换一次向;终点的 1 厘米和 1° 容差也可以用足。

逐个 n 竞争

所有 n 的当前最佳解

每个规模参数 n 都是一个独立计分的子题。点击任意卡片可查看当前纪录构型,或打开编辑器提交更优解答。

讨论区(2)↓
子题场景 1 · 侧方,宽车位
当前纪录8.892338278
难
纪录保持者Joost de Winter
解题方式AI · OpenAI: GPT-6.2 Sol
子题场景 2 · 侧方,紧车位
当前纪录9.031922959
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 3 · 垂直,邻车斜停
当前纪录10.277653955
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 4 · 斜列,入口不对称
当前纪录10.733285089
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 5 · 不规则,四车围合
当前纪录10.468168548
难
纪录保持者Joost de Winter
解题方式AI · OpenAI: GPT Chat Latest
子题场景 6 · 双柱,错位入口
当前纪录12.412187834
难
纪录保持者Joost de Winter
解题方式AI · OpenAI: GPT Chat Latest
子题场景 7 · 尽头车位,靠墙
当前纪录9.48306825
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 8 · 立柱围栏
当前纪录11.317172919
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 9 · 立柱,两侧择路
当前纪录11.096209981
难
纪录保持者Joost de Winter
解题方式AI · OpenAI: GPT-6.2 Sol
子题场景 10 · 靠墙车位,通道尽头
当前纪录13.909990488
难
纪录保持者Joost de Winter
解题方式AI · OpenAI: GPT Chat Latest
子题场景 11 · 串列车棚,里位
当前纪录5.88045935
难
纪录保持者NUE_13
解题方式AI · DeepSeek: DeepSeek V4.1 Flash
子题场景 12 · 偏置门洞,靠墙车库
当前纪录13.64800524
难
纪录保持者L.M.
解题方式AI · Anthropic: Claude Opus 5.5

引用与数据

该题族所有子题的权威分数、证明状态、坐标数据与文献来源均汇总于下方稳定链接,按 CC BY 4.0 协议发布。由于分数随纪录刷新而更新,引用时请同时注明文件中的 generatedAt 时间戳。

GET https://minmaxarena.com/data/shortest-parking-route.json

引用建议使用 2026-10 冻结归档版:实时纪录会变,但冻结版永久固定,便于日后核查。

GET https://minmaxarena.com/data/editions/2026-10/shortest-parking-route.json
BibTeX(点击复制)
@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

讨论区

欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖;发言使用与排行榜一致的公开署名,并附带唯一注册编号(#UID)以防冒名。新发言经审核后公开。