在自主車輛路徑規劃中逆向D*算法的應用

雷雨能，賴文娟，曾 刊

(中國兵器工業第五八研究所 軍品部，四川 綿陽 621000)

自主車輛研究是當今的1 個熱點，路徑規劃作為自主車輛完成行駛任務的安全保障，是其智能化程度的重要標志。所謂路徑規劃，是指在具有障礙物的環境中，機器人按照某一特定性能指標(如距離、時間等)搜索1 條從起始狀態到目標狀態的最優或次優路徑的過程。由于自主車輛運行在戶外復雜環境中，因此對路徑規劃的仿真研究非常必要。傳統的路徑規劃算法主要有人工勢場法、可視圖法，而目前比較流行的路徑規劃算法主要有A*、D*、神經網絡、遺傳以及蟻群等等算法［1］。其中，文獻［2］采用的D*算法比較適合在小規模、部分已知的環境中進行路徑規劃，而在較大規模復雜環境中，直接規劃起點到終點的計算代價往往很大。

針對上述問題，本文對逆向D*算法進行了分析和驗證。對自主車輛裝備的各種傳感器所探測到的前方路面環境建立局部柵格地圖。在局部柵格地圖中采用A*方法［3］搜索中間節點，并規劃得出車輛當前位置到中間節點的局部路徑。在行駛到中間節點后，自主車輛再重新搜索下1 個中間節點，并規劃下1 條局部路徑，自主車輛沿著下1 條局部路徑行駛。依此循環后，直到到達最終目的地。通過實驗驗證，該算法克服了D*算法在大規模環境下計算量較大的缺點，提高了路徑規劃算法的效率。

1 逆向D* 算法

1.1 基本思想

在部分信息未知的復雜環境中，機器人路徑規劃有以下3 個特點［4］:①環境信息的改變大多是在機器人周圍相當近的1 個區域當中進行的，這主要是因為機器人一般裝備的各種傳感器都只具有一定的觀察范圍。這意味著路徑規劃過程不一定非要在整個全局環境內進行。②機器人的行進過程中，如果大多數的障礙物很小，那么簡單的路徑改變就足以表達，這樣就可以避免很高的計算代價。③在機器人行進過程中的1 個節點上，在大多數情況之下只有剩下的一部分路徑需要重新規劃。那么，根據第2 個特點，重新規劃的這部分路徑就可以變得更短，D*算法正是針對部分信息已知的環境中路徑規劃問題提出的。

D*算法在小規模環境區域規劃中比較有效，但在較大規模環境下直接規劃起點到終點的路徑，往往造成很大的計算代價。為了不再計算初始的目標距離勢場，通過定義“機器人距離”的方法來建立機器人當前位置中心的局部區域勢場，并且通過搜索距離目標估計代價最小的中間目標節點，來滿足機器人滾動優化［5］的需要，提出了逆向D*算法。

1.2 設計流程

逆向D*算法的設計流程如下:

1)采用柵格環境建模法對機器人行進中傳感器所感知到的前方信息建立局部環境地圖，對障礙物柵格進行預膨脹，以保證機器人和障礙物有一定的安全膨脹距離。通過膨脹后，機器人可以被看成是以其參考點為中心的“點”機器人。

2)設置機器人從起點S(xs，ys)到目標點G(xg，yg)運動過程中所經歷的目標勢能最小值Emin。假設自由柵格坐標點I(xi，yi)的勢能為，則在滾動優化過程中，機器人要以其當前位置R 為中心，向外尋找目標勢能小于Emin-ε(ε ＞0，為常數項)的中間柵格節點I。而此柵格節點I 應該滿足

3)在搜索中間柵格節點I 過程中，以A*方法建立確定搜索優先度的估計函數f(i)。其中，被搜索點I 的估價函數f(i)=g(i)+h(i)。而與D*算法不同的是，g(i)是從機器人當前位置R 到搜索柵格節點I 的實際代價，即機器人距離，h(i)是搜索柵格節點I 到目標節點G 的估計代價。

4)在被搜索的區域里，機器人距離g(i)被記錄在柵格位圖中，當搜索到滿足上述條件的I 節點后，從節點I 出發，按照機器人距離g(i)減少的梯度方向，回溯到當前機器人位置R，而該回溯的逆向過程就是從機器人當前位置R 到達中間目標I 的路徑。

5)機器人從起點出發，通過不斷地采用A*方法搜索中間目標I 來實現滾動的動態路徑規劃。

2 環境地圖的表示

無論采用哪種路徑規劃算法，都需要知道機器人所在的自身環境，包括機器人自身的位置、障礙物的位置、路標以及目標的位置等，這樣機器人才能搜索到達目的地位置的行走路徑，以便更好地完成任務。而如何對環境建立模型，就成了路徑規劃的基本前提。目前，建立環境模型的方法主要有幾何建模法、拓撲建模法以及柵格地圖建模法［1］。針對不同的路徑規劃需要不同的建模方法，由于柵格地圖很容易創建和維護，故本文所述的逆向D*算法所采用的環境表示方法是柵格地圖環境建模法。

柵格地圖就是將整個工作環境分為若干相同大小的柵格，對于每個柵格指出其是否存在障礙物。機器人所了解的每個柵格的信息直接與環境中某區域對應，環境被表示成離散柵格，柵格“0”表示為可通行的柵格，柵格“1”表示為障礙物柵格。本文所建立的環境地圖如圖1 所示。柵格范圍為20 ×20 方格，柵格單元尺寸為0.5 m，黑色方格為膨脹后的障礙物柵格，空白柵格為可通行柵格。

圖1 環境柵格地圖

3 算法流程

本文所設計的自主車輛路徑規劃仿真流程如圖2 所示。

4 實驗結果與結論

為了說明逆向D*算法在自主車輛路徑規劃中應用的可行性及有效性，采用圖1 所示的環境柵格地圖，以最短距離和最短計算量作為路徑規劃的優化性能指標，利用matlab 進行自主車輛逆向D*算法的實驗仿真。為了說明逆向D*算法的優越性，還與D*算法的仿真結果進行了比較和分析。實驗的硬件配置:處理器為Pentium(R)Dual-Core CPU E5500 2.8 GHz;內存為2 GB。

本實驗中，自主車輛從起始點S(3，3)出發，預計行駛到目標點G(18，18)，以完成路徑規劃任務。起始點和目標點在柵格地圖中的位置如圖3 所示。實驗中還設定自主車輛傳感器所能探測到的局部環境柵格地圖范圍為6 ×6 方格，而估價函數中的機器人距離g(i)為歐幾里德距離。

圖2 算法流程

圖3 起始點和目標點位置示意圖

逆向D*算法的仿真結果如圖4 ～圖6 所示。自主車輛在行進過程中，總共搜索到2 個中間節點，分別是L1和L2，圖4 ～圖6 分別表示起始點S 到中間節點L1、中間節點L1到中間節點L2、中間節點L2到目標點G 的規劃結果，柵格位圖中的數字表示機器人距離g(i)。同等實驗條件下，D*算法的仿真結果如圖5 所示。

圖4 逆向D* 算法路徑規劃(1)

圖5 逆向D* 算法路徑規劃(2)

圖6 逆向D* 算法路徑規劃(3)

圖7 D* 算法路徑規劃

以上實驗結果說明，逆向D*算法與D*算法規劃出的路徑一樣，都是最短的安全行駛路徑，但逆向D*算法在路徑規劃過程中，3 次累計需要計算的機器人距離g(i)次數比D*算法需要計算的機器人距離g(i)次數要少3 倍以上，這樣大大減少了計算量，提高路徑規劃執行的效率。

5 結束語

本文討論了自主車輛的路徑規劃，分析了逆向D*路徑規劃算法的原理以及基本流程，利用仿真實驗驗證了其有效性，并與D*路徑規劃算法做分析比較，驗證了該算法能大大提高路徑規劃的執行效率。

［1］朱大奇，顏明重. 移動機器人路徑規劃技術研究概述［J］.控制與決策，2010，25(7):962-967.

［2］劉亮.自主移動機器人的路徑規劃與避障研究［D］.武漢:武漢京理工大學，2007.

［3］劉進. 自主式移動機器人控制系統與路徑規劃研究［D］.青島:青島大學，2009.

［4］張毅，羅元，鄭太雄.移動機器人技術及其應用［M］.北京:電子工業出版社，2007.

［5］張純剛，席裕庚.全局環境未知時基于滾動窗口的機器人路徑規劃［J］.中國科學(E 輯)，2001，31(2):51-57.

［6］黃鶴.部分環境信息已知的智能機器人路徑規劃方法研究［D］.南京:南京理工大學，2005.

［7］張亮，周繼寶. 基于遺傳算法的后勤運輸車路徑規劃［J］.四川兵工學報，2012(2):81-83.