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

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

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

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

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

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

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

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

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 引言

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

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

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

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

1 單交叉口環(huán)境下路口的沖突分析

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

1.1 人與車沖突

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

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

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

1.2 車與車沖突

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

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

圖6b 中右轉(zhuǎn)車輛考慮安全交通規(guī)則，右轉(zhuǎn)后只進入最右車道，將不會與除駛?cè)胱钣臆嚨赖钠渌囕v存在沖突風險，且還能保證車輛行駛安全。車與車之間發(fā)生沖突時的決策規(guī)劃流程圖如圖7所示。

3 仿真驗證與分析

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

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

4 結(jié)論

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

參考文獻：

[1]高自友，吳建軍. 出行者博弈、網(wǎng)絡結(jié)構(gòu)與城市交通系統(tǒng)復雜性[J].復雜系統(tǒng)與復雜性科學，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]李秀智，赫亞磊，孫炎珺，等. 基于復合式協(xié)同策略的移動機器人自主探索[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] 陳卓然，韓定定. 一類交通信息物理系統(tǒng)的動態(tài)路徑引導[J]. 復雜系統(tǒng)與復雜性學，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] 郭蓬，吳學易，戎輝，等. 基于代價函數(shù)的無人駕駛汽車局部路徑規(guī)劃算法[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.

（責任編輯 李 進）