基于一種改進(jìn)A*算法的移動(dòng)機(jī)器人路徑規(guī)劃

孫煒+呂云峰+唐宏偉+薛敏

摘 要：針對(duì)全局路徑規(guī)劃問題提出了一種改進(jìn)的A*算法.首先，采用柵格方法建立環(huán)境模型，使用A*算法進(jìn)行初步的路徑規(guī)劃.其次，針對(duì)A*算法規(guī)劃的路徑冗余點(diǎn)較多以及路徑長(zhǎng)度和轉(zhuǎn)折角度較大的缺陷，提出將A*算法規(guī)劃出的路徑按較小的分割步長(zhǎng)進(jìn)行分割，得到一系列路徑節(jié)點(diǎn).最后，從起點(diǎn)開始依次用直線連接終點(diǎn)，當(dāng)直線沒有穿過障礙物時(shí)，則將中間路徑點(diǎn)剔除，減小路徑長(zhǎng)度和轉(zhuǎn)折角度.在仿真實(shí)驗(yàn)和實(shí)物實(shí)驗(yàn)中，分析和比較了本文算法與A*算法以及另一種改進(jìn)A*方法.另外還研究了在不同障礙率、任務(wù)點(diǎn)數(shù)量和分割步長(zhǎng)的情況下，本文算法與其他算法的優(yōu)劣.結(jié)果表明，本文算法能有效地減小路徑長(zhǎng)度和轉(zhuǎn)折角度.

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

中圖分類號(hào)：TP391.4 文獻(xiàn)標(biāo)志碼：A

Mobile Robot Path Planning Based on an Improved A* Algorithm SUN Wei1， LV Yunfeng1， TANG Hongwei1，2， XUE Min1

（1. College of Electrical and Information Engineering， Hunan University， Changsha 410082， China；

2. Department of Electrical Engineering， Shaoyang University， Shaoyang 422000， China）

Abstract：An improved A* algorithm was presented for global path planning of mobile robot. Firstly， the environment model was described using the grid method， and the preliminary path was obtained by traditional A* algorithm. Secondly， the path planned by A* method was flaw with much redundant points， large path length， and turning angle. The original path was partitioned by tiny step to obtain a series of path point. The finish point from the start point was connected by using straight line in sequence. To decrease the path length and turning angle， the path node can be removed if there are no obstacles on the line. The analysis and comparison between the proposed algorithm， traditional A* algorithm and another improved A* method were then given in the simulation experiment and physical experiments. Additionally， the merits of the proposed algorithm and other algorithms were compared when the obstacle rate， amount of task point， and step length were different. The experiment results show that the proposed algorithm effectively reduces the path length and turning angle.

Key words：mobile robot； path planning； A* algorithm； grid method

路徑規(guī)劃問題一直是智能機(jī)器人領(lǐng)域的一個(gè)研究熱點(diǎn).移動(dòng)機(jī)器人路徑規(guī)劃是指機(jī)器人基于機(jī)載傳感器獲得的環(huán)境信息規(guī)劃出一條從起點(diǎn)到終點(diǎn)的無碰、安全的可行路徑，并在此基礎(chǔ)上盡可能地優(yōu)化路徑[1].移動(dòng)機(jī)器人路徑規(guī)劃主要解決以下三個(gè)問題：第一是規(guī)劃出的路徑能使機(jī)器人從起點(diǎn)運(yùn)動(dòng)到終點(diǎn)；第二是采用相應(yīng)的算法使得機(jī)器人能夠避開環(huán)境中的障礙物；第三是在滿足前面兩點(diǎn)要求的基礎(chǔ)上，盡可能地優(yōu)化機(jī)器人的運(yùn)動(dòng)軌跡，通常是以規(guī)劃出的路徑最短作為優(yōu)化目標(biāo)[2].根據(jù)機(jī)器人對(duì)環(huán)境信息的感知程度，路徑規(guī)劃問題分為全局路徑規(guī)劃和局部路徑規(guī)劃.前者是指機(jī)器人在擁有全部環(huán)境信息的基礎(chǔ)上進(jìn)行的路徑規(guī)劃，又稱為離線路徑規(guī)劃；后者是指機(jī)器人在只有部分環(huán)境信息的基礎(chǔ)上進(jìn)行的路徑規(guī)劃，又稱為在線路徑規(guī)劃[3].本文主要討論全局路徑規(guī)劃.

移動(dòng)機(jī)器人路徑規(guī)劃的研究起始于20世紀(jì)70年代，到目前為止，已有大量的研究成果.針對(duì)全局路徑規(guī)劃，主要方法有可視圖法、拓?fù)鋵W(xué)法、人工智能算法和柵格法[4].文獻(xiàn)[5]針對(duì)自由空間法當(dāng)環(huán)境發(fā)生變化時(shí)，需要重新建立網(wǎng)絡(luò)連接模型，因而導(dǎo)致路徑規(guī)劃算法的環(huán)境適應(yīng)性差和實(shí)時(shí)性不高的缺陷，提出了一種基于可視圖的全局路徑規(guī)劃算法，該方法是直接在環(huán)境地圖上進(jìn)行路徑規(guī)劃，從而提高了算法的環(huán)境適應(yīng)能力和實(shí)時(shí)性.神經(jīng)網(wǎng)絡(luò)作為人工智能中一種重要的算法也被應(yīng)用到了移動(dòng)機(jī)器人路徑規(guī)劃領(lǐng)域，如文獻(xiàn)[6]，首先建立了一個(gè)障礙物罰函數(shù)的神經(jīng)網(wǎng)絡(luò)模型，并得到了整條路徑的能量函數(shù)；然后求得該函數(shù)的極小值點(diǎn)，且應(yīng)用了模擬退火算法避免陷入局部最優(yōu)；最終對(duì)得到的路徑進(jìn)行了優(yōu)化，使得路徑更加平滑和安全.除此之外，學(xué)者們還采用其它的智能算法來解決移動(dòng)機(jī)器人路徑規(guī)劃問題，如模糊邏輯[7-9]，蟻群算法[10]，粒子群優(yōu)化[11]，遺傳算法[12-13]等.

柵格法是將機(jī)器人運(yùn)動(dòng)環(huán)境建立成一系列具有二值信息的網(wǎng)格模型，再用搜索算法獲取最優(yōu)路徑.文獻(xiàn)[14]提出了一種改進(jìn)的A*算法，解決了傳統(tǒng)A*算法得到的路徑包含過多冗余點(diǎn)問題，并得到機(jī)器人在拐點(diǎn)處的最小轉(zhuǎn)折角度.但該算法并沒有減小機(jī)器人的路徑長(zhǎng)度和轉(zhuǎn)折角度.文獻(xiàn)[15]針對(duì)傳統(tǒng)A*算法得到的路徑折線多、累計(jì)轉(zhuǎn)折角度大的問題，提出了一種平滑A*算法，減少了不必要的路徑點(diǎn)并減小了路徑長(zhǎng)度和轉(zhuǎn)折角度.但只是在原有的路徑點(diǎn)上進(jìn)行處理，路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量有限.本文提出了另一種改進(jìn)的A*算法，將進(jìn)一步地減少移動(dòng)機(jī)器人的總路徑長(zhǎng)度和總轉(zhuǎn)折角度.

1 環(huán)境模型描述

眾所周知，移動(dòng)機(jī)器人工作環(huán)境地圖建立是路徑規(guī)劃中十分重要的一步.地圖建立是指將各種傳感器獲得的環(huán)境信息進(jìn)行融合并抽象成地圖模型[16].采用柵格單位描述二維環(huán)境信息非常簡(jiǎn)單有效，應(yīng)用廣泛.所以，本文也使用柵格法來建立移動(dòng)機(jī)器人工作環(huán)境模型.如圖1所示，柵格法將機(jī)器人工作環(huán)境分割成一系列具有相同尺寸的柵格，并將這些柵格分成兩類：可通過柵格和不可通過柵格.圖1中，空白柵格表示可通過柵格，即移動(dòng)機(jī)器人能自由通過的地方，黑色柵格表示不可通過柵格，即該柵格有靜態(tài)的障礙物.

為了方便研究又不失一般性，本文做出以下3點(diǎn)合理的假設(shè)：1）障礙物邊界是在實(shí)際邊界的基礎(chǔ)上加一個(gè)移動(dòng)機(jī)器人安全距離得到的，這樣就可以將移動(dòng)機(jī)器人看作是環(huán)境中的一個(gè)質(zhì)點(diǎn)；2）在這有限的二維空間中，機(jī)器人的移動(dòng)方向可以是任意的，并且不考慮高度的影響；3）在整個(gè)路徑規(guī)劃過程中，環(huán)境信息是不變的.圖1是一個(gè)10*10的移動(dòng)機(jī)器人工作環(huán)境，S是機(jī)器人起點(diǎn)，D是終點(diǎn).本文的工作就是找到一條從起點(diǎn)到終點(diǎn)的無碰的最優(yōu)路徑.

2 A*全局路徑規(guī)劃算法

A*算法是一種典型的啟發(fā)式搜索方法.通過估價(jià)函數(shù)來引導(dǎo)和決定它的搜索方向.從起點(diǎn)開始搜索周圍的節(jié)點(diǎn)，由估價(jià)函數(shù)得到每個(gè)節(jié)點(diǎn)的價(jià)值，選擇價(jià)值最低的作為下一個(gè)擴(kuò)展節(jié)點(diǎn)，循環(huán)重復(fù)這一過程直到搜索到終點(diǎn)，則停止搜索，獲得最終路徑.由于每一次都是以估價(jià)值最低的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)，所以最終的路徑代價(jià)是最低的.估價(jià)函數(shù)由式（1）給出：

式中：g（n）是狀態(tài)空間中從起始節(jié)點(diǎn)到節(jié)點(diǎn)n的實(shí)際代價(jià)，h（n）是從節(jié)點(diǎn)n到終點(diǎn)的啟發(fā)式估計(jì)代價(jià)函數(shù)，本文采用曼哈頓距離作為啟發(fā)式函數(shù)[14].

xd是目標(biāo)點(diǎn)的橫坐標(biāo)，yd是目標(biāo)點(diǎn)的縱坐標(biāo)，xn是節(jié)點(diǎn)n的橫坐標(biāo)，yn是節(jié)點(diǎn)n的縱坐標(biāo).

在A*算法搜索路徑的過程中，需要不斷地更新兩個(gè)列表，一個(gè)是開啟列表，另一個(gè)是關(guān)閉列表.開啟列表存儲(chǔ)的是所有的周圍節(jié)點(diǎn).A*算法從開啟列表中選擇具有最小估價(jià)值的節(jié)點(diǎn)作為下一個(gè)擴(kuò)展節(jié)點(diǎn).關(guān)閉列表存儲(chǔ)的是所有經(jīng)過的節(jié)點(diǎn)和環(huán)境中的障礙節(jié)點(diǎn).應(yīng)用A*算法進(jìn)行路徑搜索的具體流程如下所述：

Step1 把起始節(jié)點(diǎn)放入開啟列表.

Step2 檢查開啟列表是否為空，如果為空，則表示搜索失敗；不為空，則執(zhí)行Step3.

Step3 選取開啟列表中具有最低f（·）的節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)，對(duì)擴(kuò)展節(jié)點(diǎn)的每個(gè)周圍節(jié)點(diǎn)作如下處理：①當(dāng)該節(jié)點(diǎn)的周圍節(jié)點(diǎn)是障礙點(diǎn)或者是關(guān)閉列表中的節(jié)點(diǎn)，則沒有任何動(dòng)作；②當(dāng)該節(jié)點(diǎn)的周圍點(diǎn)不在開啟列表中，則把該節(jié)點(diǎn)的周圍節(jié)點(diǎn)添加進(jìn)開啟列表中，并將當(dāng)前擴(kuò)展節(jié)點(diǎn)作為該節(jié)點(diǎn)的周圍節(jié)點(diǎn)的父節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)的周圍節(jié)點(diǎn)的f（·）和g（·）；③當(dāng)該節(jié)點(diǎn)的周圍節(jié)點(diǎn)在開啟列表中，如果以當(dāng)前擴(kuò)展節(jié)點(diǎn)作為父節(jié)點(diǎn)，該節(jié)點(diǎn)的周圍節(jié)點(diǎn)的g（·）比原來更低，則把當(dāng)前擴(kuò)展節(jié)點(diǎn)作為父節(jié)點(diǎn)，并重新計(jì)算該節(jié)點(diǎn)的周圍節(jié)點(diǎn)的f（·）和g（·）.否則，不作任何改變.

Step4 將當(dāng)前擴(kuò)展節(jié)點(diǎn)放入關(guān)閉列表中，并檢查終點(diǎn)是否在開啟列表中.如果不在開啟列表中，則跳回Step2繼續(xù)搜索；否則，最優(yōu)路徑已經(jīng)找到，結(jié)束搜索.

Step5 從終點(diǎn)開始，沿著每一個(gè)父節(jié)點(diǎn)移動(dòng)，回到起始點(diǎn)，這就是最終的路徑.

3 改進(jìn)的A*算法

采用A*算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃雖然能獲得一條安全無碰的路徑，但路徑點(diǎn)較多，折線多，導(dǎo)致路徑的總長(zhǎng)度和總轉(zhuǎn)折角度較大.這在移動(dòng)機(jī)器人實(shí)際應(yīng)用中將消耗更多的能量和花費(fèi)更多的時(shí)間.本文提出了一種改進(jìn)的A*算法，能有效地減少路徑長(zhǎng)度和轉(zhuǎn)折角度.

圖2的實(shí)線是在一個(gè)任意環(huán)境中A*算法規(guī)劃出的路徑，本文方法是在原路徑的基礎(chǔ)上，從起點(diǎn)開始以較小的步長(zhǎng)分割原路徑，得到更多路徑點(diǎn)，如圖2的路徑點(diǎn)a1到a20.按照一定的規(guī)則剔除冗余路徑點(diǎn)，將剩余的路徑點(diǎn)按順序連接，最終獲得更加優(yōu)化的路徑.

圖3是本文算法的流程圖，圖中符號(hào)的定義如下：

k為分割路徑的步長(zhǎng)；c，m，i分別是當(dāng)前路徑點(diǎn)下標(biāo)、待連接路徑點(diǎn)下標(biāo)和新路徑點(diǎn)下標(biāo)；A為以步長(zhǎng)k分割原始路徑得到的路徑點(diǎn)集合A={a1，a2，…，aN}，其中a1是起始點(diǎn)，aN是終點(diǎn)；ac為當(dāng)前路徑點(diǎn)；am為當(dāng)前待連接點(diǎn)；

lcm為連接ac與am的直線；lc，c+1為連接ac與ac+1的直線；B為新的路徑點(diǎn)集合，B={b1，b2，…，bs }.

注意，以步長(zhǎng)k分割路徑是在原路徑的直線段進(jìn)行的.例如，對(duì)圖4中A*算法得到的路徑進(jìn)行分割，先進(jìn)行直線段L1的分割，從起點(diǎn)開始依次得到路徑點(diǎn)a1，a2，…，a7，此時(shí)a8與原路徑點(diǎn)的距離小于步長(zhǎng)k，則將原路徑點(diǎn)作為a8，并從路徑點(diǎn)a8開始重復(fù)上述過程，分割直線段L2和L3直到將終點(diǎn)作為路徑點(diǎn)a20時(shí)，分割過程結(jié)束.

圖4中的實(shí)線是在任意環(huán)境中A*算法規(guī)劃出的路徑1，由直線段L1 ，L2 和L3組成，本文方

法規(guī)劃出的路徑3由直線段La1a6，La6a9，La9a10和La10a20組成，其中Laiaj是指起點(diǎn)為ai，終點(diǎn)為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長(zhǎng)度明顯大于路徑3的路徑長(zhǎng)度.另外，路徑1的總轉(zhuǎn)折角度：

路徑3的總轉(zhuǎn)折角度：

其中α2=∠ba6a9 ， β2=∠da9a10，γ1=∠ca10a20.而α1=α2+β2，β1=γ1+γ2，γ2=∠a15a20a10，則θ1=α1+β1=α2+β2+γ1+γ2=θ3+γ2.所以，θ1>θ3.相對(duì)于A*算法，本文方法縮短了總路徑長(zhǎng)度，減小了總轉(zhuǎn)折角度.

文獻(xiàn)[15]提出的平滑A*算法直接地剔除A*算法規(guī)劃出的路徑點(diǎn)，使得路徑更加平滑.而本文方法是先進(jìn)行分割，再剔除冗余的路徑點(diǎn).圖4中直線段La1a8，La8a11和La11a20是文獻(xiàn)[15]中平滑A*算法得到的路徑2.顯然，路徑2的長(zhǎng)度大于路徑3的長(zhǎng)度.另外，路徑2的轉(zhuǎn)折角度：

其中α1=∠ba8a9，β3=∠a15a20a10，而α1=α2+β2，β3=γ1+γ3，γ3=∠a11a20a10，則θ2=α1+β3=α2+β2+γ1+γ3=θ3+γ3，所以θ2>θ3.相對(duì)于文獻(xiàn)[15]提出的平滑A*算法，本文方法得到的路徑也更加優(yōu)化.

4 實(shí) 驗(yàn)

為了驗(yàn)證本文算法的可行性和有效性，進(jìn)行了計(jì)算機(jī)仿真實(shí)驗(yàn)和實(shí)物實(shí)驗(yàn).考察了不同情形下算法的性能，以下將從4個(gè)方面進(jìn)行仿真實(shí)驗(yàn)： 1）探究同樣的條件下本文算法與A*算法以及文獻(xiàn)[15]的平滑A*算法的性能；2）環(huán)境障礙率p對(duì)各算法的影響；3）不同目標(biāo)點(diǎn)數(shù)n下算法的優(yōu)劣；4）本文算法在不同的分割步長(zhǎng)k下的效果.以下的4種情形都是在邊長(zhǎng)為200個(gè)單位的正方形環(huán)境下進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)環(huán)境分割成20*20個(gè)柵格元素，每個(gè)元素是邊長(zhǎng)為10個(gè)單位的正方形柵格.將實(shí)驗(yàn)環(huán)境分割成20*20個(gè)柵格元素，每個(gè)元素是邊長(zhǎng)為10個(gè)單位的正方形柵格.

情形1 環(huán)境障礙率（障礙柵格數(shù)量占總柵格數(shù)量的比例）p=30%，取本文算法的分割步長(zhǎng)k=0.1，目標(biāo)數(shù)n=1即只有一個(gè)終點(diǎn)，起點(diǎn)是（4，4），終點(diǎn)是（198，198），機(jī)器人在起點(diǎn)的角度為90°.進(jìn)行了50次實(shí)驗(yàn)，圖5和圖6是不同算法規(guī)劃出的路徑長(zhǎng)度和轉(zhuǎn)折角度，表1是3種算法50次實(shí)驗(yàn)的各項(xiàng)平均值比較.從實(shí)驗(yàn)結(jié)果中可以看出，本文提出的改進(jìn)A*算法相對(duì)于A* 算法和文獻(xiàn)[15]的平滑A* 算法，有效地減少了路徑長(zhǎng)度和轉(zhuǎn)折角度.注意，雖然環(huán)境障礙率都是30%，但障礙柵格是隨機(jī)分布的，這就導(dǎo)致了不同的環(huán)境復(fù)雜度，所以同樣的算法和實(shí)驗(yàn)條件在不同的實(shí)驗(yàn)次數(shù)下卻有不同的實(shí)驗(yàn)結(jié)果.

情形2 考察在不同的環(huán)境障礙率下，各個(gè)算法的性能.令分割步長(zhǎng)k=0.1，目標(biāo)數(shù)n為1，起點(diǎn)（4，4）、終點(diǎn)（198，198），機(jī)器人在起點(diǎn)的角度為90°.分別在環(huán)境障礙率為10%，20%，30%，40%，50%時(shí)，進(jìn)行了50次實(shí)驗(yàn)，并求得不同障礙率下路徑長(zhǎng)度的均值和轉(zhuǎn)折角度的均值，實(shí)驗(yàn)結(jié)果如圖7、圖8所示.可以看出，一方面當(dāng)環(huán)境障礙率增大時(shí)，各個(gè)算法得到的路徑長(zhǎng)度和轉(zhuǎn)折角度也在不斷增大.這是因?yàn)榄h(huán)境障礙率一定程度上代表了環(huán)境的復(fù)雜度，當(dāng)環(huán)境越復(fù)雜時(shí)，那么規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度也就越大；另一方面，在圖7和圖8中，方框內(nèi)的數(shù)據(jù)是本文算法相對(duì)于A*算法路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量.當(dāng)環(huán)境障礙率越大時(shí)，路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量也不斷增大，這說明相對(duì)于A*算法，本文方法更加適合在障礙物較多的環(huán)境中使用.

情形3 在移動(dòng)機(jī)器人的工作空間中可能存在多個(gè)任務(wù)點(diǎn)，這就意味著環(huán)境中會(huì)有多個(gè)不同的終點(diǎn).這里將研究當(dāng)機(jī)器人有多個(gè)任務(wù)點(diǎn)時(shí)，各個(gè)路徑規(guī)劃算法的優(yōu)劣性.這里做以下兩點(diǎn)規(guī)定：1）對(duì)環(huán)境中的任務(wù)點(diǎn)進(jìn)行了編號(hào)，任務(wù)點(diǎn)1，（198，198）；任務(wù)點(diǎn)2，（4，198）；任務(wù)點(diǎn)3，（95，95）；任務(wù)點(diǎn)4，（198，4）.2）當(dāng)機(jī)器人有n個(gè)任務(wù)需要執(zhí)行時(shí)，它的執(zhí)行順序是由任務(wù)點(diǎn)1遞增至任務(wù)點(diǎn)n.取障礙率p=30%，分割步長(zhǎng)k=0.1，分別在n等于1，2，3，4時(shí)，進(jìn)行了50次實(shí)驗(yàn)，并求得路徑長(zhǎng)度和轉(zhuǎn)折角度的均值，實(shí)驗(yàn)結(jié)果如圖9和圖10所示，圖中方框內(nèi)的數(shù)據(jù)是本文算法相對(duì)于A*算法路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量.顯而易見，當(dāng)機(jī)器人的任務(wù)點(diǎn)越多，本文算法相對(duì)于A*算法規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度的減少量越大.

情形4 本文算法中存在一個(gè)分割步長(zhǎng)k，這里將考察參數(shù)k對(duì)算法效果的影響.令環(huán)境障礙率p=30%，僅有一個(gè)任務(wù)點(diǎn)（198，198），起點(diǎn)是（4，4），機(jī)器人在起點(diǎn)的角度為90°.在不同的分割步長(zhǎng)下進(jìn)行了50實(shí)驗(yàn)，并求出相應(yīng)的均值，實(shí)驗(yàn)結(jié)果如圖11和圖12所示.可以得出這樣的結(jié)論：當(dāng)分割步長(zhǎng)越小時(shí)，本文算法得到的路徑長(zhǎng)度和轉(zhuǎn)折角度也越小.顯然，這是因?yàn)榉指畈介L(zhǎng)越小，路徑分割得越精細(xì)，路徑長(zhǎng)度和轉(zhuǎn)折角度也就相應(yīng)減小.

在實(shí)物實(shí)驗(yàn)中，本文采用的移動(dòng)機(jī)器人是Turtlebot2，移動(dòng)底座的最大移動(dòng)速度：0.7 m/s，最大角速度：180°/s.采用ThinkPad E450C筆記本電腦作為移動(dòng)機(jī)器人的控制器.移動(dòng)機(jī)器人的實(shí)際運(yùn)動(dòng)空間如圖13所示，是3.6 m×6.6 m的矩形環(huán)境.起點(diǎn)（0.9 m，0.9 m），終點(diǎn)（2.7 m，6.3 m），機(jī)器人在起點(diǎn)的角度為90°.為了使用本文改進(jìn)的A*算法進(jìn)行路徑規(guī)劃，需要先建立環(huán)境的柵格模型，設(shè)置柵格元素為0.6 m×0.6 m的正方形，對(duì)實(shí)際障礙物進(jìn)行膨化處理，映射成圖14的黑色柵格.分別采用A*算法、文獻(xiàn)[15]的平滑A*算法和本文算法進(jìn)行移動(dòng)機(jī)器人的路徑規(guī)劃.圖14的直線段La1a5，La5a11，La11a21，La21a27，La27a32，La32a44 和

La44a53是A*算法規(guī)劃出的路徑；文獻(xiàn)[15]中平滑A*算法得到的路徑是直線段La1a5，La5a11，La11a21，La21a27，La27a32和La32a53；直線段La1a8，La8a24，La24a25，La25a35和La35a53是本文算法得到的結(jié)果.由于移動(dòng)機(jī)器人的運(yùn)動(dòng)總是存在外界干擾和運(yùn)動(dòng)精度等因素，其運(yùn)動(dòng)的實(shí)際路徑長(zhǎng)度與轉(zhuǎn)折角度總是比規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度要稍稍大一些，如表2所示.但無論是規(guī)劃的路徑長(zhǎng)度和轉(zhuǎn)折角度，還是移動(dòng)機(jī)器人實(shí)際運(yùn)動(dòng)的路徑長(zhǎng)度和轉(zhuǎn)折角度，本文算法得到的實(shí)驗(yàn)結(jié)果都比A*算法和文獻(xiàn)[15]平滑A*算法更加優(yōu)化.

5 結(jié) 論

采用A*算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃，可以得到一條從起點(diǎn)連接終點(diǎn)的無碰安全路徑，但路徑的冗余點(diǎn)較多，路徑長(zhǎng)度和轉(zhuǎn)折角度較大.針對(duì)這些問題，本文提出了一種改進(jìn)A*算法，能有效地減少路徑冗余點(diǎn)和減小路徑長(zhǎng)度及轉(zhuǎn)折角度.并且，分析比較了不同的環(huán)境障礙率、任務(wù)點(diǎn)數(shù)量、分割步長(zhǎng)對(duì)算法性能的影響.一方面，相對(duì)于A*算法，本文方法更加適合多任務(wù)點(diǎn)，高障礙率環(huán)境下的移動(dòng)機(jī)器人路徑規(guī)劃；另一方面，采用較小的分割步長(zhǎng)可使得規(guī)劃出的路徑更加優(yōu)化.

參考文獻(xiàn)

[1] 席裕庚，張純剛.一類動(dòng)態(tài)不確定環(huán)境下機(jī)器人的滾動(dòng)路徑規(guī)劃[J].自動(dòng)化學(xué)報(bào)，2002，28（2）： 161-175.

XI Yugeng， ZHANG Chungang.Rolling path planning of mobile robot in a kind of dynamic uncertain environment[J]. Acta Automatica Sinica， 2002，28（2）：161-175.（In Chinese）

[2] 張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報(bào)，2005， 17（2）： 439-443.

ZHANG Handong， ZHENG Rui， CEN Yuwan. Present situation and future development of mobile robot path planning technology[J]. Journal of System Simulation， 2005，17（2）：439-443.（In Chinese）

[3] 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010， 25（7）： 961-967.

ZHU Daqi， YAN Mingzhong. Survey on technology of mobile robot path planning[J]. Control and Decision， 2010，25（7）：961-967.（In Chinese）

[4] 吳乙萬，黃智.基于動(dòng)態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，40（1）： 33-37.

WU Yiwan， HUANG Zhi. Dynamic virtual obstacle based local path planning for intelligent vehicle[J]. Journal of Hunan University：Natural Sciences， 2013，40（1）：33-37.（In Chinese）

[5] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法[J].沈陽工業(yè)大學(xué)學(xué)報(bào)，2009，31（2）： 225-229.

YANG Huaiqing， XIAO Xinggui， YAO Dong. A V-graph based global path planning algorithm for mobile robot[J]. Journal of Shenyang University of Technology， 2009，31（2）：225-229.（In Chinese）

[6] 梁瑾，宋科璞.神經(jīng)網(wǎng)絡(luò)在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào)，2010，22（增刊1）： 269-272.

LIANG Jin， SONG Kepu. The application of neural network in mobile robot path planning[J]. Journal of System Simulation， 2010，22（s1）：269-272.（In Chinese）

[7] 郝冬，劉斌.基于模糊邏輯行為融合路徑規(guī)劃方法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（3）： 660-663.

HAO Dong， LIU Bin. Behavior fusion path planning method for mobile robot based on fuzzy logic[J]. Computer Engineering and Design， 2010，30（3）：660-663.（In Chinese）

[8] ARPINO C P， MELENDEZ W M， GUZMAN J， et al. Fuzzylogic based speed planning for autonomous navigationunder velocity field control[C]//2009 IEEE Int Conf on Mechatronics. Malaga， 2009： 201-212.

[9] ZOUMPONOS G T， ASPRAGATHOS N A. Fuzzy logic pathplanning for the robotic placement of fabrics on a worktable[J]. Robotics and Computer Integrated Manufacturing， 2008， 24 （2）： 174-186.

[10]鄧高峰，張雪萍，劉彥萍.一種障礙環(huán)境下機(jī)器人路徑規(guī)劃的蟻群粒子群算法[J].控制理論與應(yīng)用，2009，26（8）： 879-883.

DENG Gaofeng， ZHANG Xueping， LIU Yanping. Ant colony optimization and particle swarm optimization for robot-path planning in obstacle environment[J]. Control Theory & Applications， 2009，26（8）：879-883.（In Chinese）

[11]吳憲祥，郭寶龍，王娟.基于粒子群三次樣條優(yōu)化的移動(dòng)機(jī)器人路徑規(guī)劃算法[J].機(jī)器人，2009，31（6）： 556-560.

WU Xianxiang， GUO Baolong， WANG Juan. Mobile robot path planning algorithm based on particle swarm optimization of cubic splines[J]. ROBOT， 2009，31（6）：556-560.（In Chinese）

[12]王雪松，高陽，程玉虎，等.知識(shí)引導(dǎo)遺傳算法實(shí)現(xiàn)機(jī)器人路徑規(guī)劃[J].控制與決策，2009，24（7）： 1043-1049.

WANG Xuesong， GAO Yang， CHENG Yuhu， et al. Knowledge-guided genetic algorithm for path planning of robot[J]. Control and Decision， 2009，24（7）：1043-1049.（In Chinese）

[13]THEODORE M， KAVEH A， ROGER L W. Genetic algorithms for autonomous robot navigation[J]. IEEE In Strumentation and Measurement Magazine， 2007，12（1）： 26-31.

[14]王殿君.基于改進(jìn)A*算法的室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃[J].清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2012， 52（8）： 1085-1089.

WANG Dianjun. Indoor mobile-robot path planning based on an improved A* algorithm[J]. Journal of Tsinghua University：Science and Technology，2012，52（8）：1085-1089.（In Chinese）

[15]王紅衛(wèi)，馬勇，謝勇，等.基于平滑A*算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，38（11）： 1647-1651.

WANG Hongwei， MA Yong， XIE Yong， et al. Mobile robot optimal path planning based on smoothing A* algorithm[J]. Journal of Tongji University：Natural Science， 2010，38（11）：1647-1651.（In Chinese）

[16]朱慶保，張玉蘭.基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法[J].機(jī)器人，2005，27（2）： 132-136.

ZHU Qingbao， ZHANG Yulan. An ant colony algorithm based on grid method for mobile robot path planning[J]. ROBOT， 2005，27（2）：132-136.（In Chinese）