基于A星算法的移動機器人路徑規劃應用研究

周宇杭 王文明 李澤彬 代宇浩 徐宇豪 柳晨陽

摘要：移動機器人路徑規劃一直是一個比較熱門的話題，A星算法以及其擴展性算法被廣范地應用于求解移動機器人的最優路徑。該文在研究機器人路徑規劃算法中，詳細闡述了傳統A星算法的基本原理，并通過柵格法分割了機器人路徑規劃區域，利用MATLAB仿真平臺生成了機器人二維路徑仿真地圖對其進行仿真實驗，并對結果進行分析和研究，為今后進一步的研究提供經驗。

關鍵詞：移動機器人;路徑規劃;A星算法;柵格法;MATLAB

中圖分類號：TP18 文獻標識碼：A

文章編號：1009-3044（2020）13-0001-03

1背景

路徑規劃是指在依靠特定的策略方法，符合一定的性能指標的前提下，從預先設定的起始點到達指定的目標點所形成的最佳路徑。隨著科技水平的不斷提高，路徑規劃技術得以在很多領域中廣泛應用。如小到游戲程序設計，大到巡航導彈的軌道路徑;從農業中的田地精確測繪，到工業機器人設計;車輛道路行駛的GPS定位，室內掃地機器人路徑規劃，無人機的無障礙自主飛行和城市道路精準網格規劃。至此，隨之衍生出各種路徑規劃方法，其中包括傳統算法和智能算法。由于傳統算法所需的內存比較大，儲存的空間也比較大，隨著數目增加，實施難度將會逐步增大。為了更好地研究路徑規劃問題，專注于智能算法，對其進行不斷研究和改進，從而能夠催生出新的智能算法。比較常見的智能算法有遺傳算法、人工勢場法、蟻群算法等。路徑規劃也有多種分類，可以根據機器人對當前環境信息掌握以及障礙物的情況，可以分為如下幾種情況：

1）機器人已經提前被告知周圍的環境信息以及障礙物隨機放置，處于靜止不動的情況下，移動機器人做出相應的路徑規劃;

2）機器人了解了當前的環境信息以及障礙物不斷更新的情況下，做出合理的判斷;

3）機器人對于構建的環境信息處于未知但已知障礙點的情況下，進行合理的路徑探索過程;

4）機器人對于障礙物以及環境信息都未了解情況下，對結果進行精確的規劃。

也有機器人對當前環境的信息掌握程度的不同，可分為以下情況進行討論：

1）機器人先一步一步將環境信息檢驗完成后，再對于總體的路徑進行合理規劃;

2）依靠相關的傳感器進行機器人的局部路徑規劃。（例如ROS機人，通過激光雷達對于障礙物信息得以確定）

筆者則是從A星算法人手，A星算法是一種典型的啟發性搜索算法，在人工智能方面應用廣泛。而筆者建立的環境信息中，障礙的位置是隨機變化的，如同上述分類中2），搜索出來的路徑，最后比較得出效率最高的最優路徑。

2環境模型的建立

為了大致模擬機器人的工作環境且不考慮機器人的大體形狀，所以就決定構建一個二維平面環境。為了精確模擬機器人所在區域的具體位置，采用柵格法，通過劃分形狀大小相等的區域，根據所設計的二維平面環境，確定機器人的工作空間區域大小，從而確定區域之中柵格的數目，保證機器人可以自由行走在已設定的環境中。用直角坐標系把已分割好工作空間在MATLAB中表示出來，最終將整個機器人可行走的區域劃分成12*12的柵格，同時將機器人和障礙物用分別用x，v形成的二維坐標來表示，圖中障礙物用黑色圓點來表示，其他空白未標記的位置為機器人可以行走的區域空間。

3基于柵格圖下A星算法的路徑規劃

3.1 A星算法思想

A星算法是一種啟發性的算法，即由通過設定評估函數，全面性地對網格的各個節點進行評估。而每個節點就是機器人所到達的位置，對每個位置點都進行智能化評估，找到最好的位置，從而最終找到目標位置。A星算法評估函數如下：

其中，F（n）是一種對總過程節點的評估函數，表示從起始節點到目標節點的總的估計代價，G（n）是表示在特定狀態空間下，從起始節點到達下一個節點的實際代價;H（n）是預測從當前節點到達目標節點的大致需要多少代價的最佳路徑的估計值，最短路徑（最優解）的關鍵在于選取代價函數，所以將其視為核心問題。對于預估啟發方法，通常選用曼哈頓預估方法，該方法在A星算法中較為常見使用，比較容易人手。

其中D為曼哈頓距離，ab為下所屬的矩形面積

常見的A星算法在擴展當前節點的周圍節點一般采用八鄰域法，即一次同時擴展當前節點周圍八個點。在柵格圖下，擴展節點圖有前后左右表示如下：

3.2曼哈頓距離

曼哈頓距離可以大概描述為在一個矩形區域間，某一點到達另一點距離是近似等于南北方向的垂直距離與東西方向上垂直距離之和，但是曼哈頓距離不是處于固定值，隨著節點的變化，曼哈頓值也會隨之進行相對應的變化。圖3中黑色曲線表示A節點到B節點的實際距離，黃綠色線代表歐式距離（AB直線距離），紅色線是曼哈頓等價距離。

3.3 A星算法初步過程

首先對于搜索區域進行簡化成一組可量化的節點，節點可以適應于不同類型的區域之中，因為在劃分搜索區域時，不僅僅是標準的矩形，可能是其他多邊形，所以此時用節點代替多邊形的某一區域則更準確和可靠。其次A星算法在執行時，會創建兩個列表，一個列表叫Open list（開放列表），另一個列表叫Close list（封閉列表）。將未擴展的節點放人Open list中存放，而將已擴展完的節點存放到Closelist中。在Openlist中，將列表中節點根據F值的大小，按照從大到小的順序進行排列，找到F值中的最小一個，并從Open list中刪除，將其添加到Close list中。由于起點只有唯一存在的節點，將它放入開放列表，同時讓其作為當前節點，通過當前節點搜索鄰近八個擴展節點，最后將起點放人封閉列表。如果這些節點不在開放列表中，則將這些擴展節點全部添加到開放列表中，并根據F值的大小，按照上述操作過程，選出F值最小的節點，添加到封閉列表，作為當前節點，并按照此情況繼續搜索其余節點;如果這些擴展點在開放列表中，那么在擴展的節點的開放列表中，令當前節點為父節點，路徑中所設計的代價函數將對這個節點進行評估，并且重新計算該節點的G值，與之前的G值進行比較，選擇出G值最小，作為當前節點的G值，再對F值進行重新計算，依次排列，循環上述搜索步驟，直至找到目標，將目標點添加到開放列表中，將開放列表中的各個節點逆序排出，從而得到一條搜索路徑，即為最佳路徑（最短路徑）。

A星算法作為一種典型的啟發性搜索算法，常常對其進行改進和優化，使在路徑規劃算法中更富有效率。通常在路徑規劃中，它不需要把所有的節點都一一搜索出來，速度非常快，但同時，它對于路徑規劃中機器人移動存在代價預測，所以有的時候會出現搜索不到最適路徑，這是其局限性。

3.4 A星算法實施流程圖及步驟

具體實施步驟如下：

1）進行初始化過程，生成一個存在障礙物環境，機器人對最初環境進行識別判斷。

2）隨機添加40個障礙物，判斷障礙物與之前障礙物是否有重復，如果有重復則重新添加。

3）機器人通過A星算法，識別出各個節點F值，判斷是否是可行點，如果是則將其添加到開放列表中。

4）機器人首先生成一條路徑，最后達到目標點，再將開放列表中的點逆順遍歷，最后判斷是最佳路徑，如果是將路徑顯示出來，不是的話，將顯示未搜索到合適路徑。

4實驗仿真與分析

4.1MATLAB環境建模

利用柵格法精確分割12*12方格作為機器人的路徑規劃的實驗區域，為了減小不必要的誤差，實驗中將移動機器人、目標點以及障礙物不考慮具體形狀和大小均看作質點，通過利用X，Y組成的二維坐標一一對應精確表示質點在所顯示地圖上的實際位置。隨機設置生成障礙數是40個，設置起始點坐標start[1，1]，設置目標點坐標goal[10，8]。有限面積范圍為11*11，生成邊界以及可視范圍。在MATLAB軟件中，設置相關的基本元素，使障礙物、移動機器人和目標點的顏色，形狀各不相同，便于區別。（障礙物是黑色實心圓點，是紅色實心圓點，障礙物是藍色實心）

如圖5、圖6所示，依據障礙物的隨機設置，在相同的基本的元素下，會出現不同地圖形式，可以獲得不同的最佳路線。

4.2運行仿真

通過MATLAB仿真軟件調節進行程序運行。利用曼哈頓距離公式推算相應的G值，計算各個時刻的F值，從而使移動機器人順著G值最小的點進行移動，最后到達目標點位置。

在二維平面下的有效范圍內，移動機器人的起始點的坐標為[1，1]，運動方向存在八個方向，隨機生成的40個障礙物，方向速度均為靜止。如圖6所示，用平滑的曲線連接各個點，得到最佳路線。

4.3實驗數據分析

如表1數據可知，在隨機放置40個障礙物的地圖中，移動機器人移動路徑長度及最大偏角不同，其算法的消耗代價也不相同。對于傳統A星算法，只是簡單地考慮到對于F值大小的如何判斷，而沒有過多的深入研究，可能會存在在可行區域內機器人會出現搜索不到目標的情況。另外對于偏角的過大也應該注意，為了使機器人能夠無碰撞地進行路徑探索，對于H（n）這個代價函數進行合適的分析以及設計就顯得很重要，在實際路徑規劃中，才能使得移動機器人更能成功尋找到最佳路徑。

5結束語

通過柵格法構建的移動機器人的二維平面模型，利用A星算法的啟發性特性，搜索速度快的特點，很好解決機器人在規劃好的二維平面環境中，隨機放置靜態障礙物時，移動機器人能在無碰撞狀態下，通過估計最小代價來尋找最佳路徑的問題。在已建立的環境中設置基礎信息，利用曼哈頓公式，計算對角距離，從而確定G值和F值，移動機器人通過起始點沿著G值最小點來尋找目標點。在MATTJAB軟件下，建立相對應的環境，實驗結果表明該方法在二維平面環境中可以在有障礙物情況下盡可能找到一條最佳路徑（最短路徑）。同時，還存在搜索不到合適路徑的時候。在之后的研究中，還需要解決的問題，盡量使得算法更加便捷和精準。