基于多目标协同演化算法的大规模自动驾驶策略

刘章杰 李慧云

1(中国科学院深圳先进技术研究院 深圳 518055)

2(中国科学院人机智能协同系统重点实验室 深圳 518055)

3(粤港澳人机智能协同系统联合实验室 深圳 518055)

1 引 言

随着经济的发展和车流密度的增加，城市交通拥堵日益严重，造成出行成本增加、通勤时间变长、事故率上升、经济损失增大和环境污染加剧等问题[1-2]。如何实现大规模车辆协调驾驶，在平均速度、事故率等全局优化问题上取得突破已成为当前研究的重点和难点。

基于优化的中心化调度方法在较小的场景中能充分利用计算资源，因此在给定目标函数和约束条件的情况下，可采用中心化模型求解器进行优化求解。然而，中心化的优化算法(包括强化学习、神经网络和模糊逻辑等[3])的计算复杂度随着交叉口数量、车辆规模、道路网络复杂程度以及车辆之间可能的冲突关系等的增加呈指数增长[4]。即使未来的计算能力足够大，由于信息传输的延迟、丢失和计算时间，中心化服务器也很难实时响应交通请求。这是因为交通网络具有高度动态、瞬时变化的特点，所以几乎不可能以中心化的优化方法及时处理真实的交通事件和调度规划交通网络中的车辆。

而传统的演化算法(如遗传算法[5]等)和一些智能优化算法(如蚁群算法、粒子群算法[6-7]等)，带有分布式的特点，能很好地处理规模庞大(地图复杂、车辆数量多)的问题。例如，研究人员引入分布式节点，针对整体交通流，提出蚁群算法和粒子群算法，综合考虑局部和全局最优的影响，不断调整搜索方向和搜索速度，并根据个体适应度进行迭代演化，在整体上能够较好地处理大规模优化问题[8-9]。针对交通流调度优化问题，研究人员引入粒子群优化算法，对交通流和车辆进行分布式调度调整，从而缓解交通拥堵的情况[10]。

但在车路协同网络中，传统的演化算法和智能优化算法存在以下问题：(1)仅创建单一种群，因为在车路协同网络中，车辆种类十分多元化，包括乘用车、商用车等，单一的种群环境不能满足演化的需要，同时在利用局部和全局信息上存在不充分的地方；(2)在对个体进行评价时，仅考虑个体在当前环境下的适应度，未能充分考虑在车路协同网络中个体车辆对其邻域环境的影响，以及个体之间的竞争与合作、个体与环境之间、种群之间协作竞争的影响；(3)传统的演化算法和智能优化算法在演化进程中，容易收敛到局部最优并且收敛速度较慢。

本文提出基于协同演化算法的大规模无人驾驶系统决策优化方法，建立面向网联汽车的多目标优化决策的博弈演化平台。通过构造网格道路模型，建立简化的车辆运动学模型，使得其中的各车辆之间以近邻博弈的方式进行交互。同时引入多种群环境和真实的道路交通环境，构建真实道路模型和车辆动力学模型。在演化进程中，充分考虑不同种群个体之间、个体与环境之间的影响。最终，基于设计的奖励函数，模拟生物种群相互竞争合作的演化进程，从而在整体上观察网络中种群自发涌现的分布特点，寻找不同环境下的最优驾驶策略。

2 相关研究进展

2.1 驾驶策略空间

随着车联网技术的发展，良好的驾驶策略可以有效减少交通负荷并提高整体平均速度以及交通网络吞吐量，而设计不当的驾驶策略则可能会导致交通拥堵甚至造成交通事故[11-12]。驾驶策略可以分为 3 类[13-15]：保守型、理性型和激进型。其中，保守型驾驶策略总是以相对较低的速度行驶；理性型策略根据交通环境来调整速度和行为，若前车速度较小且有足够的变道空间时，则选择变道加速超车；激进型策略总是以高速行驶，且在前车速度较小时总是会选择超车。

本文基于 3 类驾驶行为策略的特点，给出形式化的说明，并引入 q 态模型和状态转换机，形式化地描述 3 类策略在驾驶过程中的特点，扩展驾驶策略空间，在竞争与合作的更广泛的水平上探索各类策略交互的过程和结果。

2.2 协同演化算法

将达尔文的进化理论应用在自动化问题研究方面已有较长时间。Fogel 等[16]提出了进化规划，以寻求针对众多工程问题的最佳解决方案。但是，进化算法通常用于单个物种，当一个物种进化时，物种之间的选择压力随之改变，其他物种也会做出反应并最终适应它——这导致物种之间的高度适应性现象[17-18]。研究人员通过引入协同演化算法来探索两个或多个物种之间的相互作用[19]，观察多个对象通过竞争或相互协作，从而促进整体的发展[20]。从数学的角度来看，协同演化具有博弈论的动态特征，最终通过连续演化的过程达到稳定的平衡状态[21]。

在过去 20 年中，演化算法(Evolutionary Algorithms)已被证明是解决多目标优化问题的有效方法。由于种群的本质，多目标协同演化算法能够在单个算法执行中生成一组权衡的解决方案(称为非主导解决方案)，而不必像通常使用数学编程技术那样执行一系列独立的方案。此外，多目标协同演化算法可以成功地应用于具有诸如多边、不连续和不连续可行区域等困难特征的问题。另一方面，协同演化算法是传统演化算法的扩展，已应用于多目标优化问题的解决方案，从而推动了新算法和分析公式的开发，这些算法和分析公式同时也推动了协同演化算法研究的最新发展，并在多目标协同演化算法中开辟了新的研究路径。 协同演化算法在相应的环境下构建多个子种群的方法有：随机分解、模型构建和扰动构建。其中，随机分解为随机选择基因的顺序，通过事先评估或预实验决定分组的数量和大小；模型构建为基于已有的演化模型构建种群和个体数量，在演化过程中动态实施种群更新演化；扰动构建为通过随机扰动或噪声的方式，对决策变量进行扰动式分解。

与传统演化算法相比，协同演化算法充分考虑种群之间以及种群与环境之间的相互影响，并且充分考虑种群、个体之间的竞争与合作水平；在评估个体时考虑该个体与其他种群个体之间的交互关系，在解决大规模全局优化问题时具有多层次、多操作、多选择的特点，在高维度、多目标、大规模等问题中具有收敛速度快、优化质量高、可扩展性良好的优势。

3 问题描述与系统设计

3.1 问题描述

3.2 车辆模型

其中，vt为车辆t时刻的速度； 为车辆t时刻的加速度；xt为车辆t时刻的几何中心横坐标；yt为车辆t时刻几何中心的纵坐标；αt为车辆t时刻的车姿角度；θt为车辆t时刻的方向盘转角；xc为信号灯几何中心的横坐标；yc为信号灯几何中心的纵坐标；dt为车辆t时刻与信号灯的距离。

3.3 道路模型

将栅格长度gl设为等于车辆长度，从而使得每一个栅格中的车辆中心位不超过一辆。如图 1 所示，车辆A的中心位于网格gr3,2中，车辆B的中心位于另一个网格gr3,3中。随后，本文采用公式(4)定义状态 的二进制状态。当车辆中心点落入网格中时，网格将被占用，其状态为 1；当网格内部没有车辆时，状态为 0。

利用本文所构建的道路模型和车辆模型，单个车辆将仅与其相邻车辆间接交互。因此，在每一个时间步长，将交互复杂度从n！(n为一个车邻域内车辆数量)降到n。这样大大降低了模型的复杂性，并增强了可扩展性。

图1 车辆与道路模型Fig. 1 Vehicle and road model

3.4 策略的形式化表达

本文对多种候选驾驶策略进行探索。

(1)保守型策略(即完全合作)：初始以最大速度行驶，当前车的速度较慢时减速，不超车，避免强烈地使用油门和刹车。

(2)激进型策略(即完全竞争)：总是以最高速度行驶，遇到前车的速度较慢时始终超车。

(3)理性型策略(介于完全合作与完全竞争之间)：温和地使用油门和刹车，遇到前车的速度较慢时，可选择超车或减速。

对于理性型策略，本文采用 q 态 Potts 模型描述其竞争和合作的不同程度。

3.5 算法流程

本文探索候选策略步骤如下：

(1)初始化道路和车辆种群，其中随机设置车辆目的地。

图2 状态转换图Fig. 2 State transition diagram

(2)根据车辆运动学模型运行车辆以及模拟交通信号灯，直到所有车辆到达目的地。在每个时间步长更新道路环境(即网格状态)。

(4)获得总体种群车辆得分的平均值μ和标准差δ。根据图 3 所示的后代繁衍规则，确定每个单独车辆的后代数量。繁衍完成后，归一化种群数量和大小，确保交通流密度不变，继续下一代模拟运行。其中，后代繁衍规则进行 3 个层次的划分。

图3 后代繁衍数量根据得分数据而有所不同Fig. 3 The number of offspring varies according to the scores

图4 系统流程图Fig. 4 System flow chart

4 实验结果与数据分析系

4.1 实验环境

4.1.1 道路环境

在不失一般性的前提下，本文选择广东省深圳市的一个城市交通场景(图 5 黑色虚线)进行实验。其中，道路总长超过 4.5 km，每条车道宽 3.75 m，符合中国道路的建设标准。实验中，从 OSM(开放式街道地图)中导入矢量地图，其中每个车道由中心线上的一组点表示，然后通过等间隔插值对车道中的点进行采样，以获得每个网格的中心点以及该点的曲率，以建立 3.3 小节中介绍的道路网格模型。

图5 城市道路环境Fig. 5 Urban road environment

4.1.2 车辆

车辆总数设置为 340，最初在该区域内随机分布，并根据不同的策略分为多个种群。交通密度大约为 0.006 辆/m2。需要说明的是，该水平的车辆密度在城市高速公路中非常常见。例如，Jing 等[22]研究给出的实际交通数据显示，北京主干路网的平均交通流量每天超过 16 h 高于 0.005 辆/m2。

实验中，所有车辆的目的地均为随机设置。在车辆的生命周期中，每辆车都会根据自己的策略与其他车辆及道路交互，从而影响其他车辆并促进整体发展。

4.1.3 交通灯调度

在城市交通中，常见使用的交通信号灯为固定时间片轮转算法，其中每个时间片长度为 8 s。

4.1.4 候选驾驶策略

本文共对 3 种候选驾驶策略进行研究：(1)保守型策略——不超车，以最大速度行驶，当前车的速度较慢时减速，保持不超车；(2)理性型策略——以最大速度行驶，当前方车辆的速度较慢且有足够变道超车的空间时变道超车；(3)激进型策略——以最高速度行驶，且始终超车。

本文研究的具体实验参数如表 1 所示。

表1 实验参数列表Table 1 The list of experiment parameters

4.2 实验结果

本文在模拟仿真环境中 4.5 km 的道路上进行了 340 辆汽车的实验。其中，本文实验采用 Python 开发。

图 6 为 3 种候选策略种群演化结果。由于交通流密度较大，激进型策略出现了大量事故(图 6(b))，受激进型策略的影响，保守型策略和理性型策略同样产生事故(急速刹车)。从图 6(c)可看出，激进型和理性型策略取得较高的平均速度，而保守型策略的较低。经过 50 代演化后，理性型策略胜出，保守型策略和激进型策略均被淘汰(图 6(a))。

另外，本文引入变道因子 p 来描述更多的中间候选策略。中间策略描述为：当遇到前车较低速度且有足够超车空间时，变道超车；当没有足够空间时，则以概率p超车。例如，“0.3 型中间策略”表示在没有足够变道空间时以 0.3 的概率变道。

图6 三种候选策略种群演化结果Fig. 6 Result of evolution for multi-population with 3 candidate policies

如图 7(a)所示，当出现多代事故为 0 后，种群分布处于收敛状态(事故为 0，各种群速度接近)，各策略层次分明，与变道因子 p 呈现反相关(激进型策略实际上是 p＝1)。图 7(c)显示，保守策略的平均速度明显较低，所以被快速淘汰；图 7(b)显示，整体事故随着演化进程逐步降低，最后趋于 0。

4.3 讨论与分析

从上述实验结果可知，在确保安全和有足够空间的情况下，应该保持高速行驶(低速时应该加速)；交通流密度较高时，不应该频繁变道及剧烈加速，否则容易引起事故，造成交通拥堵；而在交通流密度较低时，驾驶策略应偏向于激进策略，在道路资源利用率上更加充分，同时速度上具有明显的优势。

图7 多种候选策略(包括 3 种中间策略)种群演化结果Fig. 7 Result of evolution for multi-population with 6 candidate policies

在引入基于 q 态模型的中间策略、扩展了驾驶策略空间后，种群分布表现出了明显的层次性。在交通流密度较高时，策略表现与变道因子大致呈反相关关系。其中在 9～12 代，“0.3 型中间策略”表现最优，事故率为 0，平均速度较“0 型中间策略”略微占优，总体得分最高。这表明在驾驶过程中，对于安全距离和足够变道空间的评估不能过于谨慎，否则可能会浪费道路资源，降低车辆平均速度。

表 2 将本文方法与现有的一些文献方法进行对比。移动模型(Mobility Model)[23]采用群体智能方法降低计算复杂度，由于采取演化规则不当，导致拥堵出现，平均速度较低；本文采用协同演化的方法，并且设置良好的演化规则，避免了拥堵的出现。Zhou 等[24]提出的基于两层混合模型的预测控制调度采用双层模型、区域分割、信号灯调度的方法，增加了路口的吞吐量及减少了路口的等待时间，由于采用的最大速度约束不同，平均速度结果也不同。本文引入栅格道路模型，采用分布式算法，降低了仿真时间；但是由于本文实验信号灯采用时间片轮转算法，路口吞吐量没有较好的兼顾，后续工作可以进一步改进交通的调度方式。与上述两种方法相比，由于本文为了探索驾驶策略对事故率的影响，在仿真环境下事故率仍然没有为 0，未来工作可以考虑进一步优化事故率。国家统计局数据[25]显示，2019 年平均每月事故率为 0.804 ，本文多目标优化后事故率小于 0.5 ，提升了 37%。由此可见，本文方法在平均速度、事故率与现有方法相比均有一定程度的下降。

表2 不同仿真结果对比Table 2 The comparison of simulation result

实验配备为 2 GHz 处理器和 8 GB 内存的 MacBook Pro，实验仿真时间为 3 min。由于本文采用分布式的协同演化算法，且栅格化道路之后，车辆之间采用间接交互的方式，个体车辆在每个时间步长内仅与其领域内的车辆进行间接交互，故总体计算复杂度与车辆数量成线性关系，并且可以并行处理，因此可以扩展本方法用于探索包含数百万辆自动驾驶汽车的城市级的驾驶策略。

5 总结与展望

由于城市自动驾驶汽车具有大规模和高动态特性的特点，因此不再适合采用中心化优化调度算法。本文将大规模的城市自动驾驶策略优化问题表述为众多子群体之间的多目标优化的协同演化问题，并希望观察具有代表性的候选策略中最优驾驶政策的自发涌现。

在模拟环境中进行了 4.5 km 道路上不同交通流密度下(车辆数量分别为 170 辆、340 辆)的实验。结果显示，理性型策略可以达到最佳效果；激进型策略产生的事故最高，平均速度也略高；保守型驾驶策略表现最差，25 代后就被淘汰了。采取最佳策略后，事故总数和平均速度均取得了巨大的提升。其中，事故数量趋于 0，事故率降低为 0.05% 以下(降低 90%)；平均速度方面由于保守策略的占比下降得以显著提升，由 13.8 m/s 提升到了 16.3 m/s(提升 30%)。

在此基础上，本文引入基于 q 态模型的中间策略，并在相同环境下进行了模拟演化实验，其中选取交通流密度为 0.006 辆/m2。在演化过程中，出现了明显的分层趋势，表现出在该交通流密度下，变道因子越高，策略表现越差的特点，经过 15 代的演化进程，多代事故数量趋于 0，各种群平均速度相差不大，种群比例保持相对稳定，达到收敛状态；在淘汰了保守策略后，平均速度达到了 16.4 m/s。在本文所提出的方法中，由于各车辆之间以近邻博弈的方式进行交互，使得计算复杂度与模拟的车辆规模大小呈线性关系，故可扩展至包含百万辆自动驾驶汽车的城市级驾驶策略探索。