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

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

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

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

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

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

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

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

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

1 多車道多車多駕駛行為沖突機(jī)理

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

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

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

2.1 協(xié)同決策框架

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

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

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

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

原則2 ：若車輛所匹配的目標(biāo)，已經(jīng)被其它車輛匹配過，則對(duì)匹配該目標(biāo)的所有車輛頂標(biāo)減去0.001，該目標(biāo)的頂標(biāo)加上0.001，并按照原則1 進(jìn)行匹配，不斷循環(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，對(duì)應(yīng)駕駛行為分別是當(dāng)前車道加速行駛、當(dāng)前車道保持車速行駛、當(dāng)前車道加速行駛、向左加速換道、當(dāng)前車道加速行駛和向左加速換道。其中，V1、V2、V3 和V5 采取效用值最大的駕駛行為，V4 和V6 最大效用值對(duì)應(yīng)同一目標(biāo)T7，則表示其最大效用值對(duì)應(yīng)駕駛行為違反安全距離要求，故V4 采取次大效用值的駕駛行為T6，V6采取最大效用值的駕駛行為T7，二者得到效用值組合最大的駕駛行為。綜上，實(shí)驗(yàn)表明KM 算法能夠以全局總效用最大為目標(biāo)，為每個(gè)車輛分配駕駛行為。最終路側(cè)端輸出所有車輛匹配的最優(yōu)駕駛行為結(jié)果M*。

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

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

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

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

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

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

4 結(jié) 論

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

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

參考文獻(xià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] 楊達(dá)， 呂蒙， 戴力源， 等. 車聯(lián)網(wǎng)環(huán)境下自動(dòng)駕駛車輛車道選擇決策模型[J]. 中國公路學(xué)報(bào)， 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é)報(bào)， 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]. 交通運(yùn)輸系統(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] 彭浩楠， 王偉達(dá)， 項(xiàng)昌樂， 等. 自動(dòng)駕駛汽車雙車道換道優(yōu)化軌跡規(guī)劃方法[J]. 吉林大學(xué)學(xué)報(bào)（ 工學(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é)報(bào)， 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）