最短泊车路线
一辆前轮转向的汽车(运动学自行车模型,矩形车身)从给定起点开进给定车位,全程不碰障碍物。求后轴中点走过的路程最短的路线。每个子题是一个场景。
严格定义
- 车车身是一个矩形,位置指后轴中点:车头在其前方「轴距 + 前悬」处,车尾在其后方「后悬」处,宽度左右各半。12 个场景用同一辆车:轴距 2.8 m,前悬 0.96 m,后悬 0.929 m,宽 1.942 m。状态为 (x, y, θ, v, φ):位置、车头方向、带符号的车速(倒车为负)和前轮转角
- 运动运动学自行车模型,L 为轴距。每段控制期间加速度 a 和转向速度 ω 是常数,所以车速和前轮转角随时间分段线性变化。转弯半径不小于 L / tan(最大转角),这辆车约为 3.32 m;车可以前进、后退,也可以停着打方向
- 限制|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;越小越好
- 目标在所有停进车位且不碰障碍物的路线中使路程最短
帮助理解
为什么比路程
泊车规划的文献通常比完成时间,而时间最短的走法要边走边打方向,考验的是控制的精细程度。路程只看路线本身:开得多慢都行,停下来打方向不计路程。于是问题变成几何的:一个矩形在多边形障碍物之间移动,转弯半径不小于 3.32 m,允许倒车换向,求最短路线。没有障碍物时这是 Reeds–Shepp 问题(1990),最短路线由满舵圆弧和直线段拼成,有闭式解;有了障碍物,就没有现成的公式了。
场景来源
12 个场景是 Bai Li 的 CommonParking 1.0 泊车规划基准的全部算例,场景几何和车辆参数原样采用。该基准比的是泊车用时,没有公布路程,所以这道题没有外部纪录:每个子题的起步路线由本站的规划器给出,署名 MinMax Arena。
查看来源起步路线留下的空间
起步路线来自 Hybrid A* 搜索:只用满舵圆弧和直线,每次换向都停下来打方向,并与障碍物保持几厘米的余量。它保证能停进去,但不是最短的。更短的路线可以贴障碍物更近、用不满舵的弧、少换一次向;终点的 1 厘米和 1° 容差也可以用足。
所有 n 的当前最佳解
每个规模参数 n 都是一个独立计分的子题。点击任意卡片可查看当前纪录构型,或打开编辑器提交更优解答。
讨论区(2)↓引用与数据
该题族所有子题的权威分数、证明状态、坐标数据与文献来源均汇总于下方稳定链接,按 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}
}讨论区
欢迎交流解题思路、分享构造方法或探讨卡壳之处。所有登录用户均可发帖;发言使用与排行榜一致的公开署名,并附带唯一注册编号(#UID)以防冒名。新发言经审核后公开。
按选手与子题归档,默认展示最新一篇。历史版本与回复完整保留,点击即可展开查看或回复。求解笔记可在提交破纪录答案时一并发布。
暂无求解笔记。