改進D*算法的移動機器人路徑規劃*

張希聞, 肖本賢

(1.合肥工業大學 電氣工程與自動化學院,安徽 合肥 230009；2.合肥工業大學 裝備與技術工程學院，安徽 合肥 230009)

0 引 言

可移動機器人的路徑規劃在當下具有重要的意義。智能算法有D*算法[1]、蟻群算法[2]、F*算法[3]、強化學習[4]等，依據具體問題具體分析的原則，本文采用柵格法[5]對倉庫進行建模，使用改進的D*算法對路徑進行規劃。采用D*算法的主要原因是由于本文的路障存在動態路障，且能綜合算法搜索時間和路徑長度統籌規劃，而不是單一的形成最優路徑或最快算法。本文提出了一種優化路徑的方法，即拓展Moore型元胞鄰居結構[6,7]，使得路徑較原D*算法進一步優化。在搜索時間上本文提出一種較為簡捷的辦法，即跳點法，使得搜索過程較原D*算法進一步加快。能更符合、更貼切當下的快捷物流標準。但本文提供了更快的搜索時間的同時，由于加大了路徑建模的空間復雜度，對于計算機內存的占用也成比例提高。使用D*算法進行規劃時，只有當移動機器人遇到障礙時才會重新生成可行線路，因此當下對于D*算法的改進，主要發生在路徑長度和運算時間上。就D*算法的路徑長度問題，本文提出了拓展Moore型元胞結構，對原D*算法的路徑進一步縮短,將八點拓展到十六點，進行進一步的路徑縮短。與此同時，采用跳點搜索算法對原D*算法的運算速度進行一定幅度的提高。算法不僅有更快的速度，同時具有更高的空間復雜度。跳點搜索算法可以大量節約內存，有效提高運算效率。

1 相關算法

本文采用拓展Moore型元胞鄰居結構[8]和跳點搜索算法[9]來改進D*算法進行動態路徑規劃。

1.1 元胞自動機

元胞自動機由元胞、元胞空間、鄰居和規則四個部分組成。可以用一個四元數組表示

A=(Ld,S,N,f)

(1)

式中A為元胞自動機模型；d為維度；S為元胞有限離散狀態，元胞可以是二進制形式{0,1}或者是實數形式離散集{m1,m2,…mn}；N為一個領域內所有元胞的集合，記為N=(s1,s2,…sn)，其中n為元胞鄰居個數，si∈Z，Zi∈{1,2,…,n}；f為演化規則。

1.2 D*算法

D*算法是可以規劃動態避障的路徑算法，可以用于多種領域包括航空、游戲、物流等。一般D*算法的路徑搜索包括八種位置分別為：上、下、左、右、左上、左下、右上、右下。引入估價函數的概念，對算法進行一種二維的估價，即

f(n)=g(n)+h(n)

(2)

式中h(n)為啟發函數，代表這段路徑規劃的估價最小值；g(n)為從初始位置到目標位置n的實際代價。比較常見的啟發函數,如歐幾里德函數、曼哈頓函數等。

1.3 跳點搜索算法

跳點搜索算法基本思想為省略傳統D*算法在搜索過程中對于一些不必要點的遍歷，如圖1所示，即從a～b點有3種可執行路徑，分別為a-m-b，a-n-b，a-l-b。而算法會在估值過程中對所得節點進行估價，即m,n,l,挑出最優節點，即l。但從圖中易知，對于m和n點的估價，本身并沒有太大意義路徑a-l-b始終為最優解，那么此時，即可使用跳點搜索算法，對于m和n節點直接采取跳點，不予以估價。跳點搜索算法的根本目的就是對于D*算法生成的眾多節點中進行有效篩選，有別于傳統意義上的節點遍歷，省去大量的計算時間。其中，這些被省去節點即為跳點,均有效減少了內存和算法的計算量。

圖1 3條路徑

2 基于D*算法的機器人路徑規劃

2.1 倉庫建模

根據實際倉庫中障礙以及動態障礙擺放的位置，使用柵格法對倉庫進行建模[10，11]，將二維的平面分為多個正方形網格，根據元胞法，將每一個網格都定義為一個元胞。移動機器人工作的環境由行列柵格構成，將倉庫用一個二維數組矩陣表示為map(p,q)，即

(3)

倉庫建模實際參考圖2。

圖2 倉庫

2.2 拓展Moore型鄰居結構

一般,路徑規劃，移動機器人下一次行動選擇有8種，分別為上、下、左、右、左上、左下、右上、右下[12]。而本文采用的元胞邊長為原元胞邊長的2倍，本文元胞鄰胞定義為

{vi=(xi,yi)||xi-x0|+|yi-y0|≤2,xi,yi∈Z}

(4)

式中vi為其鄰胞集合,(x0,y0)為其坐標。將圖3中元胞分為2種，元胞周圍的8個鄰胞為x1,x2,…,xn；外層的16個元胞為y1,y2,…,yn。有如圖3規則，當x1有障礙物時，不能移動到y1,y2,y16；當x2有障礙物時，不能移動到y2,y3,y4。其他以此類推。通過以上的障礙值輸入，進一步完善了移動機器人的位移路徑，保證了生成路徑的可行性。

圖3 拓展Moore型鄰居結構

2.3 跳點搜索算法對于跳點的選擇

情況1節點周圍不存在障礙物

A1,A2為柵格中的兩個節點，Apred表示A1的父節點，如圖4所示Apred到A2有很多條路徑可行，比如其中Apred-1-2-3-4-A2，然而此法明顯遜于Apred-A1-0-A2，易知，從Apred～A2最短路徑一定經過A1，經過A1的路徑明顯優于不經過A1的路徑，因此，此類重復計算毫無意義，故使用跳點搜索算法，刪除這些不必要的節點。篩選條件如下

L({Apred,…,n|A})≤L({Apred,A,n})

(5)

式中L()為該段路徑的長度，n為x的相鄰接點，{Apred,…,n|A}為一個不經過節點A且分別以Apred和n為起始點和終點的路徑，{Apred,A,n}為經過A節點的分別以Apred和n為起始點和終點的路徑。

圖4 路徑對比

情況2節點周圍存在障礙物

這種情況不能繼續按照上面的情況進行參考。本文以向右上的位移為基準[13]，即如圖5所示，A作為強制鄰節點生成，篩選條件如下[14]：

1)節點A的自然鄰節點不包含n；

2)L({Apred,…,n|A})≥L({Apred,A,n})

圖5 節點周圍存在障礙

2.4 改進D*算法的動態路徑規劃

找到所有符合上述條件的必要節點，刪除所有不必要的節點，從而實現跳點搜索算法，過程如下：將出發點A放入Open-list中，優先以上方和右方進行路線的擴展，直到遇到障礙物后，向對角線方向擴展，當沿著對角線方向擴展到新的障礙物時，再重新回到上方和右方進行擴展，直到一個方向出現倉庫的邊緣，另一個方向出現強制鄰節點，此時將強制鄰節點添加到OpenList中，繼續向出現強制鄰節點的方向擴展。直到發現終點位置。此時跳點搜索算法結束，繼續采用拓展Moore型元胞法。定義OpenList2和CloseList2，將可擴展的元胞和成為最有路徑的元胞存放其中。并且定義tmpcloseList表存放外圍16個元胞中不可擴展的部分。將目標元胞A0放入CloseList中，搜索當前8個鄰居元胞，判定其是否存在障礙，若存在，則判斷其較遠的16個元胞是否可擴展，把不可擴展的元胞放入tmpcloseList中。判定當前元胞的24個鄰居元胞，如果不在OpenList2和tmpcloseList中，則將其放入OpenList2中。然后計算f值，將其設為帶擴展元胞的父元胞，若帶擴展元胞不在OpenList2和tmpcloseList中，則計算新f值，與舊的f值相比較。且將帶擴展元胞的父元胞改為當前元胞。遍歷OpenList2中的所有元胞， 找到f值較小的元胞并放入CloseList2中并清空tmpcloseList，直到當前元胞為起始元胞，結束。

3 仿真與實驗

為了證明本文思路，本文分別進行了傳統D*算法的路徑規劃和本文改進后的跳點擴展Moore型元胞D*算法進行規劃，對比了路徑長度、搜索時間和擴展的節點等。分別在15×15和30×30兩種柵格中的倉庫中進行路徑規劃，使用的計算機設備：Window10操作系統。CPU為i7-7200U，內存為4 GB。

圖6為15×15仿真實驗，其中線條左下起始點為路徑起始點，線條右上終止點為路徑終點，黑色方格為靜態障礙，淺色方格為遍歷的節點。線為規劃出的路徑，可以看出，規劃出的路徑遍歷的節點數目明顯減少，并且規劃出的路徑較原D*算法更為合理。具體為：D*算法遍歷節點數為56，路徑長度為22.37，改進算法遍歷節點數為8，路徑長度為22.73。

圖6 算法對比

圖7為30×30仿真實驗，其中格子的顏色同上15×15柵格規定。具體結果為：D*算法遍歷節點數為181，路徑長度為48.62；改進算法遍歷節點數為12，路徑長度為46.84。

圖7 算法對比

移動機器人實驗如圖8所示。

圖8 移動機器人

為了驗證本文改進后的算法產生的結論，實驗建立在機器人操作系統ROS上進行。移動機器人具有通過相機采集外界數據功能，可以準確獲取環境因素和障礙因素。經過計算生成一種具有三個維度的點云數據，然后轉換為激光模擬的數據，依靠amcl和gmapping模塊建模二維地圖柵格。接下來使用move_base里面的global planner以及local planner共同協作完成全局和部分路徑生成。

4 結 論

綜合實驗、數據和大量的理論知識，本文改進后的D*算法，即通過跳點搜索算法減少運算時間和拓展Moore型元胞法減少路徑長度，一定程度上優化了原先的D*算法，提高了效率，節約了內存。多種柵格法建模后的倉庫作為實驗對象，發現或多或少均有優化，無論是路徑上還是運算時間上。較大的倉庫跳點搜索算法運算時間優化越明顯，較小的倉庫拓展Moore型元胞法路徑長度優化的越明顯。后續希望在三維空間中對這一方法進行驗證，預計會得到和二維類似的結論。