自动驾驶系统并行加速测试方法研究*

张培兴，邱 彬，朱 冰，赵 健，孙宇航，范天昕

（1. 吉林大学，汽车仿真与控制国家重点实验室，长春 130022；2. 清华大学，汽车安全与节能国家重点实验室，北京 100084；3. 工业和信息化部装备工业发展中心，北京 100846）

前言

随着自动驾驶技术的不断成熟，实现自动驾驶汽车量产上路已具备了一定的技术可行性，然而如何验证自动驾驶系统的安全性尚未形成统一的共识，这已成为制约自动驾驶汽车量产的重要障碍。

基于场景的测试方法是解决自动驾驶系统安全性验证难题的重要手段，根据自动驾驶汽车的开发过程将测试场景分为功能场景、逻辑场景和具体场景3 个层次。具体场景作为测试过程中直接使用的场景结构，其生成方法已成为当前的研究热点。在研究初期，从逻辑场景抽样具体场景的过程多采用遍历获取所有组合或蒙特卡洛随机生成的方式。由于逻辑场景中覆盖大量的安全具体场景，这类场景对于测试过程而言价值较小，降低了整体的测试效率。为解决这一问题，基于危险场景强化生成的加速测试方法得到越来越多的关注。这类方法主要分为基于概率的方法与基于优化的方法两类。基于概率的方法最先由Zhao 等提出，其使用重要性采样的方式建立似然函数，提升危险场景发生概率从而提高测试效率；Feng等和Gao等也提出了类似的基于概率的危险场景生成方式。基于优化的方法将危险场景看作参数空间中的最优解，寻找危险具体场景的过程可视为参数优化的过程，Zhu等建立了多种优化搜索框架。

然而，上述两类加速方法大多基于串行处理结构，即下一试验点的生成必须依赖上一试验结果，这使其无法充分利用并行计算的优势。随着自动驾驶系统复杂程度的增加和应用范围的扩大，其须测试的场景数量呈指数爆炸的形式，并行的测试手段将成为未来自动驾驶测试的趋势。一些学者已开始将并行测试手段引入自动驾驶系统测试过程，Andreas 等将快速搜索随机树引入并行测试中，百度也正在建立自动驾驶并行测试实验室，但现有研究大多未考虑危险场景的强化生成，尚未实现并行测试与加速测试的有效融合。

为解决上述方法的不足，本文中将并行测试方法与基于优化的危险场景生成框架相融合，提出一种自动驾驶系统并行加速测试方法。该方法分为3层架构：顶层管理层负责子集空间之间底层执行单元的流动和子集空间关闭与合并；中层协调层负责下属子集空间内底层执行单元测试参数的生成；底层执行层负责具体试验的运行。以前车切入场景为例，对某黑盒自动驾驶算法分别使用并行加速、并行遍历、单线程加速和单线程遍历4 种方式进行对比测试，在测试具体场景总数为4590 的情况下，4 种方式均发现所有危险场景，其分别耗时1.3、5.7、22.4和96.2 h，证明了本文方法的有效性。

1 并行加速测试架构

随着自动驾驶系统复杂程度的增加，测试过程须考虑的要素数量不断提高，由此导致逻辑场景参数空间迅速增大，且随着测试要素种类的增加极易产生维度爆炸现象，传统矩阵测试的方式在测试效率和测试成本等方面已无法满足自动驾驶系统的测试需求，基于危险场景强化生成的加速测试方法成为自动驾驶系统安全性验证的主流。

将加速测试方法与并行计算方式相结合，提出由顶层管理层、中层协调层、底层执行层构成的3 层并行加速测试架构，在充分利用多计算单元优势进行并行计算的前提下，通过危险场景强化生成进一步加速测试进程。加速测试架构如图1 所示，每层包含若干个计算单元。

图1 并行加速测试架构

在试验过程中，首先将逻辑参数空间的全集空间按照一定的规律划分为若干个仅包含参数空间不同部分内容的子集空间；分配不同计算单元的角色，包括顶、中、底3 层，整个全集空间仅包含一个顶层管理单元，每个子集空间有其各自的中层协调单元，其余均为底层执行单元；将底层执行单元平均分配到不同的中层协调单元下属的子集空间中进行参数试验；随着试验的进行，顶层管理单元协调底层执行层中的不同底层执行单元在不同子集空间之间进行流动，将量化指标值较差的子集空间中的低效单元转移到量化指标值较好的子集空间；中层协调单元计算下属子集空间内的底层执行单元执行试验的具体参数，并标记下属子集空间内的低效单元；底层执行层由多个并行的计算单元构成，它们可各自独立地接收中层协调层发送来的试验参数进行试验。相比现有方法，由于将逻辑场景参数空间分区，可以在宏观层级保障测试的完备性，更大几率发现所有危险场景所在区域；通过子集空间之间和子集空间内部的底层执行单元调度，可以在微观层级提高危险场景的生成概率，提升测试效率。

架构中涉及的名词定义如下：

（1）顶层管理单元 负责全集空间层面调度底层执行单元流动的计算单元，数量为1，同时负责子集空间关闭与合并；

（2）中层协调单元 负责下属子集空间层级的底层执行单元流动的计算单元，其数量与活跃子集空间数量相同，同时负责标记子集空间内的低效单元；

（3）底层执行单元 接收中层协调单元发送的试验参数进行仿真试验的计算单元；

（4）低效单元 测试效率较低，可能被顶层管理单元调配至其它子集空间的底层执行单元；

（5）全集空间 逻辑场景参数空间离散生成的所有具体场景参数集合空间；

（6）子集空间 将全集空间划分得到的部分具体场景参数集合空间；

（7）量化指标 根据试验目的所定义的评价指标。

顶层管理单元在一轮迭代过程中的详细工作内容如下：顶层管理单元首先根据每个子集空间里的中层协调单元发送的子集空间量化指标值确定该空间的流入流出情况，如图2 中的蓝色、橙色方框所示；随后顶层管理单元会依次计算每个流出子集空间内的每个低效单元是否流出，将确定流出的低效单元进行标记；之后顶层管理单元依次计算流出的低效单元流入的子集空间标号，如图2 中的箭头所示；对于没有探索价值的子集空间，顶层管理单元会将其关闭避免底层执行单元流入，如图2 中的叉号所示。在试验结束后，顶层管理单元还将临近的危险位置所在的子集空间进行合并，从而形成完整的危险空间分布，如图2 中左下方两个小区域边界的虚线所示。

图2 顶层管理单元工作示意

为保证空间内部的底层执行单元前往较为危险的参数位置，建立了中层协调单元以确保子集空间内的危险场景参数强化生成，整个工作框架如图3所示。为扩大前期探索自由度，本文中引入了汇聚区域的概念，汇聚区域指子集空间内量化指标值超过阈值的参数点位置（极值点）可以影响的周围其他参数的范围，如图3 中的阴影区域所示。中层协调单元的管理原则如下：汇聚区域内的底层执行单元会根据极值点的位置和自身最大量化指标值的位置进行移动，而汇聚区域外的底层执行单元仅会根据自身的最大量化指标值的位置进行移动，如图3 中的空心箭头和实心箭头所示。同时，中层协调单元会记录空间内的低效单元，如图2和图3中的黄色圆所示。

图3 中层协调单元工作示意

2 加速测试模块构建

2.1 顶层管理模块

子集空间之间的底层执行单元流动分为流入和流出两部分。在每轮迭代结束后，对于子集空间平均量化指标值低于总体平均量化指标值且不存在活跃危险场景的子集空间，顶层管理单元会调度该子集空间内的低效单元以一定的概率离开当前空间并迁至其他流入空间。流失子集空间内的低效单元离开当前空间的概率p为

式中：p为第个子集空间中低效单元离开该空间的概率；ˉ为第次迭代所有底层执行单元量化指标的平均值；g为第次迭代第个子集空间中的平均量化指标值；为当前迭代次数；为调节参数，代表顶层执行者的权威程度，该值越大，顶层管理单元的权威程度越大，次级管理者越容易听从顶层管理单元的调配，该值一般大于10；为预先设计的最大迭代次数；为顶层管理单元期望分配给每个子集空间的底层执行单元数量，该值一般大于初始分配的底层执行单元数量，代表顶层管理单元期望每个子集空间都有足够多的底层执行单元；n为第个子集空间在第轮迭代时的底层执行单元数量；n为第个子集空间在第轮迭代时剩余的活跃极值点数量。

当前空间量化指标值越差、底层执行单元数量越多、迭代次数越大，则该低效单元越易离开。

通过顶层管理模块的运行，底层执行单元会逐步向具有较高探索价值的子集空间富集，进一步强化高危险子集空间内危险场景的生成，提高测试效率。

需要注意的是，一个空间内可能存在多个低效单元，它们在一次迭代中的离开概率是顺序计算的，即每个确定离开的低效单元都会改变当前子集空间内的底层执行单元数量从而影响该空间的流失概率；当一个子集空间内的所有底层执行单元都流失后，顶层执行会将该空间定义为无价值区，将该空间关闭。

量化指标值较好或有新危险场景产生的空间为流入空间，流入空间的流入概率与该子集空间的底层执行单元数量、新产生的危险场景数量和量化指标值有关，其流入概率为

式中：为符合输入条件的子集空间个数；n*为符合条件的个子集空间在第回合的底层执行单元的总个数；g*为符合条件的个子集空间在第回合的量化指标的总和；l*为符合条件的个子集空间在第回合产生的最大极值点的总数；a、b、c为调节参数，用来调节3个子项的权重，它们之和为1，随着迭代的进行，新产生极值点数量的影响权重c越来越大；、、、分别为a、b的初始和终止系数。

同样需要注意的是，每个新低效单元的流入都会改变空间的底层执行单元数量，从而须重新计算流入不同空间的概率。

顶层管理还负责结束迭代。为保证没有危险场景生成时及时停止迭代以提高计算效率，该方法设定的迭代停止条件为不存在活跃极值点，且一定迭代次数内没有产生新的极值点。

2.2 中层协调模块

中层协调模块主要负责子集空间内部的危险场景强化生成，可参考现有优化算法，例如模拟退火法和梯度下降法等，考虑到子集空间内参数并行的需求，参考粒子群优化算法计算子集空间内底层执行单元的下一次试验参数。同时，为保证试验前期有较强的随机搜索能力，引入了汇聚区域的概念。满足式（6）的点即表示其位于汇聚区域内，所有符合条件的点即构成了汇聚区域空间。

汇聚区域代表区域内极值（危险场景）影响的区域，它随着迭代次数的增加不断扩大。

其中：

式中：s为参数点在第维度与最近活跃极值点的距离；为参数空间的不同维度；为参数空间的维度；r为在第维的汇聚区域轴长；r为第轮迭代的汇聚区域轴长；为初始的汇聚区域轴长；为参数空间不同维度的参数最大值；为参数空间不同维度的参数最小值；为所有底层执行单元的数量。

底层执行单元下一回合移动的速度为

下一次参数的位置为

式中x为第+1 轮迭代中底层执行单元的移动位置。

由于参数空间一般经过离散处理，计算得到的点可能不会正好落在离散得到的参数点的位置处，此时在未试验的参数点中找到距离计算得到最近的参数作为下一次试验参数。

对于极值位置处的底层执行单元，中层协调会在未试验过的参数点中寻找距离其当前位置最近的参数点作为其下一步试验参数。本文中规定当这一最近距离大于最初离散步长欧氏距离2 倍时，中层协调会将其剔除出活跃极值集合。

对于新流入的底层执行单元，中层协调会随机选择一个活跃极值，并将其最近的未试验过的位置作为下一次试验参数。

中层协调还负责标记空间内的低效单元。 空间中第个底层执行单元成为低效单元的概率f为

式中：、为调节参数，其和为1；为5 轮迭代次数内所有底层执行单元的平均量化指标值；ˉ′为第个底层执行单元在该子集空间内5 轮迭代次数内的平均量化指标值；为该空间内5 轮迭代次数内底层执行单元的平均量化指标值；l为极值标记，若该点在第回合为最大极值，则为0；w为子集空间内第个底层执行单元在第轮迭代时的拥挤系数，若其在上一回合的计算得到的点与未试验最近点的距离大于最初离散步长欧氏距离的2 倍（计算点周围的离散参数点全部被试验），则该点处为1，否则为0。

为防止低效单元在不同子集空间之间发生频繁流动，规定一个底层执行单元在当前空间迭代次数少于5时不会被标记为低效单元。

2.3 底层执行模块

底层执行层是在试验过程中负责执行具体仿真试验的多个计算单元构成的集合，计算单元可由不同测试软件构成。本文中选择Matlab、PreScan 和CarSim 联合仿真作为底层执行单元，Matlab 作为顶层管理单元和中层协调单元的算法承载平台，如图4 所示。Matlab 在承载算法的同时，其UDP 模块还负责顶层管理层、中层协调层与底层执行层之间的数据通信；PreScan 提供仿真场景环境和传感器模型，同时控制仿真测试的自动进行；CarSim负责提供高精度车辆动力学模型。

图4 计算单元软件详情

3 测试试验与结果分析

为评定所提出的并行加速测试方法在自动驾驶系统测试过程中的实用价值，使用并行加速、并行遍历、单线程加速、单线程遍历4 种方式对某黑盒自动驾驶算法在前车切入场景中的安全性进行测试，量化指标选择测试过程中的最大碰撞时间的倒数。

以HighD数据集中的前车切入逻辑场景为例，参照现有场景要素选择方法。本次试验选择切入后本车速度、切入后前车与本车距离和切入后前车速度v作为场景参数，它们的参数空间分别为［14 m/s，38 m/s］、［5 m，55 m］、［18.5 m/s，45.5 m/s］。速度间隔取3 m/s，距离间隔取1 m，共得到4590个具体场景参数。

为说明并行加速方法的有效性，且考虑测试过程中的设备成本，并行与单线程测试过程中的底层执行单元并未选择相同的配置。单线程测试过程中，选择的主机参数为：CPU i99900k、GPU RTX 2080ti、内存32GB；并行测试过程中，选择的主机参数为：CPU i56500、GPU GTX 1060、内存16GB。

4 种方法均发现了所有危险情况，危险结果如图5 所示（图中不同坐标轴代表逻辑场景参数类型，空心圆代表测试过的危险情况具体场景参数位置）。

图5 前车切入测试场景危险结果

参照SHRP2 中关于碰撞危害等级的定义：严重碰撞、一般碰撞、轻度碰撞和接近碰撞，文中将接近碰撞及以上危害等级的场景均视为危险情况，筛选的具体参数选择碰撞时间（time to collision，TTC），其阈值根据现有数据统计情况选择1.5 s。

4 种方法的测试过程如表1 所示。从表中可以看出，并行加速测试方法耗时并没有完全与单线程方法形成底层执行单元的倍数关系，首先是因为并行测试主机配置相比单线程测试较低，其次是多线程之间的通信延迟和不同测试情况下的等待。本文设定的测试时长为30 s，当发生碰撞时试验直接弹出，由于在并行的情况下本文的方法会等待所有底层执行单元都完成当轮迭代后再进行下一步参数计算，这在一定程度上降低了算法的测试效率。不过根据4 种方法测试结果看出，虽然并行测试使用的主机配置较弱，但本文提出的方法充分显示了多单元并行计算的优势，加速自动驾驶仿真测试流程。

表1 4种方法测试过程

4 结论

针对自动驾驶系统加速测试需求，将并行测试方法与危险场景强化生成框架相结合，提出一种自动驾驶系统并行加速测试方法，建立了3 层架构，顶层管理和中层协调分别负责全集空间和子集空间内的场景寻优，底层执行层负责具体仿真试验。将该方法与并行遍历、单线程加速、单线程遍历3 种方法进行对比。结果表明，本文提出的并行加速测试方法可有效、快速地搜索出危险具体场景参数，加速自动驾驶系统测试流程，提高测试效率。