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

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

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

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

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

文章編號(hào)：1009-3044（2020）13-0001-03

1背景

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

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

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

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

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

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

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

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

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

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

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

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

3.1 A星算法思想

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

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

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

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

3.2曼哈頓距離

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

3.3 A星算法初步過程

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

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

3.4 A星算法實(shí)施流程圖及步驟

具體實(shí)施步驟如下：

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

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

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

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

4實(shí)驗(yàn)仿真與分析

4.1MATLAB環(huán)境建模

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

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

4.2運(yùn)行仿真

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

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

4.3實(shí)驗(yàn)數(shù)據(jù)分析

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

5結(jié)束語

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