移動(dòng)機(jī)器人路徑規(guī)劃綜述

1、移動(dòng)機(jī)器人路徑規(guī)劃綜述目錄1 引言22 傳統(tǒng)路徑規(guī)劃方法22.1 自由空間法22.2 圖搜索法32.3 柵格法33 智能路徑規(guī)劃方法. . 43.1 基于模糊邏輯的路徑規(guī)劃43.2 基于遺傳算法的路徑規(guī)劃53.3 基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃53.4 人工勢(shì)場(chǎng)法53.5 基于模糊邏輯與信息融合的路徑規(guī)劃64 結(jié)論與展望6參考文獻(xiàn)7引言所謂移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)，就是機(jī)器人根據(jù)自身傳感器對(duì)環(huán)境的感知，自行規(guī)劃出一條安全的運(yùn)行路線，同時(shí)高效完成作業(yè)任務(wù)。移動(dòng)機(jī)器人路徑規(guī)劃主要解決 3 個(gè)問(wèn)題：使機(jī)器人能從初始點(diǎn)運(yùn)動(dòng)到目標(biāo)點(diǎn)；用一定的算法使機(jī)器人能繞開障礙物，并且經(jīng)過(guò)某些必須經(jīng)過(guò)的點(diǎn)完成相應(yīng)的作業(yè)任務(wù)；在

2、完成以上任務(wù)的前提下，盡量?jī)?yōu)化機(jī)器人運(yùn)行軌跡。機(jī)器人路徑規(guī)劃技術(shù)是智能移動(dòng)機(jī)器人研究的核心內(nèi)容之一，它起始于20 世紀(jì) 70 年代，迄今為止，己有大量的研究成果報(bào)道 1 。路徑規(guī)劃方法的分類也呈現(xiàn)多樣化，可以分為基于地圖的全局路徑規(guī)劃方法 2,3和基于傳感器的局部路徑規(guī)劃方法 4 ，也可以分為傳統(tǒng)路徑規(guī)劃方法 5 與智能路徑規(guī)劃方法 6 。本文主要按傳統(tǒng)路徑規(guī)劃方法與智能路徑規(guī)劃方法進(jìn)行總結(jié)與評(píng)價(jià)。傳統(tǒng)路徑規(guī)劃方法主要包含自由空間法，圖搜索法，柵格法等，智能路徑規(guī)劃算法主要包含基于模糊邏輯的路徑規(guī)劃，基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃，基于遺傳算法的路徑規(guī)劃，人工勢(shì)場(chǎng)法以及信息融合方法等。傳統(tǒng)路徑規(guī)劃方法

3、2.1 自由空間法自由空間法 7 應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃，采用預(yù)先定義的如廣義錐形和凸多邊形等基本形狀構(gòu)造自由空間，并將自由空間表示為連通圖，通過(guò)搜索連通圖來(lái)進(jìn)行路徑規(guī)劃。自由空間的構(gòu)造方法 8 是：從障礙物的一個(gè)頂點(diǎn)開始，依次作其它頂點(diǎn)的鏈接線，刪除不必要的鏈接線，使得鏈接線與障礙物邊界所圍成的每一個(gè)自由空間都是面積最大的凸多邊形；連接各鏈接線的中點(diǎn)形成的網(wǎng)絡(luò)圖即為機(jī)器人可自由運(yùn)動(dòng)的路線。其優(yōu)點(diǎn)是比較靈活，起始點(diǎn)和目標(biāo)點(diǎn)的改變不會(huì)造成連通圖的重構(gòu)，缺點(diǎn)是復(fù)雜程度與障礙物的多少成正比，且有時(shí)無(wú)法獲得最短路徑。2.2 圖搜索法圖搜索法視移動(dòng)機(jī)器人為一點(diǎn)，將機(jī)器人、目標(biāo)點(diǎn)和多邊形障礙物的各頂點(diǎn)進(jìn)

4、行組合連接，并保證這些直線均不與障礙物相交，這就形成了一張圖，稱為可視圖。由于任意兩直線的頂點(diǎn)都是可見的，從起點(diǎn)沿著這些直線到達(dá)目標(biāo)點(diǎn)的所有路徑均是運(yùn)動(dòng)物體的無(wú)碰路徑。搜索最優(yōu)路徑的問(wèn)題就轉(zhuǎn)化為從起點(diǎn)到目標(biāo)點(diǎn)經(jīng)過(guò)這些可視直線的最短距離問(wèn)題。運(yùn)用優(yōu)化算法，可刪除一些不必要的連線以簡(jiǎn)化可視圖，縮短搜索時(shí)間。該法能夠求得最短路徑，但假設(shè)忽略移動(dòng)機(jī)器人的尺寸大小，使得機(jī)器人通過(guò)障礙物頂點(diǎn)時(shí)離障礙物太近甚至接觸，并且搜索時(shí)間長(zhǎng)。切線圖法和 Voronoi 圖法對(duì)可視圖法進(jìn)行了改造。切線圖（如圖 1）用障礙物的切線表示弧，因此是從起始點(diǎn)到目標(biāo)點(diǎn)的最短路徑的圖，即移動(dòng)機(jī)器人必須幾乎接近障礙物行走。其缺點(diǎn)是如

5、果控制過(guò)程中產(chǎn)生位置誤差，移動(dòng)機(jī)器人碰撞的可能性會(huì)很高。圖 2 用盡可能遠(yuǎn)離障礙物和墻壁的路徑表示弧。由此，從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑將會(huì)增長(zhǎng)，但采用這種控制方式時(shí)，即使產(chǎn)生位置誤差，移動(dòng)機(jī)器人也不會(huì)碰到障礙物 9 。(a 切線圖 (b Voronoi 圖圖 1 切線法與 Voronoi 圖法2.3 柵格法柵格法是將機(jī)器人周圍空間分解為相互連接且不重疊的空間單元: 柵格 (cell, 由這些柵格構(gòu)成一個(gè)連通圖 , 依據(jù)障礙物占有情況 , 在此圖上搜索一條從起始柵格到目標(biāo)柵格無(wú)碰撞的最優(yōu)路徑 . 這其中根據(jù)柵格處理方法的不同 , 又分為精確柵格法和近似柵格法 , 后者也稱概率柵格法 10,11.

6、 精確柵格法 12 是將自由空間分解成多個(gè)不重疊的單元 , 這些單元的組合與原自由空間精確相等 ,如圖 2 就是常用的一種精確柵格分解法梯形柵格分解 .圖2柵格法大部分機(jī)器人路徑規(guī)劃中的全局規(guī)劃都是基于上述幾種方法進(jìn)行的, 但是以上這些傳統(tǒng)方法在路徑搜索效率及路徑優(yōu)化方面尚有待于進(jìn)一步改善。 3 智能路徑規(guī)劃方法3.1 基于模糊邏輯的路徑規(guī)劃模糊方法是在線規(guī)劃中通常采用的一種規(guī)劃方法 , 包括建模和局部規(guī)劃。莊曉東等 13 提出一種基于模糊概念的動(dòng)態(tài)環(huán)境模型 , 參照物體的位置和運(yùn)動(dòng)信息構(gòu)造二維隸屬度函數(shù) ; 然后通過(guò)模糊綜合評(píng)價(jià)對(duì)各個(gè)方向進(jìn)行綜合考察 , 得到搜索結(jié)果。該方法在移動(dòng)障礙物和移

7、動(dòng)目標(biāo)的環(huán)境中能有效地實(shí)現(xiàn)機(jī)器人避碰和導(dǎo)航。李彩虹等 14 提出了一種在未知環(huán)境下移動(dòng)機(jī)器人的模糊控制算法 , 并對(duì)此算法進(jìn)行了推導(dǎo)與仿真 , 證明該算法魯棒性強(qiáng) , 可消除傳統(tǒng)算法中存在的對(duì)移動(dòng)機(jī)器人的定位精度敏感、對(duì)環(huán)境信息依賴性強(qiáng)等缺點(diǎn) , 使移動(dòng)機(jī)器人的行為表現(xiàn)出很好的一致性、連續(xù)性和穩(wěn)定性。 Hartmut Surmann 等15 提出一種未知環(huán)境下的高級(jí)機(jī)器人模糊導(dǎo)航方法 , 由 8 個(gè)不同的超聲傳感器來(lái)提供環(huán)境信息 , 然后利用基于模糊控制的導(dǎo)航器來(lái)計(jì)算這些信息 , 規(guī)劃?rùn)C(jī)器人路徑。3.2 基于遺傳算法的路徑規(guī)劃遺傳算法是最早應(yīng)用于組合優(yōu)化問(wèn)題的智能優(yōu)化算法 , 該算法及其派生算

8、法在機(jī)器人路徑規(guī)劃研究領(lǐng)域已得到應(yīng)用 16-18. 在蟻群算法較好解決旅行商問(wèn)題 (TSP 的基礎(chǔ)上 , 許多學(xué)者進(jìn)一步將蟻群優(yōu)化算法引入到水下機(jī)器人 (UV 的路徑規(guī)劃研究中 19,20. 最近 , 徐玉如等 21 考慮了海流因素的影響 , 提出了一種基于遺傳算法和粒子群優(yōu)化 (PSO 算法的 AUV 全局路徑規(guī)劃思想。3.3 基于神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃神經(jīng)網(wǎng)絡(luò)作為人工智能的重要內(nèi)容, 在移動(dòng)機(jī)器人路徑規(guī)劃研究中得到了廣泛關(guān)注 22-26,如 Ghatee 等 27 將 Hopfield神經(jīng)網(wǎng)絡(luò)應(yīng)用到路徑距離的優(yōu)化中; Zhu 等25 將自組織SOM神經(jīng)網(wǎng)絡(luò)應(yīng)用到多任務(wù)多機(jī)器人的任務(wù)分配與路徑規(guī)

9、劃中. 近年來(lái)加拿大學(xué)者 Simon 28,29提出一種新的生物啟發(fā)動(dòng)態(tài)神經(jīng)網(wǎng)絡(luò)模型, 將神經(jīng)網(wǎng)絡(luò)的神經(jīng)元與二維規(guī)劃空間的離散坐標(biāo)對(duì)應(yīng)起來(lái), 通過(guò)規(guī)定障礙物和非障礙物對(duì)神經(jīng)元輸入激勵(lì)和抑制的不同 , 直接計(jì)算相關(guān)神經(jīng)元的輸出 , 由此判定機(jī)器人的運(yùn)行方向 . 由于該神經(jīng)網(wǎng)絡(luò)不需要學(xué)習(xí)訓(xùn)練過(guò)程 , 路徑規(guī)劃實(shí)時(shí)性好 , 同時(shí)利用神經(jīng)網(wǎng)絡(luò)本身的快速衰減特性 , 較好地解決了機(jī)器人路徑規(guī)劃的死區(qū)問(wèn)題 30,31.3.4 人工勢(shì)場(chǎng)法人工勢(shì)場(chǎng)法 32,33是由 Khatib 提出的一種虛擬力法。其基本思想是將移動(dòng)機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種虛擬人工受力場(chǎng)中的運(yùn)動(dòng)。障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生斥力，目標(biāo)點(diǎn)產(chǎn)生引

10、力，引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢(shì) , 機(jī)器人在勢(shì)場(chǎng)中受到抽象力作用，抽象力使得機(jī)器人繞過(guò)障礙物。該法結(jié)構(gòu)簡(jiǎn)單，便于低層的實(shí)時(shí)控制，在實(shí)時(shí)避障和平滑的軌跡控制方面，得到了廣泛應(yīng)用，其不足在于存在局部最優(yōu)解，容易產(chǎn)生死鎖現(xiàn)象，因而可能使移動(dòng)機(jī)器人在到達(dá)目標(biāo)點(diǎn)之前就停留在局部最優(yōu)點(diǎn)。為解決局部極小值問(wèn)題，已經(jīng)研究出一些改進(jìn)算法，如Sato 提出的 Laplace 勢(shì)場(chǎng)法 34 。改進(jìn)算法是通過(guò)數(shù)學(xué)上合理定義勢(shì)場(chǎng)方程，來(lái)保證勢(shì)場(chǎng)中不存在局部極值。3.5 基于模糊邏輯與信息融合的路徑規(guī)劃 由于模糊邏輯和信息融合技術(shù)在不確定性信息處理方面有極好的表現(xiàn) , 且 移動(dòng)機(jī)器人傳感器采集的環(huán)境信息存在不

11、確定性和不完整性 , 使得模糊邏輯和 信息融合技術(shù)在移動(dòng)機(jī)器人路徑規(guī)劃中有較好的應(yīng)用 . 如 Lang 等35 針對(duì)全覆 蓋路徑規(guī)劃提出的移動(dòng)機(jī)器人模糊路徑規(guī)劃方法, Perez等 36 提出的基于速度 場(chǎng)的模糊路徑規(guī)劃方法等 , Zun 等37,38提出基于信息融合技術(shù)的移動(dòng)機(jī)器人和無(wú) 人機(jī)的路徑規(guī)劃與避碰方法 . 將智能算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃， 克服了許多傳統(tǒng)路徑規(guī)劃方法中的 不足，但該方法也有不足之處。例如遺傳優(yōu)化與蟻群算法的路徑規(guī)劃，需要與其 他路徑規(guī)劃方法結(jié)合在一起使用 , 單獨(dú)完成路徑規(guī)劃任務(wù)的情況較少 . 對(duì)神經(jīng) 網(wǎng)絡(luò)路徑規(guī)劃而言 , 大多數(shù)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃均存在規(guī)劃知識(shí)的

12、學(xué)習(xí)過(guò)程 , 不 僅存在學(xué)習(xí)樣本難以獲取 , 而且存在學(xué)習(xí)滯后問(wèn)題 , 從而影響神經(jīng)網(wǎng)絡(luò)路徑規(guī) 劃的實(shí)時(shí)性 . 生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃雖然實(shí)時(shí)性較好 , 但其輸入激勵(lì)與抑 制的設(shè)定也存在人為不確定因素 . 信息融合技術(shù)主要應(yīng)用于機(jī)器人傳感器信號(hào) 處理方面 , 而非直接的路徑規(guī)劃策略 . 4 結(jié)論與展望 智能移動(dòng)機(jī)器人路徑規(guī)劃 39,40問(wèn)題一直是機(jī)器人研究的核心內(nèi)容之一 . 本 文傳統(tǒng)路徑規(guī)劃方法與智能路徑規(guī)劃方法兩方面 , 對(duì)移動(dòng)機(jī)器人路徑規(guī)劃技術(shù) 研究現(xiàn)狀進(jìn)行了總結(jié)與評(píng)價(jià)。 從過(guò)去的研究狀況和機(jī)器人未來(lái)的發(fā)展需求來(lái)看 , 目前移動(dòng)機(jī)器人路徑規(guī) 劃技術(shù)研究主要集中在以下幾個(gè)方面： 1 新的

13、路徑方法的研究 ; 2 機(jī)器人底層控制與路徑規(guī)劃算法的結(jié)合研究 ; 3 多機(jī)器人任務(wù)分配、通信協(xié)作及路徑規(guī)劃的研究。 6參考文獻(xiàn) 1 朱大奇 , 顏明重 . 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述J. 控制與決策 ,2010, (07: 961-967. 2 孟偲 ,王田苗 . 一種移動(dòng)機(jī)器人全局最優(yōu)路徑規(guī)劃算法J機(jī)器人 , 2008,(03 . 3 張宏烈 . 移動(dòng)機(jī)器人全局路徑規(guī)劃的研究 D 哈爾濱工程大學(xué) ,2002 . 4鮑慶勇 ,李舜酩 ,沈峘 ,門秀花 . 自主移動(dòng)機(jī)器人局部路徑規(guī)劃綜述J. 傳感器與微系 統(tǒng), 2009, (09 . 5 成偉明 , 唐振民 , 趙春霞 , 劉華軍 . 移動(dòng)機(jī)

14、器人路徑規(guī)劃中的圖方法應(yīng)用綜述 J. 工程圖 學(xué)學(xué)報(bào) , 2008, (04 6 蔡曉慧 . 基于智能算法的移動(dòng)機(jī)器人路徑規(guī)劃研究 D 浙江大學(xué) , 2007 . 7 李磊 , 葉濤 , 等 . 移動(dòng)機(jī)器人技術(shù)研究現(xiàn)狀與未來(lái) J. 機(jī)器人 ,2002, 24(5: 475-480. 8 Habib M K, Asama H. Efficient method to generate collision free path for autonomous mobile robot based on new free space structuring approach J. Proc. IEEE/

15、RSJ IROS, 1991: 563-567. 9楊淮清 ,肖興貴 ,姚棟 .一種基于可視圖法的機(jī)器人全局路徑規(guī)劃算法J. 沈陽(yáng)工業(yè)大學(xué)學(xué) 報(bào), 2009, (02 .10 Jaillet L, Simeon T. Path deformation roadmaps: Compact graphs with useful cyclesfor motion planningJ. Int J of Robotics Research, 2008, 27(11: 1175-1188. 11 Cai C H, Ferrari S. Information-driven sensor path pla

16、nning by approximate cell decompositionJ. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2009, 39(3: 672-689.成偉明 , 唐振民 , 趙春霞 , 等. 移動(dòng)機(jī)器人路徑規(guī)劃中的圖方法應(yīng)用綜述 J. 工程圖學(xué) 學(xué)報(bào) , 2008, (4: 6-14.(Cheng W M, Tang Z M, Zhao C X, et al. A survey of mobilerobots path planning using geometric methods. J

17、 of Engineering Graphics, 2008, (4:6-14.莊曉東 ,孟慶春 ,殷波 ,等 . 環(huán)境中基于模糊概念的機(jī)器人路徑搜索方法 J. 機(jī)器人 ,2001. 3 (5 :3972399. 14 李彩虹 ,張景元 ,李貽斌 . 基于模糊控制的移動(dòng)機(jī)器人的路徑規(guī)劃 J. 淄博學(xué)院學(xué)報(bào) , 2001, (3 :27230. 15 Hartmut Surmann, Jrg Huser, JensWehking. Path lanning for a fuzzy controlled autonomous mobile robot A . Fifth IEEEInt . Con

18、f . On Fuzzy Systems Fuzz2IEEE 96C . UAS:New Orleans, 996. 16 Theodore W M, Kaveh A, Roger L W. Genetic algorithms for autonomous robot navigationJ. IEEE Instrumentation and Measurement Magazine, 2007, 12(1: 26-31. 17 Aybars U. Path planning on a cuboid using genetic algorithmsJ. Information Science

19、s, 2008, 178: 3275-3287. 18 Wang X P, Feng Z P. GA-based path planning for multiple AUVsJ. Int J of Control, 2007, 80(7: 1180-1185. 19 劉利強(qiáng) , 于飛 , 戴運(yùn)桃 . 基于蟻群算法的水下潛器全局路徑規(guī)劃技術(shù)研究 J. 系統(tǒng)仿真 學(xué)報(bào) , 2007, 19(18: 4174-4177. (Liu L Q, Yu F, Dai Y T. Path planning of underwater vehicle in 3D space based on ant col

20、ony algorithmJ. J of System Simulation, 2007, 19(18: 4174-4177. 20 王宏健 , 伍祥紅 , 施小成 . 基于蟻群算法的 AUV 全局路徑規(guī)劃方法 J. 中國(guó)造船 , 2008, 49(2: 88-93.(Wang H J, Wu X H, Shi X C. AUV global path planning based on ant colony optimization algorithmJ. Ship Building of China, 2008, 49(2: 88-93. 7徐玉如 , 姚耀中 . 考慮海流影響的水下機(jī)器人

21、全局路徑規(guī)劃研究 J. 中國(guó)造船 , 2008, 49(4: 109-114. (Xu Y R, Yao Y Z. Research on AUV global path planningconsidering ocean currentJ. Ship Building of China, 2008, 49(4: 109-114. 22 Luo C, Yang S Y. A bioinspired neural network for realtime concurrent map building and complete coverage robot navigation in unkno

22、wn environmentJ. IEEE Trans on NeuralNetwork, 2008, 19(7: 1279-1298. 23 Tse P W, Lang S, Leung K C, et al. Design of a navigation system for a household mobile robot using neural networksC. Int Conf Neural Network. Anchorage, 1998: 2151-2156. 24 Yasutomi F, Takaoka D, Yamada M, et al. Cleaning robot

23、 controlC. IEEE Int Conf Systems, Man, and Cybernetics. Beijing, 1988: 1839-1841. 25 Zhu A, Yang S X. A neural network approach to task assignment of multi-robotsJ. IEEE Trans on Neural Network, 2006, 17(5: 1278-1287. 26 Pereira F B. Bio-inspired algorithms for the vehicle routing problemM. Berlin:

24、Springer, 2009.Ghatee M, Mohades A. Motion planning in order to optimize the length and clearance applying a Hopfield neural networkJ. Expert Systems with Applications, 2009,4688-4695. 28 Yang S X, Meng M. Neural network approaches to dynamic collision-free robot trajectory generationJ. IEEE Trans o

25、n Systems, Man, and Cybernetics, Part B: Cybernetics, 2001, 31(3: 302-318. 29 Yang S X, Meng M H. Real-time collision-free motion planning of mobile robots using neural dynamics based approachesJ. IEEE Trans on Neural Network, 2003, 14(6: 1541-1552. 30 Yang S X, Luo C. A neural network approach to c

26、omplete coverage path planningJ. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(1: 718- 725. 31 Li H, Yang S X, Seto M L. Neural-network-based path planning for a multirobot system withmoving obstaclesJ. IEEE Trans on Systems, Man, and Cybernetics, Part C: Applications an

27、d Reviews, 2009, 39(4: 410-419. 32 李磊 , 葉濤 , 等 . 移動(dòng)機(jī)器人技術(shù)研究現(xiàn)狀與未來(lái) J. 機(jī)器人 , 2002, 24(5: 475-480. 33 Khatib. Real-time obstacle for manipulators and mobile robot J. The International Journal of Robotic Research. 1986, (1: 90-98. 34 Sato K. Deadlock-free motion planning using Laplace potential field J. Advanced Robotics, 1993, (5: 449-461. 35 Fu Y, Lang S Y L. Fuzzy logic based mobile robot area filling with vision system for indoor env