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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step5 從終點開始，沿著每一個父節(jié)點移動，回到起始點，這就是最終的路徑.

3 改進的A*算法

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

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

圖3是本文算法的流程圖，圖中符號的定義如下：

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

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

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

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

法規(guī)劃出的路徑3由直線段La1a6，La6a9，La9a10和La10a20組成，其中Laiaj是指起點為ai，終點為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長度明顯大于路徑3的路徑長度.另外，路徑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.相對于A*算法，本文方法縮短了總路徑長度，減小了總轉(zhuǎn)折角度.

文獻[15]提出的平滑A*算法直接地剔除A*算法規(guī)劃出的路徑點，使得路徑更加平滑.而本文方法是先進行分割，再剔除冗余的路徑點.圖4中直線段La1a8，La8a11和La11a20是文獻[15]中平滑A*算法得到的路徑2.顯然，路徑2的長度大于路徑3的長度.另外，路徑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.相對于文獻[15]提出的平滑A*算法，本文方法得到的路徑也更加優(yōu)化.

4 實 驗

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

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

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

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

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

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

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

5 結(jié) 論

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

參考文獻

[1] 席裕庚，張純剛.一類動態(tài)不確定環(huán)境下機器人的滾動路徑規(guī)劃[J].自動化學(xué)報，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] 張捍東，鄭睿，岑豫皖.移動機器人路徑規(guī)劃技術(shù)的現(xiàn)狀與展望[J].系統(tǒng)仿真學(xué)報，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] 朱大奇，顏明重.移動機器人路徑規(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] 吳乙萬，黃智.基于動態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法[J].湖南大學(xué)學(xué)報：自然科學(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] 楊淮清，肖興貴，姚棟.一種基于可視圖法的機器人全局路徑規(guī)劃算法[J].沈陽工業(yè)大學(xué)學(xué)報，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ò)在移動機器人路徑規(guī)劃中的應(yīng)用[J].系統(tǒng)仿真學(xué)報，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].計算機工程與設(shè)計，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)境下機器人路徑規(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)化的移動機器人路徑規(guī)劃算法[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]王雪松，高陽，程玉虎，等.知識引導(dǎo)遺傳算法實現(xiàn)機器人路徑規(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]王殿君.基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃[J].清華大學(xué)學(xué)報：自然科學(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*算法的移動機器人路徑規(guī)劃[J].同濟大學(xué)學(xué)報：自然科學(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]朱慶保，張玉蘭.基于柵格法的機器人路徑規(guī)劃蟻群算法[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）