移動機器人路徑規(guī)劃綜述

1、移動機器人路徑規(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 人工勢場法53.5 基于模糊邏輯與信息融合的路徑規(guī)劃64 結(jié)論與展望6參考文獻(xiàn)7引言所謂移動機器人路徑規(guī)劃技術(shù)，就是機器人根據(jù)自身傳感器對環(huán)境的感知，自行規(guī)劃出一條安全的運行路線，同時高效完成作業(yè)任務(wù)。移動機器人路徑規(guī)劃主要解決 3 個問題：使機器人能從初始點運動到目標(biāo)點；用一定的算法使機器人能繞開障礙物，并且經(jīng)過某些必須經(jīng)過的點完成相應(yīng)的作業(yè)任務(wù)；在

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

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

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

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

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

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

8、法在機器人路徑規(guī)劃研究領(lǐng)域已得到應(yīng)用 16-18. 在蟻群算法較好解決旅行商問題 (TSP 的基礎(chǔ)上 , 許多學(xué)者進(jìn)一步將蟻群優(yōu)化算法引入到水下機器人 (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)容, 在移動機器人路徑規(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ù)多機器人的任務(wù)分配與路徑規(guī)

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

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

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

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

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

14、器人路徑規(guī)劃中的圖方法應(yīng)用綜述 J. 工程圖 學(xué)學(xué)報 , 2008, (04 6 蔡曉慧 . 基于智能算法的移動機器人路徑規(guī)劃研究 D 浙江大學(xué) , 2007 . 7 李磊 , 葉濤 , 等 . 移動機器人技術(shù)研究現(xiàn)狀與未來 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楊淮清 ,肖興貴 ,姚棟 .一種基于可視圖法的機器人全局路徑規(guī)劃算法J. 沈陽工業(yè)大學(xué)學(xué) 報, 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.成偉明 , 唐振民 , 趙春霞 , 等. 移動機器人路徑規(guī)劃中的圖方法應(yīng)用綜述 J. 工程圖學(xué) 學(xué)報 , 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. 機器人 ,2001. 3 (5 :3972399. 14 李彩虹 ,張景元 ,李貽斌 . 基于模糊控制的移動機器人的路徑規(guī)劃 J. 淄博學(xué)院學(xué)報 , 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 劉利強 , 于飛 , 戴運桃 . 基于蟻群算法的水下潛器全局路徑規(guī)劃技術(shù)研究 J. 系統(tǒng)仿真 學(xué)報 , 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. 中國造船 , 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徐玉如 , 姚耀中 . 考慮海流影響的水下機器人

21、全局路徑規(guī)劃研究 J. 中國造船 , 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 李磊 , 葉濤 , 等 . 移動機器人技術(shù)研究現(xiàn)狀與未來 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