P98 · 最短泊车路线 · 讨论

P98 s07证明

NUE_13

================================================================ P98 shortest-parking-route / s07 —— 一个可证明最优的实例 附完整闭式、盒内精确极小、以及踩过的坑 ================================================================ 【结论】 s07 的最优值 = 9.483095650 m(我提交的解), 站点容差盒内的绝对下界 = 9.483068240 m。 即在 (9.98 mm, 0.998 deg) 这个内缩盒上,我的解就是精确最优 (盒内极小 9.483095653,与解差 3e-9,纯属 9 位小数取整)。 与全容差盒的绝对下界只差 0.027 mm。 s07 是 12 个实例里唯一一个障碍完全不参与约束的: 最优路径离最近障碍/墙 252.5 mm,而规则只要求 0.1 mm。 所以它是唯一一个可以把问题当成「纯点车 + 终点容差」来精确求解的实例。 ---------------------------------------------------------------- 0. 记号与几个先把话说清楚的事实 ---------------------------------------------------------------- 参数(12 例共用): wheelbase 2.8, frontOverhang 0.96, rearOverhang 0.929, width 1.942 speed 2.5, accel 1, steeringAngle 0.7, steeringRate 0.5 曲率上限: KMAX = tan(0.7)/2.8 = 0.3008172787 r = 1/KMAX = 3.324277 分数 = 后轴中点走过的弧长。(不是时间、不是控制条数) 三个容易被忽略、但可以直接利用的规则细节: (a) 速度与加速度与分数无关。分数只累计位移, 所以「跑多慢」「用多少条控制」都不影响分数。 (b) 静止打方向是免费的。车速 v=0 时角速度 = v*K = 0, 所以 [T, 0, ±0.5] 这类控制既不移动也不改变分数, 只消耗时间。因此「打方向盘」不进入代价函数。 (c) 终点容差是「每轴」而不是「半径」。 实测:多个 (dx,dy) = (9.8 mm, 9.8 mm) 的提交被接受, 其欧氏偏差 13.9 mm > 10 mm。所以容差盒是 |dx| <= 0.01, |dy| <= 0.01, |dtheta| <= 1 deg 的轴对齐盒子,四个角都是合法的,不是圆。 推论 (c) 非常重要:最优解几乎总落在盒角上(见第 3 节), 盒内 1 cm 的横向自由度值大约 0.5 m 路程。 ---------------------------------------------------------------- 1. 下界:把问题放松成「点车问题」 ---------------------------------------------------------------- 设 (x(t), y(t), th(t)) 是后轴中点在任意一条合格轨迹上的位姿。 因为转向角受限,处处有 |kappa| <= KMAX;因为可以前进/倒车, 曲率可正可负;换挡点(cusp)随时允许。 于是这条轨迹就是一条「曲率受限的点车曲线」,其长度 L = ∫ |v| dt = ∫ |ds| 满足 L >= d_RS(起点位姿, 终点位姿) 其中 d_RS 是 Reeds-Shepp 距离(点车、|kappa|<=KMAX、允许倒车与 cusp 的最短长度)。 另外终点位姿必须落在容差盒 B 内,所以 L >= min_{P in B} d_RS(start, P) =: LB(B) 注意这个放松扔掉的东西:障碍(只会增加长度)、 速度/加速度/转向速率限制(只会缩小可行集)、 控制条数与时间上限。所以 LB(B) 对任何合法答案都成立。 这就是全部证明的第一半,而且不依赖任何数值优化。

NUE_13

---------------------------------------------------------------- 2. 点车问题是闭式的:Reeds-Shepp 48 词 ---------------------------------------------------------------- RS 的极值原理说:最短路径是有限段 {L±, S±, R±} 的拼接, 穷举后只有 48 个词(12 个基词 x 反射/时间反演)。 把目标换到起点车体系并无量纲化: x = KMAX*[ cos(th0)*(X1-X0) + sin(th0)*(Y1-Y0) ] y = KMAX*[-sin(th0)*(X1-X0) + cos(th0)*(Y1-Y0) ] phi = th1 - th0 s07 的答案是基词 LRSL,四行闭式: u1 = sqrt( (x - sin phi)^2 + (y - 1 + cos phi)^2 ) u = sqrt(u1^2 - 4) - 2 A = atan2( 2, sqrt(u1^2 - 4) ) t = mod2pi( atan2(y - 1 + cos phi, x - sin phi) + A + pi/2 ) v = mod2pi( t - phi + pi/2 ) 可行 <=> u1 >= 2 且 t >= 0 且 v >= 0 长度 L = ( t + pi/2 + u + v ) / KMAX 四段(曲率, 行程): [ +t , L ] 前左弧 [ -pi/2 , R ] 倒车右弧 <-- 注意这一段是常数 [ -u , S ] 倒车直行 [ -v , L ] 倒车左弧 第二段 −pi/2/KMAX = −5.221762 m 与终点完全无关, 这是 LRSL 这个词的签名,也是最容易自查的地方。 s07 实际数值: 起点 (1.5, -6.8, -2.967059728) 目标 (0,0,-1.078743332) + (9.98mm, -9.98mm, 0.998deg) (x, y, phi) ~= (0.086730, -2.089331, 1.905735) 四段长度 = [ +1.188922, -5.221762, -2.996918, -0.075493 ] m 合计 = 9.483095653 m 自查(强烈建议自己做一次): 把这 48 词全部实现后, (i) 每个候选解仿真回目标点,误差应 < 1e-14; (ii) d_RS(a,b) 与 d_RS(b,a) 应相等(我实测差 1e-15)。 这两条一过,闭式基本不会错。 ---------------------------------------------------------------- 3. 容差盒上的极小:为什么一定在盒角 ---------------------------------------------------------------- 需要一把「距离函数对终点扰动有多敏感」的尺子。实测三定律 (起点固定在原点、零位姿): 纵向 eps : d = eps (严格 1-Lipschitz,且紧) 旋转 dth : d = r * dth (严格,且紧) 横向 eps : d = 2*sqrt(2*r*eps) (!!! 平方根律) 横向这条就是平行泊车的标度律,实测比值 1.4142 = sqrt(2): eps = 1e-2 -> d = 0.515534 eps = 1e-3 -> d = 0.163072 eps = 1e-4 -> d = 0.051569 (2*sqrt(2*r*eps) = 0.051571) eps = 1e-5 -> d = 0.016308 三个直接后果: (i) RS 度量对横向位移不是 Lipschitz 的(d/eps -> 无穷)。 所以在横向方向,距离函数在 0 处是「尖点」, 它的极小总是被推到盒子的边界上。12 个实例实测 12/12 最优终点都在盒角(或至少在某几个轴上贴边)。 (ii) 横向 1 cm 的自由度值 0.5155 m 路程。这就是为什么 榜上所有解都贴着 (0.01, 0.01, 1deg) 的角。 也解释了为什么「把终点从 0.0098 m 挪到 0.00998 m」 这种看似无聊的操作能换来 0.25 mm。 (iii) 想用 Lipschitz 分支定界「严格证明」盒内下界是不通的: 要用到的模量是 omega(s) = 2*sqrt(2*r*s),于是盒边长 h 必须 h ~ eps^2 / (8r) 才能把界压到 eps。要证到 1e-4 m 需要 h ~ 4e-10 m,二维要 5e16 个盒子。实践上不可能。 正确做法是:不要在盒上做区间搜索,而是 对每个词,把它的长度当作 (x,y,phi) 的光滑函数直接极小。 极小要么在盒角(直接代入),要么满足 grad L = 0(Newton/ Nelder-Mead 收敛到机器精度)。48 个词 x 多起点即可。 这就是本文所有「盒内精确极小」的来源。 用这个方法算 s07: 盒 (0.01000 m, 1.000 deg) -> 9.483068240 <== 绝对下界 盒 (0.00980 m, 0.980 deg) -> 9.483342367 盒 (0.00998 m, 0.998 deg) -> 9.483095653 <== 我提交的是 9.483095650 最优盒角都在 (dx, dy, dth) = (+w, -w, +w) 这一类顶点上。

NUE_13

---------------------------------------------------------------- 4. 上界:显式可行解 ---------------------------------------------------------------- 按上面取盒角 (9.98mm, -9.98mm, 0.998deg),得到 4 段 (s,k) 链: s = [ +1.188922, -5.221762, -2.996918, -0.075493 ] k = [ +KMAX, -KMAX, 0, +KMAX ] 转控制序列的固定套路(因为静止打方向免费): 每段之前先 [ |dphi|/0.5 , 0, ±0.5 ] 把方向盘打到位, 然后按行程 L=|s| 走: L <= vmax^2/amax = 6.25 : [ sqrt(L), ±1, 0 ] x2 L > 6.25 : [2.5,±1,0] + [(L-6.25)/2.5,0,0] + [2.5,-1,0] 负号 = 倒车。 得到 13 条控制,总时间 19.163 s,峰值车速 2.285(< 2.5)。 独立复验(RK4, dt = 2e-5, 直接用 9 位小数的控制串): len = 9.483095649 dx = 9.982e-3, dy = 9.979e-3, dtheta = 0.9980 deg 机身最小余隙 = 0.252488 m ---------------------------------------------------------------- 5. 所以 ---------------------------------------------------------------- 下界:任何合格答案 >= 9.483068240 (站点容差盒全用满时) 上界:存在合格答案 = 9.483095650 (余隙 0.25 m,远离一切障碍) 差 0.000027 m,完全来自我给取整/模型误差留的保险。 若把目标盒内缩到 (9.98mm, 0.998deg)(我的解就落在它的角上), 则盒内精确极小 = 9.483095653,与解差 3e-9 —— 该盒上的最优性成立。 换句话说:s07 在这道题里是「可以用纸笔算完」的。 48 个候选挑一个,代 5 行公式,收工。 ---------------------------------------------------------------- 6. 复现清单 ---------------------------------------------------------------- 1) 实现 48 词,用「仿真回目标」和「d(a,b)=d(b,a)」两条自查。 2) 对每个词,在容差盒上做多起点 Nelder-Mead(建议 5x5x7 起点 + 6 轮收缩精修),取全局最小;盒角单独代入。 3) 用第 4 节的套路把 (s,k) 转成控制串,控制串按 9 位小数取整后 再用细步长 RK4 复验(dt <= 2e-5)。 4) 自查三个数:机身余隙、每轴 dx/dy、|dtheta|。 ---------------------------------------------------------------- 7. 一些 Negative results(可以省你时间) ---------------------------------------------------------------- a) 用 1-Lipschitz 模量做分支定界 -> 是错的。 横向是 sqrt 律,d/eps 随 eps->0 发散, 用 |dB| 当模量会给出「假下界」,看起来能证明最优,其实是假的。 我一开始就算出过 9.482895 这样的「认证下界」,比真下界还低,是无效的。 b) 反过来,「盒上采样最小值 + 一个 Lipschitz 修正」也不够: 修正项量级是 sqrt(2*r*h) 而不是 h,永远压不到 1e-4。 c) 逐词直接极小是可行的替代:每个词的光滑函数极小是可靠的, 唯一残余风险是「多起点漏掉全局最小」,用足够密的起点 + 收缩精修 可以把它压到 1e-9 以下(不同起点收敛到同一个值即是证据)。 d) 不要用四舍五入后的顶点坐标去手算障碍距离。 在 s07 里我用手算把 3.354 mm 算成了 2.0 mm, 原因是边线平移 3.77 mm —— 一度让我以为是距离函数有 bug。

NUE_13

---------------------------------------------------------------- 8. 另外 11 个实例为什么证不了;后续方向 ---------------------------------------------------------------- 对 11 个实例逐一检查「点车最优路径」的机身余隙,结果全部为 0 (即 RS 最优解直接撞进障碍)。所以 d_RS 下界对它们没有任何证明力。 把「我的解长 − 同端点上的 d_RS」定义为障碍成本 obsCost: s01 0.594 s02 0.742 s03 0.232 s04 0.171 s05 0.493 s06 0.951 s07 0.000 s08 1.372 s09 3.694 s10 3.046 s11 0.586 s12 2.609 (单位 m) 只有 s07 是 0。 这 11 个实例的正确描述是「受约束的 bang-bang + 障碍接触」: * 每段最优曲率只取 {0, ±KMAX}; * 满舵段是绕瞬心 C = (x - sin(th)/k, y + cos(th)/k) 的刚体旋转, 车身角点到 C 的距离 rho(a,b) = sqrt(a^2 + (b - 1/k)^2) 恒定, 于是「角点撞障碍边线」是单条三角方程 cos(th - psi) = -d / rho 弧段内部的最优点 <=> 该方程取重根 <=> |d| = rho(圆与直线相切); * 对偶族(障碍顶点撞车身边线)同形:|D| = h; * 段端 cusp 处的接触不满足相切关系(实测 d - rho = -2.43 / -2.35)。 这些逐条数值验证过,是判断「当前解是否真的最优」的好工具 (相切条件不成立且不是 cusp 接触 -> 说明还没到最优)。 但全局最优仍要「词 x 接触模式」的有限枚举,没有初等闭式。 剩下的可见收益主要在两处: (i) 终点盒角。0.01 m/1 deg 是全合法区域,横向每 0.2 mm 值 ~0.7 mm; 我用满到 (0.00998, 0.998 deg),12 个实例合计压了 9.6 mm。 (ii) 换词。s06/s10/s11/s12 的端点在 theta 方向的最优点是盒内部 (dtheta = 0),扩盒无效,说明它们的瓶颈是路径词而不是余量。

NUE_13

本证明由DeepSeek V4.1 Flash生成。

NUE_13

现在的记录又经过了两轮压缩,已经非常极限地逼近下界9.483068240,目前记录9.483068837已经非常非常极限,但我opencode的今日免费额度用光了啊啊啊 贴个数据你就知道有多极限了:dx=9.999992111e-3、dy=9.999990199e-3、dθ=0.999998987°,而提交要求需要dx=1e-2, dy=1e-2, dθ=1°(d指误差),离误差上限都仅剩1e-4以下。

NUE_13

也就是最优已被证明了,可还没有完全成功实现验证器能通过的理论最优。大肥鱼太爱放水了……