A*算法在移動機器人路徑規劃中的研究

魯 毅，高永平，龍江騰

(東華理工大學 信息工程學院，江西 南昌 330013)

0 引言

隨著工業化社會的發展，貨物的搬運和輸送成為重要的問題，其中移動機器人技術得到了極大的關注[1]，移動機器人技術可以極大地提高貨物的運輸能力，使得貨物的運輸更加的自動化，而在移動機器人技術中，機器人路徑規劃算法[2]一直是研究重點，路徑規劃算法有Dijkstra算法[3]，BFS算法[4]，A*算法[5]等，Dijkstra算法可以搜索到一條最優路徑，但是搜索效率太低，BFS算法搜索效率很高，但是不一定能搜索到一條最優路徑，A*算法結合了Dijkstra算法和BFS算法的優點[6]，但是也存在一些缺點，因此，本文提出改進A*算法，既能尋找到一條最優路徑，而且搜索效率也比較高。

1 傳統尋路算法

1.1 Dijkstra算法

Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法[7]，用于計算從起點到其他各頂點的最短距離。主要是從起點開始不斷向外搜索，直到搜索到終點結束。算法原理：假設一個帶權有向圖G，將其分成A，B兩個集合，其中A集合中存放的是已訪問頂點和其最短路徑值，B集合中存放的是未訪問的頂點，算法步驟如下：

1)初始時，將起點S放在集合A中，集合B中存放其他所有頂點和起點S到其他頂點的距離。

2)從集合B中選取到起點S的最短距離的頂點a，并將頂點a加入到集合A中，同時從集合B中刪除頂點a.

3)以頂點a為中間點，更新集合B中各個頂點到起點S的距離。

4)循環執行步驟2和3，直到遍歷完圖中所有的頂點為止。

Dijkstra算法是一種盲目式搜索算法，所以搜索效率較低，對于n個節點的圖，計算起點到其他各節點的最短距離，算法的時間復雜度為O(n2)，因此，在大型地圖中尋路效率比較低。算法流程圖如圖1所示。

圖1 Dijkstra算法基本流程

1.2 最佳優先搜索算法

最佳優先搜索算法是一種啟發式搜索算法[8]，是在廣度優先算法的基礎上形成的，該算法使用了估價函數，利用估價函數計算當前節點到目標節點的估價值，然后選擇估價值最小的節點進行訪問，直到搜索到目標節點為止。最佳優先搜索算法(BFS)不能保證找到的路徑是一條最短路徑，但是其計算過程相對于Dijkstra算法會快很多。

算法實現需要兩個列表，A列表和B列表，A列表中是將要被訪問的節點，B列表中是已被訪問的節點，算法步驟如下：

1)初始時，將起點放入到A列表中，B列表為空；

2)從A列表中選取估價值最小的節點k,并對k的所有子節點m進行如下操作：

如果m子節點不在A列表和B列表中時，將m子節點加入到A列表中，并計算出m的估價值，并對A列表中的節點依據估價值進行排序。

如果m節點在A列表中，重新計算m節點的估價值，并將該估價值和A列表中m的估價值進行比較，如果小于A列表中的估價值，則將A列表中的估價值進行替換，并且對A列表重新排序。

如果m在B列表中，重新計算m節點的估價值，并將其和B列表中m節點的估價值進行比較，如果小于B列表中m的估價值，則將m從B列表中刪除，并加入到A列表中，然后對A列表中的節點進行排序。

3)將節點k從A列表中刪除，并加入到B列表中。

4)循環執行上述步驟，直到搜索到目標節點或者A列表為空為止。

最佳優先搜索算法在搜索路徑的過程中效率極高，但是最佳優先搜索算法只考慮了當前點到目標點的估計值，沒有考慮起點到當前點的成本值，因此不一定能夠搜索到一條最優路徑。

2 傳統A*算法

A*(A-Star)算法是一種效率高且能搜索到最優路徑的算法[9]。有許多的尋路算法都是在A*算法的基礎上形成的,例如D*算法[10]和NavMesh導航算法[11]，該算法利用了啟發函數的特性，使用啟發函數計算出當前點的估價值，利用估價值來選取最優節點，最終搜索出一條最優路徑。

A*算法結合了Dijkstra算法和最佳優先搜索算法的優勢[12]，它在一定程度上保留了Dijkstra 算法搜索最短路徑的能力，又引入了最佳優先搜索算法的貪婪策略，防止了算法盲目的搜索，組合成了一個融合性的評價函數，評價函數為：

F(n)=G(n)+H(n)

(1)

式(1)中，n為當前節點，F(n)是從起始節點到目標節點的估計值，G(n)是起始節點到當前節點的實際值，H(n)是當前節點到目標節點的估計值，也稱為啟發函數，啟發函數的計算有多種，如曼哈頓距離、歐幾里得距離、對角線距離等。本文啟發函數采用曼哈頓距離[13]，即為：

H(n)=|x1-x2|+|y1-y2|

(2)

式(2)中，(x1,x2)是當前節點的坐標，(y1,y2)是目標節點的坐標。

A*算法就是利用估價函數來對每一個節點進行評估，得到估價最優的節點，再從這個節點繼續搜索直到目標點。通過啟發式搜索，可以避免搜索大量的無用節點，極大地提高了搜索效率。算法步驟如下：

1)首先創建兩個空表open列表和close列表，定義起始節點為S，目標節點為K.

2)將起始節點S加入到open列表中。

3)尋找open列表中f值最小的節點a作為當前節點，若節點a是目標節點，則找到路徑，退出循環，若不是，則繼續下一步。

4)把當前節點a從open列表中刪除并放入到close列表中，對節點a所有相鄰節點進行如下判斷：

a)如果相鄰節點不在open列表和close列表中，將此節點添加到open列表中，用當前節點a作為該節點的父節點，并計算該節點的f值；

b)如果相鄰節點已在open列表中，則再次計算該節點的f值，如果新f值小于舊f值，則用新f值替代舊f值，同時將該節點的父節點改為當前節點a；

c)如果相鄰節點已在close列表中，則忽略該節點；

重復執行步驟3)和4)，若當前節點是目標節點或者open列表為空，則結束循環。

3 改進A*算法

3.1 啟發函數的優化

啟發函數在A*算法中具有導引作用，能夠指引A*算法搜索到一條更好的路徑，但是傳統的啟發函數存在一些效率低的問題，因此對啟發函數做一些優化，改進后的啟發函數為：

F(n)=G(n)+W(n)*H(n)

(3)

式(3)中，W(n)是啟發函數H(n)的權重系數，添加這個權重系數可以使得啟發函數的搜索效率更高，在遠離目標點時，W(n)的權重系數比較大，這樣可以加速算法向目標點搜索，在靠近目標點的時候，W(n)的權重系數較小，這樣可以使算法搜索的路徑更加的精確，通過使用優化的啟發函數可以極大地提高機器人路徑規劃的效率。

3.2 雙向搜索A*算法

雙向搜索A*算法是在傳統A*算法的基礎上進行改進的，傳統的A*算法是從起點開始搜索到終點，搜索效率比較低，雙向搜索A*算法是同時從起點和終點開始搜索，即從起點向終點進行搜索，同時從終點向起點進行搜索，直到兩邊搜索點相交，結束搜索。雙向搜索A*算法的搜索效率比較高，可以極大縮短搜索路徑時間，算法步驟如下：

1)首先創建正向open表和close表，反向open表和close表，將起點S放入正向open表中，終點K放入反向open表中，同時從兩端進行搜索。

2)分別從正向open表和反向open表中選取F值最小的節點作為各自的當前節點，并將其加入到各自的close表中。

3)對各自當前節點的相鄰節點進行操作，若相鄰節點不在open表中，則將其加入到各自的open表中，并把當前節點作為其父節點，若相鄰節點在open表中，則比較其當前的F值和open表中的F值，若小于open表中的F值，則用當前F值替換open表中的F值，并將其父節點更換為當前節點，若相鄰節點為障礙物或者在close表中，則跳過該節點。

4)重復循環步驟2)和3),當正向open表和反向open表為空時，表示無路徑，退出循環，或者雙向搜索出現交集點，表示找到路徑，算法結束。

雙向搜索A*算法從路徑的兩端開始搜索，相比于傳統A*算法極大地提高了路徑搜索效率。算法流程圖如圖2所示。

圖2 改進A*算法基本流程

4 仿真結果和分析

4.1 仿真環境

為驗證本文所提A*算法的有效性，采用仿真軟件平臺MATLAB R2020b進行仿真實驗，構建20*20的柵格地圖，如圖3所示，圖中的紅色圓圈代表起點，空心方格代表終點，實心黑色方格代表障礙物。

圖3 20*20柵格地圖

4.2 實驗分析

為了對四種算法進行比較分析，采用了兩種類型的地圖，分別使用四種算法在兩種地圖上進行路徑規劃，兩種地圖路徑規劃的結果如圖4,5所示，同時對比四種算法在兩種不同地圖上的路徑長度，搜索節點數和搜索時間，結果如表1所示。

圖4 地圖1中四種算法路徑規劃結果

表1 四種算法實驗數據對比

由表1可知，在地圖1中，改進A*算法比傳統A*算法的搜索時間減少了1.71s,搜索效率提高了14.83%，改進A*算法比BFS算法的路徑長度減少了30.71m，路徑長度減少了19.32%，改進A*算法比Dijkstra算法的搜索時間減少了80.05s，搜索效率提高了89.07%，搜索節點數比Dijkstra算法減少了128個，減少率達58.45%.在地圖2中，改進A*算法比傳統A*算法的搜索時間減少了6.08s，搜索效率提高了24.95%，搜索節點數比傳統A*算法減少了13個，減少率達9.28%，改進A*算法比BFS算法的路徑長度減少了50.71m，路徑長度減少了24.46%，改進A*算法比Dijkstra算法的搜索時間減少了192.53s，搜索效率提高了91.37%，搜索節點數比Dijkstra算法減少了217個，減少率達63.08%.因此，采用改進A*算法進行移動機器人路徑規劃，不僅搜索效率高，還可以得到一條最優的路徑，極大地提高了移動機器人路徑規劃的性能。

圖5 地圖2中四種算法路徑規劃結果

5 結論

針對移動機器人路徑規劃問題，傳統算法搜索效率低，搜索路徑不一定為最優，本文采用了改進A*算法進行移動機器人路徑規劃，提出了優化啟發函數，加快了算法的導向能力，采用雙向搜索的方式，極大地提高了算法的搜索效率，通過仿真實驗可知，改進A*算法在搜索效率上比傳統A*算法和Dijkstra算法要高，在路徑長度上比BFS算法要短，所以，采用改進A*算法能極大地提高移動機器人路徑規劃的性能，具有較大的應用前景。