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

最短泊车路线 · 场景 12 · 偏置门洞,靠墙车库

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

子题场景 12 · 偏置门洞,靠墙车库
目标最小化 路程

纪录对比

路程 · 越小越好
纪录数值 / 区间作者 / 持有人来源
外部已知最好——暂无收录
本站纪录13.64800524L.M.纪录详情 ↓

严格定义

  • 车车身是一个矩形,位置指后轴中点:车头在其前方「轴距 + 前悬」处,车尾在其后方「后悬」处,宽度左右各半。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ℓ
放大编辑并提交 ↗

当前展示:本站纪录

已验证构造路程 13.649 m

帮助理解

为什么比路程

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

场景来源

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

查看来源

起步路线留下的空间

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

最短泊车路线 场景 12 · 偏置门洞,靠墙车库 的当前纪录构型,13.64800524
构型与历史

纪录详情

查看构型、求解笔记与纪录历史。

纪录保持者L.M.
解题方式AI · Anthropic: Claude Opus 5.5
挑战这个纪录 ↗提交证明 / 思路 ↓在讨论区分享最优性证明或关键界限思路,经审核采纳后可获证明分。
纪录保持者的求解笔记暂无求解笔记(点击展开)+

纪录保持者暂未分享求解过程。

历史纪录(16 次易主)
  1. L.M.AI · Anthropic: Claude Opus 5.5
    13.648007394→13.64800524
  2. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.64800768→13.648007394
  3. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.648011398→13.64800768
  4. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.648018685→13.648011398
  5. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.648021574→13.648018685
  6. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.648031935→13.648021574
  7. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.648299147→13.648031935
  8. Joost de WinterAI · OpenAI: GPT Chat Latest
    13.660248267→13.648299147
  9. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.661082961→13.660248267
  10. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.672898055→13.661082961
  11. NUE_13AI · DeepSeek: DeepSeek V4.1 Flash
    13.687064062→13.672898055
  12. qiboqiAI · OpenAI: GPT-6 Luna
    14.484974757→13.687064062
  13. qiboqi人工
    14.533021938→14.484974757
  14. qiboqi人工
    15.274677887→14.533021938
  15. qiboqiAI · OpenAI: GPT-6 Luna
    16.755231281→15.274677887
  16. qiboqiAI · OpenAI: GPT-6 Luna
    16.929056908→16.755231281
ANSWER FORMAT

答案怎么写

坐标单位为米,角度为弧度、逆时针为正,车头方向 θ 从 x 轴正方向量起。位置都指后轴中点。子题参数给出车身尺寸(car)、限制(limits)、起点 start 和车位 goal(各为 [x, y, θ]),以及障碍物 obstacles(每个是一个凸多边形的顶点)。

提交 controls:按先后顺序的控制段 [时长, 加速度, 转向速度],单位依次为秒、m/s²、rad/s,每个数都是最多九位小数的十进制字符串。车从起点出发,起初静止、前轮回正;每段控制期间加速度和前轮转向速度保持不变。结束时车必须停住、前轮回正,并停进车位(位置误差不超过 0.01 m,方向误差不超过 1°)。分数只是路程:开得多慢都可以,停着打方向不计路程。页面编辑器可以用键盘开车,也可以点“自动”让规划器走完剩下的路;它给出的就是可以直接提交的 controls。

当前第一名的答案

{
  "controls": [
    [
      "1.400000000",
      "0",
      "-0.500000000"
    ],
    [
      "1.013567199",
      "1.000000000",
      "0"
    ],
    [
      "1.013567199",
      "-1.000000000",
      "0"
    ],
    [
      "2.800000000",
      "0",
      "0.500000000"
    ],
    [
      "1.862255272",
      "1.000000000",
      "0"
    ],
    [
      "1.862255272",
      "-1.000000000",
      "0"
    ],
    [
      "0.000000004",
      "0",
      "-0.500000000"
    ],
    [
      "0.000000083",
      "-1.000000000",
      "0"
    ],
    [
      "0.000000083",
      "1.000000000",
      "0"
    ],
    [
      "2.799999996",
      "0",
      "-0.500000000"
    ],
    [
      "1.565286113",
      "-1.000000000",
      "0"
    ],
    [
      "1.565286113",
      "1.000000000",
      "0"
    ],
    [
      "1.400213743",
      "0",
      "0.500000000"
    ],
    [
      "0.788583528",
      "-1.000000000",
      "0"
    ],
    [
      "0.788583528",
      "1.000000000",
      "0"
    ],
    [
      "1.399786246",
      "0",
      "0.500000000"
    ],
    [
      "0.833868861",
      "-1.000000000",
      "0"
    ],
    [
      "0.833868861",
      "1.000000000",
      "0"
    ],
    [
      "1.400025364",
      "0",
      "-0.500000000"
    ],
    [
      "2.002535334",
      "-1.000000000",
      "0"
    ],
    [
      "2.002535334",
      "1.000000000",
      "0"
    ],
    [
      "0.410075274",
      "0",
      "-0.500000000"
    ],
    [
      "0.032258344",
      "-1.000000000",
      "0"
    ],
    [
      "0.032258344",
      "1.000000000",
      "0"
    ],
    [
      "0.989899351",
      "0",
      "-0.500000000"
    ],
    [
      "1.172255022",
      "-1.000000000",
      "0"
    ],
    [
      "1.172255022",
      "1.000000000",
      "0"
    ],
    [
      "1.400000000",
      "0",
      "0.500000000"
    ]
  ]
}
提交格式与技术细节需要编写程序或准备 JSON 答案时再查看+

子题参数

{
  "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.813217291",
    "5.910953721",
    "0.191986218"
  ],
  "goal": [
    "-0.703854264",
    "-1.717040892",
    "1.884955592"
  ],
  "obstacles": [
    {
      "kind": "wall",
      "corners": [
        [
          "-2.2304872",
          "-4.299700786"
        ],
        [
          "5.282859278",
          "-1.85846653"
        ],
        [
          "5.128350781",
          "-1.382938272"
        ],
        [
          "-2.384995698",
          "-3.824172528"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "-1.909467439",
          "-3.669664031"
        ],
        [
          "-4.103488099",
          "3.082837235"
        ],
        [
          "-4.579016358",
          "2.928328738"
        ],
        [
          "-2.384995698",
          "-3.824172528"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "5.128350781",
          "-1.382938272"
        ],
        [
          "2.934330121",
          "5.369562993"
        ],
        [
          "2.458801863",
          "5.215054496"
        ],
        [
          "4.652822523",
          "-1.537446769"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "-4.579016358",
          "2.928328738"
        ],
        [
          "-1.297871376",
          "3.994437368"
        ],
        [
          "-1.452379874",
          "4.469965627"
        ],
        [
          "-4.733524855",
          "3.403856996"
        ]
      ]
    },
    {
      "kind": "wall",
      "corners": [
        [
          "2.125932082",
          "5.106898548"
        ],
        [
          "2.934330121",
          "5.369562993"
        ],
        [
          "2.779821624",
          "5.845091252"
        ],
        [
          "1.971423585",
          "5.582426806"
        ]
      ]
    }
  ]
}

当前第一名的答案

{
  "controls": [
    [
      "1.400000000",
      "0",
      "-0.500000000"
    ],
    [
      "1.013567199",
      "1.000000000",
      "0"
    ],
    [
      "1.013567199",
      "-1.000000000",
      "0"
    ],
    [
      "2.800000000",
      "0",
      "0.500000000"
    ],
    [
      "1.862255272",
      "1.000000000",
      "0"
    ],
    [
      "1.862255272",
      "-1.000000000",
      "0"
    ],
    [
      "0.000000004",
      "0",
      "-0.500000000"
    ],
    [
      "0.000000083",
      "-1.000000000",
      "0"
    ],
    [
      "0.000000083",
      "1.000000000",
      "0"
    ],
    [
      "2.799999996",
      "0",
      "-0.500000000"
    ],
    [
      "1.565286113",
      "-1.000000000",
      "0"
    ],
    [
      "1.565286113",
      "1.000000000",
      "0"
    ],
    [
      "1.400213743",
      "0",
      "0.500000000"
    ],
    [
      "0.788583528",
      "-1.000000000",
      "0"
    ],
    [
      "0.788583528",
      "1.000000000",
      "0"
    ],
    [
      "1.399786246",
      "0",
      "0.500000000"
    ],
    [
      "0.833868861",
      "-1.000000000",
      "0"
    ],
    [
      "0.833868861",
      "1.000000000",
      "0"
    ],
    [
      "1.400025364",
      "0",
      "-0.500000000"
    ],
    [
      "2.002535334",
      "-1.000000000",
      "0"
    ],
    [
      "2.002535334",
      "1.000000000",
      "0"
    ],
    [
      "0.410075274",
      "0",
      "-0.500000000"
    ],
    [
      "0.032258344",
      "-1.000000000",
      "0"
    ],
    [
      "0.032258344",
      "1.000000000",
      "0"
    ],
    [
      "0.989899351",
      "0",
      "-0.500000000"
    ],
    [
      "1.172255022",
      "-1.000000000",
      "0"
    ],
    [
      "1.172255022",
      "1.000000000",
      "0"
    ],
    [
      "1.400000000",
      "0",
      "0.500000000"
    ]
  ]
}

提交 controls:按先后顺序的控制段 [时长, 加速度, 转向速度],单位依次为秒、m/s²、rad/s,每个数都是最多九位小数的十进制字符串。车从起点出发,起初静止、前轮回正;每段控制期间加速度和前轮转向速度保持不变。结束时车必须停住、前轮回正,并停进车位(位置误差不超过 0.01 m,方向误差不超过 1°)。分数只是路程:开得多慢都可以,停着打方向不计路程。页面编辑器可以用键盘开车,也可以点“自动”让规划器走完剩下的路;它给出的就是可以直接提交的 controls。 · 验证器 v1.0.0

DISCUSSION

讨论区

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