基于A星算法的移動機器人路徑規(guī)劃應(yīng)用研究

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

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

關(guān)鍵詞：移動機器人;路徑規(guī)劃;A星算法;柵格法;MATLAB

中圖分類號：TP18 文獻(xiàn)標(biāo)識碼：A

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

1背景

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

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

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

3）機器人對于構(gòu)建的環(huán)境信息處于未知但已知障礙點的情況下，進(jìn)行合理的路徑探索過程;

4）機器人對于障礙物以及環(huán)境信息都未了解情況下，對結(jié)果進(jìn)行精確的規(guī)劃。

也有機器人對當(dāng)前環(huán)境的信息掌握程度的不同，可分為以下情況進(jìn)行討論：

1）機器人先一步一步將環(huán)境信息檢驗完成后，再對于總體的路徑進(jìn)行合理規(guī)劃;

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

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

2環(huán)境模型的建立

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

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

3.1 A星算法思想

A星算法是一種啟發(fā)性的算法，即由通過設(shè)定評估函數(shù)，全面性地對網(wǎng)格的各個節(jié)點進(jìn)行評估。而每個節(jié)點就是機器人所到達(dá)的位置，對每個位置點都進(jìn)行智能化評估，找到最好的位置，從而最終找到目標(biāo)位置。A星算法評估函數(shù)如下：

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

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

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

3.2曼哈頓距離

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

3.3 A星算法初步過程

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

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

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

具體實施步驟如下：

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

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

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

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

4實驗仿真與分析

4.1MATLAB環(huán)境建模

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

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

4.2運行仿真

通過MATLAB仿真軟件調(diào)節(jié)進(jìn)行程序運行。利用曼哈頓距離公式推算相應(yīng)的G值，計算各個時刻的F值，從而使移動機器人順著G值最小的點進(jìn)行移動，最后到達(dá)目標(biāo)點位置。

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

4.3實驗數(shù)據(jù)分析

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

5結(jié)束語

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