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

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

2、鍵詞：移動(dòng)機(jī)器人；路徑規(guī)劃；a*f法；柵格中圖分類號(hào)：tp391.4文獻(xiàn)標(biāo)志碼：amobile robot path planning based on an improved a* algorithm sun weil, lv yunfengl， tang hongweil，2， xue mini(1. college of electrical and information engineering， hunan university， changsha 410082， china；2. department of electrical engineering，shaoyang unive

3、rsity，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 fla

4、w 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 ca

5、n 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 a

6、lgorithms 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è)研宄?

7、岬?.移動(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ǔ)上

8、進(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ò)模 型，并

9、得到了整條路徑的能量函數(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ī)器人的路徑 長度和轉(zhuǎn)折角度.文獻(xiàn)15針對(duì)傳統(tǒng)a*算法得到的路 徑折線多、累計(jì)轉(zhuǎn)

10、折角度大的問題，提出了一種平滑 a*算法，減少了不必要的路徑點(diǎn)并減小了路徑長度和 轉(zhuǎn)折角度.但只是在原有的路徑點(diǎn)上進(jìn)行處理，路徑長 度和轉(zhuǎn)折角度的減少量有限.本文提出了另一種改進(jìn) 的a*算法，將進(jìn)一步地減少移動(dòng)機(jī)器人的總路徑長度 和總轉(zhuǎn)折角度.1環(huán)境模型描述眾所周知，移動(dòng)機(jī)器人工作環(huán)境地圖建立是路徑 規(guī)劃中十分重要的一步.地圖建立是指將各種傳感器 獲得的環(huán)境信息進(jìn)行融合并抽象成地圖模型16.采用 柵格單位描述二維環(huán)境信息非常簡單有效，應(yīng)用廣泛. 所以，本文也使用柵格法來建立移動(dòng)機(jī)器人工作環(huán)境 模型.如圖1所75，柵格法將機(jī)器人工作環(huán)境分割成一 系列具有相同尺寸的柵格，并將這些柵格分成兩類： 可

11、通過柵格和不可通過柵格.圖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*算法是一

12、種典型的啟發(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*算法搜索路徑的過程中，需要不斷地更新

13、兩個(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)行路徑搜索的具體流程如下所述：stepl把起始節(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)開啟 列表

14、中，并將當(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ò)i節(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ī)劃雖然能獲 得一條

15、安全無碰的路徑，但路徑點(diǎn)較多，折線多，導(dǎo) 致路徑的總長度和總轉(zhuǎn)折角度較大.這在移動(dòng)機(jī)器人 實(shí)際應(yīng)用中將消耗更多的能量和花費(fèi)更多的?r間.本 文提出了一種改進(jìn)的a*算法，能有效地減少路徑長度 和轉(zhuǎn)折角度.2的實(shí)線是在一個(gè)任意環(huán)境中a*算法規(guī)劃出的路徑，本文方法是在原路徑的基礎(chǔ)上，從起點(diǎn)開始以 較小的步長分割原路徑，得到更多路徑點(diǎn)，如圖2的 路徑點(diǎn)al到a20.按照一定的規(guī)則剔除冗余路徑點(diǎn)，將 剩余的路徑點(diǎn)按順序連接，最終獲得更加優(yōu)化的路徑.3是本文算法的流程中符號(hào)的定義如下:k為分割路徑的步長;m，i分別是當(dāng)前路徑點(diǎn)下標(biāo)、待連接路徑點(diǎn)下標(biāo)和新路徑點(diǎn)下標(biāo)；a為以步 長k分割原始路徑得到的路徑點(diǎn)集合

16、a=al, a2, an，其中al是起始點(diǎn)，an是終點(diǎn)；ac為當(dāng)前路徑點(diǎn); am為當(dāng)前待連接點(diǎn)；icm為連接ac與am的直線；lc，c+1為連接ac 與ac+1的直線；b為新的路徑點(diǎn)集合，b=bl, b2, bs .注意，以步長k分割路徑是在原路徑的直線段進(jìn) 行的.例如，對(duì)圖4中a*算法得到的路徑進(jìn)行分割，先進(jìn)行直線段l1的分割，從起點(diǎn)開始依次得到路徑點(diǎn) al, a2,a7,此時(shí)a8與原路徑點(diǎn)的距離小于步長k,則將原路徑點(diǎn)作為a8,并從路徑點(diǎn)a8開始重復(fù)上 述過程，分割直線段l2和l3直到將終點(diǎn)作為路徑點(diǎn) a20時(shí)，分割過程結(jié)束.圖4中的實(shí)線是在任意環(huán)境中a*算法規(guī)劃出的路 徑1，由直線段li

17、，l2和l3組成，本文方法規(guī)劃出的路徑3由直線段lala6, la6a9, la9al0 和lal0a20組成，其中l(wèi)aiaj是指起點(diǎn)為ai，終點(diǎn)為aj的直線段.由圖4可以直觀地看出：路徑1的路徑長度 明顯大于路徑3的路徑長度.另外，路徑1的總轉(zhuǎn)折角 度：路徑3的總轉(zhuǎn)折角度：其中 a2=zba6a9， 2=zda9alo, y 1=z cal0a20.而 a 1= a 2+3 2，3 1= y 1+ y 2, y 2=z al5a20al0,則 0 1= a 1+1= a 2+ 3 2+ y 1+ y 2= 0 3+丫 2.所以，0 l> 0 3.相對(duì)于a*算法，本文方法縮短了 總路徑長

18、度，減小了總轉(zhuǎn)折角度.文獻(xiàn)15提出的平滑a*算法直接地剔除a*算法規(guī) 劃出的路徑點(diǎn)，使得路徑更加平滑.而本文方法是先進(jìn)行分割，再剔除冗余的路徑點(diǎn).圖4中直線段lala8, la8all和lalla2o是文獻(xiàn)15中平滑a*算法得到的路徑2.顯然，路徑2的長度大于路徑3的長度.另外，路 徑2的轉(zhuǎn)折角度：其中 a l=zba8a9，3 3=zal5a20al0,而 a 1= a 2+32， 3=yl+y3, y 3=zalla20al0,貝 lj 0 2=a 1+ 3 3= a 2+ 3 2+ y 1+ y 3= 0 3+ y 3,所以 9 2> 0 3.相對(duì)于文獻(xiàn)15提出的平滑a*算法，本文

19、方法得到的路徑也 更加優(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）本文算法在不同的 分割步長k下的效果.以下的4種情形都是在邊長為 200個(gè)單位的正方形環(huán)境下進(jìn)行實(shí)驗(yàn)，將實(shí)驗(yàn)環(huán)境分 割成20*20個(gè)柵格元素，每個(gè)元素是邊長為10個(gè)單位 的正方形柵格.將實(shí)驗(yàn)環(huán)境分割成20*20個(gè)柵格元素， 每個(gè)元素是邊長為10個(gè)單位的正方形柵格.情形1環(huán)境障礙率（障礙柵格數(shù)

20、量占總柵格數(shù)量 的比例）p=30%，取本文算法的分割步長k=0.1，目標(biāo) 數(shù)n=l即只有一個(gè)終點(diǎn)，起點(diǎn)是（4, 4），終點(diǎn)是（198， 198），機(jī)器人在起點(diǎn)的角度為90° .進(jìn)行了 50次實(shí)驗(yàn)，圖5和圖6是不同算法規(guī)劃出的路徑長度和轉(zhuǎn)折角度， 表1是3種算法50次實(shí)驗(yàn)的各項(xiàng)平均值比較.從實(shí)驗(yàn) 結(jié)果中可以看出，本文提出的改進(jìn)a*算法相對(duì)于a* 算法和文獻(xiàn)15的平滑a*算法，有效地減少了路徑長 度和轉(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)境障礙率

21、下，各個(gè)算法的 性能.令分割步長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)，并求得不同障礙率下路徑長度的均值 和轉(zhuǎn)折角度的均值，實(shí)驗(yàn)結(jié)果如圖7、圖8所示.可以 看出，一方面當(dāng)環(huán)境障礙率增大時(shí)，各個(gè)算法得到的 路徑長度和轉(zhuǎn)折角度也在不斷增大.這是因?yàn)榄h(huán)境障 礙率一定程度上代表了環(huán)境的復(fù)雜度，當(dāng)環(huán)境越復(fù)雜 時(shí)，那么規(guī)劃的路徑長度和轉(zhuǎn)折角度也就越大；另一 方面，在圖7和圖8中，方框內(nèi)的數(shù)據(jù)是本文算法相 對(duì)于a*算法路徑長度和轉(zhuǎn)折角度的減少量.當(dāng)環(huán)

22、境障 礙率越大時(shí)，路徑長度和轉(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%，分 割步長k=0.1，分別在n等于1，2, 3, 4時(shí)，進(jìn)行了

23、50次實(shí)驗(yàn)，并求得路徑長度和轉(zhuǎn)折角度的均值，實(shí)驗(yàn)結(jié)果如圖9和圖10所示，圖中方框內(nèi)的數(shù)據(jù)是本文算 法相對(duì)于a*算法路徑長度和轉(zhuǎn)折角度的減少量.顯而 易見，當(dāng)機(jī)器人的任務(wù)點(diǎn)越多，本文算法相對(duì)于a* 算法規(guī)劃的路徑長度和轉(zhuǎn)折角度的減少量越大.情形4本文算法中存在一個(gè)分割步長k，這里將 考察參數(shù)k對(duì)算法效果的影響.令環(huán)境障礙率p=30%, 僅有一個(gè)任務(wù)點(diǎn)（198，198），起點(diǎn)是（4，4），機(jī)器 人在起點(diǎn)的角度為90° .在不同的分割步長下進(jìn)行了50實(shí)驗(yàn)，并求出相應(yīng)的均值，？?驗(yàn)結(jié)果如圖11和 12所示.可以得出這樣的結(jié)論：當(dāng)分割步長越小時(shí)，本 文算法得到的路徑長度和轉(zhuǎn)折角度也越小.顯然，

24、這是因?yàn)榉指畈介L越小，路徑分割得越精細(xì)，路徑長度和 轉(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 mx6.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 x0.6m的正方形，對(duì)實(shí)際障礙物進(jìn)行膨化處

25、理，映射 成圖14的黑色柵格.分別采用a*算法、文獻(xiàn)15的平 滑a*算法和本文算法進(jìn)行移動(dòng)機(jī)器人的路徑規(guī)劃.圖 14 的直線段 lala5, la5all, lalla21, la21a27, la27a32, la32a44 和la44a53是a*算法規(guī)劃出的路徑；文獻(xiàn)15中平 滑a*算法得到的路徑是直線段lala5, la5all, lalla21, la21a27, la27a32 和 la32a53；直線段 lala8, la8a24, la24a25, la25a35和la35a53是本文算法得到的結(jié)果.由于移動(dòng)機(jī)器人的運(yùn)動(dòng)總是存在外界干擾和運(yùn)動(dòng)精度 等因素，其運(yùn)動(dòng)的實(shí)際路徑長度與轉(zhuǎn)

26、折角度總是比規(guī) 劃的路徑長度和轉(zhuǎn)折角度要稍稍大一些，如表2所示.但無論是規(guī)劃的路徑長度和轉(zhuǎn)折角度，還是移動(dòng)機(jī)器 人實(shí)際運(yùn)動(dò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)較多，路徑長度和轉(zhuǎn)折角度較大.針對(duì)這些問題，本 文提出了一種改進(jìn)a*算法，能有效地減少路徑冗余點(diǎn) 和減小路徑長度及轉(zhuǎn)折角度.并且，分析比較了不同的 環(huán)境障礙率、任務(wù)點(diǎn)數(shù)量、分割步長對(duì)算法性能的影 響.一方面，相對(duì)于a*算法，本文方法更加適合多任 務(wù)點(diǎn)，高障礙率環(huán)境下的移?踴?器人路徑

27、規(guī)劃；另一 方面，采用較小的分割步長可使得規(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. acta automatica sinica，2002, 28(2): 161-175. (in chinese)2 張捍東，鄭睿，岑豫皖.移動(dòng)機(jī)器人路徑規(guī)劃 技術(shù)的現(xiàn)狀與展望u.系統(tǒng)仿真學(xué)報(bào)，2

28、005, 17 (2)： 439-443.zhang handong，zheng rui，cen yuwan. present situation and future development of mobile robot path planning technologyj. journal of system simulation，2005，17 (2): 439-443. (in chinese)3 朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述j.控制與決策，2010，25 (7)：961-967.zhu daqh yan mingzhong. survey on technology o

29、f mobile robot path planningj. control and decision, 2010，25 (7)： 961-967. (in chinese)4 吳乙萬，黃智.基于動(dòng)態(tài)虛擬障礙物的智能車輛局部路徑規(guī)劃方法.湖南大學(xué)學(xué)報(bào)：自然科學(xué)版， 2013，40 (1)：33-37.wu yiwan, huang zhi. dynamic virtual obstacle based local path planning for intelligent vehiclej.journal of hunan university： natural sciences, 2013，

30、 40 (1)： 33-37. (in chinese)5 楊淮清，肖興貴，姚棟.一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法.沈陽工業(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 robotj. journal of shenyang university of technology, 2009，31 (2)： 225-229. (in chinese)6 梁瑾，宋科璞.神經(jīng)網(wǎng)絡(luò)在移動(dòng)機(jī)器人路徑規(guī) 劃

31、中的應(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 planningj. journal of system simulation, 2010, 22(sl): 269-272.(in chinese)7 郝冬，劉斌.基于模糊邏輯行為融合路徑規(guī)劃660-663.方法j.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （3hao dong， liu bin. behavior fusion path planning method for

32、 mobile robot based on fuzzy logicj. computer engineering and design, 2010，30 (3)： 660-663. (in chinese)8 arpinocp, melendez wm, guzman j，etal. fuzzylogic based speed planning for autonomous navigationunder velocity field controlc/2009 ieee int conf on mechatronics. malaga, 2009：201-212.9 zoumponos

33、g t， aspragathos n a. fuzzy logic pathplanning for the robotic placement of fabricson a worktablej. robotics and computer integratedmanufacturing， 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 a

34、nd particle swarm optimization for robot-path planning in obstacle environment. 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 cu