最短泊车路线 · 场景 12 · 偏置门洞,靠墙车库
一辆前轮转向的汽车(运动学自行车模型,矩形车身)从给定起点开进给定车位,全程不碰障碍物。求后轴中点走过的路程最短的路线。每个子题是一个场景。
纪录对比
路程 · 越小越好| 纪录 | 数值 / 区间 | 作者 / 持有人 | 来源 |
|---|---|---|---|
| 外部已知最好 | — | — | 暂无收录 |
| 本站纪录 | 13.64800524 | L.M. | 纪录详情 ↓ |
严格定义
- 车车身是一个矩形,位置指后轴中点:车头在其前方「轴距 + 前悬」处,车尾在其后方「后悬」处,宽度左右各半。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;越小越好
- 目标在所有停进车位且不碰障碍物的路线中使路程最短