EUDM：基于引导分支的自动驾驶高效不确定性决策

Efficient Uncertainty-aware Decision-making for Automated Driving Using Guided Branching：基于引导分支的自动驾驶高效不确定性决策

摘要

由于其他交通参与者的潜在随机行为和感知不确定性(如跟踪噪声和预测误差等)，自动驾驶汽车在密集交通场景中的决策具有挑战性。虽然部分可观察马尔可夫决策过程(POMDP)提供了一种系统的方法来整合这些不确定性，但当扩展到现实世界的大尺寸问题时，它很快变得难以计算。在本文中，我们提出了一个高效的不确定性感知决策(EUDM)框架，该框架可以实时生成复杂驾驶环境下的长期横向和纵向行为。通过特定领域闭环策略树(DCP-Tree)结构和条件聚焦分支(CFB)机制将计算复杂度控制在适当的水平。关键思想是利用特定领域的专家知识来指导行动和意图空间中的分支。利用实车捕获的车载传感数据和交互式多智能体仿真平台对所提框架进行了验证。我们还发布了框架的代码以适应基准测试。

1.介绍

近年来，在多传感器感知、预测、决策、轨迹规划和控制领域的工作，使自动驾驶能够在有其他交通参与者和障碍物的困难环境中行驶。对其他智能体的潜在意图进行推理是安全、稳健的自动驾驶系统的关键能力。然而，即使给定完美的感知，由于其他智能体的不确定和有时不可预测的意图，仍然具有挑战性，无法做出安全有效的决策。如果考虑到不完善的跟踪结果和预测误差等其他系统不确定性，情况就更糟了。

关于不确定性下的决策已经有大量的文献。部分可观察马尔可夫决策过程(POMDP)[1]为部分可观察随机环境下的规划提供了一个通用的、原则性的数学框架。然而，由于维度的诅咒，当问题规模扩大时，POMDP很快变得难以计算[2]。为了解决计算困难，在线POMDP规划算法[3]将规划和执行交错进行，只在当前信念的邻域中进行推理。在线POMDP求解器，如POMCP [4]，DESPOT[5,6]和ABT[7]已经被提出，POMDP求解器的最新进展被应用于许多自动驾驶车辆的不确定性感知规划算法[8]-[13]。然而，尽管应用了各种简化和离散化，现有方法的效率仍然不足以满足高动态驾驶场景(参见第二节的详细研究)。

整合领域知识对于有效地做出稳健的决策至关重要。多策略决策(Multipolicy decision-making, MPDM)[14] -[16]对被控(自我)车辆和其他智能体进行有限离散语义级策略(如变道(LC)、车道保持(LK)等)的确定性闭环前向仿真，而不是对每辆车的每一个可能的控制输入进行评估。然而，假设所有智能体的语义行为在整个规划范围内是固定的，这在长期决策中可能不成立。此外，如果最初的行为预测不准确，风险可能被低估[17,18]，这可能导致不安全的决策。我们的目标是控制决策问题的计算复杂性以实现实时执行，同时保持足够的灵活性和保真度以保证安全。本文提出了一种高效的不确定性感知决策框架。首先，EUDM使用特定于领域的闭环策略树(DCP-Tree)来构建语义级的动作空间。策略树中的每个节点都是自车有限时域的语义行为。然后，从根节点到叶节点的每个跟踪都代表自车的一系列语义动作。每个轨迹都以类似于[14]的闭环模拟形式进行评估，但允许自车行为在规划范围内发生变化。

DCP-Tree本质上确定了自我车辆的初步语义级动作序列，然而，其他智能体车辆的行为(意图)仍未确定。由于智能体车辆的意图组合呈指数爆炸式增长，单纯地对所有可能的智能体意图组合进行抽样是低效的。为了克服这个问题，EUDM使用条件聚焦分支(CFB)机制，在自车行为序列上使用开环安全评估条件来挑选潜在的风险场景。EUDM具有高度并行性，可以实时(20 Hz)生成长期(长达8秒)横向和纵向细粒度行为计划。主要贡献总结如下:

• 一种高效的自动驾驶不确定性决策框架。

• 提出的决策框架的实时和开源实现。

• 利用真实车辆捕获的车载传感数据和交互式多智能体仿真平台进行了全面的实验和比较，以验证其性能。

本文的其余部分组织如下。第二节将审查有关工作。第三节概述了拟议的决策框架。第四节和第五节分别详细介绍了方法和执行情况。第六节对实验结果和基准分析进行阐述。最后，第七节对本文进行总结。

2.相关工作

有大量关于自动驾驶决策的文献[19,20]。许多研究者以解耦的方式解决规划问题，即“预测和计划”[21]-[24]。具体来说，预测结果在一个规划周期内是固定的。可能存在一些缺点。首先，在这种解耦设计中，智能体与智能体之间的交互存在问题。其次，考虑到机载传感，不完善的跟踪可能导致预测误差，影响决策的安全性。第三，即使给出了完美的感知，由于部分可观测性，预测不确定性仍然在预测时域的基础上显著扩大[25]。

POMDP是一种使用一般概率框架处理驾驶任务中各种不确定性的强大工具[26]。然而，由于维度的诅咒，当问题规模扩大时，POMDP很快变得难以计算[2]。利用在线POMDP求解器的进步[5]-[7,27]，提出了几种通过简化系统模型和限制问题规模来解决决策问题的方法。规划问题分为路径规划和速度规划，而POMDP仅应用于速度规划。Hubmann等人提出了基于pomdp的城市交叉口[12]和合并[13]场景的决策方法。然而，人类驾驶知识并没有被纳入启发式设计。同时，在快速变化的环境中，效率仍然不足(小于5hz)。Cunninghan等人[14,16]提出了多策略决策(MPDM)框架，该框架将POMDP过程近似为所有智能体预定义的语义级驱动策略(如LC、LK等)的闭环模拟。领域知识的引入大大加快了问题的解决。然而，自车行为在整个规划范围内是固定的，这可能导致决策失效。此外，根据初始行为预测(初始信念)对隐藏意图(其他智能体的驾驶策略)进行采样，并且在模拟过程中不会更新。因此，由于初始行为预测不准确或意图样本不足，风险结果可能无法反映在策略评估中[17]。

在本文中，我们遵循MPDM中语义级闭环策略的思想。然而，有两个主要的区别。首先，自车的策略可以根据DCP-Tree在规划范围内进行变化，这使得它适合于长期决策。其次，在行为预测完全不确定的情况下，采用集中分支的方法对风险场景进行甄别，提高了框架的安全性。

3.系统概述

我们的系统概述如图2所示，这与我们之前的工作[28]相似。不同的是，本文的重点是决策部分。不同于将预测和规划模块解耦的方法[21]-[24]，我们的方法是在规划时域中跟踪和更新智能体的意图。

在EUDM中，DCP-Tree用于指导动作域中的分支，并基于先前的最佳策略更新语义级策略树。然后，自车的每个动作序列被安排到一个单独的线程中。对于每个自车动作序列，采用CFB机制识别出附近车辆的危险隐藏意图，并在意图空间中实现引导分支。CFB过程输出的是一组包含附近车辆不同隐藏意图组合的场景。然后通过闭环模拟评估每个场景，以并行地解释子线程中智能体之间的交互。将所有的场景反馈给成本评估模块，并对风险分支进行偏置处罚。EUDM框架的输出是由闭环前向仿真模型生成的一系列离散车辆状态(实验中分辨率为0.4 s)表示的最佳策略。将状态序列送入运动规划器，指导轨迹生成过程[28]。

4.通过引导分支进行决策

4.1关于POMDP的初步介绍

一个POMDP可以定义为<S,A,T,R,Z,O,γ>，它们分别是状态空间，动作空间，状态转移函数，奖励函数，观察空间，观察函数，折扣因子。智能体的状态是部分可观察的，被描述为信念b，它是S上的概率分布。使用贝叶斯推理，可以在给定动作a和观测值z的情况下更新信念状态。在线POMDP规划器的目标是找到一个最优策略π *，使总期望折扣奖励最大化，给定初始信念状态b0在规划时域th上。我们建议感兴趣的读者参阅[4,26]了解更多细节。

最优策略通常使用从当前信念b0开始的多步前瞻性搜索来实现。在搜索过程中采取行动并接收观察结果后，可以使用信念更新函数扩展信念树。然而，信念树的规模相对于树深度h呈指数增长，在给定大的行动空间|A|和观察空间|Z|的情况下，这在计算上是难以处理的。最先进的在线POMDP求解器[5,7,27]使用蒙特卡罗采样来处理维度诅咒和历史诅咒[27]。同时，可以使用分支定界法[5]和可达性分析[7]等通用启发式搜索来加快搜索速度。请注意，本文的重点是利用特定领域的知识来实现引导分支，这也与一般的启发式搜索技术兼容。

4.2特定域的闭环策略树

MPDM[15]指出，对于决策问题，POMDP将过多的计算精力花在了探索不太可能被访问的空间上。MPDM的主要特点是使用语义级策略，而不是传统的“状态”级动作(例如，离散的加速度或速度)。通过使用语义级策略，状态空间的探索由简单的闭环控制器(即领域知识)指导。在MPDM的激励下，我们还使用语义级策略作为领域知识的一个来源。然而，正如第二节所阐述的，MPDM的一个主要限制是自我车辆的语义级策略不允许在规划范围内改变。

例如，MPDM可以模拟整个规划周期(例如，8秒)的LC和LK策略。典型的模式，如在不同的阶段(例如，在2秒，4秒，6秒)变道不包括在它的决策空间。因此，MPDM的决策往往是局部的，可能不适合长期决策(示例见图3)。

如图3所示，为MPDM(左)和EUDM(右)的比较。自车(灰色)需要进行超车操作。MPDM的模拟行为在规划层面上是固定的。自车在通过阻塞车辆之前无法做出左变车道(LCL)决定，因此生成的计划是局部的和被动的。EUDM考虑了未来不同阶段的行为变化，从而形成一致且有远见的计划。

本文利用DCP-Tree生成未来自车行为序列，使自车的语义策略在规划时域中发生变化。DCP-Tree的节点是预定义的语义级动作，与一定的持续时间相关联。树的有向边表示时间上的执行顺序。DCP-Tree起源于一个正在进行的操作，该操作是在最后一个规划周期中执行最佳策略的语义级操作。每次我们进入一个新的规划集，DCP-Tree通过将a设置为根节点来重建。由于自车策略允许在规划范围内改变，因此挑战在于可能的策略序列的数量随树的深度(即规划范围)呈指数级增长。为了克服这个问题，DCP-Tree通过一个预先定义的策略来扩展，这个策略来自于对人类驾驶员的观察，通常我们不会在一个决策周期内频繁地来回改变驾驶策略。例如，驾驶员经常评估是否可以进行一次策略变更，例如在几秒钟内从LK切换到LC。这并不妨碍驾驶员进行复杂的操作，因为不同决策周期的连续决策可以组合在一起。在此激励下，从正在进行的动作来看，每个策略序列在一个规划周期内最多包含一次动作变更，如图4所示，而来回行为是通过重新规划来实现的。

 假设有三个离散的语义级动作{a1, a2, a3}，树的高度是3。左树和中间树的持续操作是a1，最佳策略是紫色虚线跟踪。执行a1后，正在进行的操作切换到a3，并且DCP-Tree被更新到右树。每个跟踪只包含一个操作更改。例如，假设正在进行的动作是LK，则得到的策略序列可以包括(LK-LC-LC-LC....)、(LK-LK-LC-LC....)和(LK-LK-LK-LC..)等。请注意，DCP-Tree中叶节点的大小是O[(|A|−1)(h−2)|A|]，∀h > 1，它与树的高度h呈线性增长。同样值得注意的是，MPDM只是我们的dcp树的一个分支，dcp树包括多个未来决策点。与MPDM相比，DCP-Tree具有更大的决策空间，从而具有更灵活的机动，如图3所示。此外，我们还观察到，与MPDM相比，连续规划周期之间的决策一致性显著提高。

4.3条件聚焦分支（CFB）

从本质上讲，DCP-Tree在行动空间中提供了一种引导分支机制。剩下的问题是确定附近车辆的语义级意图，即意图空间中的分支。这里的挑战是，附近车辆的意图组合与智能体的数量呈指数级增长。MPDM中，在整个规划视界内，附近车辆的意图是固定的，并根据行为预测算法对初始意图进行采样。MPDM的局限性在于，在样本数量有限的情况下，可能无法推出有影响的风险结果，尤其是在初始意图预测不准确的情况下[17]。

为了克服这一点，我们提出了CFB机制。这里的目标是找到附近车辆的意图，这些车辆可能会导致尽可能少的分支的危险结果。术语“有条件的”意味着自车策略序列的条件作用。驾驶员观察到的附近车辆的动作与打算进行的操作是不同的，例如，当司机打算进行向左变道时，他会更加注意左边车道的情况，而不是右边车道的情况。因此，通过对自车策略序列的调节，我们可以根据自车未来的行为挑选出一组相关的车辆策略。选择过程目前基于基于规则的专家知识，详见第5节。我们指出，基于学习的机制也可以被纳入，我们将其作为重要的未来工作。

通过对自车策略序列的调节，我们获得了需要进一步检查的车辆子集。与其列举所有可能的意图，我们引入一个初步的安全检查来挑选出我们应该特别注意的车辆。采用基于多个假设的开环前向仿真模型进行了初步的安全性评估。例如，对于意图不确定的车辆，我们分别预测车辆是LC或LK时的情况。在意图假设下，采用前向仿真模型进行预测。使用开环模拟的思想是，通过忽略智能体之间的相互作用，我们检查如果周围的智能体完全不合作并且不对其他智能体做出反应，情况会有多严重。对于未通过初步安全评估的车辆，在闭环前向仿真中进一步研究了不同的场景。对于通过评估的车辆，我们使用初始信念的最大后验(MAP)。因此，意图空间中的分支被引导到潜在的风险场景。在实践中，我们发现初步安全检查虽然设计简单，但可以识别出许多危险情况。算法1描述了EUDM的流程。每个策略序列的评估可以并行执行(第5行到第11行)。通过闭环前向仿真模型(8 ~ 10行)对CFB选择的每个关键场景进行并行检查。使用第5节中详细介绍的奖励函数评估每个策略(第11行)，并选出最佳策略(第13行)。

5.实现细节

5.1语义级动作

我们考虑横向和纵向行为，以确保驾驶策略的多样性。与[16]类似，我们将横向动作定义为{LK, LCL, LCR}。对于纵向动作，我们使用{加速，保持速度，减速}。请注意，这些纵向动作不是离散的控制信号，如[10,12]中的加速命令，而是连续的期望速度应用于前向仿真模型。每个语义级动作的持续时间为2秒，闭环仿真模型以0.4 s的分辨率，以保持模拟的保真度。请注意，正在进行的操作的持续时间由每个规划周期的重新规划(0.05秒)扣除。DCP-Tree的深度设为4，因此我们得到的规划视界为8 s。

5.2前向仿真

闭环仿真的目标是将多智能体系统的状态向前推进，同时考虑潜在的相互作用。仿真模型应在仿真逼真度和推理效率之间取得良好的平衡。我们分别采用IDM模型[29]和纯追踪控制[30]作为纵向和横向仿真模型。注入控制噪声以反映驾驶行为的随机特性。

5.3信念状态

本研究考虑的隐藏意图包括横向行为，如{LK, LCL, LCR}。在前向仿真过程中，对智能体车辆的信念进行了更新，如图2所示。在这项工作中，我们采用了基于规则的轻量级信念跟踪模块，该模块以速度差、当前和相邻车道上的领先和跟随智能体的距离、安全风险(RSS)[31]和MOBIL变道模型[32]等一系列特征和指标作为输入。信念跟踪器生成意图的概率分布(即LK, LCL, LCR)。在策略评估中，概率作为重要权重。在实验中，我们发现基于规则的信念跟踪器虽然结构简单，但效果良好。目前，我们正在探索使用基于学习的信念跟踪器进行意图跟踪[25]，并将其纳入EUDM框架。

如图5所示，自车正在接近另一辆车，并做出换道决策(1和2)。在自车完成向右变道后，EUDM检测到由于前车意图不确定而导致的几个危险场景。下图为另一辆车超过自车并并入我们的车道(1和2)。EUDM捕捉到危险情况并采取适当的减速策略(3)。

5.4CFB机制

（1）CFB的第一步是关键车辆的选择，对于当前车道和相邻车道，我们沿车道向前和向后搜索一定距离（根据自车速度调整），该范围内的车辆标记为关键车辆。

（2）第二步是根据初始信念进行不确定车辆选择。具体来说，我们挑选出三个意图概率彼此接近的车辆作为不确定车辆。请注意，而对于概率意图明确的，直接选取其MAP。

（3）第三步是利用开环前向仿真进行安全性评估。对于未通过评估的车辆，我们列举其意图的所有可能组合。每个组合成为一个cfb选择的情景，并计算情景的概率。第

（4）四步是根据用户偏好挑选出前k个场景，我们进一步边缘化前k个场景之间的概率。在评估过程中，边缘概率成为cfb选择情景的权重。

5.5策略评估

策略序列的总体奖励是通过对每个cfb选择的场景的奖励加权求和来计算的。奖励函数由多个用户定义指标的线性组合组成，包括效率(通过当前速度和期望速度之间的差异来衡量)、安全性(通过我们的车辆与周围车辆之间的距离来衡量)和一致性(通过最后的最佳策略与待评估策略之间的差异来衡量)。

5.6轨迹生成

我们的行为规划器的输出是一系列分辨率为0.4 s的自车的离散状态。将行为规划的结果传送到我们之前的工作[28]中提出的运动规划器（SSC），它利用时空走廊结构来生成安全和动态可行的轨迹。

6.实验结果

6.1仿真平台与环境

实验是在第三节介绍的交互式多智能体仿真平台上进行的。所有智能体可以在不知道其他车辆的驾驶模型的情况下相互交互。自车中使用的前向仿真模型可能与在智能体上运行的实际模型不同。本文提出的决策方法在c11中实现。所有的实验都是在一台配备Intel i7-8700K CPU的台式计算机上进行的，我们提出的方法可以在20 Hz的频率下稳定运行。

6.2定性结果

为了验证我们的EUDM可以在高度交互的场景中生成灵活和一致的行为，我们展示了几个使用真实世界数据和模拟的案例。

图（a）表示超车。首先，我们的车辆产生超车动作并尝试向左变道，因为它自信地认为前方车辆将会保持车道行驶(1)。其次，在自车接近区域时，前方车辆加速，因此不确定前方车辆是否会在自车之前插入。根据闭环仿真结果(2)，CFB识别出该危险情景，自车计划减速。第三，前方车辆减速。虽然之前的危险场景仍未通过开环模拟的初步安全评估，但在考虑相互作用的超车行为下，闭环模拟成功了。自车经过评估后，决定加速通过。

图（b）表示(b)放弃超车，给其他车辆让路。首先，我们的车辆决定向左变道并超车(1)。其次，前车加速，在评估潜在风险后，自我车辆决定减速跟随前车进行向左变道(2)。第三，前车进行向左变道，后面的车辆试图超过我们(3)。然后，自我车辆决定放弃向左变道并屈服(3和4)。

（1）冲突地区的超车和让步：冲突区域在城市交通中很常见。如图6所示，自车必须通过一个冲突区域，而该冲突区域有一辆前方车辆也试图变道并通过。此外，在当前观测条件下，前方车辆的初始信念是不确定的。如图6所示，EUDM框架可以根据情况自动选择合适的行为(即超车或退让)。

（2）测试使用真实的车载传感数据:在这种情况下，我们的方法以开环的方式通过使用真实自动驾驶车辆收集的数据进行测试。目的是验证所提出的方法是否可以捕获风险场景，并在不确定预测和噪声感知下工作。如图5所示，EUDM可以根据情况做出适当的超车或减速决策。

6.3定量结果

我们与MPDM进行了全面的定量比较[16]，MPDM是最先进的自动驾驶决策方法之一。我们使用两个基准轨迹，即Double Merge和Ring来评估这两种方法。详细实验见附件视频，统计结果见下表。

（1）指标：我们引入三个主要指标来评估两种方法的性能，即安全性，效率和舒适性。为了安全起见，我们计算自车与其他智能体之间的距离小于阈值(即安全距离)的帧的比例。效率用整车的平均速度表示。舒适性由每公里不舒适减速次数(UD)和大曲率变化次数(LCC)来描述。UD和LCC的阈值分别设置为1.6 m/s2和0.12 (s·m)−1。

（2）基准测试:我们还通过从EUDM中去除CFB机制进行了研究，得出了EDM方法，如表所示。目的是验证CFB是否可以提高框架的鲁棒性和安全性。如表1所示。根据安全度量，EUDM比EDM和MPDM做出更安全的决策。原因是EUDM明确地探索有风险的场景并进行有偏差的分支。注意，双合并地图是一个密集的交互场景，由于代理车辆的攻击性行为，不安全的情况很难完全避免。在效率方面，我们的方法和MPDM表现相似，而EDM具有更高的平均速度。这是因为EDM比MPDM扩大了行动空间，可能会采取过于激进的冒险行动(见图3)。在舒适性方面，EUDM可以生成比其他两个基线更平滑的行为，因为它事先在风险场景下采取保守策略，避免了硬刹车。

7.结论及未来工作

本文通过引入两种新技术，即DCP-Tree和CFB机制，提出了密集交互场景下自动驾驶的EUDM框架。完整的框架是开源的，并使用真实世界的数据和仿真环境进行综合评估，未来，我们将对EUDM框架进行闭环现场测试。

8.参考链接

EUDM与MPDM的对比：https://zhuanlan.zhihu.com/p/638795181