ball tree优化的自动驾驶仿真测试场景生成方法

秦琴 谷文军

摘 要：基于场景的仿真测试方法可以有效加速自动驾驶汽车的测试进程，但是传统的采样方法面对高维度采样空间时无法维持高效性，提出了一种ball tree优化的仿真测试场景采样方法，并基于Carla模拟器构建了仿真测试场景自动化生成框架验证算法的有效性。分别使用随机采样方法、基于KD tree结构的最近邻采样方法与基于ball tree结构的最近邻采样方法进行场景参数采样，并生成不同天气要素下的仿真测试场景进行验证。最后将仿真过程与人工方法进行对比。结果表明，提出方法相对于人工方法具有11.38倍场景制作速度的提升，且相对于KD tree结构的采样方法的场景生成速度提升了27.97%。

关键词：自动驾驶； 场景生成； 最近邻算法； ball tree； CARLA

中图分类号：TP391.9   文献标志码：A

文章编号：1001-3695（2023）09-034-2781-04

doi：10.19734/j.issn.1001-3695.2022.12.0818

Ball tree optimized automatic driving simulation test scenario generation method

Qin Qin， Gu Wenjun

（School of Intelligent Manufacturing & Control Engineering， Shanghai Polytechnic University， Shanghai 201209， China）

Abstract：The scenario-based simulation test method can effectively accelerate the test process of autonomous vehicles， but the traditional sampling method cannot maintain high efficiency in the face of high-dimensional sampling space. This paper proposed a ball tree optimized simulation test scene sampling method. And based on the Carla simulator， it built a simulation test scenario automatic generation framework to verify the effectiveness of the algorithm. The proposed method used the random sampling method， the nearest neighbor sampling method based on the KD tree structure and the nearest neighbor sampling method based on the ball tree structure to sample scene parameters and generated extreme weather simulation test scenarios for verification. Finally， the results show that the proposed method increases by 11.38 times in scene production speed by comparing the simulation process with the manual method and show that the scene generation speed has increased by 27.97% by comparing that with the KD tree structure sampling method.

Key words：autonomous driving; scenario generation; nearest neighbor algorithm; ball tree; CARLA

0 引言

自動驾驶技术的进步推动了无人驾驶汽车的研发取得了巨大的进展，但是最近美国国家公路交通安全管理局（national highway traffic safety administration，NHTSA）公布的自动驾驶事故报告［1］表明，当前的汽车自动驾驶系统与实车测试均存在着巨大的不足与安全隐患。为了减少发生事故的风险，在将自动驾驶系统部署到实车之前对其进行充分的测试和验证具有极大的必要性。根据兰德公司的报告［2］显示，要证明汽车自动驾驶相比于人类驾驶员能够减少20%的交通事故死亡率，需要进行约80亿千米的公共道路测试。然而在现实世界中进行传统的道路测试需要付出极大的人力、物力与时间成本，而且很难进行危险的边缘驾驶场景测试，尤其是一些如极端天气等场景下的测试需求，很难在真实世界的环境中完成。因此，利用仿真模拟器加速进行自动驾驶系统测试的研究越来越受到研究者的关注。

传统的自动驾驶仿真测试仅限于一组人工制作的场景，测试的目标是满足ISO26262等安全标准［3］。然而手动创建测试用例场景模式固定且需要投入大量的人力和时间成本，此外自动驾驶汽车工作环境极高的复杂性决定了人工制作的仿真测试场景远远不能覆盖所有的驾驶场景，因此近几年研究者们围绕自动驾驶仿真测试环境的场景生成做了大量的工作。文献［4，5］在分析自动驾驶关键性影响因素的基础上，采用层次分析法确定场景要素的重要性，在此基础上使用组合测试方法构建仿真测试场景，接着根据提出的复杂指标的有效性来指导场景用例的自动化生成。Fellner等人［6］基于快速搜索随机树算法，通过寻找模型的变异值确定场景参数，可以在考虑2 300多种场景要素的情况下，快速生成场景测试用例。Klischat等人［7］使用基于优化搜索的方法将边缘场景的设计建模转换为优化问题，采用自车可行驶域临界度指标来定义目标函数，可以有效增加边缘场景用例的数量。Feng等人［8］通过对自然环境进行稀疏但对抗性地调整，将场景参数分为关键参数和非关键参数，对关键参数采用重要性采样，对非关键参数采用蒙特卡罗直接采样，从而高效率地生成自然但具有对抗性的仿真测试场景。文献［9］运用生成对抗网络（GAN），与变分自编码器（VAE）基于真实交通流数据集生成了可用于自动驾驶全面性能评估地场景库，并且对生成的场景进行聚类，用于探索自动驾驶汽车之间的互动机制。

文献［10］在传统随机搜索算法的基础上，结合了K近邻算法的特点，在对场景随机采样的同时加入了近邻搜索算法以提升危险场景的挖掘能力，旨在发掘影响驾驶工况的危险场景要素。文献［10］提升了采样算法对危险场景的挖掘能力，但是忽略了KD tree结构的近邻搜索算法面对高维搜索空间时的参数采样速度问题，本文针对此问题进行了改进。由于在自动驾驶领域，对场景还没有形成统一的定义，本文采用Ulbrich的定义［11］，根据文献［12］对该定义的扩展将场景的构建流程分为功能场景、逻辑场景和具体场景三部分，搭建了场景自动生成框架，同时提出基于ball tree优化的最近邻场景采样算法（ball tree optimized K-nearest neighbors）生成测试用例，并且通过分析不同天气要素场景下行车场景进行验证。本文的贡献如下：

a）本文基于开源仿真模拟器Carla，提出了一种低成本的场景自动化生成框架构建方法，允许用户手动配置参数，在算法模型开发阶段就可以对其进行模型在环自动化测试。

b）在场景要素采样方面，对比传统的人工方法、基于随机搜索的采样方法和基于K维树（KD tree）结构的采样方法，本文提出的基于球树（ball tree）结构的采样方法能够极大地提升仿真测试场景参数空间的采样效率。

1 仿真测试场景生成框架搭建

本文构建了仿真测试场景自动生成框架，框架能够在Carla模拟器中自动生成仿真测试场景。框架的组成架构如图1所示。

1.1 Carla模拟器

Carla是由英特尔和丰田基于虚幻4（Unreal Engine 4）游戏引擎开发的一款开源自动驾驶仿真模拟器。采用了模块化的设计，并且提供了丰富的API接口，以解决自动驾驶系统测试与验证的一系列关键问题，例如感知和规划算法。Carla本身采用了client-server的多服務器架构模式，通过TCP协议进行通信，具备很强的可扩展性［13］。Carla提供了灵活的API接口，允许开发者编写代码控制仿真的每个部分，例如交通流的生成、交通参与者的行为、天气的变化、传感器的通信等。用户可以配置多种传感器套件，包括激光雷达、多摄像头、深度传感器和GPS等。Carla还提供了非图形渲染的仿真模式，满足快速的交通模拟和仿真执行。Carla支持OpenDrive标准和OpenScenario标准的地图格式，用户可以通过RoadRunner快速构建地图，使用Scenario Runner快速定义需要的交通场景。此外，由于Carla开源的特性，能够很方便地进行二次开发。Carla仿真场景如图2所示。

1.2 场景描述文件

为了对场景进行结构化描述，本文基于YAML语言结构设计了用于场景建模的描述文件。依据文献［12］对场景定义的扩展，场景描述文件主要包括功能场景、逻辑场景与具体场景三个层次。功能场景是一系列动作与状态描述，例如浓雾天气下，自车加速行驶通过一段直道。逻辑场景是一系列参数分布范围，例如雾能见度采样范围为20～50 m，光照入射角度采样范围为30°～60°，具体场景就是一系列确定的参数值，例如雾能见度为30 m，光照入射角为30°。

1.3 场景要素解释器

场景要素解释器的作用是提取场景描述文件中的具体场景关键字及其参数值，并将其解释为场景静态文件中的具体参数，合成场景静态文件。在仿真开始后，场景要素解释器还接收采样器的采样结果输入，并将最新的采样结果解释为静态文件中的参数，合成新的场景静态文件，驱动新场景仿真的进行。

1.4 场景静态文件

OpenDrive与OpenScenario是自动化及测量系统标准协会（Association for Standardization of Automation and Measuring Systems，ASAM）发布的OpenX系列标准的重要组成部分，在自动驾驶仿真模拟系统集成、测试、评价领域中发挥着至关重要的基石作用，是众多整车厂、供应商及仿真工具商使用的数据格式统一标准。Carla的场景支持OpenDrive与OpenScenario标准，用户可以使用场景驱动器根据场景静态文件内容向Carla模拟器中注入场景信息。

1.5 采样器

仿真测试场景生成框架中集成了采样器，用于从逻辑场景中的参数分布空间内搜索用于场景生成的参数值。由于大多数的自动驾驶场景都是高维度的，关键场景搜索的复杂度会随着维度的增加呈指数级增长［14］。为了能够快速地搜索高维空间内的目标参数，本文在文献［10］的基础上提出了一种基于球树结构的最近邻采样算法，能够快速搜索自车出现违规行为时场景参数的近邻空间，挖掘关键场景要素。

1.6 场景驱动器

场景驱动器是基于Carla ScenarioRunner模块开发的向Carla模拟器中注入场景信息的模块，它可以解析OpenDrive和OpenScenario格式的场景静态文件供自车模型使用。场景驱动器还支持与Carla的验证评估平台Carla LeaderBoard集成，将场景信息提交给Carla LeaderBoard 进行验证并评估自车的行驶状态。

1.7 测试评价模块

测试评价模块基于Carla LeaderBoard构建，该模块以驾驶得分作为考察指标，主要包含路线完成度与违规惩罚两部分，其中违规惩罚来自于Carla自动驾驶挑战赛 ，如表1所示。

当自车在行驶过程中出现违规行为时，将会累计惩罚得分，导致自车不能以100%的成功率完成驾驶任务。驾驶得分计算公式为［15］

score（v）=1RN∑RNi=1max（100C（v，ri）-I（v，ri），0）（1）

其中：v为当前评估的自车模型；C（v，ri）为第i条路线r的完成度；I（v，ri）为违规惩罚得分；R表示一条路线的重复次数;N表示路线的数量。以上介绍了仿真测试场景生成框架各个组件的功能及实现原理，主要的场景仿真测试流程如图3所示。

2 ball tree优化的场景要素采样算法

文献［10］提出的随机最近邻采样算法（RNS）扩展了传统了随机搜索算法，将随机搜索与基于KD tree结构近邻搜索结合，保留了驾驶工况下危险场景发生的随机性，也增强了场景搜索过程中针对危险场景要素的挖掘能力，但是当面对高维度的场景要素参数时，近邻搜索由于需要用大量样本点计算和比较空间距离，需要进行大规模的计算，会极大地拖慢算法的执行速度，影响参数采样的速度［16］。

针对近邻搜索算法计算量大，查询效率低的问题，采用空间分区数据结构实现K近邻的快速搜索是其一种改进方向，改进的原理是构造搜索二叉树，对样本按照特定的几何形态进行划分，在K近邻查找时，通过比较欧氏距离对二叉树进行剪枝处理，减少需要计算的节点数量，从而加快查询速度。常见的空间分区结构有K维树与球树等。

本文采用球樹结构对提出的基于K维树（KD tree）结构的随机最近邻算法进行了改进，提升了其高维度空间的搜索能力。算法伪代码具体形式如下：

算法1 ball tree K近邻场景要素采样算法

输入：参数分布空间D;迭代次数t;场景逻辑分布Sd;阈值δ;近邻k。

输出：场景要素值列表Sl。

for x=1，2，…，t do

if score＜δ或（score＞δ且N≥k） then

从D中随机采样，将结果赋给Sl

else

根据Sd生成搜索区域A

从A中应用ball-tree K近邻搜索算法搜索≥k个近邻场景，将结果赋给Sl

返回Sl

end for

对于KD tree结构的K近邻算法，在样本空间中，所有的点都在一个超方体内，KD tree结构构建步骤如下：

算法2 KD tree结构构建算法

输入：样本参数分布空间D。

输出：二叉搜索树根节点p1。

a）如果当前超方体中只有一个样本点p，则返回这个点。

b）选择一个维度d，将样本空间分为两个超方体c1与c2。

c）在d维度选择一个切割点p1作为根节点，将小于这个点的样本归于超方体c1，作为左子树。其余的样本归于另一个超方体c2，作为右子树。

d）递归执行步骤a）～c），构建左右子树。

e）返回树的根节点p1。

对于ball tree结构的KNN算法，在样本空间中，所有的点都在一个超球体内，ball tree结构构建步骤如下：

算法3 ball tree结构构建算法

输入：样本参数分布空间D。

输出：二叉搜索树根节点p1。

a）如果当前超球体中只有一个样本点p，则返回这个点；

b）选择一个维度d，质心为二叉树的根节点p；

c）计算d维度下子超球体内距离质心最远的点p1；

d）计算维度下距离p1最远的样本点p2；

e）将全部样本点划分为两个超球体S1与S2，距离p1更近的划分到S1，为左子树，距离p2更近的划分到S2，为右子树；

f）递归执行步骤a）～e），构建左右子树；

g）返回根节点p。

分区结构构建示意图如图4所示，其中圆形为参数空间的点，三角形为当前参数值。

图4所示KD tree中将参数空间分割为多个超方体，由于在求解距离时使用的是欧氏距离，实际上是寻找一个超球体（欧拉球［17］），使其能够包含至少k个样本点，超球体与超方体有很大的可能性会相交， 每一个相交的参数空间都需要进行搜索，因此随着空间维度的增加，计算复杂度也会呈指数级上升。但是在ball tree结构中，这种相交的可能性极低，因此对于复杂的自动驾驶仿真测试场景采样，ball tree结构的KNN算法能够提升采样速度。

3 面向天气要素的测试场景生成

天气要素对自动驾驶汽车传感器的影响极大。光照强度和雾会影响相机的成像距离，雨滴形成的雨线会对激光雷达的激光束产生反射，降低激光雷达的探测距离，雨雪会对毫米波雷达的信号强度产生重要的影响［18］。因此，对自动驾驶系统进行不同天气要素下的测试极具必要性。本文设计了面向天气要素的测试场景生成实验用于验证上文所述的仿真测试场景自动化生成框架和ball tree优化的场景要素采样算法的有效性。实验选用Carla模拟器提供的地图town5作为车辆行驶地图，town5的道路如图5所示。实验设置了天气逻辑场景，主要天气要素为云量、降水量、光照角度、空气湿度、雾能见度、雾浓度，并且加入了行人密度与车辆密度两个变量，共同构成场景要素参数空间。参数分布如表2所示。

实验中自车控制模型采用LBC控制器模型，LBC模型在当年的自动驾驶挑战赛中实现了所有驾驶任务的100%成功率［19］，即没有出现违规行为（违规行为注解见https：//leaderboard.carla.org/#infractions）。LBC模型通过特权智能体获取驾驶环境信息，包括车道线、车辆位置、红绿灯状态、车辆和行人，通过这些信息模仿人类驾驶员获得驾驶策略。LBC模型下层使用一个简单的PID控制器进行导航点的追踪。

LBC纵向控制策略是达到期望速度v*t：

v*t=1/K∑Kk=1‖i-i-1‖2δt（2）

其中：K为所有导航点的数量；δt为导航点之间的间隔；i为自车的位置，由式（3）给出。

wi={R-1i（xi+1-xi），…，R-1x（xi+K-xi）}（3）

其中：R-1i为逆矩阵，用于计算自车在仿真世界中坐标的相对偏移量。LBC的横向控制策略是达到期望转向角S*。

S*=tan-1（pypx）（4）

其中：點p为LBC模型在导航点上的投影点。

基于上述实验设置本文使用前文所述仿真测试场景自动化生成框架，生成了仿真测试场景如图6所示。

4 实验评价

本文针对不同的天气要素使用了随机采样、基于KD tree结构的最近邻采样和基于ball tree结构的最近邻采样三种方法，生成了100个仿真测试场景，经过和人工采样对比发现，自动化场景生成方法能够显著加快测试效率，对比结果如表3所示，人工方法制作100个不同的仿真测试场景，需要耗费967 min，不管是基于随机采样的场景自动生成方法还是基于KD tree或ball tree结构的场景自动化生成方法，消耗的时间均远小于人工制作场景的方法。三种方法的测试结果如图7所示，×表示LBC模型在此场景下出现违规行为，●表示LBC模型在此场景下未出现违规行为。随机采样方法能够生成较多的违规场景，但是场景参数分布较为分散，基于最近邻的采样方法，生成导致自车出现违规行为的场景较少，且场景参数分布较为集中，有助于测试人员进一步挖掘造成驾驶违规的原因。如图7所示，低光照，高云量，强降水量的条件下更容易发生违规行为。

以人工方法制作场景的速度作为单位1对比自动生成方法的场景生成的加速效果，随机采样方法由于计算复杂度的限制，加速效果是人工方法的3.68倍；KD tree结构的最近邻方法将采样空间的大小约束在目标点的周围，减小了计算的复杂度，采样速度是人工方法的8.19倍；ball tree结构的最近邻方法，由于超球体结构的设计，进一步减小了搜索空间的大小，采样速度是人工方法的11.38倍，比KD tree结构快27.97%。

5 结束语

本文构建了自动驾驶仿真测试场景生成框架，面向Carla模拟器自动化地生成仿真测试场景，使得用户可以基于开源方案低成本地构建自动化仿真测试环境，进行快速验证。在仿真测试框架的采样器中，本文提出了基于ball tree结构优化的自动驾驶仿真测试场景生成方法，该方法比传统的随机采样方法和基于KD tree结构的最近邻方法采样效率更高，且对后者的生成效率有27.97%的改进。

自动驾驶汽车的行驶场景具有及其复杂、无限丰富、不可预知的特点，人为地构建自动驾驶场景不能满足自动驾驶汽车测实验证的需求，基于场景的自动化测试方案能够为自动驾驶技术的快速发展和落地提供有力的支撑。

参考文献：

［1］National Highway Traffic Safety Administration. Standing general order on crash reporting［EB/OL］. （2021-01）. https：//www.nhtsa.gov/laws-regulations/standing-general-order-crash-reporting.

［2］Kalra N， Paddock S M. Driving to safety： how many miles of driving would it take to demonstrate autonomous vehicle reliability？［J］. Transportation Research Part A： Policy and Practice， 2016，94：182-193.

［3］Kafka P. The automotive standard ISO 26262， the innovative driver for enhanced safety assessment & technology for motor cars［J］. Procedia Engineering， 2012，45： 2-10.

［4］Xia Qin， Duan Jianli， Gao Feng， et al. Test scenario design for intelligent driving system ensuring coverage and effectiveness［J］. International Journal of Automotive Technology， 2018，19： 751-758.

［5］Xia Qin， Duan Jianli， Gao Feng， et al. Automatic generation method of test scenario for ADAS based on complexity［EB/OL］. （2017-09-23）. https：//doi.org/10.4271/2017-01-1992.

［6］Fellner A， Krenn W， Schlick R， et al. Model-based， mutation-dri-ven test-case generation via heuristic-guided branching search［J］. ACM Trans on Embedded Computing Systems， 2019，18（1）： article No.4.

［7］Klischat M， Liu E I， Holtke F， et al. Scenario factory： creating safety-critical traffic scenarios for automated vehicles［C］//Proc of the 23rd International Conference on Intelligent Transportation Systems. Piscataway， NJ： IEEE Press， 2020： 1-7.

［8］Feng Shuo， Yan Xintao， Sun Haowei， et al. Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment［J］. Nature Communications， 2021，12： article No. 748.

［9］Knies C，Diermeyer F.Data-driven test scenario generation for coo-perative maneuver planning on highways［J］.Applied Sciences，2020，10（22）：8154.

［10］Ramakrishna S，Luo Baiting，Barve Y，et al.Risk-aware scene sampling for dynamic assurance of autonomous systems［EB/OL］. （2022-02-28）.https：//arxiv.org/abs/2202.13510.

［11］Ulbrich S，Menzel T，Reschka A，et al. Defining and substantiating the terms scene，situation，and scenario for automated driving［C］//Proc of the 18th International Conference on Intelligent Transportation Systems. Piscataway，NJ： IEEE Press，2015： 982-988.

［12］Menzel T，Bagschik G，Maurer M. Scenarios for development，test and validation of automated vehicles［C］//Proc of IEEE Intelligent Vehicles Symposium. Piscataway，NJ： IEEE Press，2018： 1821-1827.

［13］Pirri P，Pahl C，Ioini N E，et al. Towards cooperative maneuvering simulation： tools and architecture［C］//Proc of the 18th Annual Consumer Communications & Networking Conference. Piscataway，NJ： IEEE Press，2021： 1-6.

［14］Feng Shuo，Feng Yiheng，Sun Haowei，et al. Testing scenario library generation for connected and automated vehicles，part Ⅱ： case studies［J］. IEEE Trans on Intelligent Transportation Systems，2021，22（9）： 5635-5647.

［15］ Ros G，Koltun V，Codevilla F，et al. CARLA autonomous driving challenge［EB/OL］. （2019-05-17）. https：//carlachallenge.org/challenge/.

［16］徐國天.一种高维向量空间K近邻快速搜索方法［J］.小型微型计算机系统，2020，41（11）： 2274-2281.（Xu Guotian. Fast search method for K nearest neighbor in high dimensional vector space［J］.Journal of Chinese Computer Systems，2020，41（11）：2274-2281.）

［17］Aiger D，Kaplan H，Sharir M. Reporting neighbors in high-dimensional Euclidean space［J］.SIAM Journal on Computing，2014，43（4）：1363-1395.

［18］白雪松，邓伟文，任秉韬，等.一种自动驾驶仿真场景要素的提取方法［J］.汽车工程，2021，43（7）：1030-1036，1065.（Bai Xuesong，Deng Weiwen，Ren Bingtao，et al.An extraction method of scenario elements for autonomous driving simulation［J］. Automotive Engineering，2021，43（7）：1030-1036，1065.）

［19］Chen Dian，Zhou B，Koltun V，et al.Learning by cheating［EB/OL］.（2019-12-27）.https：//arxiv.org/abs/1912.12294.

收稿日期：2022-12-04；修回日期：2023-02-03

作者简介：秦琴（1978-），女，上海人，副教授，硕导，博士，主要研究方向为汽车电子、图像处理、数字孪生；谷文军（1995-），男（通信作者），江苏淮安人，硕士研究生，主要研究方向为自动驾驶、汽车电子、软件测试（zeroxus@foxmail.com）．