高速多车多驾驶行为的冲突协同决策方法

张新锋 吴琳 李致远 柳欢

摘 要： 为解决高速公路场景下多车多驾驶行为车辆空间位置冲突的问题，提出了一种基于二分图最优匹配的驾驶行为冲突协同决策方法。根据静态交通信息，创建车辆可行候选驾驶行为集，依据车道平均车速、车辆密度、行进空间、即碰时间（TTC）、行驶负担等5 种评价指标构建效用函数，对候选驾驶行为定量评价；以车辆实施驾驶行为结束时刻的潜在空间位置为目标集合，驾驶行为评价效用为权值，构建基于车辆集合与目标集合的二分图；以全局总效用值最大为决策目标，采用Kuhn-Munkres（KM）算法求解最优匹配；搭建仿真场景，来验证该方法的有效性。结果表明：该协同决策方法可有效解决多车多驾驶行为冲突，保证车辆行车安全，提高道路上初末时刻车辆2% 的效用值和8% 的平均车速，增加了通行效率，且驾驶行为决策的准确性相比于遗传算法（GA）、粒子群算法（PSO）分别提高了11% 和9%，同时KM算法的实时性远高于GA 算法和PSO 算法。

关键词： 自动驾驶；协同决策；二分图；Kuhn-Munkres（KM）算法；效用函数

中图分类号： U 461 文献标识码： A DOI： 10.3969/j.issn.1674-8484.2023.05.010

行为决策系统是自动驾驶车辆的关键技术，作为自动驾驶技术的核心，其智能化程度影响车辆行驶的安全性和可靠性，以及在复杂多变的实时交通环境下的适应性[1]。

基于效用函数的自动驾驶行为决策方法具有灵活性、适应性、多目标优化和透明性等多个优点，使自动驾驶系统更具有实际应用和可行性。该方法通过人为构造多个备选方案并设置評价指标，选择最优效用对应的驾驶行为作为最佳驾驶行为[2]。如WANGPengwei 等[3] 建立了综合考虑驾驶效率和安全性的驾驶行为效益评价模型；杨达等[4] 建立了车联网环境下的自动驾驶车辆车道选择决策模型；M. Schmidt 等[5]根据车道满意度为车辆生成车道变化建议；A. Furda等[2] 建立了一个多准则决策系统，综合考虑多个评价指标决策最优驾驶行为。

现有的自动驾驶行为决策方法主要针对单车，决策过程中采取自车利益优先策略。当驾驶环境中出现2 个或更多车辆时，车辆潜在空间位置将会发生冲突，不利于道路交通的全局高效安全运行。因此需研究车辆间的协同决策，协同决策中车辆群体关注共同利益或共同目标，有利于保证道路交通安全，提高通行效率[6]。如E. Lovellette 等[7] 以博弈论的方法建立了多车道公路自动驾驶车辆的车道和速度分配算法；LIUYingxiang 等[8] 建立了基于多智能体强化学习算法的自动驾驶车辆决策模型；T. Kessler 等[9] 通过优化求解协调多车驾驶行为。但上述研究主要存在以下问题：1）协同决策模块部署在车载端，对单车算力提出了巨大要求；2）采用单车感知道路交通环境，其决策结果具有一定局限性；3）多车协同决策转化为优化问题，随着车辆数目的增加，解空间将呈指数扩大，求解难度与耗时也将会增加。

针对上述问题，本文基于车路协同环境高速公路多车道多车场景，通过将多车协同决策转化为二分图最优匹配问题，提出一种高速多车多驾驶行为冲突协同决策方法，以提高多车协同决策的整体效用值和车辆通行效率。假设研究场景内所有车辆均为网联自动驾驶车辆，可与路侧设备交互，利用路侧端对车辆驾驶行为进行协调，避免单车决策由于对道路环境信息判断错误，导致决策失误，与其它车辆驾驶行为产生冲突的问题。

1 多车道多车多驾驶行为冲突机理

多车交通场景会出现驾驶行为冲突，以三车道两车这一典型交通场景为例分析多车道多车多驾驶行为冲突机理。驾驶行为冲突示意如图1 所示，其中Lane1 为快车道，Lane 2 为中间车道，Lane 3 为慢车道。图1中，自动驾驶车辆V1 和V2 分别行驶于Lane 3和Lane 2，2 车均包含2 种候选驾驶行为：保持车道和向左换道。

假设某一时刻V1 从驾驶行为决策模块获取的最优驾驶行为是向左换道，V2 从驾驶行为决策模块获取的最优驾驶行为是保持车道。若2 车同时执行最优驾驶行为，则实施驾驶行为结束时刻车辆潜在空间位置不满足安全距离要求，会产生碰撞风险，甚至导致交通事故发生，该情况即为多车多驾驶行为冲突。造成该冲突问题主要原因在于，车辆在决策时均采用单车驾驶行为决策方法，优先考虑自车利益，不考虑礼让其他车辆。当驾驶环境中出现2 个或更多车辆，且不同车辆最优驾驶行为对应潜在空间位置不满足安全距离要求时，就会产生驾驶行为冲突。

2 多车多驾驶行为冲突协同决策方法

2.1 协同决策框架

为解决多车道多车多驾驶行为冲突问题，针对高速公路场景，利用车路协同技术，发挥车路协同环境道路交通群体协同决策的优势[10-11]，本文提出基于二分图最优匹配的高速多车多驾驶行为冲突协同决策方法，以全局总效用[2] 最大为目标函数，进行多车道多车多驾驶行为协同优化决策。该决策系统包括车载端和路侧端，协同决策框架如图2。

图2 中车载端处理本车驾驶行为决策信息，智能路侧设备（road side unit，RSU）即路侧端处理交通群体决策信息，实现协同决策。决策过程中车载端任务包括：1） 基于静态交通信息创建车辆候选驾驶行为集；2） 通过效用函数对车辆驾驶行为定量评价；3） 预测车辆实施驾驶行为结束时刻的潜在位置。车载端发送包含驾驶行为、效用值等信息的候选驾驶行为集。路侧端主要任务接受车载端信息，求解多车协同决策的最优匹配。

根据车辆与潜在位置区间、目标与潜在位置区间的对应关系，构造车辆集合V = {V1，V2，V3，V4，V5，V6} 与目标集合T = {T1，T2，T3，T4，T5，T6，T7，T8} 的二分图，如图6 所示。

表3 中若同一目标对应多个潜在位置区间，则表明这些潜在位置区间存在冲突，即车辆对应的驾驶行为存在冲突。由表3 得到KM 算法求解车辆和驾驶行为最优匹配所需车辆与目标之间的权值数据，如表4。

通過KM 算法对图6 匹配求解，匹配原则是：原则1 ：只有车辆的顶标与对应目标的权值相等时，则对车辆匹配该目标；

原则2 ：若车辆所匹配的目标，已经被其它车辆匹配过，则对匹配该目标的所有车辆顶标减去0.001，该目标的顶标加上0.001，并按照原则1 进行匹配，不断循环，直到该目标只被唯一车辆匹配；

原则3 ：当所有车辆匹配到唯一目标，则匹配结束。具体如图7 所示。

由图7 可知：车辆V1、V2、V3、V4、V5 和V6 匹配的目标分别是T1、T3、T4、T6、T5 和T7，对应驾驶行为分别是当前车道加速行驶、当前车道保持车速行驶、当前车道加速行驶、向左加速换道、当前车道加速行驶和向左加速换道。其中，V1、V2、V3 和V5 采取效用值最大的驾驶行为，V4 和V6 最大效用值对应同一目标T7，则表示其最大效用值对应驾驶行为违反安全距离要求，故V4 采取次大效用值的驾驶行为T6，V6采取最大效用值的驾驶行为T7，二者得到效用值组合最大的驾驶行为。综上，实验表明KM 算法能够以全局总效用最大为目标，为每个车辆分配驾驶行为。最终路侧端输出所有车辆匹配的最优驾驶行为结果M*。

车辆执行最优驾驶行为后，其位置随时间变化曲线如图8，横纵向位置变化曲线如图9， 颜色谱表示时间。由图8 可知车辆V2 始终行驶在V1 前方，两车之间未发生碰撞；由图9 可知V3 和V4 行驶至相同位置处的时间存在差异，故两车从未发生碰撞，同理V5 和V6从未发生碰撞。综上，验证了协同决策方法可解决多车多驾驶行为冲突，保证车辆行车安全。

车辆执行所分配的驾驶行为初末时刻全局总效用值和平均车速，如表5 所示。

由表5 可知：实施驾驶行为结束时刻总效用值与平均车速均增加，即全局道路交通环境通行效率、驾驶空间效益以及驾驶空间安全性都得到改善。

为进一步验证算法的性能， 采用遗传算法（genetic algorithm，GA）和粒子群算法（particle swarmoptimization，PSO）与KM 算法进行对比，每种算法都重复实验50 次，PSO 的粒子群规模和GA 算法的种群规模均设置为20，PSO 的最大迭代次数和GA 算法的最大遗传代数均设置为100，对比结果如表6。

由表6 可知：KM 算法可以稳定求得最优解，GA和PSO求解效果不稳定。KM算法与其他两种算法相比，其求解速度具有明显优势，分配求解耗时不到0.1 ms。将车辆数量增加为16 辆和24 辆时，KM 算法实验50次的分配耗时也均小于0.3 ms。

综上，KM 算法与GA 和PSO 这2 种算法相比，其精度和速度具有明显的优势，能够更好地适应车辆驾驶决策的实时性和准确性要求。

4 结 论

针对高速公路场景下多车道多车驾驶行为决策时，因自车利益优先策略导致车辆潜在空间位置发生冲突的问题，提出了基于二分图最优匹配的高速多车多驾驶行为冲突协同决策方法。以车道平均车速、车辆密度、行进空间、即碰时间（TTC）、行驶负担等5 项评价指标为变量，建立效用函数对车辆驾驶行为进行定量评价；以全局总效用最大为目标，通过KM 算法对多车协同决策转化的二分图最优匹配问题进行求解，得到车辆的最优匹配驾驶行为。

仿真结果表明：本文提出的协同决策方法能够有效解决多车多驾驶行为冲突，保证了车辆行车安全，提高道路上初末时刻车辆2% 的效用值和8% 的平均车速，增加了通行效率，且驾驶行为决策的准确性相比于遗传算法（GA）、粒子群算法（PSO）分别提高了11% 和9%、驾驶空间效益以及安全性得到改善，且采用KM算法求解耗时小于1.0 ms， 可以稳定求得最优解，算法的实时性远高于GA 算法和PSO 算法，可以适应车辆驾驶行为决策对实时性和准确性的要求。

参考文献（ References）

[1] YIN Taiqiao， LI Ying， Fan Jiaohao， et al. A novel gatedrecurrent unit network based on svm and moth-flameoptimization algorithm for behavior decision-making ofautonomous vehicles [J]. IEEE Access， 2021， 9： 20410-20422.

[2] Furda A， Vlacic L. Enabling safe autonomous drivingin real-world city traffic using multiple criteria decisionmaking [J]. IEEE Intel Transp Syst Maga， 2011， 3（1）： 4-17.

[3] WANG Pengwei， GAO Song， LI Liang， et al. Research ondriving behavior decision making system of autonomous driving vehicle vased on benefit evaluation model [J].Archives Transp， 2020， 53（1）： 21-36.

[4] 杨达， 吕蒙， 戴力源， 等. 车联网环境下自动驾驶车辆车道选择决策模型[J]. 中国公路学报， 2022， 35（4）： 243-255.

YANG Da， L? Meng， DAI Liyuan，et al. Decision-makingmodel for the lane selection of automated vehicles inthe connected vehicle environment [J]. Chin J HighwayTransp， 2022， 35（4）： 243-255. （in Chinese）

[5] Schmidt M， Wissing C， Nattermann T， et al. Aprobabilistic model for discretionary lane changeproposals in highway driving situations [J]. Forschung imIngenieurwesen， 2021， 85（2）： 485-500.

[6] Düring M， Pascheka P. Cooperative decentralized decisionmaking for conflict resolution among autonomous agents[C]// 2014 IEEE Intl Symp Inno Intel Syst Appl （INISTA）Proc， 2014： 154-161.

[7] Lovellette E， Hexmoor H. Lane and speed allocationmechanism for autonomous vehicle agents on a multi-lanehighway [J]. Internet of Things， 2021， 13： 1-19.

[8] LIU Yingxiang， LI Hao， ZHU Xuefeng. Brainstormingmulti-agent reinforcement learning for multi-vehiclesgames [C]// 2021 Intl Conf Digi Soc Intell Syst （DSInS），2021： 357-361.

[9] Kessler T， Knoll A. Cooperative multi-vehicle behaviorcoordination for autonomous driving [C]// 2019 IEEE IntelVehi Symp （IV）， 2019： 1953-1960.

[10] 李珣， 曲仕茹， 夏余. 車路协同环境下多车道车辆的协同换道规则[J]. 中国公路学报， 2014， 27（8）： 97-104.

LI Xun， QU Shiru， XIA Yu. Cooperative lane-changingrules on multilane under condition of cooperative vehicleand infrastructure system [J]. Chin J Highway Transp，2014， 27（8）： 97-104. （in Chinese）

[11] 张毅， 姚丹亚， 李力， 等. 智能车路协同系统关键技术与应用[J]. 交通运输系统工程与信息， 2021， 21（5）： 40-51.

ZHANG Yi， YAO Danyao， LI Li， et al.Technologiesand applications for intelligent vehicle-infrastructurecooperation systems [J]. J Transp Syst Eng Info Tech，2021， 21（5）： 40-51. （in Chinese）

[12] Barbera A J， Horst J A， SCHLENOFF C I， et al. Taskanalysis of autonomous on-road driving [C]// MobileRobots XVII， 2004， 5609： 61-72.

[13] LU Xinghao， ZHAO Haiyan， GAO Bingzhao， et al.Decision-making method of autonomous vehicles in urbanenvironments considering traffic laws [J]. IEEE TransIntel Transp Syst， 2022， 23（11）： 21641-21652.

[14] 彭浩楠， 王伟达， 项昌乐， 等. 自动驾驶汽车双车道换道优化轨迹规划方法[J]. 吉林大学学报（ 工学版）， 2022，8（2）： 1-12.

PENG Haonan， WANG Weida， IANG Changle， et al.Optimization-based lane changing trajectory planningapproach for autonomous vehicles on two-lane road [J]. JJilin Univ （Eng Tech Ed）， 2022， 8（2）： 1-12. （in Chinese）

[15] 刘思阳， 蒙涛， 雷家坤， 等. 微纳卫星星座的Kuhn-Munkres 匹配部署优化方法[J]. 宇航学报， 2021， 42（7）：895-906.

LIU Siyang， MENG Tao， LEI Jiakun， et al.Kuhn-Munkresmatching deployment optimization method for microsatelliteconstellation [J]. J Astronautics， 2021， 42（7）： 895-906. （in Chinese）