無信號燈交叉路口智能車輛調度算法研究

謝彭輝,孫 寧,龐 堯,趙文騫,錢俊杰

(1.南京林業大學汽車與交通工程學院,江蘇 南京 210037;2.南京林業大學信息科學技術學院,江蘇 南京 210037)

0 引言

隨著無人駕駛技術的快速發展,智能車輛在無信號燈交叉路口的通行調度成為研究熱點[1-2]。智能車輛在交叉路口的通行效率與其通過速度、調度策略相關。因為交叉路口一般會限定最高通過速度,所以調度策略的優劣會直接影響車輛在交叉路口的通行效率和行駛安全。受傳感器范圍限制以及周圍復雜環境對電磁信號的阻擋,智能車輛無法感知交叉路口的全局信息,導致交叉路口的全局調度難以實現。這不僅降低了車輛的通行效率,還增加了交通事故的發生概率[3]。相關的調度方案主要分為集中式和分布式這2類。

集中式調度以全局最優為調度目標,由智能路基單元收集全局信息并進行算法處理,從而將調度策略發送至每個進入交叉路口的車輛[4]。

集中式車輛調度模式簡單,但對路基單元的算力要求較高,且系統可靠性差。分布式調度去除中心化,由智能車輛利用車載傳感器感知局部信息進行調度規劃,使每輛車在一定情況下承擔了一定的任務。這簡化了調度時需要處理的信息量[5],具有良好的應用前景。

吳偉等[6]提出了基于網格化基礎的交叉路口車輛調度優化模型,使用分支定界法獲得車輛最佳路徑。此方法中的模型簡明易懂,但屬于靜態算法,不適用于存在多車輛通過的路口調度場景。姜辰凱等[7]提出了改進的Dijkstra算法,可實現多個自動導引運輸車(automated guided vehicle,AGV)的動態路徑規劃。該算法能在最優路徑下避免沖突,具有較好的魯棒性。

本文提出了基于動態網格權值的調度算法。網格權值法是1種分布式車輛調度方案。其基本原理是:將交叉路口的沖突區看作1個網格圖;每個網格的權值不同;車輛根據網格權值選擇下一步進入的網格,以得出最優調度策略。基于動態網格權值的調度算法能夠有效解決沖突碰撞問題,為提高車輛在交叉路口的通過效率提供了可行思路。

1 系統模型

智能車輛能感知一定范圍內的信息,以獲取地理位置、瞬時車速、行駛方向角等。本文假定有1個無信號燈控制的網格化后的雙向六車道交叉路口[8],并定義網格區為車輛沖突區域。根據相關交通法律規定,車輛在進入沖突區后不得變換車道[9]。每個網格僅能容納1輛車。車輛在沖突區的前進方向只可以直行或以1°～90°轉彎,且車輛每次都行駛至每個網格的中心位置。每個網格都為正方形。權值設置如下。

①方向權值ε。本文設:車輛當前所處網格中心與終點網格中心的連線為標準線;車輛行駛方向(即車頭朝向)與基準線夾角為θ;ε=cosθ。θ越大,則ε越小。方向權值可以使車輛行駛路徑b向初始靜態最優路徑a逼近,并確保車輛不偏航。

②預警權值δ。車輛在直行或轉向至下個行進網格時:若下個網格已被其他車輛占用,則規定下個網格的δ為0.4(下個回合車輛已駛出該網格);若下個網格也同時被其他車輛選中為行進方格,則規定下個網格的δ為0.1;若下個網格未被其他車輛選中且未被占用,則規定下個網格的δ為0.8。

③轉向權值β。本文規定車輛在左側左轉、右側右轉、直行時的β分別為0.3、0.6、0.9。

本文根據得到的綜合權值ω=ε×δ×β,先對行駛進沖突區車輛的綜合權值進行實時更新,以得到可變的綜合權值;再根據綜合權值實時更新車輛的路徑,使車輛能盡快到達終點網格。

2 算法設計

2.1 底層算法邏輯設計

底層算法流程如圖1所示。

圖1 底層算法流程圖

2.2 算法實現過程

算法實現分為2個步驟,分別為尋徑和沖突調度。

2.2.1 尋徑

本文將車輛實體和運動背景以單元格實例化,并規定車輛每次只移動1個單元格。

本文跳出混合迭代貪婪算法(greedy algorithm,GA)[10-11]只在已有方案中尋找最優,而不能提供新方案的局限,以避免基于經驗選擇的貪婪思想的弊端。

本文假設路徑集P為網格中從源節點到目標節點所有路徑的集合。路徑集P分為幾類路徑子集:P1為只有1條邊的路徑;P2為只有2條邊的路徑;依次類推。因為每條邊的權值不同,所以P2中路徑的長度不一定比P1大。

貪婪選擇過程如下。現假設車輛A從網格13出發,終點為網格34。根據權值設置原則與縮短搜索半徑規則,以車輛A為主體進行首次貪婪性質選擇,得到最佳路徑序列為{13,20,27,34}。當車輛A運動至網格20時,車輛B直行也選中網格27為最佳路徑。這時,對車輛A、B進行沖突調度處理。假設處理結果為車輛B擁有27網格的優先行駛權,此時車輛A要到達終點方格,則需要作出對最佳路徑的更新。對27網格設為死權(無法選取),由此車輛開始進行第二次貪婪性質選擇,即網格20。此時擁有2條有向路線可作為首項元素進行加權選擇{21,26}。對于21→34、26→34這2條單源最短路徑的選取,則需要遍歷鄰接頂點,并比較得到1條或多條最短路徑。以上過程體現為:車輛在不斷地進行“貪婪選擇”與“位置移動”決策,直至車輛到達目標位置。其整體上呈現為GA在動態過程的遞推增強。

調度模型如圖2所示。

圖2 調度模型

圖2中:a為未經調度處理的車輛A行駛路線;b為經過調度處理的車輛A行駛路線;c點為車輛A、B未經調度處理的沖突點。

引申至當n輛車在網格中行駛時,上述情況在每輛車運動時都會發生,則需要不斷地對每輛車的最佳路徑作出實時動態處理,直至每輛車都擁有各自的尋優路徑為止。

本文采用一維數組α[v]={v0,v1,…,vn}來保存頂點到源頂點的路徑長度,并初始化路徑長度為無窮大。本文用一維數組α[s]={s0,s1,…,sn}來保存頂點所在最短路徑的前驅頂點,以便輸出路徑。本文使用1個數據結構來保證每次從未確定最短路徑的頂點中提取出路徑最短的頂點。

同時,為了避免單鄰域操作的重復貪婪搜索過程容易陷入相應鄰域結構的局部最優解,本文根據混合迭代GA[10]的思想,進一步對有潛力區域作更深入的檢索。檢索偽代碼如下。

Foreachv!=s: α[v]←∞,pred[v]←null;α[s]←0;

Creat an empty priority queue PQ;

Foreach v∈V:Insert(PQ,v,α[v]);

While(is-not-empty(PQ))

u←Del-Min(PQ); //提取局部優解

Foreach edge e =(u,v)leaving u: //局部優解重檢索

If(α[v]>α[u]+l)

Decrease-Key(PQ,v,α[u]+l)

α[v]←α[u]+l;

pred[v]←u;

本文通過對車輛運動的周圍臨界區作循環遍歷處理,根據所提出的權值規則初步求出優解,進一步根據優解的下一步擇徑作出有效判別,以實現混合迭代求徑并提取最優解。

基于以上分析,本文對需要對最佳路徑作出重新選擇的車輛進行循環,直到即將行駛的最佳路徑方格不存在沖突點為止。

2.2.2 沖突調度

本文構造1個車輛類,并在該類中設置屬性變量元素。屬性變量元素包括車輛的名稱編號、優先級、最佳路徑序列、最佳路徑序列的長度。沖突調度時規則的設置是依照車輛類內屬性變量依次作出優先選擇權判斷。

(1)優先運行原則。

①優先級。優先級高者通行。

②最佳路徑序列剩余量。剩余量少者通行。

③車輛名稱編號。美國信息交換標準代碼(American standard code for information intercharge,ASCII)小者通行。

本文對車輛進行實例化對象構造,創建沖突調度所需要使用到的各因子。因子包括優先級、最佳路徑序列、序列組長和名稱編號。本文封裝錄入方法成員函數和類外調度方法函數,并導入所有車輛屬性信息。

車輛沖突調度樣例如表1所示。

表1 車輛沖突調度樣例表

屬性比較順序為優先級>序列剩余量>ASCII。

(2)通行優先級比較流程。

①創建1個類數組array。在這樣1個數組中存儲著各車輛類與其屬性信息。

②以最佳路徑序列的第一項元素作為需求值,將需求值自小到大進行排序,使得存在沖突點的車輛在數組內以區間形式存儲。通過這樣的處理,可以得到1個以沖突點劃分區間的排序數組。

③對有沖突點的車輛元素,作出優先級比較處理,以此進一步篩選出擁有優先通行權的車輛。

④優先序列排序。

車輛交換排序的C++偽代碼如下。

for(i=0;i

{

for(j=0;j

{

if(j+1

swap(j+1,j)

}

}

⑤重復上述操作,進行ASCII的比較,即可得到數據處理結果。該結果是根據上述條件進行調度排序之后的結構數組。處理后的數組中,準確的表示應為array[0]中存儲著車輛A2的名稱編號、優先級、最佳序列及其長度。而在每次貪婪性質選擇時,并不需要關心整體的最佳序列,只需要了解最佳序列中存在的沖突點,并作出區塊分類。所以,以沖突點替換序列能更直觀地表現出經過上述排序之后的結果。

車輛調度排序處理結果如表2所示。

表2 車輛調度排序處理結果

經過以上數組處理之后,易得在每個沖突點的區塊之中,區塊的第一個位置存儲的就是該沖突點的最優先行駛車輛。例如:A2、A1、A6在沖突點1區塊之中;A4、A3、A5在沖突點4區塊之中。那么,A2與A4是在其對應的沖突點中最優先行駛的車輛。

底層指針初始采取雙指針處理。本文設置指針p1指向數組第一個元素、指針p2指向數組第二個元素。

底層指針初始化如圖3所示。

圖3 底層指針初始化示意圖

p2不斷往后對數組進行掃描,并校驗沖突點是否相等,同時需控制p2不要超過數組。p1與p2所指向的車輛的沖突點不一致時,返回p1所指向的車輛。該車輛就是該沖突區塊優先車輛。例如:p1指向類數組的第一個位置(A2);p2指向類數組的第二個位置(A1);p2不斷向后移動,直到p2指向數組的第四個位置(A4)時,p1的沖突點不為p2的沖突點,則返回p1所指向的車輛。由此完成1個沖突區塊的優先車輛提取。

在提取優先車輛后,p1指向p2所指向的車輛,而p2繼續往后進行數據掃描和校驗。

底層數據結構指針移動如圖4所示。

圖4 底層數據結構指針移動示意圖

指針移動的C++偽代碼如下。

if(p1.沖突點!=p2.沖突點)

p1=p2;

p2=car[i+1];

return p1車輛;

}

實現過程使用單層循環、雙指針、時間復雜度T(n)、空間復雜度O(n)。以此不斷重復上述操作,直到p2指針超出數組范圍。此時,指針返回p1所指向的車輛。至此,算法進程結束。

3 數據試驗

在算法運行過程中,本文取一次調度環節進行試驗。整體運作過程為:①數據導入;②加權求取最佳路徑;③沖突判斷并調度;④校驗無誤后數據結果傳輸至硬件層并開始運作。

此過程需循環執行步驟②和步驟③,直至得到無沖突的全局最優解。試驗在程序中導入15×15的網格,并輸入25組數據進行校驗。

參考圖2所示的6×6網格規律,每個網格由數字標號代表,則計算機內表示方法為:y=(數字標號/x軸長)+1;x=數字標號%x軸長。如網格127沖突點,即為(7,9)位置。

試驗根據2.2節作數據處理。數據分析結果如表3所示。由表3可知,沖突點{17,38,63,79,94,100,109,113,127,136}存在。本文使用C++(GDB/LLDB)對數據進行處理,并導出數據結果。得到的調度優先權結果為:在網格17處,B1擁有優先行駛權;在網格38處,B11擁有優先行駛權;在網格63處,B20擁有優先行駛權;在網格79處,C17擁有優先行駛權;在網格94處,B2擁有優先行駛權;在網格100處,B15擁有優先行駛權;在網格109處,A14擁有優先行駛權;在網格113處,C11擁有優先行駛權;在網格127處,A9擁有優先行駛權;在網格136處,B10擁有優先行駛權。本文可進一步得到調度后各車輛的調度路徑結果。

表3 數據分析結果

例如A10、B20存在著63(x=3,y=5)的沖突點。在作出調度判斷之后,B20具有此位置的優先選擇權。此時,A10對A20車輛做出避讓措施,并重新選擇了62(x=2,y=5)作為新的路徑網格。進行了上述的預警調度之后,即可以有效地規避最佳路徑的沖突選擇。通過如上數據導入試驗,可以得到智能車輛防撞的整體調度在軟件算法層的理論結構可行性。

4 結論

本文在劉庭瑋等[11]提出的基于經驗選擇的貪婪思想基礎上,對GA進行了動態增強。這著重體現在GA的貪婪選擇并不是在一次基于經驗選擇之后結束,而是伴隨著整個流程的運作過程不斷地進行經驗選擇,直到流程結束。本文對GA進行了試驗性嘗試并補充了對沖突車輛調度的方案,使動態尋徑與動態調度相結合,得到1套完整的車流運動控制方案。該方案為車輛高速移動場景下無信號燈交叉路口智能車輛的運行提供了良好的防撞調度措施。后續研究將優化賦值原則,以探討復雜情況下的權值分配方法。