無(wú)信號(hào)燈交叉路口智能車輛調(diào)度算法研究

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

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

0 引言

隨著無(wú)人駕駛技術(shù)的快速發(fā)展,智能車輛在無(wú)信號(hào)燈交叉路口的通行調(diào)度成為研究熱點(diǎn)[1-2]。智能車輛在交叉路口的通行效率與其通過速度、調(diào)度策略相關(guān)。因?yàn)榻徊媛房谝话銜?huì)限定最高通過速度,所以調(diào)度策略的優(yōu)劣會(huì)直接影響車輛在交叉路口的通行效率和行駛安全。受傳感器范圍限制以及周圍復(fù)雜環(huán)境對(duì)電磁信號(hào)的阻擋,智能車輛無(wú)法感知交叉路口的全局信息,導(dǎo)致交叉路口的全局調(diào)度難以實(shí)現(xiàn)。這不僅降低了車輛的通行效率,還增加了交通事故的發(fā)生概率[3]。相關(guān)的調(diào)度方案主要分為集中式和分布式這2類。

集中式調(diào)度以全局最優(yōu)為調(diào)度目標(biāo),由智能路基單元收集全局信息并進(jìn)行算法處理,從而將調(diào)度策略發(fā)送至每個(gè)進(jìn)入交叉路口的車輛[4]。

集中式車輛調(diào)度模式簡(jiǎn)單,但對(duì)路基單元的算力要求較高,且系統(tǒng)可靠性差。分布式調(diào)度去除中心化,由智能車輛利用車載傳感器感知局部信息進(jìn)行調(diào)度規(guī)劃,使每輛車在一定情況下承擔(dān)了一定的任務(wù)。這簡(jiǎn)化了調(diào)度時(shí)需要處理的信息量[5],具有良好的應(yīng)用前景。

吳偉等[6]提出了基于網(wǎng)格化基礎(chǔ)的交叉路口車輛調(diào)度優(yōu)化模型,使用分支定界法獲得車輛最佳路徑。此方法中的模型簡(jiǎn)明易懂,但屬于靜態(tài)算法,不適用于存在多車輛通過的路口調(diào)度場(chǎng)景。姜辰凱等[7]提出了改進(jìn)的Dijkstra算法,可實(shí)現(xiàn)多個(gè)自動(dòng)導(dǎo)引運(yùn)輸車(automated guided vehicle,AGV)的動(dòng)態(tài)路徑規(guī)劃。該算法能在最優(yōu)路徑下避免沖突,具有較好的魯棒性。

本文提出了基于動(dòng)態(tài)網(wǎng)格權(quán)值的調(diào)度算法。網(wǎng)格權(quán)值法是1種分布式車輛調(diào)度方案。其基本原理是:將交叉路口的沖突區(qū)看作1個(gè)網(wǎng)格圖;每個(gè)網(wǎng)格的權(quán)值不同;車輛根據(jù)網(wǎng)格權(quán)值選擇下一步進(jìn)入的網(wǎng)格,以得出最優(yōu)調(diào)度策略。基于動(dòng)態(tài)網(wǎng)格權(quán)值的調(diào)度算法能夠有效解決沖突碰撞問題,為提高車輛在交叉路口的通過效率提供了可行思路。

1 系統(tǒng)模型

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

①方向權(quán)值ε。本文設(shè):車輛當(dāng)前所處網(wǎng)格中心與終點(diǎn)網(wǎng)格中心的連線為標(biāo)準(zhǔn)線;車輛行駛方向(即車頭朝向)與基準(zhǔn)線夾角為θ;ε=cosθ。θ越大,則ε越小。方向權(quán)值可以使車輛行駛路徑b向初始靜態(tài)最優(yōu)路徑a逼近,并確保車輛不偏航。

②預(yù)警權(quán)值δ。車輛在直行或轉(zhuǎn)向至下個(gè)行進(jìn)網(wǎng)格時(shí):若下個(gè)網(wǎng)格已被其他車輛占用,則規(guī)定下個(gè)網(wǎng)格的δ為0.4(下個(gè)回合車輛已駛出該網(wǎng)格);若下個(gè)網(wǎng)格也同時(shí)被其他車輛選中為行進(jìn)方格,則規(guī)定下個(gè)網(wǎng)格的δ為0.1;若下個(gè)網(wǎng)格未被其他車輛選中且未被占用,則規(guī)定下個(gè)網(wǎng)格的δ為0.8。

③轉(zhuǎn)向權(quán)值β。本文規(guī)定車輛在左側(cè)左轉(zhuǎn)、右側(cè)右轉(zhuǎn)、直行時(shí)的β分別為0.3、0.6、0.9。

本文根據(jù)得到的綜合權(quán)值ω=ε×δ×β,先對(duì)行駛進(jìn)沖突區(qū)車輛的綜合權(quán)值進(jìn)行實(shí)時(shí)更新,以得到可變的綜合權(quán)值;再根據(jù)綜合權(quán)值實(shí)時(shí)更新車輛的路徑,使車輛能盡快到達(dá)終點(diǎn)網(wǎng)格。

2 算法設(shè)計(jì)

2.1 底層算法邏輯設(shè)計(jì)

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

圖1 底層算法流程圖

2.2 算法實(shí)現(xiàn)過程

算法實(shí)現(xiàn)分為2個(gè)步驟,分別為尋徑和沖突調(diào)度。

2.2.1 尋徑

本文將車輛實(shí)體和運(yùn)動(dòng)背景以單元格實(shí)例化,并規(guī)定車輛每次只移動(dòng)1個(gè)單元格。

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

本文假設(shè)路徑集P為網(wǎng)格中從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)所有路徑的集合。路徑集P分為幾類路徑子集:P1為只有1條邊的路徑;P2為只有2條邊的路徑;依次類推。因?yàn)槊織l邊的權(quán)值不同,所以P2中路徑的長(zhǎng)度不一定比P1大。

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

調(diào)度模型如圖2所示。

圖2 調(diào)度模型

圖2中:a為未經(jīng)調(diào)度處理的車輛A行駛路線;b為經(jīng)過調(diào)度處理的車輛A行駛路線;c點(diǎn)為車輛A、B未經(jīng)調(diào)度處理的沖突點(diǎn)。

引申至當(dāng)n輛車在網(wǎng)格中行駛時(shí),上述情況在每輛車運(yùn)動(dòng)時(shí)都會(huì)發(fā)生,則需要不斷地對(duì)每輛車的最佳路徑作出實(shí)時(shí)動(dòng)態(tài)處理,直至每輛車都擁有各自的尋優(yōu)路徑為止。

本文采用一維數(shù)組α[v]={v0,v1,…,vn}來(lái)保存頂點(diǎn)到源頂點(diǎn)的路徑長(zhǎng)度,并初始化路徑長(zhǎng)度為無(wú)窮大。本文用一維數(shù)組α[s]={s0,s1,…,sn}來(lái)保存頂點(diǎn)所在最短路徑的前驅(qū)頂點(diǎn),以便輸出路徑。本文使用1個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)保證每次從未確定最短路徑的頂點(diǎn)中提取出路徑最短的頂點(diǎn)。

同時(shí),為了避免單鄰域操作的重復(fù)貪婪搜索過程容易陷入相應(yīng)鄰域結(jié)構(gòu)的局部最優(yōu)解,本文根據(jù)混合迭代GA[10]的思想,進(jìn)一步對(duì)有潛力區(qū)域作更深入的檢索。檢索偽代碼如下。

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); //提取局部?jī)?yōu)解

Foreach edge e =(u,v)leaving u: //局部?jī)?yōu)解重檢索

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

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

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

pred[v]←u;

本文通過對(duì)車輛運(yùn)動(dòng)的周圍臨界區(qū)作循環(huán)遍歷處理,根據(jù)所提出的權(quán)值規(guī)則初步求出優(yōu)解,進(jìn)一步根據(jù)優(yōu)解的下一步擇徑作出有效判別,以實(shí)現(xiàn)混合迭代求徑并提取最優(yōu)解。

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

2.2.2 沖突調(diào)度

本文構(gòu)造1個(gè)車輛類,并在該類中設(shè)置屬性變量元素。屬性變量元素包括車輛的名稱編號(hào)、優(yōu)先級(jí)、最佳路徑序列、最佳路徑序列的長(zhǎng)度。沖突調(diào)度時(shí)規(guī)則的設(shè)置是依照車輛類內(nèi)屬性變量依次作出優(yōu)先選擇權(quán)判斷。

(1)優(yōu)先運(yùn)行原則。

①優(yōu)先級(jí)。優(yōu)先級(jí)高者通行。

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

③車輛名稱編號(hào)。美國(guó)信息交換標(biāo)準(zhǔn)代碼(American standard code for information intercharge,ASCII)小者通行。

本文對(duì)車輛進(jìn)行實(shí)例化對(duì)象構(gòu)造,創(chuàng)建沖突調(diào)度所需要使用到的各因子。因子包括優(yōu)先級(jí)、最佳路徑序列、序列組長(zhǎng)和名稱編號(hào)。本文封裝錄入方法成員函數(shù)和類外調(diào)度方法函數(shù),并導(dǎo)入所有車輛屬性信息。

車輛沖突調(diào)度樣例如表1所示。

表1 車輛沖突調(diào)度樣例表

屬性比較順序?yàn)閮?yōu)先級(jí)>序列剩余量>ASCII。

(2)通行優(yōu)先級(jí)比較流程。

①創(chuàng)建1個(gè)類數(shù)組array。在這樣1個(gè)數(shù)組中存儲(chǔ)著各車輛類與其屬性信息。

②以最佳路徑序列的第一項(xiàng)元素作為需求值,將需求值自小到大進(jìn)行排序,使得存在沖突點(diǎn)的車輛在數(shù)組內(nèi)以區(qū)間形式存儲(chǔ)。通過這樣的處理,可以得到1個(gè)以沖突點(diǎn)劃分區(qū)間的排序數(shù)組。

③對(duì)有沖突點(diǎn)的車輛元素,作出優(yōu)先級(jí)比較處理,以此進(jìn)一步篩選出擁有優(yōu)先通行權(quán)的車輛。

④優(yōu)先序列排序。

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

for(i=0;i

{

for(j=0;j

{

if(j+1

swap(j+1,j)

}

}

⑤重復(fù)上述操作,進(jìn)行ASCII的比較,即可得到數(shù)據(jù)處理結(jié)果。該結(jié)果是根據(jù)上述條件進(jìn)行調(diào)度排序之后的結(jié)構(gòu)數(shù)組。處理后的數(shù)組中,準(zhǔn)確的表示應(yīng)為array[0]中存儲(chǔ)著車輛A2的名稱編號(hào)、優(yōu)先級(jí)、最佳序列及其長(zhǎng)度。而在每次貪婪性質(zhì)選擇時(shí),并不需要關(guān)心整體的最佳序列,只需要了解最佳序列中存在的沖突點(diǎn),并作出區(qū)塊分類。所以,以沖突點(diǎn)替換序列能更直觀地表現(xiàn)出經(jīng)過上述排序之后的結(jié)果。

車輛調(diào)度排序處理結(jié)果如表2所示。

表2 車輛調(diào)度排序處理結(jié)果

經(jīng)過以上數(shù)組處理之后,易得在每個(gè)沖突點(diǎn)的區(qū)塊之中,區(qū)塊的第一個(gè)位置存儲(chǔ)的就是該沖突點(diǎn)的最優(yōu)先行駛車輛。例如:A2、A1、A6在沖突點(diǎn)1區(qū)塊之中;A4、A3、A5在沖突點(diǎn)4區(qū)塊之中。那么,A2與A4是在其對(duì)應(yīng)的沖突點(diǎn)中最優(yōu)先行駛的車輛。

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

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

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

p2不斷往后對(duì)數(shù)組進(jìn)行掃描,并校驗(yàn)沖突點(diǎn)是否相等,同時(shí)需控制p2不要超過數(shù)組。p1與p2所指向的車輛的沖突點(diǎn)不一致時(shí),返回p1所指向的車輛。該車輛就是該沖突區(qū)塊優(yōu)先車輛。例如:p1指向類數(shù)組的第一個(gè)位置(A2);p2指向類數(shù)組的第二個(gè)位置(A1);p2不斷向后移動(dòng),直到p2指向數(shù)組的第四個(gè)位置(A4)時(shí),p1的沖突點(diǎn)不為p2的沖突點(diǎn),則返回p1所指向的車輛。由此完成1個(gè)沖突區(qū)塊的優(yōu)先車輛提取。

在提取優(yōu)先車輛后,p1指向p2所指向的車輛,而p2繼續(xù)往后進(jìn)行數(shù)據(jù)掃描和校驗(yàn)。

底層數(shù)據(jù)結(jié)構(gòu)指針移動(dòng)如圖4所示。

圖4 底層數(shù)據(jù)結(jié)構(gòu)指針移動(dòng)示意圖

指針移動(dòng)的C++偽代碼如下。

if(p1.沖突點(diǎn)!=p2.沖突點(diǎn))

p1=p2;

p2=car[i+1];

return p1車輛;

}

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

3 數(shù)據(jù)試驗(yàn)

在算法運(yùn)行過程中,本文取一次調(diào)度環(huán)節(jié)進(jìn)行試驗(yàn)。整體運(yùn)作過程為:①數(shù)據(jù)導(dǎo)入;②加權(quán)求取最佳路徑;③沖突判斷并調(diào)度;④校驗(yàn)無(wú)誤后數(shù)據(jù)結(jié)果傳輸至硬件層并開始運(yùn)作。

此過程需循環(huán)執(zhí)行步驟②和步驟③,直至得到無(wú)沖突的全局最優(yōu)解。試驗(yàn)在程序中導(dǎo)入15×15的網(wǎng)格,并輸入25組數(shù)據(jù)進(jìn)行校驗(yàn)。

參考圖2所示的6×6網(wǎng)格規(guī)律,每個(gè)網(wǎng)格由數(shù)字標(biāo)號(hào)代表,則計(jì)算機(jī)內(nèi)表示方法為:y=(數(shù)字標(biāo)號(hào)/x軸長(zhǎng))+1;x=數(shù)字標(biāo)號(hào)%x軸長(zhǎng)。如網(wǎng)格127沖突點(diǎn),即為(7,9)位置。

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

表3 數(shù)據(jù)分析結(jié)果

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

4 結(jié)論

本文在劉庭瑋等[11]提出的基于經(jīng)驗(yàn)選擇的貪婪思想基礎(chǔ)上,對(duì)GA進(jìn)行了動(dòng)態(tài)增強(qiáng)。這著重體現(xiàn)在GA的貪婪選擇并不是在一次基于經(jīng)驗(yàn)選擇之后結(jié)束,而是伴隨著整個(gè)流程的運(yùn)作過程不斷地進(jìn)行經(jīng)驗(yàn)選擇,直到流程結(jié)束。本文對(duì)GA進(jìn)行了試驗(yàn)性嘗試并補(bǔ)充了對(duì)沖突車輛調(diào)度的方案,使動(dòng)態(tài)尋徑與動(dòng)態(tài)調(diào)度相結(jié)合,得到1套完整的車流運(yùn)動(dòng)控制方案。該方案為車輛高速移動(dòng)場(chǎng)景下無(wú)信號(hào)燈交叉路口智能車輛的運(yùn)行提供了良好的防撞調(diào)度措施。后續(xù)研究將優(yōu)化賦值原則,以探討復(fù)雜情況下的權(quán)值分配方法。