基于局部博弈的單交叉口路徑規劃研究

摘要：針對智能車輛在單交叉口環境下存在因沖突風險引起的碰撞率高和通行效率低的問題，提出一種基于局部博弈算法的路徑規劃算法。通過建立路口沖突風險模型分析存在的沖突風險，對車輛與行人的沖突提出消解方法；引入局部博弈理論，建立收益函數評價可行決策，求出在約束條件下純策略納什均衡的解，并對車輛速度進行規劃，最終實現智能車輛的路徑規劃。仿真結果表明，提出的路徑規劃算法在不同車流量下相比于演化博弈和合作博弈算法交互成功率提升9.32%，通行效率平均提升33%，能有效緩解交通壓力。

關鍵詞：智能車輛；人車沖突；局部博弈；納什均衡；路徑規劃

中圖分類號： TB391; U491.23 文獻標識碼： A

收稿日期：2023-01-20；修回日期：2023-03-22

基金項目：國家自然科學基金（52175236）

第一作者：姜楠（1998-），男，安徽淮南人，碩士研究生，主要研究方向為自動化駕駛路徑規劃方法。

通信作者：趙清海（1985-），男，山東濰坊人，博士，副教授，主要研究方向為輕量化車輛結構設計。

Single Intersection Path Planning Based on Local Game

JIANG Nan^1a， ZHAO Qinghai^1a，2， XU Chong^1a， DU Siyu^1b

（1.a.School of Mechanical and Electrical Engineering; b. School of Automation， Qingdao University， Qingdao 266071，China; 2.Electric vehicle intelligent power integration technology national local joint engineering research center， Qingdao 266071，China）

Abstract：Aiming at the problems of high collision rate and low traffic efficiency caused by conflict risk of intelligent vehicles in single intersection environment， a path planning algorithm based on local game algorithm is proposed. By establishing the intersection conflict risk model， the conflict risk is analyzed， and the conflict resolution method between vehicles and pedestrians is proposed. The local game theory is introduced to establish the profit function to evaluate the feasible decision， and the solution of the pure strategy Nash equilibrium under the constraint condition is obtained. The vehicle speed is planned， and the path planning of the intelligent vehicle is finally realized. The simulation results show that the proposed path planning algorithm improves the interaction success rate by 9.32% compared with the evolutionary game and cooperative game algorithm under different traffic flows， and the traffic efficiency increases by 33% on average， which can effectively alleviate the traffic pressure.

Keywords： intelligent vehicle; people-vehicle conflict; local game; nash equilibrium; path planning

0 引言

近年來，路徑規劃算法作為智能駕駛系統中的關鍵技術已逐步成為國內外學者研究的熱點問題之一^[1-2]。其中智能車輛路徑規劃在單交叉口環境下的安全性和通行效率無法滿足智能汽車的要求，因此如何減少碰撞率并提高通行效率對智能交通發展具有重大意義。

目前路徑規劃算法分為全局路徑規劃和局部路徑規劃，其中局部路徑規劃主要包含以下幾種算法：勢場法^[3]通過引入勢場的概念，利用矢量場來抽象行駛車輛的運動，計算車輛所受到的合力場，憑借合力場來規劃出車輛的運動軌跡；Tang^[4]、Dolgov^[5]等基于搜索的方法在機器人路徑規劃領域得到廣泛應用，該類算法具有較高最優性，但僅適用于在已知環境下的智能車輛路徑規劃；快速搜索隨機樹法（Rapid-exploration random tree， RRT）^[6] 、Mohammed^[7]以及Gammell^[8]等基于采樣的方法，結構簡單規劃效率高，但并不適用于狹小路段內的路徑規劃。以上方法均只適用于在已知環境狀態下的路徑規劃，對于交叉路口環境下未知且多變的特殊道路環境，運用以上算法很難獲取最優路徑。

基于優化的路徑規劃方法是通過參數化的數值來描述車輛路徑，并利用不同評價指標體系構建收益函數，以風險收益對車輛進行路徑規劃^[9-11]。Yang等^[12]提出一種基于合作博弈的路徑規劃算法，并利用遺傳算法求解最優策略集，但必須需要參與博弈車輛的以往通行數據，且交互成功率較低；Liu等^[13]基于演化博弈，同時以障礙物的危險程度以及路徑軌跡的平滑性作為評價的指標規劃出最優路徑，最后通過實車驗證了算法的可行性；馬慶祿等^[14]基于演化博弈理論，在無信號交叉口環境下研究駕駛人行為博弈，但沒有考慮有信號燈的情況；Wang等^[15]利用離散策略納什博弈表示非合作行為，并通過合作博弈對合作控制機制進行建模；Zhang等^[16]提出基于優化運輸基礎的設施框架，運用博弈論處理收集信息，次框架能通過收集和分析數據做出相應規劃來減少道路擁堵；孫啟鵬等^[17]基于風險均衡理論，利用博弈論求解最優行為決策；魏麗英等^[18]基于演化博弈建立行人與車輛的沖突博弈模型，調控博弈參與者的通行順序，提高通行效率。

上述研究均通過博弈理論來解決道路擁擠的問題，但均是將環境下的博弈問題當成一個整體，因此在環境復雜程度過高的情形下存在較高的規劃失敗率以及較低的通行效率。針對以上問題，以確保行人和車輛安全性為前提，提出一種基于局部博弈的路徑規劃算法，建立單交叉口環境下的路口沖突模型，分析可行的通行策略；設計參與博弈車輛的收益函數并求出純策略下的納什均衡解，對車輛的速度進行最優規劃并規劃出車輛路徑；最后通過搭建仿真環境來驗證算法的沖突交互成功率和不同車流量下的通行效率。

1 單交叉口環境下路口的沖突分析

研究場景為4向3車道的十字路口，包含信號燈以及人行道，如圖1所示，每個路口均設置信號燈，信號燈周期為60s（紅燈為29s、黃燈3s、綠燈27s），左側車道、中間車道、右側車道分別為直行車道與左轉車道、直行車道、直行車道與右轉車道；場景分為等待博弈區與參與博弈區，通過數據中心獲取車輛當前位置坐標和速度參數并分發處理后的數據。為方便描述沖突區域將博弈區按照車道進行網格劃分，如圖2所示，每個區域設有相應數字坐標，例如：此時車輛所處的位置為[2， 3]和[3， 3]。

1.1 人與車沖突

在人行通道并考慮信號燈的情況下，事先行人與車輛之間無任何信息交流，因此二者存在碰撞風險，此場景被定義為人車沖突情形。如圖3所示，車輛左轉時沖突區為[5，8]、[6，8]、[7，8]，右轉時沖突區為[7，8]；因行人具有很強的主觀意識，則行人具有更高優先級，車輛將規劃出合理路徑避讓行人。

當車輛左轉發生沖突時主要可分為3類，如圖4 所示，圖4a 所示情況下車輛發生沖突的區域為[5，8]、[6，8]、[7，8]，沖突區域碰撞概率如圖5所示（藍色柱狀圖），為確保行人的安全，車輛可駛入[7，8]區域或減速至行人通過沖突區域；圖4b 所示情況下的沖突區域碰撞的概率如圖5（橙色柱狀圖），車輛可從[5，8]路口駛出或減速至行人通過沖突區域；圖4c 所示情況，由于行人已處于沖突區域，由于行人具有最高的優先級，因此車輛應減速或停止至行人通過沖突區。

當車輛右轉時因安全駕駛規則，則不考慮車輛右轉入除最右車道以外的其他車道，則沖突區僅為[7，8]區域，車輛可減速并等待行人通過沖突區域。

1.2 車與車沖突

車與車在真實環境并考慮信號燈的情況下，僅需考慮2種在十字路口情況下的沖突情形，如圖6所示，分別為車輛左轉和右轉時可能存在的沖突風險。

在圖6 a 中A車、B車、C車分別為從十字路口相同方向的不同路口直線行駛進入博弈區，則當前左轉車輛與A車、B車、C車可能發生沖突的區域如表1所示。當發生沖突時，先行車輛將勻速行駛或加速通行沖突區域，后行車輛將換至其他車道或減速等待先行車輛通過沖突區。

圖6b 中右轉車輛考慮安全交通規則，右轉后只進入最右車道，將不會與除駛入最右車道的其他車輛存在沖突風險，且還能保證車輛行駛安全。車與車之間發生沖突時的決策規劃流程圖如圖7所示。

3 仿真驗證與分析

為驗證算法的沖突交互成功率（若該次仿真中所有車輛均可通過博弈區到達安全區，則視為沖突交互成功）和通行效率，搭建十字路口仿真環境如圖8所示，其中車輛類型為普通轎車，SUV，面包車等中小型汽車，每個人行道一個通行周期人數為9到15人，假設車輛與行人均遵守基本交通規則，假設車輛以20km/h勻速通過路口，車輛的行駛路徑如圖9a所示，車輛采取等待行人的行為決策，圖9a、9b、9c分別為進入博弈區后不同時間所對應的位置。圖11a為車輛在博弈區的速度曲線，圖中曲線平穩變化，說明車輛具有良好的平穩性以及舒適性。車與車之間的沖突區域如圖10a所示，圖10b、10c、10d分別為進入博弈區后不同時間對應的車輛位置。圖11b為兩車的速度曲線，圖中兩車的速度變化平穩，并未出現大幅度抖動的情況，則說明兩車在通過博弈區時具有良好的平穩性和舒適性。由此可以看出該算法能有效規避碰撞，保證行人與車輛的安全，并且做出最優決策的時間也進一步縮減，則整體的通行效率將提升。

在不同交通流（見圖12a）下，每一種算法通過博弈區的交互成功率以及通行效率如圖12b和圖12c所示，每個車流量對應的仿真次數為100次，可以得出在不同交流量下局部博弈都有著較高的交互成功率，平均高于其他博弈算法9.32%，小車流量時3種算法的平均時間相差很少，但隨著交通流量的增大，局部博弈的優勢就會逐漸顯現，平均高于其他算法33%。

4 結論

針對因沖突問題造成的智能車輛安全性低且通行效率不高的問題，本文利用跨學科研究法，提出一種基于局部博弈的路徑規劃算法。首先，對單交叉口環境下智能車輛可能存在的沖突問題進行建模分析，并提出交互沖突的解決策略；其次引入局部博弈算法，利用收益函數來評價決策結果，并求得純策略下的納什均衡解后，對規劃車輛做出速度規劃；最后搭建仿真環境，以路口在不同車流量下的交互成功率和通行效率作為評價指標。結果表明，所提出的算法能夠規劃出適合路口快速通行的道路，實現在單交叉口環境下的安全且高效通行。在此研究中，本文所考慮車輛的優先級以及車輛參數均相同，距離真實環境還有較大的差距，后續研究中將會逐步加入不同的車輛模型和優先級，更加貼近真實環境。

參考文獻：

[1]高自友，吳建軍. 出行者博弈、網絡結構與城市交通系統復雜性[J].復雜系統與復雜性科學，2010，7（4）：55-64.

GAO Z Y， WU J J. Travelers game， network structure and urban traffic system complexity[J]. Complex Systems and Complexity Science， 2010， 7（4）： 55-64.

[2]SALAHUDDIN M A， AL-FUQAH A， GUIZANI M. Software-Defined networking for RSU clouds in support of the Internet of vehicles[J]. Internet of Things Journal IEEE， 2015， 2（2）： 133-144.

[3]陳慧巖，陳舒平，龔建偉. 智能汽車橫向控制方法研究綜述[J]，兵工學報，2017，38（6）：1203-1214.

CHEN H Y， CHEN S P， GONG J W. A review on the research of lateral control for intelligent vehicles[J]. Acta ArmamentarII， 2017， 38（6）： 1203-1214.

[4]TANG G， TANG C Q， CLARAMUNT C， et al. Geometric a-star algorithm： an improved a-star algorithm for AGV path planning in a port environment[J]. IEEE Access， 2021， 9： 59196-59210.

[5]DOLGOV D， THRUN S， MONTEMERLO M， et al. Path planning for autonomous vehicles in unknown semi-structured environments[J]. The International Journal of Robotics Research， 2010， 29（5）： 485-501.

[6]李秀智，赫亞磊，孫炎珺，等. 基于復合式協同策略的移動機器人自主探索[J]. 機器人，2021，43（1）：44-53.

LI X Z， HE Y L， SUN Y J，et al. Autonomous exploration of mobile robot based on compound cooperative strategy[J]. Robot， 2021， 43（1）： 44-53.

[7]MOHAMMED H， ROMDHANE L， JARADAT M A. RRT* N： an efficient approach to path planning in 3D for static and dynamic environments[J]. Advanced Robotics， 2021， 35（3/4）： 168-180.

[8]GAMMELL J D， SRINIVASA S S， BARFOOT T D. Informed RRT*： optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. Chicago，IL，USA： IEEE， 2014： 2997-3004.

[9]ZHAO C， LI L， PEI X， et al. A comparative study of state-of-the-art driving strategies for autonomous vehicles[J]. Accident Analysis amp; Prevention， 2021， 150： 105937.

[10] 高海龍，王煒，常玉林，等. 無信號交叉口臨界間隙的理論計算模型[J]. 中國公路學報，2001（2）：80-82.

GAO H L， WANG W， CHANG Y L， et al. A mathematical model for critical gap of unsignalized intersections[J]. China Journal of Highway and Transport， 2001（2）： 80-82.

[11] 陳卓然，韓定定. 一類交通信息物理系統的動態路徑引導[J]. 復雜系統與復雜性學，2022，19（1）：81-87.

CHEN Z R， HAN D D. Dynamic route guidance strategy in transportation cyber-physical systems[J]. Complex Systems and Complexity Science， 2022， 19（1）： 81-87.

[12] YANG Z， HUANG H， WANG G， et al. Cooperative driving model for non-signalized intersections with cooperative games[J]. Journal of Central South University， 2018， 25（9）： 2164-2181.

[13] 郭蓬，吳學易，戎輝，等. 基于代價函數的無人駕駛汽車局部路徑規劃算法[J]. 中國公路學報，2019，32（6）：79-85.

GUO P， WU X Y， RONG H，et al. Local path planning of driver less cars based on cost function[J]. Chan J Highw Transp， 2019， 32（6）： 79-85.

[14] 馬慶祿，聶振宇. 基于博弈論的無信號交叉口沖突消解方法[J]. 重慶理工大學學報：自然科學，2021，35（10）：144-151.

MA Q L， NIE Z. Conflict resolution method based on game theory at unsignalized intersection[J]. Journal of Chongqing University of Technology （Natural Science）， 2021， 35（10）： 144-151.

[15] WANG H， MENG Q， CHEN S K， et al. Competitive and cooperative behaviour analysis of connected and autonomous vehicles across unsignalised intersections： a game-theoretic approach[J]. Transportation Research Part B： Methodological， 2021， 149： 322-346.

[16] ZHANG Y， TIAN F， SONG B， et al. Social vehicle swarms： a novel perspective on socially aware vehicular communication architecture[J]. IEEE Wireless Communications， 2016， 23（4）：82-89.

[17] 孫啟鵬，武智剛，等. 基于風險預測的自動駕駛車輛行為決策模型[J]. 浙江大學學報（工學版），2022，56（9）：1761-1771.

SUN Q P， WU Z G， et al. Decision-making model of autonomous vehicle behavior based on risk prediction[J]. Journal of Zhejiang University （Engineering Science）， 2022， 56（9）： 1761-1771.

[18] 魏麗英，崔裕楓，李東瑩. 基于演化博弈論的行人與機動車沖突演化機理研究[J]. 物理學報，2018，67（19）：37-49.

WEI L Y， CUI Y F， LI D Y. Evolution mechanism of conflict between pedestrian and vehicle based on evolutionary game theory[J]. Acta Phys Sin， 2018，67（19）：37-49.

（責任編輯 李 進）