基于最大團理論的自治交叉路口控制方法

劉明劍, 朱云鶴, 張思佳, 孫 華

(大連海洋大學 信息工程學院, 遼寧 大連 116023)

交叉路口是城市路網中重要的節點與樞紐,也是城市道路交通安全和擁堵頻發的瓶頸點[1-5]。隨著具備聯網功能和完全自動駕駛車輛(connected and automated vehicles,CAV)的出現,在降低交叉路口交通事故和緩解擁堵方面,將發揮革命性作用[6]。目前,針對CAV的交叉路口管理系統研究主要分為兩類:①在傳統交通信號控制系統基礎上,利用CAV獲得高精度交通數據,對信號控制系統相位和相序方案進行調整來滿足智能車輛的通行需求;②拋棄傳統的信號控制方式,實現針對全自動駕駛車輛調度的無信號交叉路口管理模式。

在基于CAV的改進傳統信號控制系統研究中,Li等[7]介紹了基于CAV信號控制系統的全局規劃、局部規劃以及自組織控制模式,通過數據分析,給出上述模式適用的不同交通情況。Guo等[8]將CAV獲得數據集成到信號控制系統中,根據CAV狀態信息對相位和相序進行優化,來提升交叉路口的通行效率。

雖然上述研究成果能夠在一定程度上提高CAV的通行效率,然而信號控制系統本質是為人類駕駛車輛服務,對于可以精確控制的CAV而言,執行效率仍然過低。因此,一些研究機構開始著眼于未來,研究適用于CAV的交叉路口控制系統,其中起步較早的是德克薩斯大學奧斯丁分校Stone團隊開發的自治交叉路口管理系統(autonomous intersection management,AIM)[9],研究者設計了性能較為優秀的先來先服務(first come first served, FCFS)控制策略。并在此基礎上,相繼提出了多種高效的控制策略[10],包括支持人類駕駛車輛的FCFS-light控制策略和考慮緊急車輛通行的FCFS-emerg策略等。Vasirani等[11]也在AIM系統中以競價拍賣為核心思想,設計了基于組合拍賣的交叉路口控制策略。

隨后,基于車輛集中調度方式,Mahbub等[12]提出了在狀態和控制雙約束條件下進行有效調度的交叉路口控制策略。Xu等[13]基于蒙特卡洛搜索方法,提出了協同駕駛控制策略,提高了交叉路口的通行效率。Zhu等[14]通過預測車輛可能到達延遲,建立了基于準確預測車輛到達時間的交叉路口控制策略。劉明劍等[15]提出了基于禁忌搜索的交叉路口控制策略,通過消減車輛間沖突關系,來提升交叉路口的吞吐量。常玉林等[16]提出了基于蟻群算法的控制策略,通過分析交叉路口車流量情況,能夠更加準確地搜索到車輛的最優行駛路徑。Pei等[17]提出了一種基于動態規劃的多車協作控制策略。吳偉等[18]建立了基于混合整數線性規劃的交叉口控制策略。

利用分布式控制方式,蔣陽升等[19]提出了一種基于虛擬車隊的時序調度模型,實現了交叉路口調度的全局優化。Gonzlez等[20]提出了一種多車分布式協作管理系統,該系統通過引入明確的規則,讓車輛遵守規則來提高通行效率。Yesilyurt等[21]通過共享車輛在交叉路口中期望占據的行駛區域以及它們的預計到達時間,來協調車輛間通行順序。

也有學者利用深度學習方法開展了交叉路口調度的研究,Zhang等[22]提出了一種基于卷積神經網絡的框架來預測不同車流密度下的車輛平均等待時間,進而選擇耗時最少的方案作為調度策略。

FCFS目前仍然為一種高效的交叉路口控制策略,但FCFS控制策略缺乏對未來交叉路口車流量變化的考量,容易發生死鎖,決策過程中也存在一定的盲目性,不利于實現交叉路口中車輛吞吐量的最大化需求。交通信號控制策略是針對人類駕駛車輛設計的策略,對于能夠精確控制的CAV而言,存在執行效率過低的問題;基于啟發式算法的交叉路口控制策略在車流量密度較大時容易陷入局部最優,無法進一步提升交叉路口的通行效率。

為了解決上述交叉路口控制策略存在的問題,本文提出了一種基于最大團自治交叉路口控制策略,在保證系統實時性需求的前提下,提高了交叉路口的通行效率,最后通過仿真實驗證明了控制策略的有效性與可靠性。

1 問題描述與建模

自治交叉路口控制系統是服務于具備完全自動駕駛功能CAV的交叉路口控制系統。首先,CAV進入交叉路口區域,開始向路側單元發送預約通過交叉路口的請求;其次,路側單元根據接收到的預約請求信息,模擬出車輛的行駛軌跡;再次,控制系統依據相應控制策略,給出CAV在交叉路口中的通行順序;最后,CAV駛離交叉路口區域,中斷與路側單元之間通信。交叉路口控制系統如圖1所示。

圖1 交叉路口控制系統

1.1 自治交叉路口控制系統的處理機制

(1) 交叉路口空間區域劃分機制。將矩形的交叉路口空間區域S進行網格化劃分處理,劃分為g2個二維空間小區域網格。劃分之后路口的第i個小區域網格為si,那么整個交叉路口S可以看作是由si組成的有限集合,如圖1所示。

S={si|1≤i≤g2,g∈N+}。

(1)

(2) 交叉路口時間批處理機制。定義整個交叉路口控制系統的離散時間域為T,將其等量切分后每個處理周期為Ti,整個控制系統的時間軸T是由批處理周期Ti組成的無限集合:

T={T1,T2,…,Ti,Ti+1,…,Tk}。

(2)

在每一個批處理周期Ti,自治交叉路口控制系統接收到預約過交叉路口的車輛請求集合為R:

R={vi|1≤i≤n,m∈N+}。

(3)

從R集合中選取可以通過交叉路口的車輛請求集合為Rac:

Rac={vi|1≤i≤m≤n,n、m∈N+},Rac?R。

(4)

1.2 控制系統建模

為了提高自治交叉路口的通行效率,并保證行車安全,需要確保在每一個批處理周期,預約通過交叉路口的任意兩輛車之間均不存在沖突關系,即車輛vi和vj(i≠j)在交叉路口行駛過程中,任意時刻均不能占用相同的一個或一組小網格交叉路口空間區域。

通過以上分析,建立每個批處理周期自治交叉路口求解的目標函數f,即在集合R選取最大車輛預約請求集合maxRac:

(5)

2 求解算法

2.1 基于最大團的自治交叉路口控制問題描述

基于第1節分析的車輛間的沖突關系可以建立車輛間沖突關系圖,即節點(CAV)以及弧(車輛間的沖突關系)組成的沖突關系圖G=(V,E),其中V為圖G中車輛預約請求集合Rall的車輛節點集;E則為車輛沖突關系的集合,即存在預約請求沖突關系的車輛節點之間有邊連接。自治交叉路口控制系統流程如圖2所示。

圖2 控制系統整體流程

2.2 基于最大團的自治交叉路口控制策略

尋找最大相容車輛節點集合maxRac的3個子階段如下。

(1) 隨機選擇車輛預約請求節點階段:隨機從集合中選擇一個車輛預約請求節點,對選擇車輛節點性質沒有傾向性。

(2) 選擇最大度的車輛預約請求節點階段:從集合中選擇一個具有最大度的車輛預約請求結點(初始時計算)。

(3) 選擇懲罰節點階段:加入節點懲罰機制,使得搜索過程多樣化,避免搜索停滯,基于貪心算法,越頻繁加入當前團的點,則在未來選擇過程中越不容易被重新選擇。

NDMC控制策略3個子階段運行完成之后,輸出最終接受車輛數集合Rac,即本周期內找到的最大接受請求車輛集合。

3 實驗與分析

為了對本研究提出的基于最大團的自治交叉路口控制策略的準確性和執行效率進行驗證,在開源自治交叉路口仿真平臺AIM[12]中,設定在平衡與不平衡2種車流量情況下對NDMC控制策略、FCFS控制策略、基于禁忌搜索控制策略(Tabu)[15]以及交通信號控制策略(traffic-light)的性能進行了對比評估。

3.1 實驗仿真設定

(1)仿真參數設定。在AIM系統中,設定一個雙向六車道正方形交叉路口區域(g=12)[12],單條車道寬度設定為3.25 m;生成車輛數量分布服從泊松分布,交通流分布服從Greenshields模型,車輛行駛速度依據車流量變化進行調整;交通路口通信范圍為以交叉路口中心點位半徑的300 m區域;車型為2種并按照2點分布生成(小型車尺寸為4.30 m×2.35 m,生成概率為0.8;大型車尺寸為10.0 m×2.5 m,生成概率為0.2)。控制系統的時間仿真步為0.02 s,時間片的劃分與仿真步保持一致,系統批處理周期為2 s,實驗的執行時間均為1 h。

3.2 平衡車流下控制策略性能評估實驗

在AIM仿真平臺中,平衡車流量情況表示進入交叉路口4個方向上車流量基本相當。

(1)車輛排隊情況分析。交叉路口各個駛入方向上車輛到達服從數學期望λ相一致的泊松分布,不失一般性,λ分別取值為0.100、0.125、0.150、0.175。統計2 min內交叉路口中車輛的排隊情況。如圖3所示,NDMC控制策略當λ取值為0.100、0.125、0.150時排隊總數低于26輛;而當λ=0.175時,車輛排隊數呈增加趨勢,但也維持在80輛之內,顯示出了較強的魯棒性。

圖3 服從泊松分布取不同λ值的車輛排隊長度對比

(2)平衡車流量情況下對比情況。在每個交叉路口進入方向的每條車道起始處依據泊松分布生成車流,車輛密度ω從0輛/h變化到2 500輛/h,車輛前進方向依據交通規則基礎上按照隨機規則生成(如最右側車道,車輛有直行或右轉彎2種前進方向)。交通信號控制策略采用固定的相位配時方案,如表1所示。

表1 傳統交通信號控制的相位配時

圖4為本文策略與其他策略性能對比情況。如圖4(a)所示,隨著車流量密度增加,FCFS控制策略發生死鎖次數也隨之增加,車輛完成數方面增加較為緩慢,當車流量密度小于500 輛/h時,NDMC控制策略與其他策略性能基本相當;當車輛密度大于1 000輛/h時,NDMC控制策略優于其他策略。當車流量密度小于240輛/h時,NDMC控制策略與其他策略的平均等待時間均維持在可接受范圍內;當流量密度超過300輛/h時,FCFS控制策略的平均等待時間出現了大幅度增加;當車輛密度超過2 000輛/h時,NDMC控制策略的平均等待時間低于其他控制策略。

圖4 平衡車流下不同策略性能對比情況

隨后,在平衡車流量情況下,對NDMC控制策略服務車輛數和拒絕車輛數情況進行評估,如圖5所示。NDMC控制策略服務車輛數即車輛完成數隨著車流量密度增加呈現出增加趨勢,當車輛密度大于1 000輛/h時,增加趨勢減緩;拒絕車輛數也隨著車輛密度增加而提高,當車輛密度為2 500輛/h時,拒絕的車輛數為3 656輛次,呈現出逐漸增加趨勢。這是因為隨著車流量密度增加,每個周期內請求數在增多,導致每個周期找到最優解即最大團的效率逐步降低。

圖5 車輛完成數和拒絕數對比分析

3.3 不平衡車流下控制策略性能評估實驗

在交叉路口東西進入方向車流量ω從0輛/h變化到2 500輛/h,南北兩進入方向的車流量密度維持1 500輛/h,其他參數設置與平衡車流下實驗設置相同。

圖6為不平衡車流下車輛平均等待時間。如圖6(a)所示,FCFS策略的車輛平均等待時間指標受不平衡車流影響最為明顯。當車輛密度超過500輛/h時,本文策略和Tabu控制策略性能基本相當,優于其他控制策略;當車輛密度超過1 600輛/h時,NDMC策略平均等待時間要低于其他策略。圖6(b)繪制了NDMC和FCFS控制策略在交叉路口南北方向和東西方向上的車輛平均等待時間對比情況。在NDMC控制策略中,南北方向車輛產生的平均等待時間高于東西方向車輛所產生平均等待時間,但仍然優于FCFS控制策略。

圖6 不平衡車流下車輛平均等待時間對比

綜上,為了對本文控制策略的執行效率進行評估,首先,評估了服從泊松分布不同λ取值的車輛排隊長度的變化情況,證明該策略有較強魯棒性;其次,與FCFS、Tabu和traffic-light控制策略在車輛完成數和車輛平均等待時間2個方面進行了對比評估,實驗結果表明:本文控制策略性能均優于上述控制策略。證明了本文路口控制策略的有效性與可靠性。

4 結論

本文基于最大團理論提出了一種自治交叉路口控制策略。首先,對車輛在交叉路口中行駛的時空軌跡進行建模;其次,根據車輛間的時空行駛軌跡建立車輛間的沖突關系模型,并將車輛間沖突關系抽象成圖;最后,通過在每個批處理周期內求解沖突關系圖中最大團的補集作為接受車輛預約請求集合,使得在單位時間內更多車輛能夠通過交叉路口,達到降低車輛平均延時和提高交叉路口吞吐量的目標。

與當前研究成果相比,本研究的工作主要體現在兩個方面:①為了降低自治交叉路口控制系統的計算復雜度,將路口區域進行網格化處理,同時將控制系統時間軸進行切分,劃分成等量批處理周期;②使用最大團理論來求解自治交叉路口控制問題,該方法自適應能力強,在不同車流量情況均能獲得較優的解,能使得更多車輛安全通過交叉路口。

本文是在系統運行正常和通信理想情況下進行相關研究,沒有考慮了車輛發生故障無法移動以及通信不暢等情況,因此未來工作設計一種在無線通信環境下仍能高效運行的路口控制策略,在更加趨近于真實交叉路口的交通環境中保證行車安全,提高自治交叉路口的通行效率。