謝博宇，李茂青，岳麗麗，陳啟香

1.蘭州交通大學 自動化與電氣工程學院，蘭州 730070

2.寶雞文理學院 電子電氣工程學院，陜西 寶雞 721000

1 引言

隨著經濟、科技的不斷發(fā)展和進步，智能交通系統(tǒng)的發(fā)展為路徑規(guī)劃問題中道路交通信息的獲取提供了新的思路和方法。路徑規(guī)劃問題是根據(jù)出行需求，在車輛導航系統(tǒng)中根據(jù)OD點信息，系統(tǒng)規(guī)劃出一條最佳的路徑。

路徑規(guī)劃問題首先要獲得道路信息，然后根據(jù)道路信息使用不同的算法得到出行時間最少的路徑。在得到每條道路的行駛時間后，選擇一種合適的算法來搜尋出一條最優(yōu)路徑。在當前的研究算法中，常用的有Dijkstra算法、A*算法、蟻群算法等。文獻[1-2]建立新的模型，如曹慧等[1]建立了隨機時變路網環(huán)境下穩(wěn)健路徑模型。文獻[3-5]改進了算法，如Zhang 等[3]首先采用動態(tài)鄰接節(jié)點關系矩陣和動態(tài)鄰接節(jié)點權重矩陣改進Dijkstra 算法。另外，Kammoun 等[6]提出了基于蟻群行為的自適應車輛導航系統(tǒng)，提出一種基于多智能體的體系結構，通過改進的蟻群算法規(guī)劃出一條最佳的路徑。

在最新的成果當中，開始提出在車聯(lián)網環(huán)境下的路徑規(guī)劃問題。通過路旁檢測設備獲取到的信息更準確、更實時，將這種方式稱之為路測工作模式。王龐偉等[7]提出基于車路協(xié)同系統(tǒng)的區(qū)域實時路徑規(guī)劃，根據(jù)在交叉口前排隊車輛的數(shù)目，按照排隊車輛消散時間來計算時間。但是該方法只考慮信號燈處于紅燈狀態(tài)時的情況。而沒有考慮多次排隊情況，以及車輛左轉和右轉情況。吳黎兵等[8]提出了一種車聯(lián)網環(huán)境下的城市車輛協(xié)同選路方法，根據(jù)車輛到達路口時道路的狀態(tài)來分別計算每條路上的權值，以此來計算出一條最佳的路徑。該方法只給出車輛直行時的計算公式，而且沒有考慮不同車道的交叉口延時時間。盡管目前國家提倡智能交通系統(tǒng)的建設和使用，未來也會大規(guī)模建設。但是由于目前大部分城市還沒有普及智能交通系統(tǒng)或者由于設備故障或者設備之間通信信號中斷等情況而導致接收不到道路信息。

在無人車避障繞行的路徑規(guī)劃研究中，為解決無人車環(huán)境感知有限的問題，使無人機-無人車協(xié)同工作來解決，它是通過無人機的大范圍環(huán)境感知能力為無人車提供導航信息[9-10]。席阿行等[11]利用SURF 算法建立了UGV 可執(zhí)行的地圖，提出優(yōu)化的A*算法優(yōu)化了所有的拐點，實驗證明可以有效地避開障礙物，找到一條全局路徑規(guī)劃。胡秋霞等[12]以無人機與無人車協(xié)同為背景，提出一種改進的人工勢場法，解決了局部極小點問題。杜仕剛等[13]針對無人機拍攝遮擋問題，使用圖像拼接技術構建全局地圖，使用車輛傳感器感知環(huán)境構建局部地圖，最后采用A*算法計算出路徑。在文獻[11-15]以及現(xiàn)有無人機與無人車協(xié)同路徑規(guī)劃算法中，多數(shù)研究是理論基礎研究，它們能夠在空曠地上避開障礙物，自行規(guī)劃出一條從起點到目標點的最優(yōu)路徑。而現(xiàn)有文獻很少應用在道路交通中，即根據(jù)城市中的可供行駛道路選擇一條使駕駛員能夠最快到達目的地的道路。

王云鵬等[14]在專利中提出一種基于無人機感知的無人駕駛車輛路徑規(guī)劃方法，主要是通過無人機獲取路網模型，根據(jù)無人飛行器的GPS信息，來進行匹配運算，得到無人車的位置。應用C 空間算法和Dijstra 算法相結合，該專利提出一種在電子地圖中選擇一條權值為道路長度和車輛占道比相結合最小的一條路徑的思路，它沒有考慮整體時間用時情況，也沒說明如何實施。同時根據(jù)全局規(guī)劃選出一條最短路后，使用人工勢場法避開道路上其他車輛。

由此提出無人機-智能車隊協(xié)同系統(tǒng)，該系統(tǒng)有兩種計算路徑的模式，即路測模式和機測模式。它們分別利用路旁檢測設備或無人機檢測的信息進行路徑規(guī)劃。在兩方面進行了改進：一是在路測模式當中，根據(jù)從智能交通系統(tǒng)中獲得到的排隊長度和信號燈的顯示，改進文獻[9-10]為考慮車輛到達路口時多種信號燈顯示情況、在不同車道行駛以及多次排隊情況，計算出一條行駛時間最短的路徑；二是提出機測模式，由無人機拍攝視頻，經過圖像處理得到在交叉口前的車輛排隊長度，并改進文獻[16]根據(jù)道路長度和車輛占道比來選擇路徑的思路，同時考慮車輛在不同車道上行駛以及多次排隊情況計算出一條行駛時間最短的路徑。

2 無人機-智能車隊協(xié)同系統(tǒng)

無人機-智能車隊協(xié)同系統(tǒng)是基于車輛導航系統(tǒng)所改進的，該系統(tǒng)將車輛導航系統(tǒng)和無人機相結合。如圖1所示為系統(tǒng)的總體示意圖。系統(tǒng)分為4個子系統(tǒng)，即智能車隊、路旁設備、交通指揮中心以及無人機子系統(tǒng)。

如圖2 所示為系統(tǒng)內部結構框圖。在無人機-智能車隊協(xié)同系統(tǒng)中，車輛有兩種計算路徑模式。路測模式是由路旁設備采集信息，并經過交通指揮中心處理最終發(fā)給車輛。在該模式中，車輛根據(jù)在交叉口前的排隊長隊以及進入道路時的交通燈顯示來計算時間。機測模式是車輛和無人機協(xié)同工作。由無人機拍攝視頻，并將視頻傳遞給車輛，由車輛經過圖像處理得到信息。同時由車輛控制無人機，包括飛行路線、飛行姿態(tài)、無人機上的攝像裝置。在此模式中，目前只根據(jù)排隊長度來計算時間。

圖2 系統(tǒng)內部結構框圖

如圖3所示為車輛從接收信息、傳遞信息到規(guī)劃最優(yōu)路徑的系統(tǒng)工作流程圖。

車輛進入某路段時，默認模式是路測模式。系統(tǒng)會判斷是否能通過路旁設備接收到至汽車位置相鄰2 個交叉口及路段上的信息，當接收不到時，提示“路測模式無法工作”。系統(tǒng)會進入機測模式，此時車輛和無人機協(xié)同工作。車輛派遣無人機去道路上拍攝視頻并傳回車輛對視頻做處理得到需要的信息。在該算法中，考慮到無人機飛行時間、圖像采集及道路背景識別的時間，無人機會比車輛提前飛行至目的地進行拍攝。無人機可以拍攝出方圓800 m范圍，包含4個交叉口的范圍，即車輛每走兩個交叉路口會計算接下來所走道路的時間，規(guī)劃一次路徑。當車輛拍攝完一個路口的視頻后，會繼續(xù)往前拍攝視頻，來保證數(shù)據(jù)的實時性要求。

圖3 系統(tǒng)工作流程

由于無人機飛行時間一般在20～30 min，針對發(fā)生長時間工作電量不足的現(xiàn)象，設置兩架無人機，一臺主用一臺備用，同時在車上設置充電裝置，無人機可隨時充電。如果無人機由于信號遮擋或者通信距離過長導致無人機丟失信號。通過在備用無人機上架設信號中繼設備，在丟失信號附近區(qū)域飛行，通過信號中繼設備實現(xiàn)無人機與車輛之間信號實時傳輸。對于特殊情況，如無人機拍攝完成準備返航時突發(fā)事故等導致該區(qū)域交通狀態(tài)突發(fā)變化，無人機需要重新采集數(shù)據(jù)進行路徑規(guī)劃，然后返航。

2.1 智能車隊

在智能車隊中，車車之間要有車車協(xié)同控制，同時要保持隊列行駛。在車隊中只有領航者才可以接收到無人機發(fā)來的視頻，其余跟隨者由領航者傳輸數(shù)據(jù)。在機測模式中，無人機將拍攝的視頻通過無線通信模塊傳輸?shù)綀D像處理模塊進行圖像處理，并將處理后的數(shù)據(jù)再次通過通信模塊傳輸?shù)铰窂揭?guī)劃模塊進行路徑規(guī)劃。車輛會根據(jù)接收到的無人機信息通過無人機控制模塊控制無人機飛行，包括飛行路線、飛行姿態(tài)、無人機上的攝像裝置。

2.2 路旁設備和交通指揮中心

路旁設備一般固定安裝在道路旁，用于采集交通信息。一般有環(huán)型感應線圈檢測器、超聲波檢測器、紅外線檢測器、微波雷達檢測器、視頻圖像車輛檢測器這幾種。由于所研究內容，需要得到在交叉口前的排隊長度信息，對比幾種檢測器，使用視頻圖像車輛檢測器進行檢測。

交通指揮中心用于接收路旁設備采集到的信息，并將信息處理成需要的數(shù)據(jù)。將處理后的視頻通過無線傳輸發(fā)送到車輛上用于路徑規(guī)劃。

2.3 無人機系統(tǒng)

無人機系統(tǒng)是由若干個相互聯(lián)系、作用、依存的組成部分結合而成的且具有完成指定任務的有機整體。在無人機系統(tǒng)中共有4 個分系統(tǒng)，即飛行器平臺分系統(tǒng)、測控與信息傳輸分系統(tǒng)、無人機定位信息分系統(tǒng)以及圖像采集分系統(tǒng)。在該系統(tǒng)中，圖像采集模塊用于對道路視頻進行拍攝，并通過機載信息傳輸模塊將視頻傳輸至智能車隊中的領航者。同時，車輛會根據(jù)無人機飛行狀態(tài)通過地面信息傳輸模塊將控制命令傳輸給無人機。

3 基于無人機-智能車隊協(xié)同系統(tǒng)的路徑規(guī)劃方法

如圖4 所示，為城市道路示意圖，研究對象為最常見的6車道路段，包含直行、左轉、右轉道。

圖4 城市道路示意圖

交叉口選用四相位信號設計方案，即每個進口方向都設置左轉專用車道，同時右轉路口為自由右轉。如圖5所示為交叉口的相位放行示意圖。

圖5 四相位放行示意圖

在此設計方案中，把一個信號周期分為3 個階段，即綠燈直行、綠燈左轉和紅燈，忽略黃燈時間。周期為C=tSL+tLL +tH，其中綠燈直行所占時間為tSL，綠燈左轉所占時間為tLL，紅燈所占時間為tH。右轉為自由右轉，所占時間為tRL =C。為方便閱讀，將主要變量列出，如表1所示。

表1 變量含義列表

基于所提出的路徑規(guī)劃方法，需要經過獲取信息、計算路阻權值、規(guī)劃最優(yōu)路徑3個步驟。獲取信息方式前文已介紹，現(xiàn)介紹后兩個步驟。

3.1 道路權值的計算

3.1.1 交叉口前運動狀態(tài)分析

車輛從不同車道由靜止到通過交叉口，所需時間有不同的計算結果。

車輛在交叉口行駛的最大速度為vi。根據(jù)某省道路交通管理條例實施辦法中第三十條關于車輛通過交叉路口時的規(guī)定：在有交通信號或交通標志控制的交叉路口，機動車時速不準超過30 km/h。故假設車輛在交叉口行駛速度為30 km/h（8.33 m/s），為計算方便，將此值設為8 m/s，即vi=8 m/s。

車輛在交叉口前從啟動到通過交叉口，運動過程是先從零做勻加速運動，加速到vi，即8 m/s。然后以8 m/s的速度做勻速運動。但是在右轉道，若使用變速運動計算，在計算權值時計算過程過于繁雜，故將變速運動近似為勻速運動。假設路口距離為30 m，右轉時通過一半路口，即15 m。則車輛通過一個交叉口時間約為3 s，故勻速度約為15/3=5 m/s。

由于右轉路口為自由右轉，在計算時為符合實際道路情形，需要考慮禮讓行人的情形，將行人所造成的阻礙通過時間設為tp。如圖6所示，為車輛右轉時等待行人情景。假設車輛以東西方向行駛，車輛等待行人分為兩種情形，情形一信號燈處于綠燈直行和左轉這段時間內，車輛需要等待時間tp1；情形二信號燈處于紅燈狀態(tài)，車輛右轉需要等待時間tp2后才可以繼續(xù)行駛。有研究指出駕駛員主觀合理等待時間約為16 s[15]。

圖6 車輛右轉時等待行人情景

3.1.2 計算關鍵值

（1）計算sS、sL、sR，這三個變量分別是直行、左轉、右轉時可通過最遠排隊車輛到交叉口的距離，這個值用于劃分車輛的排隊次數(shù)。

①sS和sL

由3.1.1 小節(jié)知車輛在直行和左轉道時，先做加速運動后做勻速運動，故sS、sL計算過程為這兩部分的距離之和。由vi=v0+at=8 可知勻加速運動時間為t加=距離為勻速運動時間為則直行時可通過最遠排隊車輛到交叉口的距離sS為：

左轉時可通過最遠排隊車輛到交叉口的距離sL為：

②sR

由圖6 所示的車輛右轉時等待行人情景可知，車輛需要等待兩個行人時間，可將一個周期分為4 個時間段。即等待tp1、車輛行駛、等待tp2、車輛行駛。sR的值因此情況復雜，為省略篇幅，在此不詳細介紹，具體見后文。

（2）計算車輛在交叉口前從停止到通過交叉口的時間，即交叉口延誤時間。同理按照不同車道劃分，依據(jù)3.1.1節(jié)來計算。直行和左轉時間為：

右轉時間為：

3.1.3 權值計算

將權值設為車輛從進入道路到分別從直行道、左轉道、右轉道離開的通過時間，即ts,tl,tr。

由前文介紹，系統(tǒng)有機測和路測兩種計算模式。當全部使用路旁設備得到信息時，能夠得到車輛抵達路口時的信號顯示時刻t0和在交叉口前的排隊長度d。當使用無人機獲取信息時，目前僅能夠得到排隊長度d。t0值計算公式如下。

計算車輛抵達路口時的信號顯示時刻t0：

其中是車輛進入道路時的信號顯示時刻，為前一段路所行駛的時間。由于t0的值在一個周期之內，故需和周期C取余。

當僅使用無人機獲取信息時，在公式中假設t0=0。

根據(jù)在交叉口前一個進口的直行、左轉、右轉三車道，把在交叉口前的排隊長度分別記為dS、dL、dR。

計算從進入一條道路到離開交叉口的時間分為以下兩個步驟。

步驟1得到所需要的數(shù)據(jù)。包括車輛抵達路口時的信號顯示時刻t0和在交叉口前的排隊長度d。

步驟2計算ts、tl、tr。首先根據(jù)t0值進行劃分，判斷此時車輛處于的時刻。接下來根據(jù)車輛到達交叉口的時間來劃分區(qū)間，選擇計算公式。

1）從直行道離開的通過時間ts

（1）0 ≤t0＜tSG

① 0 ≤dS ＜sS

注1由于公式冗長，為方便排版，將公式中C的倍數(shù)，比如mC寫為Cm,(m+1)C寫為Cm+1，全文公式同理。

②n?sS≤dS ＜(n+1)?sS(n=1,2,3,…)

2）從左轉道離開的通過時間tl

3）從右轉道離開的通過時間tr

由于車輛需要等待兩個行人時間，故將一個周期分為4 個時間段。在每個時間段內dR的取值范圍均不同，即車輛排隊次數(shù)的計算公式不同。由于篇幅限制，將每個時間段的計算順序給出。

經過上述步驟即可得到道路權值。

3.2 道路模型

由于車輛在交叉口行駛時，需要考慮直行、左轉、右轉三種情形，一般研究提出的路網模型反映不出車輛左轉、右轉的情形。同時，還要能夠表示出交叉口的轉向限制、單向交通、掉頭等情況。故使用對偶圖法來建立路網的數(shù)據(jù)模型，其實質是將基于節(jié)點的圖轉化為基于邊的圖。如圖7（a）所示為一簡單的十字路口，圖7（b）是該道路的節(jié)點-路段表示，圖7（c）是該道路的路段-鏈表示。

圖7 路網模型

3.3 最優(yōu)路徑選取

根據(jù)計算出來的權值，經過計算即可得到最優(yōu)路徑。根據(jù)3.1 節(jié)所述的方法得到權值后，使用迪杰斯特拉（Dijkstra）算法即可規(guī)劃出一條最優(yōu)的路徑。

4 仿真分析

4.1 仿真場景設置

如圖8所示，用一個簡單路網來闡述算法的實現(xiàn)過程。

此路網是由9 個交叉口，6 條主干路構成的12 條雙向6車道。把每個交叉口從①～⑨進行標號，設一對起屹點，記為OD。算例設置如下：

（1）每條道路的長度如圖8中標記所示。假設交叉口長度相等，為li=40 m。

圖8 算例路網

（2）交叉口信號配時。表2為所選區(qū)域每個交叉口的信號配時，每個交叉口均為四顯示。

表2 信號交叉口信號配時 s

（3）車輛加速度a。表3所示為不同類型轎車動力參數(shù)，表中分別為最高車速、從0 加速到100 km/h 的時間以及加速度。

表3 不同類型轎車動力參數(shù)

由表3可知車輛加速度在2～4 m/s2之間，為均衡不同車輛的類型，取加速度a=3 m/s2。

（4）道路最高速度。表4 為《城市道路工程設計規(guī)范（2016年修訂版）》中規(guī)定的各級道路的設計速度，由此確定道路的速度。

表4 各級道路的設計速度

示例道路均為主干路，故由表4可得道路設計速度為60 km/h、50 km/h、40 km/h，為方便計算，選取道路速度v=50 km/h。

4.2 不同場景下的應用

首先將舉例城市道路轉換為道路數(shù)據(jù)模型。其次假設工作模式為路測模式，即信息完全由路旁設備獲得，根據(jù)不同場景下的路況進行仿真。假設由路旁設備得到某時刻的交叉口信號顯示已知，根據(jù)該例起屹點行駛方向設置。在南北方向，路口①68 s，②34 s，③76 s，⑤ 45 s，⑥67 s，⑧32 s，⑨24 s；東西方向，路口④40 s，⑤ 39 s，⑥ 12 s，⑦ 52 s，⑧ 47 s，⑨ 64 s。

然后通過設置不同的排隊長度來實現(xiàn)不同場景下的仿真。

（1）道路狀況良好，不存在擁堵情況

在交叉口前均設置很少的排隊車輛，來實現(xiàn)仿真。具體數(shù)據(jù)為，在每條道路前的直行車道排隊長度分別為：10、35、20、17、18、17、25、34、15、19、14、26、24、23、27、23、15、34、15、35、18、21、35、16、10、0 m；左轉車道排隊長度分別為：28、20、13、16、25、13、24、22、45、22、23、22、10、12、14、14、28、20、23、18、12、12、13、14、0、0 m；右轉車道排隊長度分別為：10、25、10、10、13、10、24、34、12、32、24、58、56、34、30、23、42、10、45、50、29、50、76、87、0、0 m。仿真結果見表5。

表5 不存在擁堵情況下的路線結果

由圖8所知，在表5中，序號1、2、6三條路線行駛過程當中會經歷3 個直行路口、1 個左轉路口、1 個右轉路口；序號2、3、4 三條路線行駛過程當中會經歷1 個直行路口、2個左轉路口、2個右轉路口。由表5可以得出，車輛在行駛過程中，遇到左轉路口少的情況下，行駛時間會變短。當左轉路口一樣多的情況下，可以很好地找出最短的一條路徑。

（2）道路狀況很差，全部路段均存在擁堵情況

由《交通工程學》建議的服務水平分級標準中車輛排隊長度＞100 m，即為擁堵路段。故在每條道路前的排隊長度具體數(shù)據(jù)為，直行車道：200、510、240、395、310、275、435、244、409、319、294、457、324、356、352、232、386、244、326、254、218、450、245、430、30、0 m；左轉車道：230、288、290、185、273、245、276、232、341、186、185、228、216、229、330、199、258、231、283、148、149、380、216、294、30、0 m；右轉車道：195、208、269、254、208、178、202、169、219、170、170、259、209、238、214、175、202、163、199、157、181、340、178、227、25、0 m。仿真結果見表6。

由上文得出遇到左轉少的情況，行駛時間會變短。但是在表6 中，可以看出路線6 的時間會由第一變?yōu)榈诹?，這是由在交叉口前的排隊車輛數(shù)所決定的。其選擇路線的結果如圖8所示，在圖中由紅色線表示。

表6 大量在擁堵情況下的路線結果

（3）在某些直行路口有大量排隊車輛

假設當直行道路存在大量排隊的車輛，所提算法可以繞過這些排隊長度很長的路口。具體數(shù)據(jù)為，在每條道路前的直行車道排隊長度分別為：100、350、100、274、50、175、435、344、215、219、214、186、224、223、352、232、300、344、153、354、318、241、345、216、21、0 m；左轉車道排隊長度分別為：232、288、93、185、34、248、100、132、153、180、180、142、104、123、200、200、58、233、223、153、153、212、213、194、21、0 m；右轉車道排隊長度分別為：195、258、30、187、67、180、160、170、104、102、171、58、156、195、100、178、142、120、145、150、129、150、176、187、20、0 m。仿真結果見表7。

表7 在某些直行路口有大量排隊車輛的路線結果

由表1 可以看出，在仿真（1）和（2）中序號為5 的路線的行駛時間排名第五和第三，但是在此次仿真中排名第一。由此證明可以根據(jù)交叉口的排隊車輛長度來選擇路線，可以很好地避開那些擁堵的路口。

（4）道路中偶發(fā)交通事故

在（1）的數(shù)據(jù)基礎上，進行本次仿真。如果1到4的路段（即1-4）發(fā)生交通事故，車輛會選擇繞開此路徑，而走另外的路線，此時車輛選擇O →①→②→⑤→⑥→⑨→D 這條路。如果1到4和5到6（即1-4和5-6）兩條路同時發(fā)生交通事故，則車輛會選擇O →①→②→⑤→⑧→⑨→D 這條路。

對于（4）所述，只是提供了一種解決偶發(fā)交通事故的思路，具體情形還沒有具體考慮。

5 結束語

重點研究了基于無人機-智能車隊協(xié)同系統(tǒng)下的實時路徑決策方法，針對現(xiàn)有的基于智能交通系統(tǒng)下的路徑決策方法無法完全保障道路數(shù)據(jù)的獲取，提出兩種工作模式，即路測模式和機測模式。將現(xiàn)有文獻中考慮單一信號燈和單一車道擴展為車輛考慮在不同車道上的行駛時間以及在交叉口的延誤時間，同時考慮多次排隊情況，動態(tài)計算行駛時間并得到一條用時最少的路徑。如果缺乏路測信息，使路測模式無法工作時，通過機測模式下無人機和智能車隊形成協(xié)同工作，獲得車輛排隊長度信息。系統(tǒng)里利用機測模式考慮車輛在不同車道上行駛以及多次排隊情況計算出一條行駛時間最短的路徑。實驗證明了所提方法的有效性。接下來計劃是無人機獲取視頻后，通過視頻處理技術得到信號燈的顯示及和信號燈的當前時刻。