自动驾驶中会遇到哪些不确定性决策问题？

来源：车端

决策是自动驾驶的关键部分之一，它首先融合多传感信息，然后根据驾驶需求进行任务决策，接着在能避开可能存在的障碍物前提下，通过一些特定的约束条件，规划出两点间多条可选安全路径和并在这些路径中选取一条最优的路径作为车辆行驶轨迹。然而，要实现决策规划是一个复杂的系统工程，需要精准感知环境，理解交通参与者的意图并能够在广泛丰富的场景下，实现稳定安全的无人驾驶。需要面对真实路况中的大量 “不确定性”。这种不确定性是贯穿上下游的，并且感知局限性、行为预测偶然性、规控交互性共同交织的挑战。

接下来，让我们一起了解下自动驾驶中会遇到哪些不确定性决策问题吧。

1、 什么是确定性决策？

图片

对于确定性决策问题，其在每个状态下都有已知的可选动作，而每个动作都会导致一个确定的新状态。自动驾驶传统的行为决策、轨迹规划、路径规划，都可以看作是确定性的决策。如左下图，在自动驾驶卡车行驶的某个时刻，自车以及他车的状态加上环境信息，即是我们此时的状态(state)。在此状态下，自车可以有多个宏观动作(action)可以选择，比如向左前方变道。完成此动作后，自车状态可由变道轨迹确定，他车状态可由预测模块确定，因此新的状态也是可以唯一确定的。重复此过程，并探索其他不同的宏观动作，我们便构建了一个确定性的搜索树。对于一个确定性的搜索树进行完整地求解需要从后往前遍历搜索树的各个节点，如右图。根据某状态下最大收益的action确定该状态的收益，进而确定导致该状态的action的收益。重复该过程则可以获得在初始状态下可以获得的最大收益，同时得到确保该收益所需要执行的行为动作序列。

2、什么是非确定性决策？

图片

确定性的决策问题构建和求解都比较简单。但真实环境中，其他车辆的行为可能存在各种不确定性，因此执行同一个action，其可能以一定概率导致不同的新状态。如左下图，当从初始状态，自车选择往左前变道后，右侧车辆在此过程可能保持匀速，从而自车仍然有往右变道超越的空间。但如果右车此时加速，则会导致另外一个状态，即自车不再有向右变道的空间。如果其他车辆不同action的概率已知，我们则构建了一个随机决策树。随机决策树求解如右图。求解过程和确定性决策树的区别是，每个action的收益是其导致的各个随机状态收益的期望平均。由于随机状态导致的分岔，随机搜索树的复杂度相比确定性搜索树呈指数级增加，同时随机决策问题的解不再是一个action序列，而是一个决策树。

3、非确定性决策如何反常识（1）

图片

从上面看，非确定性决策问题的求解和确定性决策没有本质区别，都是对搜索树的反向遍历。但工程实践中，了解它们的区别很有意义。无论是确定性还是非确定性决策，其搜索树都存在维度爆炸的问题，因此工程上很少使用暴力穷举的解法。对于确定性决策问题，比如行为序列决策，或轨迹/路径规划，都会把一整条动作的序列(sequence of actons)作为一个侯选解，进而在动作序列的解空间中找到最优序列。虽然该过程相比暴力穷举搜索树并没有简化，但是我们一是可以利用梯度信息来加速求解（如基于优化的轨迹/路径规划）；二是可以利用domain knowledge来对解空间进行简化，从而方便采样求解（比如lattice planner）。

确定动作序列求解法在确定性决策规划问题里确实获得了成功，因此很自然地很多人希望把这种方法套用到非确定性问题里。但这样会带来一些问题。对比右图，右下为之前得到的非确定性问题的最优解。而右上为确定动作序列套用到非确定搜索树上的形式：动作序列在每个时间步会采用同样的动作，无论此时是何种状态。可以看出，确定动作序列无法构建出非确定问题决策树的真实形式。那这具体会带来什么问题呢？

4、非确定性决策如何反常识（2）

图片

考虑这样一个例子。在双车道的高速公路上，自车以80km/h的速度飞驰。但前方出现了一个50km/h的慢车，左前方更远处还有一个30km/h的慢车。预测模块告知左前车有50%的可能即将变道。我们需要在此时规划最优的策略，从而避免本车被慢车阻挡。如果我们套用确定动作序列的求解方法，我们会发现我们只有3种可选的方案。将3种方案套用到搜索树上，即可得到各个方案的收益：方案1是直接减速跟随50km/h的前车，损失为-5；方案2、3为往左变道然后保持车道或者再往右变道，各自有50%的概率被慢车阻挡，期望损失为-7.5。此时如果我们对比三个方案，发现方案一损失最小，故而应该是最优的方案。但实际上真的是这样的吗？

如果我们采用右图中的策略：先往左变道；如果前车保持车道，则自车再往右变道；如果前车往右变道，则自车保持车道。按此策略，我们100%可以避免被慢车阻挡，从而损失为0，故这才是最优策略。出现这样的差异，原因在于确定动作序列求解法无法考虑自车可以在未来根据当时状况确定最优策略，因而认为如果向左变道，自车会有50%的概率被慢车阻挡，最后自然保守地选择了跟随前车。

我们生活中有时也会犯这样的错误。我们规划人生时，要么不考虑未知情况，当意外发生时则毫无准备；要么考虑了各种意外，但认为无论采用何种方案都会有遭遇意外的风险，从而变得畏首畏尾。如果我们在考虑未来的各种可能时，能够规划将来不同情况下各自的应对策略，则可以做出更为准确的抉择。

5、自动驾驶有哪些非确定性决策问题

图片

自动驾驶中的不确定性决策主要有两类问题。一种是宏观问题，其考虑的动作都是宏观的语义动作，而状态转移则是该动作完整执行之后的结果。这样构建方便规划到更长远的情况，从而避免局部最优，适合于一些长周期宏观问题，比如规避拥堵等。这种构建方式得到的搜索树简单，求解方便。难点在于如何对状态转移进行准确估计。

另一种是微观问题，其动作action是系统动力学输入，如加速度。而状态转移则是系统动力学模型。此类问题能精细地考虑短周期内的敏感问题，比如他车行为预测不确定时自车的避障策略。此类问题建模简单，但决策树较复杂，求解实时性是主要难点。

不确定性决策是一个非常广非常深的学科，无论是其建模还是求解都很多值得钻研的知识。因此这次分享的主要目的不是做一个综述，而是介绍非确定性决策和我们常识中的决策有何种不同，以及如果盲目套用传统决策方法会带来什么问题。这样我们在今后的工程实践中能够更好地选择解决非确定性决策问题的方法。