决策规划算法的思考

c0d3n4m · 发表于 2022-12-18 09:38

一些不成熟的思考，希望能抛砖引玉，和大家碰撞出思维的火花。

基于采样的决策算法

基于采样的决策算法应该算是现在比较主流的决策算法了。相比于有限状态机，功能的ODD算是有了质的飞跃。基于规则的邮箱状态机决策算法被广泛应用于辅助驾驶方案中，但也仅限于辅助驾驶了。当处理下匝道问题时，一旦车流密度提升，有限状态机也就瘫痪了。我们以这个场景作为例子来看基于采样的决策算法的工作流程。采样算法会采样横向轨迹与纵向动作。横向轨迹会产生多个备选轨迹，有继续直行的轨迹，也有直行一段距离后开始变道的轨迹。然后环境将被一一映射到这些横向轨迹上给到纵向采样，也就是一张张S-T图。纵向采样会在时间序列上采样动作来在这一张张S-T图上寻找合理的纵向速度分配。相比于有限状态机，由于采样的方案在横向纵向上有大量的备选方案，因此更有可能在复杂的场景下寻找到合理的解。但是根据刚才的描述，横向与纵向的采样结果耦合在一起来看，会产生上千条需要评估的轨迹，这个状态更类似于lattice planner。因此并行运算在这里显得有为重要。横向轨迹之间的评估是可以完全并行计算的，每个横向轨迹下的纵向轨迹评估也是完全可以并行计算的。因此对于多核处理器部署这类算法，计算速度其实是能够保证实时性的。但如果针对一个算力并不高的辅助驾驶控制器，又该如何部署这种能够处理较复杂场景的决策算法呢，我的建议是放弃，放弃解千愁。
另一个值得一提小小的话题是，刚才我们谈到纵向采样是采样动作，而lattice planner中横纵向均采样了状态。这是为什么呢？其实可以这么理解，我们之所以采样动作，是将纵向问题放在了时空间下考虑，这个时序上的动作需要有更多的自由度，可能需要车辆有多次变速动作。因为需要在离散时域上采样出线性连续的多个加速度动作，从而通过两次积分获得自由度极高的s-t图中的通行轨迹。如果仅仅采样终点状态(lattice planner的做法)是不可能处理复杂的纵向时序运动的。另一个值得一提的是lattice planner的提速，除了刚才提到的并行运算加速，更常见的方案是通过强决策方案压缩采样空间以及采样优化算法搜索最优解而不是采用遍历评估所有轨迹。

基于推演的决策算法

基于推演的方案是运用了pomdp的思路开发的，pomdp本身能够考虑状态和观测的不确定性。但是为了保证算法的实时性要求，我们通常都会以此为基础作出一些列简化，比如动作概率的简化，我们通常会利用智能交通流模型来计算当前推演环境下的各个交通参与者的运动动作。而在原始pomdp的算法中，动作本身也具备不确定性，这里我们就将这个部分的积分简化掉了。另一个常用的简化是在这个时序推演过程中锁定各个交通参与者个运动意图的置信空间。当然我们完全可以通过牺牲计算耗时将belief update考虑进行，这时候就要权衡实时性和精确度了。而还有一个简化方案是剪枝自车的未来动作可能性，这将大大减小推演过程的树的树枝增长。这种剪枝可以是MPDM中的但一行为，也可以是EPSILON中的DCP tree。这里值得一提的是，我再次看了MPDP后发现直接选择单一动作是完全没问题的，并没有像EPSILON中所说的不能不出先直行后变道的场景。因为推演的过程类似于模型预测，推进自车和周围环境的未来状态，并且是实时推进，单步直行，因此对于先直行后变道的这个时序过程是完全可以执行出来的。
推演方案与刚才的采样方案相比，能够进一步拓展处理问题的ODD。为什么这么说，还是回顾刚才的下匝道场景，如果此时是一个严重堵车场景，下匝道必须要采用冒一定风险的强行加塞变道动作才有可能创造出一定的可能变道空间，此刻通过推演方案，我们可以预测到后车可能的让行可能性，从而在推演进行中打开变道窗口。而这个场景在采样方案中将是完全不可行的。因为当前的两车距离很小，甚至不满足采样决策中所规定的允许变道的最小空挡要求，自然不可能采样出任何可行轨迹。这里要强调的就是采样方案忽略了当本车做出当前动作后，后车将会做出潜在的可能响应（尽管这个响应不一定发生），从而影响预测结果，从而再进一步影响下一步的本车动作。这个连续时序上的互相影响过程在当前时刻的采样决策中是处理不了的，因为此时决策模块收到的预测信息无法考虑本车的未来动作，采样模块的评估器也无法评估本车未来动作又将如何影响周围环境。

强决策还是强规划

看到一个对决策和规划的观点：认为这两者应该是完全独立的子模块，可以以任意算法形式作为子模块独立开发，然后进行组合。这种强解耦的低聚合软件设计思路当然完全没有问题，也无法评论对错，或许不同的人思考问题的角度是完全不同的。
关于这个观点，我们思考两个问题：1，绝对解耦就是一个规划算法或一个决策算法好坏的唯一判别标准吗，如果有一套规划决策强耦合的算法，就一定是毫无意义的吗？显然不是，强耦合的著名方案就是apollo(decider and optimizer相互串行)，但如果你要说apollo确实就是垃圾那么请私信我一套你写出的好代码让我信服一下； 2，完全独立的子模块，是什么层面的独立？我认为应该是算法本身实现的独立，但在软件架构的设计层面，他们要强耦合。这就引申出来标题的关键词，我们应该更倾向于强决策方案还是强耦合方案呢？下面我们就这两个问题展开讨论。
第一个问题，关于apollo的做法，以路径规划算法为例，我们先看这个方法本身的特点：基本思路是进行path的决策，path的规划，速度的决策，速度的规划。这是一个典型的时空间解耦的算法，常常很多人看不起，认为决策规划就应该用时空间耦合的算法。但是方式是针对问题产生的，如果处理简单的场景，将时空间解耦处理，没有任何问题，而且可以简化问题的复杂度，是最好的工程化方法。然后我们回到第一个问题本身，解耦性。再来看这个方法，因为决策模块decider和规划模块optimizer互相串行产生，串行的原因就是刚才讲的由于解耦了时空间问题，从而必须先有空间轨迹，才能映射时间障碍物到空间轨迹上。因为无论从算法本身的设计，还是软件架构的设计上讲，这个方案必须是决策规划强耦合方案，因为两者互相影响着各自的算法选择。
第二个问题，强决策还是强规划。有两种很典型的方法，我们先来介绍一下。当然这个名词是我自己的分类，并不权威。我所认为的强决策方案：决策模块承担了较重的工作，规划模块或者说规划算法作为子模块在决策模块中被调用。举一个例子，在处理下匝道场景时，决策模块会计算出多个备选动作，比如加速超车变道，减速加塞变道，或者继续等待。这个备选动作，可以是语义级别的，也可以是粗轨迹级别的，甚至可以是精细轨迹级别的；然后在每个备选动作中，决策模块掉起规划算法，这当前的决策动作下，规划出一条轨迹，这条轨迹一定是精细的轨迹，满足了车辆运动学动力学约束，也考虑了舒适性，以及安全性。这样每个备选动作下都在最后规划出了一条对应的轨迹，最后通过评估模块仲裁出当下最优的轨迹。这样做的好处是将所有可能的备选动作都进行了精细考虑，得出的结果一定是最优且可行的。这是一种我认为的强决策方案。
另一种强决策，通过基于搜索的，或者动态规划，或者任何带有决策属性的算法的方案在时空间上找到一个粗解，并且这个粗解的生成过程考虑了较为完备的车辆运动学动力学约束，舒适度以及安全性。且这个过程是有明显耗时的，如采样决策算法，动态规划算法等。这个粗解虽然名为粗解，但其实已经是质量很高的初始解了，甚至对车辆运动精细程度要求不高的情况下都可以直接被控制使用。这个粗解将给到规划模块进行精细化规划，计算出最后的轨迹。这个时候给到规划模块的压力其实已经很小了。
与之相对的另一种方案我称之为强规划方案，也就是将更多的工作交给了规划。决策模块仅仅决定做什么事情，而如何做则交给规划。再这样的方案下，决策需要选择高效且考虑全面的算法既能考虑到尽量多的影响元素，又必须计算迅速。还是以下匝道为例，决策可以给出刚才说的三个备选动作，通过可行性和必要性分析直接评估中该做什么动作（当然也可以是简单的粗轨迹，如折线，连续度较低的散点等等），规划模块仅在这个动作的约束下进行规划。但是潜在的问题是由于决策不会考虑这么多，有可能导致规划在这个动作约束下根本找不到合理解。比如刚才决策决定了加速超车变道的方案，然后规划根本找不到一个合理的完成这个动作的方案。正因为决策给到的信息并不多，最差的情况只是从语义层面分割了时空间，保证了规划在处理一个凸问题，剩下的都交给了规划模块，此时规划的压力就变大了，需要解决一个初始解质量不高，参考信息不完备，约束有可能互相冲突的复杂优化问题，往往这个问题不是良定义的，偶尔带来优化问题无解的后果，因为规划模块需要充分考虑问题的复杂性，和算法本身的鲁棒性。

时间空间解耦还是不解耦

上面提及apollo的解耦方案，确实在简单场景下是最优的工程化选择，但是遇到较为复杂的场景，处理起来并不好。比如典型的动态借道超车场景，这需要时空间进行耦合规划，此时时空间联合规划就起到了作用。但是我们上面也说过了，决策算法和规划算法是耦合的，并决策也可以帮助规划算法干很多事。比如通过一个采样决策的方案，可以直接获得时空间上的初始解，这个初始解也可以直接定义出时空间上的通行走廊。注意此时由于决策的通盘考虑，初始解已经做到了在当前场景中选择最优方案。也就是说，在这个初始解及其定义的约束下，规划模块可以处理时空间耦合的问题，做到边超车，边变道的动作。此时我们依旧可以采用时空间解耦的优化算法处理当前的问题，这在无人机算法中很常见，就是将一个三维问题压缩成两个两维问题求解。当然，也完全可以将优化问题定义成一个优化变量是刚才两倍的三维问题直接求解。所以这个现象告诉我们，决策和规划分不开，他们互相可以影响对应的算法选择，两者一同考虑才能决定最优的算法组合。

预测在什么位置

常规的预测是独立于规划进行的，当提供预测时，由于其他交通参与者和车上感知噪声的随机性，不可能产生一个完美的预测。而且在独立预测下，无法模拟自我车辆与其他车辆未来运动的相互影响。比如临界汇入，在这种相互影响至关重要的情况下，耦合预测和规划更有前景。
我们考虑一个经典的决策方案POMDP：隐藏状态是在置信度更新过程中通过观察逐步估计出来的，这正是行为预测的作用。因此，POMDP隐式地包含预测，表明规划和预测是自然耦合的。同样值得注意的是，将预测和规划解耦的方法本质上是对原POMDP公式的简化。
从预测的角度来看，多目标正向模拟推进就像一个条件预测，它将预测过程限制在被控agent的决策上。这印证了通过考虑多目标，包括自车未来的潜在运动意图，预测器可以获得更好的性能。因此预测模块万万不可独立于决策和规划。

ChuanXin · 发表于 2022-12-18 09:38

大佬，这个可以采用时空间解耦的优化算法处理当前的问题，这在无人机算法中很常见，就是将一个三维问题压缩成两个两维问题求解！
这个有具体的论文可以参考嘛？

闲鱼技术01 · 发表于 2022-12-18 09:47

写得太好了！受益匪浅

DomDomm · 发表于 2022-12-18 09:56

搜一下minimum snap算法和相关论文

zt3ff3n · 发表于 2022-12-18 09:58

嗯嗯，好的

ainatipen · 发表于 2022-12-18 10:07

多谢大佬[爱]

c0d3n4m · 发表于 2022-12-18 10:17

时间每次都手动分配？

		自动登录	找回密码
密码			立即注册