改進A星算法移動機器人路徑規劃

宋 宇， 王志明

(長春工業大學 計算機科學與工程學院， 吉林 長春 130012)

0 引 言

路徑規劃問題在很多領域都具有廣泛的應用，如機器人的自主無碰撞運行、無人機的避障突防飛行等?，F有的路徑規劃方法包括蟻群算法、A星算法、D星算法、人工勢場算法、模糊邏輯算法、神經網絡算法、強化學習算法等。其中，A星算法作為一種經典路徑規劃算法，被廣泛應用于路徑規劃問題中，但由于在柵格環境下A星算法只選擇周圍柵格的中心點加入open表中，導致路徑點的選擇局限于柵格中心點，路徑轉折角度固定為一些特定的離散值，從而產生了無效冗余轉折或找到的最終路徑不是最優。文獻[1]提出了擴展Moore型鄰居結構A星算法；文獻[2]提出了結合跳點算法的A星算法；文獻[3]采用了二叉堆優化查找open表中F值的方法，加快了A星算法的執行速度；文獻[4]提出了去除冗余點的A星算法；文獻[5]采用A星算法初始化信息素，用蟻群算法進行了機器人路徑規劃；文獻[6]用蟻群算法對Hopfield神經網絡的參數進行了優化；文獻[7-8]采用了優化算法進行路徑規劃。

文中通過建立映射矩陣的方式提出了一種任意角度的A星算法，仿真實驗表明，在柵格劃分粗糙的情況下，改進算法效果顯著。

1 相關算法

1.1 A星算法

A星算法是在Dijstar算法的基礎上引入了啟發函數，加快了算法收斂速度。A星算法的估價函數為

f(x,y)=g(x,y)+h(x,y)

(1)

其中,g(x,y)為起始點到當前考察點X(x,y)的實際距離值，h(x,y)為X(x,y)點到目標點的估計距離值，距離值函數h(x,y)一般取歐幾里德距離(如式(2))或絕對值距離(如式(3))，gx、gy為目標點的x坐標與y坐標。

(2)

h(x,y)=|x-gx|+|y-gy|

(3)

A星算法不斷將當前位置周圍8個柵格的中心點加入open表，并不斷取open列表中F值最小的點作為當前位置，直到當前位置的臨近點出現目標點或open表為空為止，A星算法的流程如下：

1)初始化open表、opencost表、close表為空，將起點坐標加入open表，將起點的cost值0加入opencost表。

2)將open表中具有最小F值的點的坐標作為當前點，同時從open表與opencost表中刪除這個點的信息，并把當前點的坐標加入close表。

3)依次計算當前點的鄰居柵格中心的8個點的g值與f值，若這個點在close表中，則跳過這個點；若這個點既不在open表中，也不在close表中，則將這個點的坐標加入open表，同時將這個點的g值加入opencost表，并將這個點的箭頭指向當前點。若這個點已經在open表中，則比較這個點之前的g值與通過當前點計算得到的g值的大小，若前者大，則修改這個點的g值為當前計算得到的g值，并將這個點的箭頭方向指向當前點。

4)跳到2)，直到open表為空，或者open表中出現目標點為止。

1.2 粒子群算法

粒子群算法是一種模擬大自然群體尋優的優化算法，通過共享群體的適應度值大小來加速極值尋優過程。設D維粒子位置為xi=(xi1,xi2,…,xiD),粒子速度為vi=(vi1,vi2,…,viD)，種群中所有個體粒子目前為止適應度最優時的位置為p=(p1,p2,…,pD),到第k代為止種群中所有粒子的全局最優適應度值對應的粒子位置為pbk。則在每次迭代中粒子的速度更新公式為

(4)

位置更新公式為

(5)

通過不斷迭代，最終算法保存了最優位置，即最優解。

2 改進A星算法

2.1 粒子群搜索

使用粒子群算法搜索當前柵格的鄰居柵格內的最優粒子位置，如圖1所示。

圖1 搜索坐標邊界

最中間的格子代表當前點所在的格子，首先在當前點所在格子的8個鄰居格子內的線段上搜索到8個最優點，目標函數為F值(當前柵格的g值與當前柵格內的實際點到搜索柵格內搜索點的距離與搜索點到目標點的距離的和)，即搜索每個格子內直線上的F值最小的點，使用粒子群算法搜索時，粒子位置搜索范圍限制在每個格子內的線段上。例如，粒子群算法在每個柵格內的給定范圍搜索后得到的點如圖2所示(黑色實心點)。

圖2 搜索得到的點

將搜索到的8個最優位置存入M矩陣中。同時將搜索到的點的g值與f值存入cost與F數組中。

2.2 鄰居格子屬于open表

如果鄰居柵格序號已經在open表中，目標函數為從當前柵格的M矩陣(目前所有柵格內的點的最優位置組成的矩陣)存儲的當前柵格內的最優點到搜索柵格內點的距離與當前點的g值的和，上下左右柵格的搜索范圍為柵格內黑色線段，如圖3所示。

圖3 搜索坐標邊界

4個對角柵格的搜索范圍為整個柵格之內(即若鄰居柵格序號不在open表中，粒子群算法的搜索范圍見圖1，若柵格序號在open表中，粒子群算法的搜索范圍見圖3)。

比較被搜索柵格之前保存的g值與此次搜索到的點的目標函數值，若前者大，則將此鄰居柵格的箭頭指向當前柵格，并更新鄰居柵格的g值與鄰居柵格內M矩陣里存儲的坐標值。

2.3 設置安全距離

為了避免規劃出來的路徑穿過障礙物，設置粒子的坐標距離最近障礙物中心坐標的閾值為d，若粒子(搜索過程中點的坐標)的坐標與所有障礙物中距離最近障礙物的中心點的坐標距離小于d，則將粒子群算法的適應度函數值額外增加100/distance，distance為機器人到障礙物中心的實際距離。若粒子的坐標距離最近的障礙物距離大于閾值d，則不增加。

2.4 改進算法流程

1)以起點為當前點，以2.1所述方法搜索起點的鄰居柵格內的8個最優位置，以及這8個位置的g值(即從起點到這8個位置的距離)與f值。將起點序號加入close表，將8個鄰居柵格的序號加入open表。將搜索到的8個柵格內對應的8個最優位置存入矩陣M中。將搜索得到的8個g值與f值存入cost數組與F數組中。

2)從F數組中選擇f值最小的柵格為當前柵格，同時將此柵格序號從open表移入close表。

3)以當前柵格為中心，依次考察當前柵格的8個鄰居柵格。若鄰居柵格序號在close表中，則跳過此柵格；若鄰居柵格在open表中，則以2.2所述方法更新鄰居柵格的g值和f值，以及最優點位置；若鄰居柵格既不在open表中，也不在close表中，則以2.1所述方法更新g、f值與最優位置,同時將該柵格序號加入open表。

4)若終點不在open表中，跳到2)，若終點在open表中，則算法結束。

3 仿 真

文中將粒子群算法迭代次數設置為10次，種群個數設置為10個。粒子群算法的速度最大、最小值不設限，粒子群搜索算法中的最大速度設置值為0.03，最小速度值為-0.03，閾值距離d設置為1.6。粒子群算法全局最優項前面的系數為2，局部最優項前面的系數為1.5。在Matlab2014a環境下進行了仿真。文中將平均轉折角度定義為總的轉折角度(每次轉折時角度改變量的和)除以轉折點的個數。由傳統A星算法得到的路徑和改進A星算法得到的路徑分別如圖4和圖5所示。

圖4 A星算法路徑

圖5 改進算法路徑

由圖4和圖5可知，改進算法找到的最優路徑點較傳統A星算法找到的路徑點準確。

算法長度與轉折角對比見表1。

表1 算法長度與轉折角對比

障礙物較多情況下傳統A星算法規劃得到的路徑和障礙物較多情況下改進算法規劃得到的路徑分別如圖6和圖7所示。

圖6 障礙物較多情況下A星算法路徑

圖7 障礙物較多情況下改進算法路徑

障礙物較多情況下算法長度與轉折角對比見表2。

表2 障礙物較多情況下算法長度與轉折角對比

由表1和表2可以看出，由文中算法得出的路徑長度較短且路徑較平滑，更符合實際機器人的運動規律。另一方面，從圖6和圖7也可以看出，由于文中算法加入了對安全距離的考慮，得出的路徑盡量遠離障礙物，而不是緊貼障礙物的尖點，故文中算法得出的路徑較安全。

4 結 語

通過設置柵格內搜索到的點與柵格中心點的對應關系以及搜索方式得到了柵格內的最優點，而不是直接選擇中心點作為備選點，通過設置安全距離使得生成的路徑不經過障礙物。仿真結果表明，改進算法得出的路徑長度較短且路徑較平滑。