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

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

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

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

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

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

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

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

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

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

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

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

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

14、器人路徑規劃中的圖方法應用綜述 J. 工程圖 學學報 , 2008, (04 6 蔡曉慧 . 基于智能算法的移動機器人路徑規劃研究 D 浙江大學 , 2007 . 7 李磊 , 葉濤 , 等 . 移動機器人技術研究現狀與未來 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. 沈陽工業大學學 報, 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.成偉明 , 唐振民 , 趙春霞 , 等. 移動機器人路徑規劃中的圖方法應用綜述 J. 工程圖學 學報 , 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.莊曉東 ,孟慶春 ,殷波 ,等 . 環境中基于模糊概念的機器人路徑搜索方法 J. 機器人 ,2001. 3 (5 :3972399. 14 李彩虹 ,張景元 ,李貽斌 . 基于模糊控制的移動機器人的路徑規劃 J. 淄博學院學報 , 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 劉利強 , 于飛 , 戴運桃 . 基于蟻群算法的水下潛器全局路徑規劃技術研究 J. 系統仿真 學報 , 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 全局路徑規劃方法 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、全局路徑規劃研究 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 李磊 , 葉濤 , 等 . 移動機器人技術研究現狀與未來 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