高速多車多駕駛行為的沖突協同決策方法

張新鋒 吳琳 李致遠 柳歡

摘 要： 為解決高速公路場景下多車多駕駛行為車輛空間位置沖突的問題，提出了一種基于二分圖最優匹配的駕駛行為沖突協同決策方法。根據靜態交通信息，創建車輛可行候選駕駛行為集，依據車道平均車速、車輛密度、行進空間、即碰時間（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）