張新鋒 吳琳 李致遠(yuǎn) 柳歡

摘 要： 為解決高速公路場景下多車多駕駛行為車輛空間位置沖突的問題，提出了一種基于二分圖最優(yōu)匹配的駕駛行為沖突協(xié)同決策方法。根據(jù)靜態(tài)交通信息，創(chuàng)建車輛可行候選駕駛行為集，依據(jù)車道平均車速、車輛密度、行進空間、即碰時間（TTC）、行駛負(fù)擔(dān)等5 種評價指標(biāo)構(gòu)建效用函數(shù)，對候選駕駛行為定量評價；以車輛實施駕駛行為結(jié)束時刻的潛在空間位置為目標(biāo)集合，駕駛行為評價效用為權(quán)值，構(gòu)建基于車輛集合與目標(biāo)集合的二分圖；以全局總效用值最大為決策目標(biāo)，采用Kuhn-Munkres（KM）算法求解最優(yōu)匹配；搭建仿真場景，來驗證該方法的有效性。結(jié)果表明：該協(xié)同決策方法可有效解決多車多駕駛行為沖突，保證車輛行車安全，提高道路上初末時刻車輛2% 的效用值和8% 的平均車速，增加了通行效率，且駕駛行為決策的準(zhǔn)確性相比于遺傳算法（GA）、粒子群算法（PSO）分別提高了11% 和9%，同時KM算法的實時性遠(yuǎn)高于GA 算法和PSO 算法。

關(guān)鍵詞： 自動駕駛；協(xié)同決策；二分圖；Kuhn-Munkres（KM）算法；效用函數(shù)

中圖分類號： U 461 文獻標(biāo)識碼： A DOI： 10.3969/j.issn.1674-8484.2023.05.010

行為決策系統(tǒng)是自動駕駛車輛的關(guān)鍵技術(shù)，作為自動駕駛技術(shù)的核心，其智能化程度影響車輛行駛的安全性和可靠性，以及在復(fù)雜多變的實時交通環(huán)境下的適應(yīng)性[1]。

基于效用函數(shù)的自動駕駛行為決策方法具有靈活性、適應(yīng)性、多目標(biāo)優(yōu)化和透明性等多個優(yōu)點，使自動駕駛系統(tǒng)更具有實際應(yīng)用和可行性。該方法通過人為構(gòu)造多個備選方案并設(shè)置評價指標(biāo)，選擇最優(yōu)效用對應(yīng)的駕駛行為作為最佳駕駛行為[2]。如WANGPengwei 等[3] 建立了綜合考慮駕駛效率和安全性的駕駛行為效益評價模型；楊達等[4] 建立了車聯(lián)網(wǎng)環(huán)境下的自動駕駛車輛車道選擇決策模型；M. Schmidt 等[5]根據(jù)車道滿意度為車輛生成車道變化建議；A. Furda等[2] 建立了一個多準(zhǔn)則決策系統(tǒng)，綜合考慮多個評價指標(biāo)決策最優(yōu)駕駛行為。

現(xiàn)有的自動駕駛行為決策方法主要針對單車，決策過程中采取自車?yán)鎯?yōu)先策略。當(dāng)駕駛環(huán)境中出現(xiàn)2 個或更多車輛時，車輛潛在空間位置將會發(fā)生沖突，不利于道路交通的全局高效安全運行。因此需研究車輛間的協(xié)同決策，協(xié)同決策中車輛群體關(guān)注共同利益或共同目標(biāo)，有利于保證道路交通安全，提高通行效率[6]。如E. Lovellette 等[7] 以博弈論的方法建立了多車道公路自動駕駛車輛的車道和速度分配算法；LIUYingxiang 等[8] 建立了基于多智能體強化學(xué)習(xí)算法的自動駕駛車輛決策模型；T. Kessler 等[9] 通過優(yōu)化求解協(xié)調(diào)多車駕駛行為。但上述研究主要存在以下問題：1）協(xié)同決策模塊部署在車載端，對單車算力提出了巨大要求；2）采用單車感知道路交通環(huán)境，其決策結(jié)果具有一定局限性；3）多車協(xié)同決策轉(zhuǎn)化為優(yōu)化問題，隨著車輛數(shù)目的增加，解空間將呈指數(shù)擴大，求解難度與耗時也將會增加。

針對上述問題，本文基于車路協(xié)同環(huán)境高速公路多車道多車場景，通過將多車協(xié)同決策轉(zhuǎn)化為二分圖最優(yōu)匹配問題，提出一種高速多車多駕駛行為沖突協(xié)同決策方法，以提高多車協(xié)同決策的整體效用值和車輛通行效率。假設(shè)研究場景內(nèi)所有車輛均為網(wǎng)聯(lián)自動駕駛車輛，可與路側(cè)設(shè)備交互，利用路側(cè)端對車輛駕駛行為進行協(xié)調(diào)，避免單車決策由于對道路環(huán)境信息判斷錯誤，導(dǎo)致決策失誤，與其它車輛駕駛行為產(chǎn)生沖突的問題。

1 多車道多車多駕駛行為沖突機理

多車交通場景會出現(xiàn)駕駛行為沖突，以三車道兩車這一典型交通場景為例分析多車道多車多駕駛行為沖突機理。駕駛行為沖突示意如圖1 所示，其中Lane1 為快車道，Lane 2 為中間車道，Lane 3 為慢車道。圖1中，自動駕駛車輛V1 和V2 分別行駛于Lane 3和Lane 2，2 車均包含2 種候選駕駛行為：保持車道和向左換道。

假設(shè)某一時刻V1 從駕駛行為決策模塊獲取的最優(yōu)駕駛行為是向左換道，V2 從駕駛行為決策模塊獲取的最優(yōu)駕駛行為是保持車道。若2 車同時執(zhí)行最優(yōu)駕駛行為，則實施駕駛行為結(jié)束時刻車輛潛在空間位置不滿足安全距離要求，會產(chǎn)生碰撞風(fēng)險，甚至導(dǎo)致交通事故發(fā)生，該情況即為多車多駕駛行為沖突。造成該沖突問題主要原因在于，車輛在決策時均采用單車駕駛行為決策方法，優(yōu)先考慮自車?yán)?，不考慮禮讓其他車輛。當(dāng)駕駛環(huán)境中出現(xiàn)2 個或更多車輛，且不同車輛最優(yōu)駕駛行為對應(yīng)潛在空間位置不滿足安全距離要求時，就會產(chǎn)生駕駛行為沖突。

2 多車多駕駛行為沖突協(xié)同決策方法

2.1 協(xié)同決策框架

為解決多車道多車多駕駛行為沖突問題，針對高速公路場景，利用車路協(xié)同技術(shù)，發(fā)揮車路協(xié)同環(huán)境道路交通群體協(xié)同決策的優(yōu)勢[10-11]，本文提出基于二分圖最優(yōu)匹配的高速多車多駕駛行為沖突協(xié)同決策方法，以全局總效用[2] 最大為目標(biāo)函數(shù)，進行多車道多車多駕駛行為協(xié)同優(yōu)化決策。該決策系統(tǒng)包括車載端和路側(cè)端，協(xié)同決策框架如圖2。

圖2 中車載端處理本車駕駛行為決策信息，智能路側(cè)設(shè)備（road side unit，RSU）即路側(cè)端處理交通群體決策信息，實現(xiàn)協(xié)同決策。決策過程中車載端任務(wù)包括：1） 基于靜態(tài)交通信息創(chuàng)建車輛候選駕駛行為集；2） 通過效用函數(shù)對車輛駕駛行為定量評價；3） 預(yù)測車輛實施駕駛行為結(jié)束時刻的潛在位置。車載端發(fā)送包含駕駛行為、效用值等信息的候選駕駛行為集。路側(cè)端主要任務(wù)接受車載端信息，求解多車協(xié)同決策的最優(yōu)匹配。

根據(jù)車輛與潛在位置區(qū)間、目標(biāo)與潛在位置區(qū)間的對應(yīng)關(guān)系，構(gòu)造車輛集合V = {V1，V2，V3，V4，V5，V6} 與目標(biāo)集合T = {T1，T2，T3，T4，T5，T6，T7，T8} 的二分圖，如圖6 所示。

表3 中若同一目標(biāo)對應(yīng)多個潛在位置區(qū)間，則表明這些潛在位置區(qū)間存在沖突，即車輛對應(yīng)的駕駛行為存在沖突。由表3 得到KM 算法求解車輛和駕駛行為最優(yōu)匹配所需車輛與目標(biāo)之間的權(quán)值數(shù)據(jù)，如表4。

通過KM 算法對圖6 匹配求解，匹配原則是：原則1 ：只有車輛的頂標(biāo)與對應(yīng)目標(biāo)的權(quán)值相等時，則對車輛匹配該目標(biāo)；

原則2 ：若車輛所匹配的目標(biāo)，已經(jīng)被其它車輛匹配過，則對匹配該目標(biāo)的所有車輛頂標(biāo)減去0.001，該目標(biāo)的頂標(biāo)加上0.001，并按照原則1 進行匹配，不斷循環(huán)，直到該目標(biāo)只被唯一車輛匹配；

原則3 ：當(dāng)所有車輛匹配到唯一目標(biāo)，則匹配結(jié)束。具體如圖7 所示。

由圖7 可知：車輛V1、V2、V3、V4、V5 和V6 匹配的目標(biāo)分別是T1、T3、T4、T6、T5 和T7，對應(yīng)駕駛行為分別是當(dāng)前車道加速行駛、當(dāng)前車道保持車速行駛、當(dāng)前車道加速行駛、向左加速換道、當(dāng)前車道加速行駛和向左加速換道。其中，V1、V2、V3 和V5 采取效用值最大的駕駛行為，V4 和V6 最大效用值對應(yīng)同一目標(biāo)T7，則表示其最大效用值對應(yīng)駕駛行為違反安全距離要求，故V4 采取次大效用值的駕駛行為T6，V6采取最大效用值的駕駛行為T7，二者得到效用值組合最大的駕駛行為。綜上，實驗表明KM 算法能夠以全局總效用最大為目標(biāo)，為每個車輛分配駕駛行為。最終路側(cè)端輸出所有車輛匹配的最優(yōu)駕駛行為結(jié)果M*。

車輛執(zhí)行最優(yōu)駕駛行為后，其位置隨時間變化曲線如圖8，橫縱向位置變化曲線如圖9， 顏色譜表示時間。由圖8 可知車輛V2 始終行駛在V1 前方，兩車之間未發(fā)生碰撞；由圖9 可知V3 和V4 行駛至相同位置處的時間存在差異，故兩車從未發(fā)生碰撞，同理V5 和V6從未發(fā)生碰撞。綜上，驗證了協(xié)同決策方法可解決多車多駕駛行為沖突，保證車輛行車安全。

車輛執(zhí)行所分配的駕駛行為初末時刻全局總效用值和平均車速，如表5 所示。

由表5 可知：實施駕駛行為結(jié)束時刻總效用值與平均車速均增加，即全局道路交通環(huán)境通行效率、駕駛空間效益以及駕駛空間安全性都得到改善。

為進一步驗證算法的性能， 采用遺傳算法（genetic algorithm，GA）和粒子群算法（particle swarmoptimization，PSO）與KM 算法進行對比，每種算法都重復(fù)實驗50 次，PSO 的粒子群規(guī)模和GA 算法的種群規(guī)模均設(shè)置為20，PSO 的最大迭代次數(shù)和GA 算法的最大遺傳代數(shù)均設(shè)置為100，對比結(jié)果如表6。

由表6 可知：KM 算法可以穩(wěn)定求得最優(yōu)解，GA和PSO求解效果不穩(wěn)定。KM算法與其他兩種算法相比，其求解速度具有明顯優(yōu)勢，分配求解耗時不到0.1 ms。將車輛數(shù)量增加為16 輛和24 輛時，KM 算法實驗50次的分配耗時也均小于0.3 ms。

綜上，KM 算法與GA 和PSO 這2 種算法相比，其精度和速度具有明顯的優(yōu)勢，能夠更好地適應(yīng)車輛駕駛決策的實時性和準(zhǔn)確性要求。

4 結(jié) 論

針對高速公路場景下多車道多車駕駛行為決策時，因自車?yán)鎯?yōu)先策略導(dǎo)致車輛潛在空間位置發(fā)生沖突的問題，提出了基于二分圖最優(yōu)匹配的高速多車多駕駛行為沖突協(xié)同決策方法。以車道平均車速、車輛密度、行進空間、即碰時間（TTC）、行駛負(fù)擔(dān)等5 項評價指標(biāo)為變量，建立效用函數(shù)對車輛駕駛行為進行定量評價；以全局總效用最大為目標(biāo)，通過KM 算法對多車協(xié)同決策轉(zhuǎn)化的二分圖最優(yōu)匹配問題進行求解，得到車輛的最優(yōu)匹配駕駛行為。

仿真結(jié)果表明：本文提出的協(xié)同決策方法能夠有效解決多車多駕駛行為沖突，保證了車輛行車安全，提高道路上初末時刻車輛2% 的效用值和8% 的平均車速，增加了通行效率，且駕駛行為決策的準(zhǔn)確性相比于遺傳算法（GA）、粒子群算法（PSO）分別提高了11% 和9%、駕駛空間效益以及安全性得到改善，且采用KM算法求解耗時小于1.0 ms， 可以穩(wěn)定求得最優(yōu)解，算法的實時性遠(yuǎn)高于GA 算法和PSO 算法，可以適應(yīng)車輛駕駛行為決策對實時性和準(zhǔn)確性的要求。

參考文獻（ 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] 楊達， 呂蒙， 戴力源， 等. 車聯(lián)網(wǎng)環(huán)境下自動駕駛車輛車道選擇決策模型[J]. 中國公路學(xué)報， 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] 李珣， 曲仕茹， 夏余. 車路協(xié)同環(huán)境下多車道車輛的協(xié)同換道規(guī)則[J]. 中國公路學(xué)報， 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] 張毅， 姚丹亞， 李力， 等. 智能車路協(xié)同系統(tǒng)關(guān)鍵技術(shù)與應(yīng)用[J]. 交通運輸系統(tǒng)工程與信息， 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] 彭浩楠， 王偉達， 項昌樂， 等. 自動駕駛汽車雙車道換道優(yōu)化軌跡規(guī)劃方法[J]. 吉林大學(xué)學(xué)報（ 工學(xué)版）， 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] 劉思陽， 蒙濤， 雷家坤， 等. 微納衛(wèi)星星座的Kuhn-Munkres 匹配部署優(yōu)化方法[J]. 宇航學(xué)報， 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）