基于多影響因素RDMA*算法的無人駕駛動態(tài)路徑規(guī)劃*

許倫輝 曹宇超 林培群

（華南理工大學土木與交通學院 廣州510640）

0 引 言

隨著人工智能影響范圍的不斷擴大，智能交通中的無人駕駛技術也在不斷的發(fā)展和成熟。各大企業(yè)如谷歌、百度、華為等也在無人駕駛領域布局。其中無人駕駛路徑規(guī)劃是無人駕駛技術中的一個重要部分，它直接影響著無人駕駛汽車行駛的效率及安全性。路徑規(guī)劃模塊是無人駕駛車輛與道路的連接關鍵，也是環(huán)境感知與運動規(guī)劃的橋梁。路徑規(guī)劃的根本目的是為車輛找到一條根據目標設定結果最優(yōu)且能安全到達的路徑。

當前，很多研究學者提出不同的路徑規(guī)劃算法，分別是以A*算法為代表的基于圖搜索的路徑規(guī)劃算法和以快速擴展樹為代表的基于采樣的路徑規(guī)劃算法[1]。卞永明等[2]在基礎A*算法估價函數的基礎上，引入懲罰函數和獎勵因，解決了傳統(tǒng)A*算法拐點多的問題，提升了AGV 的全局運輸效率；毛晨悅等[3]在無人機領域通過在勢場函數中加入了動態(tài)調節(jié)因子，提出了改進人工勢場法的避障路徑規(guī)劃方法；Chen 等[4]針對已知環(huán)境下移動機器人的路徑規(guī)劃問題，提出了一種基于網格圖的混合人工勢場和蟻群優(yōu)化路徑規(guī)劃方法；何佳等[5]綜合考慮RRT 算法節(jié)點選擇、步長選擇、擴展方向等，結合路徑規(guī)劃問題，提出了改進的RRT路徑規(guī)劃算法；劉生偉等[6]針對在較大柵格地圖上進行路徑規(guī)劃時，傳統(tǒng)A*算法搜索路徑效率低，引入切比雪夫距離作為當前節(jié)點的父節(jié)點啟發(fā)函數之和的系數，通過關鍵點選取方法提出了改進的A*路徑規(guī)劃算法；羅顯躍等[7]針對巡檢機器人避障過程中的路徑規(guī)劃問題，提出了一種基于柵格地圖參數可調勢場法的障礙物繞行智能路徑規(guī)劃算法；呂太之等[8]針對傳統(tǒng)局部路徑規(guī)劃結果中易陷入局部最優(yōu)和路徑不光滑等問題，提出了一種改進的平滑路徑算法；Fu 等[9]提出了一種基于多行為融合的勢場方法，通過設計不同的激活條件以確定當前行為，在不同的障礙物環(huán)境中產生無碰撞路徑。如今還包括一些智能仿生結合的算法。如AL-Taharw等[10]提出了一種基于靜態(tài)環(huán)境的遺傳算法解決路徑規(guī)劃問題；賀盼博等[11]提出了一種基于多約束條件的改進遺傳算法的路徑規(guī)劃；萬逸飛等[12]針對蟻群算法收斂速度慢及易陷入局部最優(yōu)的缺陷，結合A*算法提出了改進的A*蟻群算法；Yue等[13]通過添加懲罰策略來改進傳統(tǒng)蟻群算法在路徑規(guī)劃中搜索效率。上述研究大部分都只考慮了距離因素來選擇路徑，并且屬于靜態(tài)路徑規(guī)劃方法。缺點在于，單純以距離作為路徑選擇依據，忽略了出行中其他交通因素的影響，會使得評估不全面；其次初始狀態(tài)進行靜態(tài)路徑規(guī)劃，當實際無人車運行中出現(xiàn)某些不可預估的突發(fā)事件時，路徑無法及時變更，當到達了事故點后，再重新規(guī)劃會造成資源的浪費和效率的降低。部分學者對動態(tài)路徑規(guī)劃進行了研究，如曾鵬等[14]基于Vanet平臺提出了一種考慮了擁堵的動態(tài)雙向A*搜索算法；周自維等[15]針對復雜局部環(huán)境中機器人實時自主導航問題，構建了結合“雙向搜索多邊形構造算法”和“基于勢場函數的運動控制器”的路徑規(guī)劃算法；陳艷等[16]擴展了一種用于移動機器人實時路徑規(guī)劃的神經網絡方法，使用概率路線圖來解決移動機器人在不穩(wěn)定環(huán)境中的實時無碰撞運動規(guī)劃問題；成怡等[17]為了滿足移動機器人全局路徑規(guī)劃最優(yōu)和實時避障的需求，提出了一種改進A*算法與Morphin搜索樹算法相結合的動態(tài)路徑規(guī)劃方法；曾慶成等[18]從AGV 運輸作業(yè)時間角度，建立考慮擁堵的多AGV 路徑優(yōu)化模型，設計了基于多種群蟻群算法的動態(tài)路徑規(guī)劃策略；董朝瑞等[19]利用預約柵格生成交通擁堵地圖，實時更新地圖的擁堵狀況，通過改進的A*算法實現(xiàn)多機器人的動態(tài)路徑規(guī)劃。然而目前大部分動態(tài)路徑研究僅僅是基于獲取的局部的交通環(huán)境信息和周圍障礙物的實時檢測信息來更新路徑規(guī)劃結果，并沒有考慮結合全局交通狀態(tài)的動態(tài)變化情況；部分研究者考慮了全局路網動態(tài)變化的情況，但也只考慮了交通擁堵因素作為動態(tài)變化因素，影響因素的考慮缺乏全面性。

鑒于現(xiàn)有路徑規(guī)劃的局限性，筆者建立了多影響因素評價體系，基于全局及局部交通環(huán)境信息的實時輸入設計了動態(tài)路徑規(guī)劃算法——RDMA*算法。該方法可為路徑選擇提供更加合理的依據；并利用現(xiàn)成熟的融合感知技術獲取實時數據根據動態(tài)迭代更新策略進行動態(tài)路徑規(guī)劃，保證路徑規(guī)劃能適應復雜的場景。

1 考慮多影響因素的RDMA*算法構建

RDMA*算法的構建基于啟發(fā)式算法。啟發(fā)式算法應用于路徑規(guī)劃的原因主要在于它具備很高的靈活性及可拓展性，對于路徑規(guī)劃中復雜的交通道路環(huán)境，它具有較強的適應性，同時還能保持高效的搜索速率。A*算法中路徑規(guī)劃的選擇是基于啟發(fā)式代價函數[20-21]。基礎A*算法往往只以距離作為單一代價標準，RDMA*算法則綜合考慮距離及其他影響因素來改進啟發(fā)式代價部分，讓車輛的路徑選擇更加合理。

RDMA*算法首先定義g( )n 表示從初始節(jié)點到任意節(jié)點n 的距離代價，h( )n 表示從初始節(jié)點到任意節(jié)點n 的啟發(fā)式評估代價。當從初始點向目標點移動時，算法權衡這二者。在循環(huán)檢測的過程中，它搜索并標記令f( n )最小的節(jié)點n。其中：f( n )=g( n )+h( n )，即為該條選擇路徑的實際代價值。RDMA*算法采用雙向搜索模式，相比單向A*算法，雙向搜索能夠有效的降低搜索面積，對于一些存在選擇困境的問題，更能體現(xiàn)出高效的優(yōu)勢。結合不同場景不同需求，在模型中加入了多影響因素進行代價函數部分的更新，再結合動態(tài)迭代更新策略，構建RDMA*算法模型，能夠得到評價更為全面的路徑規(guī)劃結果，適應復雜多變的交通環(huán)境。

1.1 RDMA*算法

RDMA*算法在搜索中設置4 個表：正、反Open表和正、反Close 表。Open 表用于存放地圖信息中的還未被檢測過的可行區(qū)域路徑點信息。Close 表用于存放檢測過的路徑點信息。算法的核心思想是: 從正，反Open表中分別以出發(fā)點和目標點為初始節(jié)點開始循環(huán)搜索至對方目標點代價最小的點，每次只考慮1 個最優(yōu)點，判斷是否已經存在于Open表中。若存在，則以該點為新出發(fā)點再次搜索循環(huán)；若新節(jié)點代價小于Open表中已有節(jié)點，則替換原節(jié)點，反之，則刪除新節(jié)點。算法搜索流程示意圖見圖1。

RDMA*算法：（1）生成空的正、反Open 表和正、反Close 表，將起點S 放入Open的正向列表中，再將目標點E加入到Open的反向列表中。（2）檢測正，反Close 表中是否存在交集，若存在則進行步驟（3）；若不存在則進行步驟（4）。（3）在正，反Close 表的交集中，選取正反雙向的代價函數f( )n 值相加最小的頂點，把該點作為雙向搜索的交匯點，輸出正反搜索結果相結合的規(guī)劃路徑，相應代價值為正反搜索得到的二者代價值之和。（4）檢測正，反Open 表，若其中1 個為空，則結束算法，返回“無可行路徑”；否則轉到步驟（5）。（5）分別從雙向搜索正，反Open 表中，找出第一個代價最小節(jié)點U總( )U總=U正+U反，作為當前節(jié)點，將它從對應方向的Open表中移入Close 表，若此時雙向Close 表中出現(xiàn)交集，轉步驟（2）；否則轉步驟（6）。（6）以當前的最新節(jié)點U 進行拓展后續(xù)搜索，找到其擴展的后繼節(jié)點集合V ，遍歷集合V 中的節(jié)點，如果節(jié)點既不在Open表也不在Close表，計算該節(jié)點的代價值，將節(jié)點加入到Open表，設置父節(jié)點為U 。如果節(jié)點在Open表、Close表，比較當前節(jié)點的代價f( )v 和Open表、Close表中代價，如果當前節(jié)點的代價f( )v 小，更新表中的代價和父節(jié)點指針。（7）根據代價值遞增的順序，對Open表中節(jié)點排序。（8）轉步驟（2）。

圖1 RDMA*算法搜索流程示意圖Fig.1 Schematic diagram of RDMA*algorithm search process

1.2 多影響因素下的綜合代價函數構建

基于車輛出行模式的用戶在進行路徑決策時，需要在確定相關出行信息前提下，結合出行距離、舒適性等出行屬性，進行詳細的考慮和比較，同時需要兼顧考慮一些動態(tài)變化的因素，如交通狀態(tài)、擁堵程度等變化情況，從而做出比較符合自身條件的出行選擇[22]。同時在研究用戶出行選擇和出行時間作用關系上，諸葛承祥等[23]根據Nested Logit 模型，通過調查數據顯示，一般而言，用戶在出行時間確定后，才選擇合適交通方式和路徑出行。因此為了使無人駕駛車輛的路徑規(guī)劃的選擇更加合理，符合用戶取向，RDMA*算法中的啟發(fā)式代價部分采用綜合代價值進行評價，即綜合考慮距離因素代價值與交通狀態(tài)影響因素代價值。有益于提高出行者的出行效率。

1.2.1 距離因素代價值

距離是影響用戶出行時間，決定出行成本的重要因素。筆者在距離部分的代價值計算，基于柵格化后的圖數據進行計算，分為2 點間有無障礙物情況考慮。當2點間無障礙物情況下使用歐式距離作為距離的計算指標。設起始點的經緯度為（cur.x，cur.y），目標點的經緯度是（end.x，end.y）。dx表示2點橫坐標差值；dy表示2點間縱坐標差值。則A，B之間的歐式距離可以表示為

在最常見的情況下，D 可以取1，所以簡化無障礙物下道路距離代價函數定義為

在2點間有障礙物情況下使用曼哈頓距離作為距離的計算指標。 A，B 之間的曼哈頓距離可以表示為

在最常見的情況下，D 可以取1，所以簡化有障礙物道路距離代價函數為

此距離代價函數綜合考慮了計算量及存在障礙物與否。且為了使可搜索鄰域覆蓋更多角度范圍，提出一種將節(jié)點定義在柵格邊線上的表示方法，這樣每個節(jié)點的可拓展子節(jié)點就可存在于各個方向。柵格邊線包括了柵格交點和非交點，見圖2～3，A，C 節(jié)點是柵格邊線的交點，而B 節(jié)點是非交點。

圖2 柵格邊線節(jié)點示意圖Fig.2 Grid edge node diagram

對于邊線上的交點X ，其代價值等于目標點至4個相鄰網格綜合代價值的均值，見式（5）。

對于邊線上非交點Y ，它的代價值是目標點至其2個端點綜合代價值的線性組合，見式（6）。

圖3 柵格節(jié)點代價值計算示意圖Fig.3 Schematic diagram of grid node cost value calculation

其中s 是點Y 到點X1的距離占比。通過對柵格節(jié)點位置的重新定義，可以解決傳統(tǒng)柵格法以柵格中心為節(jié)點而無法處理的任意角度問題，可以保證正確的最短路徑的搜索方向。

1.2.2 交通狀態(tài)影響因素代價值

乘客出行的目標是綜合考慮效益最優(yōu)化，其中除了距離直接決定時間成本與出行成本外，交通道路擁堵情況，道路的平整情況以及其他交通影響因素也是間接影響著路徑選擇的因素[24-25]。因此，除了距離因素外，RDMA*模型中啟發(fā)式評估代價部分添加了交通擁堵系數i，道路平整度系數j，以及其他交通影響因素系數k 作為啟發(fā)函數中的另外3項評估代價指標系數。

1）交通擁堵影響因素。在用戶的剛性出行中，根本追求的是出行的時間效率，在交通中影響著時間效率的因素除了直接的距離成本，還有交通的擁堵狀況，因此通過添加交通擁堵系數來量化該部分影響因素，添加至綜合代價值中。

2）道路平整度影響因素。在用戶的柔性出行中，不僅考慮時間效率外，有時也還考慮出行乘坐的舒適度。在交通出行中，道路的平整度影響著車輛行駛通過的車速，所以間接影響著出行的時間效率；同時道路平整度對于用戶的乘坐體驗也有影響，即乘客的出行舒適度。因此通過添加道路平整度系數來量化該部分影響因素，添加至綜合代價值中。

3）其他影響因素。結合實際的用戶自身或者實際運輸任務的出行需求和特性，通過添加其他影響因素系數來量化該部分影響因素，添加至綜合代價值中。

因此，加入這3 項影響因素來對代價函數進行更新。并將該項定義為交通狀態(tài)影響因素代價值，見式（7）。

式中：c1為交通擁堵系數所占權重，c2為道路平滑度系數所占權重；c3為其他因素系數的影響權重。

1.2.2.1 交通擁堵系數

交通擁堵系數的確定根據交通流理論確定[26]。以時間成本為參照，考慮交通擁堵與速度之間的對應關系，進一步將擁堵對于綜合代價的影響進行量化。具體分為如下步驟。

1）以15 min為統(tǒng)計間隔，根據道路外部統(tǒng)計設備得到各路段的平均行程速度。定義某node 路段的區(qū)間平均速度的計算公式為

2）以路段的平均行程速度為指標，對其擁堵程度對應劃分為5個區(qū)間，見表1。

表1 道路通暢性等級Tab.1 Road patency rating

3）基于平均行程速度與交通擁堵系數的線性比例關系，設對應node 路段的擁堵系數i 的最大值為imax，最小值為imin，對應路段區(qū)間速度最大值為vmax，最小值為vmin，根據外部獲取得到的路段區(qū)間平均車速換算獲得該路段的交通擁堵系數inode。

1.2.2.2 道路平整度

道路平整度系數的確定，基于國際平整度指數IRI 進行量化分析[27]。同樣以時間成本為參考，考慮道路平整度與速度的關系，量化得到各種平整度等級的道路對應于綜合代價值中的道路平整度系數見圖4。左側縱坐標j 表示該路段的道路平整度指標系數，右側對應相應平整度系數體現(xiàn)在車輛通過的速度上的值。道路平整度的數據采集可通過相關部門道路養(yǎng)護數據獲得，并定期進行更新。

圖4 道路平整度系數與速度關系表Fig.4 Relationship table between road smoothness coefficient and speed

1.2.2.3 其他影響因素

結合不同場景下的具體出行或運輸任務需求，可以為評價函數中添加自定義化影響因子k 。模型中系數的確定可根據實際任務需求的懲罰成本與出行其他影響因素的相對權重進行確定。本文將這部分統(tǒng)一歸納為其他影響因素，后續(xù)實驗中默認值設為k=1。

1.3 影響因素的確定以及評價標準

加入上述影響因子并確定了各影響因素的系數取值后，RDMA*算法最終的綜合代價值計算函數見式（10）。

式中：g( x，y )表示距離部分代價值，h( i，j，k )表示單位距離的交通評價部分代價值。應用層次分析法計算確定各影響因素部分在綜合代價中的權重的值。層次分析法是對一些較為復雜、較為模糊，難以定量得出的問題作出決策的簡易方法。運用層次分析法建模，大體上可按如下4個步驟進行：①建立遞階層次結構模型；②構造出各層次中的所有判斷矩陣；③層次單排序及一致性檢驗；④層次總排序及一致性檢驗。

通過網絡問卷的方式，根據上述的多影響因素，設計了對比兩兩因素間相對重要度的調查問卷進行發(fā)布，對乘客進行出行路徑選擇的各影響因素相對重要性程度進行調查分析。根據相關問卷調查的結果，統(tǒng)計用戶對這影響幾項影響因素重要度評價得出比較矩陣見表2。

表2 層次分析重要度值表Tab.2 Road patency rating

根據上述比較矩陣，例如運輸距離與交通擁堵程度關系系數為3，即表示出行者認為運輸距離因素的重要度稍強于交通擁堵因素。通過Matlab軟件計算得出各影響因素權重，見圖5。

圖5 各影響因素權重結果圖Fig.5 Results of weighting of each influencing factor

按照各比例重要度及影響水平，本文選取運輸距離，交通擁堵程度，道路平整度，其他影響因素4個指標進行影響因子的構建，進行歸一化處理后獲得比例系數c，見式（11）。

式中：( α+β+γ+δ=1) 。

得到α=0.533 81，β=0.310 14，γ=0.113 46，δ=0.042 584。其中α 表示距離成本所占總代價權重，β，γ，δ 分別代表交通擁堵程度i，道路平整度j，其他影響因素k 3個因素所占權重。再根據歸一化計算，得出在式（7）中交通評價部分函數h( i，j，k)中c1=0.665 3；c2=0.243 4；c3=0.091 3。式（10）中的總體權重a=0.533 81；b=0.466 19。

2 基于道路環(huán)境數據的實時動態(tài)更新策略

在實際的出行過程中，整個交通環(huán)境往往存在著動態(tài)變化的情況，為解決車輛行駛過程中動態(tài)狀況下特殊事件的發(fā)生造成影響路徑規(guī)劃結果的問題，本文通過GPS、激光雷達，以及車載攝像頭檢測的基礎上，采用融合感知的方式，對全局環(huán)境的更新和局部環(huán)境的避障路徑更新提供路徑規(guī)劃信息支持。其中GPS 主要采集道路交通信息以更新全局道路擁堵信息；激光雷達主要負責搭建整體的道路虛擬環(huán)境完成局部可行駛區(qū)域檢測；視頻圖像識別針對動態(tài)過程中的視覺范圍內的目標進行檢測以完成局部障礙物的檢測，結合3 種設備的更新可獲得全面可靠的環(huán)境信息，以此作為依據在RDMA*算法中加入動態(tài)迭代更新策略來進行安全可靠的實時路徑的更新和規(guī)劃。

2.1 全局道路環(huán)境的信息獲取

本文基于GPS技術采集交通信息，得到區(qū)間車速等數據[28]。根據前文所述區(qū)間車速與交通擁堵系數的轉換關系，實時對道路的全局交通環(huán)境及擁堵程度進行更新，為路徑規(guī)劃提供全局的環(huán)境信息支撐。針對核心技術簡要描述，基于GPS數據的公路區(qū)間測速系統(tǒng)主要由路側單元、車載電子標簽、上位機監(jiān)測中心系統(tǒng)3個部分組成。系統(tǒng)結構見圖6。

圖6 GPS全局環(huán)境獲取系統(tǒng)結構Fig.6 GPS global environment acquisition system structure

2.2 局部道路環(huán)境信息獲取

2.2.1 基于激光雷達的可行駛區(qū)域檢測

局部環(huán)境信息獲取的第一部分主要通過激光雷達的檢測獲取到以劃分出可行駛區(qū)域及不可行駛區(qū)域[29-30]。整個核心檢測流程描述見圖7。

2.2.2 基于攝像頭的車道區(qū)域和障礙物檢測

圖7 激光雷達環(huán)境檢測流程Fig.7 Lidar environmental detection process

局部環(huán)境信息獲取的第二部分主要基于車載攝像頭的檢測，進一步檢測當前道路可行駛車道區(qū)域和周圍環(huán)境是否有障礙物的存在，動態(tài)的更新障礙物信息以保證路徑可行性，分別采用OpenCv和YOLO方法進行車道區(qū)域和障礙物信息的實時檢測[31]。

以實際場景下的圖片對象作為測試對象，識別出當前道路可行駛區(qū)域，通過不同信息熵值設置以及分類標準，分類判別出行駛過程中的目標信息，包括車輛car；周圍環(huán)境物體stuff 等，檢測效果示意圖見圖8。根據是否阻礙原行駛路徑，判斷是否將對象信息加入到障礙物列表中。進一步為后續(xù)更新道路障礙物信息和道路通行狀態(tài)提供數據支持。

圖8 基于攝像頭檢測的效果圖Fig.8 Effect map based on camera detection

2.3 基于融合感知的實時動態(tài)更新策略

基于融合感知獲取的全局與局部交通信息進行路徑規(guī)劃的動態(tài)狀態(tài)的更新，完成算法的動態(tài)規(guī)劃策略設計。首先設定1個搜索迭代周期T 。

1）輸入階段。主要輸入基于融合感知獲取的環(huán)境地圖信息和起點，終點。運行的環(huán)境地圖主要為經過柵格處理過后的電子地圖，根據感知檢測結果，將整個地圖環(huán)境分為障礙物區(qū)域和可行駛區(qū)域。

2）接近檢測階段。當到達設定的迭代檢測周期T 后，該階段會檢測當前車輛所在位置點和終點的距離，根據融合感知獲取的環(huán)境信息，然后執(zhí)行RDMA*算法計算綜合代價值，并與原規(guī)劃路徑匹配度的判斷，若與原規(guī)劃路徑一致，則繼續(xù)行駛；若與原規(guī)劃路徑不一致，則更新路徑。若未到達周期T則進行下一階段。

3）轉換階段。當感知設備主動檢測到障礙物時，標記當前車輛點為SwitchS，同時將SwitchS 作為新的起點，結合目標點信息運行RDMA*算法規(guī)劃路徑；若全局環(huán)境變化不影響原路徑規(guī)劃結果或者局部環(huán)境無檢測到障礙物，則進行下一階段。

4）結合階段。當RDMA*算法檢索到最優(yōu)的節(jié)點，并加入了Close 表后，由雙向搜索至該最優(yōu)節(jié)點得出的正反向各段路徑相結合，即為最終最新的路徑規(guī)劃結果。

實時動態(tài)處理策略Input: T Output: Pathnew，F(xiàn)min 1.xcurrent →xgoal 2.λfree1，λobs1 ←UpdateStatesT 3.λfree2，λobs2 ←UpdateObs(xobs)4.Fmin ←UpdateRDMA*Path(λfreenew，λobsnew，xgoal)5.return Pathnew，F(xiàn)min

其中：T 為迭代更新周期；Pathnew為路徑規(guī)劃結果；xcurrent表示當前車輛位置狀態(tài)信息；xgoal表示目標點狀態(tài)信息；λfree表示環(huán)境可行駛區(qū)域信息；λobs表示檢測的障礙物或不可通行信息；UpdateStatesT 表示基于周期T 的更新操作；UpdateObs 表示當檢測到障礙物時的更新操作；Fmin表示代價值最小。

3 算例分析

在保證安全性和可行性的實驗前提下，本文以廣州市某大學校園區(qū)域為背景構建無人駕駛出行測試任務，通過衛(wèi)星觀測的俯視圖，進一步構建了該校園范圍內的平面電子地圖，定義柵格坐標系，見圖9。

圖9 五山校區(qū)平面電子地圖Fig.9 Plane electronic map of Wushan Campus

無人駕駛車輛以“五山地鐵站A 口”為出發(fā)點S ，“逸夫人文館”為終點E ，進行路徑規(guī)劃案例實驗，整個實驗區(qū)域范圍的面積約為1.75 km2，測試時間為15∶00—16∶00，校園區(qū)域內人流較少的時間段。分為靜態(tài)環(huán)境和動態(tài)環(huán)境分別設定不同算法進行實驗對比分析。靜態(tài)環(huán)境即指道路環(huán)境及狀態(tài)從始至終未出現(xiàn)影響路徑規(guī)劃結果的事件；動態(tài)環(huán)境即指道路環(huán)境及狀態(tài)行駛過程中出現(xiàn)了影響路徑規(guī)劃結果的事件。在車輛行駛過程中，實時使用相當于柵格大小40×40 的搜索范圍大小進行迭代搜索，搜索的周期為T =10 s。計算流程如下。

1）根據外部感知設備獲取的初始環(huán)境信息構建初始電子地圖，見圖10，S 為起點，E 為終點。以“△”表示初始環(huán)境中的障礙物信息。

圖10 障礙物信息電子地圖Fig.10 Obstacle information electronic map

2）根據RDMA*算法進行路徑規(guī)劃。①生成空的正，反Open 表、Close 表，首先將起點S 和終點E放入對應Open 表中；②以雙向起點進行搜索，將可行駛的點信息加入對應Open表中，結合2點綜合代價計算出代價最小值點U ，將它從對應Open 表中移入Close 表，作為當前節(jié)點；③通過擴展后繼節(jié)點判斷當U 為最優(yōu)節(jié)點時，以U 為父節(jié)點再次遍歷直到正，反Close表中出現(xiàn)交集，找到最優(yōu)路徑。

3）根據實時動態(tài)更新策略，首先按照初始路徑規(guī)劃開始行駛，以T 為周期進行動態(tài)檢測，以當前位置為坐標原點進行環(huán)境檢測，若環(huán)境狀態(tài)出現(xiàn)變化，即時更新道路相關參數，將新的障礙物信息追加到障礙物數據庫中，以時間作為不同次數據的標簽，轉步驟5）；若環(huán)境無變化則轉步驟4）。

4）當根據感知設備主動檢測到環(huán)境中出現(xiàn)影響路徑規(guī)劃的結果的狀況或障礙物時，更新全局和局部環(huán)境信息，將新的障礙物信息追加到障礙物數據庫中，更新整個地圖環(huán)境信息，并再以當前時間作為標簽存儲。轉步驟5）；若交通環(huán)境的變化不影響路徑規(guī)劃結果或無檢測到障礙物，則按照原始規(guī)劃路徑繼續(xù)行駛，重復步驟3）～4）。

5）基于檢測時的點作為起點朝著目標點，根據更新的環(huán)境信息應用RDMA*算法再次進行路徑規(guī)劃，并且使車輛按照更新規(guī)劃路徑行駛。重復步驟2）～4）。

6）通過調節(jié)周期T 的大小，做到近實時的周圍環(huán)境檢測及路徑規(guī)劃。重復步驟1）～5），直到到達目標點為止。

以包含初始起點S 在內的10×10大小的區(qū)域為例，不可通行及障礙物區(qū)域的坐標信息見表3。

表3 初始10×10 區(qū)域障礙物數據信息表Tab.3 Initial 10×10 area obstacle data information table

通過Matlab 軟件基于RDMA*算法實現(xiàn)第1 個周期T 內的路徑規(guī)劃的，以包含初始起點S 在內的10×10大小范圍的路徑規(guī)劃結果為例，見圖11，其中以“△”表示障礙物位置；以“○”表示規(guī)劃行駛路徑。

圖11 初始10×10區(qū)域源碼路徑規(guī)劃示例圖Fig.11 Example diagram of initial 10×10 regional source code path planning

本算例RDMA*算法的檢測周期T 設置為10 s，不斷進行迭代搜索與計算。在靜態(tài)環(huán)境下，僅基于道路距離作為評價因素的傳統(tǒng)A*路徑規(guī)劃得到的路徑見圖12；基于考慮綜合代價的RDMA*算法最終得到的路徑規(guī)劃圖見圖13。圖中“△”表示基于環(huán)境感知得到的不可行區(qū)域及障礙物信息；“○”表示最終規(guī)劃的路徑。傳統(tǒng)路徑規(guī)劃以基礎A*算法為代表，基于傳統(tǒng)A*路徑規(guī)劃算法獲得路徑段的總距離長度g 為2.1 km，該路段交通平均擁堵系數i 為4；道路平均平整度j 為8。如式（12）計算得總代價為5.764，任務實際完成時間為138.88 s。

圖12 傳統(tǒng)A*路徑規(guī)劃算法下五山區(qū)域OD 路徑規(guī)劃圖Fig.12 OD path planning map of Wushan area under traditional A*path planning algorithm

基于RDMA*算法獲得路徑段的路徑總距離長度g 為2.5 km，該路段交通擁堵平均系數i 為2；道路平均平整度j 為3。綜合代價值如式（13）計算得為3.893，任務實際完成時間為117.00 s。

圖13 RDMA*算法下五山區(qū)域OD路徑規(guī)劃圖Fig.13 OD path planning diagram of Wushan area under RDMA*algorithm

實驗結果證明，相較于單純以距離為標準的傳統(tǒng)路徑規(guī)劃，在初始靜態(tài)環(huán)境下，基于RDMA*算法下多影響因素評估選擇的路徑有更好的實際效果，如圖14～16所示綜合代價值相比減少了32.46%，實際任務完成耗時相比減少15.75%，見表4。

圖14 靜態(tài)狀況下路徑規(guī)劃代價值對比圖Fig.14 Comparison chart of path planning cost under static conditions

圖15 傳統(tǒng)A*路徑規(guī)劃的時間-代價值關系圖Fig.15 Time-generation value relationship diagram of traditional A*path planning

圖16 RDMA*路徑規(guī)劃的時間-代價值關系圖Fig.16 Time-generation value relationship diagram of RDMA*path planning

表4 A*算法與RDMA*算法運算速率與評價結果對比表Tab.4 A * algorithm and RDMA * algorithm operation rate and evaluation result comparison table

最后基于偏差最小化對原始軌跡進行平滑處理，生成1條符合實際駕駛的最終曲線，見圖17。淺灰色是單純由路徑節(jié)點連接而成折線圖，黑色是經過平滑優(yōu)化后的路徑曲線軌跡圖。

圖17 平滑曲線軌跡Fig.17 Smooth curve track

7）動態(tài)環(huán)境下特殊事件的處理。針對實時交通道路環(huán)境的動態(tài)變化，模擬動態(tài)環(huán)境下某路段由于出現(xiàn)特殊事件，造成道路的無法通行的狀況，數據上體現(xiàn)即為路段通行代價值趨于無窮大，事故阻礙路段見圖18中方框部分。在此情況下，基于實時融合感知檢測。當車輛行駛至S1點時，主動檢測發(fā)現(xiàn)前方原始規(guī)劃路徑的出現(xiàn)障礙物，根據實時動態(tài)更新策略立即進行新一次算法迭代，即重新以此時所在的S1點為新的起點，根據新的道路環(huán)境信息動態(tài)地規(guī)劃新的路徑。得到如圖18 中“○”所示的新的規(guī)劃路徑，放棄如圖18 中“X”所示的原始路徑規(guī)劃點。新路徑總距離長度g 仍為2.5 km，平均交通擁堵系數i為3及平均平整度系數j為5，計算得綜合代價值為5.236，任務到達目標點耗時為134.57 s。在該動態(tài)環(huán)境狀況下，與改進的A*動態(tài)路徑規(guī)劃算法進行實驗對比。采用改進A*動態(tài)路徑規(guī)劃算法的無人駕駛車輛，當自身感知系統(tǒng)檢測到障礙物后，只有當行駛至臨近障礙物的區(qū)域時，即當到達事故點S2時，才會根據現(xiàn)有的道路交通環(huán)境信息再重新以障礙物點為起點進行到目標點的路徑規(guī)劃，從規(guī)劃結果看，這種方式的動態(tài)規(guī)劃將會造成從事故點S2折返回S1點間的不必要損失。數據上即造成2倍于S1點至事故點之間行駛代價值的損失。S1 與S2 距離g 為0.2 km；該路段交通平均擁堵系數i 為2；道路平均平整度j 為3。改進A*動態(tài)路徑規(guī)劃方法與RDMA*動態(tài)規(guī)劃方法相比，計算得到綜合代價值損失為0.623，見式（14）。改進A*動態(tài)路徑規(guī)劃完成任務耗時為146.00 s。

圖18 特殊事件實時路徑規(guī)劃圖Fig.18 Special event real-time path planning diagram

發(fā)生事故后，基于改進A*動態(tài)路徑規(guī)劃算法得到的時間-代價值關系圖見圖19。見圖20 為應用RDMA*算法所得到的時間-代價值關系圖，在134.57 s的行程中，RDMA*算法進行了14次迭代搜索。如圖21所示，在遇到特殊事件狀況下，RDMA*算法動態(tài)規(guī)劃的路徑結果與改進A*動態(tài)路徑規(guī)劃的結果相比，代價值相比減少了10.63%，耗時相比減少了7.83%（見表5）。論證RDMA*算法能夠應對復雜的事故場景，即時規(guī)劃1條當前最優(yōu)的路徑，節(jié)省了整體任務耗時。

圖19 特殊事件下傳改進A*動態(tài)路徑規(guī)劃的時間-代價圖Fig.19 Time-cost graph of traditional static path planning under special events

圖20 特殊事件下RDMA*動態(tài)路徑規(guī)劃的時間-代價圖Fig.20 Time-cost plot of dynamic path planning under special events

圖21 特殊事件下代價值對比圖Fig.21 Comparison chart of next generation value of special events

表5 動態(tài)狀況下改進的A*動態(tài)路徑規(guī)劃與RDMA*動態(tài)路徑規(guī)劃運算速率與評價結果對比表Tab.5 Comparison table of calculation speed and evaluation result of traditional A *and RDMA * under dynamic conditions

從實驗結果可以看出，RDMA*算法通過考慮距離因素，交通擁堵因素，道路平整度因素以及其他影響因素的綜合代價規(guī)劃的路徑結果，相較于單純以考慮距離因素的路徑規(guī)劃結果，具有更高的出行效率，消耗更低的時間成本，同時在無人駕駛車輛可行駛方向以及行駛軌跡方面進行了平滑優(yōu)化；在動態(tài)環(huán)境下，與現(xiàn)有改進的A*動態(tài)路徑規(guī)劃結果相比較，RDMA*算法中的動態(tài)迭代更新策略能結合當前的車輛信息，全局和局部道路交通信息，動態(tài)規(guī)劃出一條當前最優(yōu)的路徑，能夠更靈活且高效的解決交通環(huán)境動態(tài)變化對路徑規(guī)劃結果造成的影響。由于條件限制，未來將會在更大范圍的路網以及更復雜的道路環(huán)境上進行實驗驗證。

4 結束語

針對無人駕駛所處的復雜道路環(huán)境，為了規(guī)劃更合理及高效的最優(yōu)路徑，在A*算法模型的基礎上，論述了交通相關因素對于用戶出行路徑選擇的重要性，然后加入了與交通評價相關的交通擁堵系數，道路平滑度系數以及其他交通影響因素2項影響因子，結合雙向搜索模式設計了改進代價函數的RDMA*路徑規(guī)劃算法，使其能更全面及合理的為無人駕駛車輛提供1條最優(yōu)路徑。然后對于傳統(tǒng)的無人駕駛路徑規(guī)劃往往只根據靜態(tài)的道路狀況進行路徑的規(guī)劃，忽視了實時變換的動態(tài)道路情況以及可能出現(xiàn)的突發(fā)性事件對路徑規(guī)劃造成的影響，在融合感知技術獲取道路全局和局部環(huán)境信息的基礎上，設計了RDMA*算法實時動態(tài)更新策略實現(xiàn)近實時的動態(tài)路徑規(guī)劃，綜合考慮全局和局部的關系來解決道路環(huán)境動態(tài)變化可能對路徑規(guī)劃結果造成影響的問題。最后通過某校園區(qū)域出行案例模擬，基于理想的道路環(huán)境信息獲取，利用RDMA*方法完成了1 次完整的路徑規(guī)劃任務，并在靜態(tài)狀況與動態(tài)狀況下分別與傳統(tǒng)A*路徑規(guī)劃方法和改進A*動態(tài)路徑規(guī)劃方法進行了比較。論證了本文方法改進了無人駕駛路徑規(guī)劃的合理性，提高了任務效率，同等環(huán)境下能以更短時間完成了出行任務，能適應復雜的交通環(huán)境。為無人駕駛提供了一種新的動態(tài)路徑規(guī)劃方法。未來隨著無人駕駛車輛和5G 傳輸技術的不斷發(fā)展，可進一步拓展相關路徑規(guī)劃應用范圍，進一步提高交通數據檢測的精度，范圍和即時性。