张春成

V2

2022/02/09阅读:76主题:默认主题

弯道超车

弯道超车

滑冰也好,赛车也好, 都是速度的游戏。 而弯道既是速度的瓶颈, 更是超越的机遇, 所以是比赛的关键。

本文是使用动态规划的方法, 对通过弯道的最快方案进行估计。 该方法简单和粗糙的不可理喻, 但它的结果似乎又有点靠谱。 气不气人。

经过一通分析告诉我们一个道理, 玩赛车或者滑冰等竞速游戏, 遇到弯道要记得

早刹车、切内弯,然后油门焊死,你就赢了。

所以,在冬奥会看滑冰, 他们那帮人才会在入弯时拼了命地使小动作, 毕竟谁占内弯,谁就赢。


最速策略及其数学原理

速度滑冰和赛车运动总可以抽象成这样的形式:

用最短的时间走完规定的路径

我们不妨将它转换为路径积分

其中, 代表路径微元, 代表经过这段路径所需要的时间, 代表完赛所需的时间。

另外,由于物理世界中, 速度、位移和时间具有严格的对应关系

其中, 代表特定时刻的速度, 代表时间微元, 代表经过一段时间之后所行进的距离。

因此,在物理世界中, 速度函数与时间函数是相互对应的

回到原始设定, 赛车游戏的目标是使 最小, 它可以在数学上抽象成这样一个泛函数

同时,需要满足路径设定

其中,可以通过下式,建立时间与路径微元之间的关系

这显然是一个泛函问题, 即求解出消耗总时间 最短的速度函数

为了对这个玩意进行求解, 只要加入速度、时间和加速度的关系即可

另外,由于是弯道,所以还需要考虑向心加速度

这一坨东西是可以求解的,解法类似 捷线问题[1]

但是说实话,并没有人真的想求解这个怪物方程。

动态规划(暴力破解)

其实这种无聊的工作只要丢给计算机做就好了,

动态规划就可以用来求解这种问题。

只不过,一般的动态规划需要求解空间是离散的, 遇到这种连续情况,需要一点点技巧罢了。

规划解法说起来也不复杂,

  • 先规定一条赛道;
  • 再把一个参赛者(你可以说它是车或者是人,反正就是一个点) 丢到上面;
  • 让它具有符合物理规律的运动能力,能够自己加速、减速、转弯;
  • 然后让它自己自由地在赛道上面跑;
  • 不断让它跑,它每跑到一个点,就复制一些它的副本继续自由的跑;
    • 怎么跑无所谓,跑到哪也无所谓;
    • 跑太快,冲出赛道了?那就丢掉;
    • 跑到终点了?那就把最先到达终点的路径记录下来;
  • 这个路径就是我们要寻找的最快路径

在这个求解过程中, 我们的参赛者(和它的无数个副本)总是

立足于当前的状态, 不断迭代地探索新的可能性, 这个求解思想就是动态规划

赛道设置

为了简单起见, 我设置了一条椭圆赛道,

Fast Race 1
Fast Race 1

规定的路径就是从最高点出发, 沿逆时针方向绕左侧半圈到达最低点, 完成比赛。

图中黄色区域是可行的赛道区域; 衬有红点的蓝色区域代表赛道外区域。

由于受到物理限制, 如果我们的参赛者由于速度太快而来不及转弯, 就会出现冲出赛道而失败的情况, 这就限制了参赛者的速度不能无脑增加, 这也是路径规划的意义。

动态规划

动态规划的具体细节并没有意思, 因此我无意在此介绍, 感兴趣的可以参考我的开源代码: 代码笔记本[2]

在这里只写一下我如何处理速度、加速度与转弯之间的关系, 为了减小计算负担,我用速度的减函数来表示加速度

其中, 代表速度, 代表加速度,当且仅当 时上式取

每次运动迭代时, 加速度可以取 种不同的方向, 这样就同时解决了加速、减速和转弯的问题。

经过求解后得到“最快路径”如下

Fast Race 2
Fast Race 2

图中蓝色实线代表估计出的路径, 上面的数字代表时间节点, 最大的数字是16,这代表需要经过16个时间单位完成比赛;

图中颜色较浅的成簇状的蓝点代表探索路径时, 全部走过的路径, 实线是其中最快的一条。

贪婪的陷阱

但问题立即出现了。 那就是,这条路径绝对不是最快的,

因为但凡有点赛车经验的人都知道, 要快速过弯, 一定是入弯时减速向内道切, 出弯时加速向外道走。

但目前的结果是直楞楞地冲向弯道中点, 然后看情况不对再紧急减速, 涉险过关, 这样速度绝对快不起来, 白白浪费动力。

问题出在哪里? 是常识错了吗?不是! 问题出在迭代时采用的贪婪算法上。

由于这种规划算法的解集是“无限”的, 因此,为了使计算在多项式时间内完成, 势必要考虑优化顺序。

目前采用的方法是

根据行进距离进行优先迭代

也就是说,每次迭代时, 都只选已经走过最长距离的那一点进行计算, 因此,就在“入弯”时陷入了局部最优的陷阱。

算法改进

要改出这个陷阱也不难, 稍微调整一下贪婪算法的择优方法就可以

根据单位时间内行进距离进行优先迭代

也就是说,不仅考虑跑得最靠前的点, 后面有潜力超过它的点也要考虑进去。

效果如下

Fast Race 3
Fast Race 3

可以看到,改进方法能够在15个时间单位内冲线, 但由于最后冲线时速度较快, 所以差不多比之前的方法领先了半个时间单位。 对于分秒必争的竞速运动, 这个领先不小了。

另外,改进方法也增加了计算量, 可以看到,在弯道弧度最大的地方它迭代的次数明显增多。 但这是不能避免的事情,因为

全局最优解,几乎必然地不是局部最优。

为了验证改进方法的有效性, 我将终点位置移到最右边, 让子弹多飞一会。 可以看到,

  • 改进前需要21个时间单位

    Fast Race 4
    Fast Race 4
  • 改进后仅需要19个时间单位

    Fast Race 5
    Fast Race 5

改进后的算法在入弯时速度稍慢, 但之后持续加速,直到撞线, 快得有道理。

经过一通分析告诉我们一个道理, 玩赛车或者滑冰等竞速游戏, 遇到弯道要记得

早刹车、切内弯,然后油门焊死,你就赢了。

所以,在冬奥会看滑冰, 他们那帮人才会在入弯时拼了命地使小动作, 毕竟谁占内弯,谁就赢。

参考资料

[1]

捷线问题: https://mathworld.wolfram.com/BrachistochroneProblem.html#:~:text=The%20brachistochrone%20problem%20was%20one%20of%20the%20earliest,by%20Leibniz%2C%20L%27Hospital%2C%20Newton%2C%20and%20the%20two%20Bernoullis

[2]

代码笔记本: https://observablehq.com/@listenzcc/the-fastest-trace-estimation-with-dynamic-programming

分类:

后端

标签:

后端

作者介绍

张春成
V2