基于粒子濾波的移動(dòng)機(jī)器人定位及路徑優(yōu)化問(wèn)題研究

1、基于粒子濾波的移動(dòng)機(jī)器人定位及路徑優(yōu)化問(wèn)題研究基于粒子濾波的移動(dòng)機(jī)器人定位及路徑優(yōu)化問(wèn)題研究 范利春 信息與電氣工程學(xué)院 電氣工程與自動(dòng)化 2005-10 班 指導(dǎo)教師：李明 摘摘 要：要：首先研究了基于粒子濾波算法的移動(dòng)機(jī)器人自定位問(wèn)題，建立了 機(jī)器人的粒子濾波定位模型，實(shí)現(xiàn)了機(jī)器人依據(jù)激光測(cè)距儀的自定位。其次針 對(duì)復(fù)雜未知環(huán)境地圖，提出了骨架提取算法，將二維平面地圖轉(zhuǎn)化為骨架圖， 結(jié)合A*搜索算法進(jìn)行路徑的選擇并引入微粒群算法對(duì)機(jī)器人路徑進(jìn)行優(yōu)化，解 決了復(fù)雜未知地圖的路徑規(guī)劃及優(yōu)化問(wèn)題。最后在仿真環(huán)境中對(duì)上述方法進(jìn)行 了實(shí)驗(yàn)。 關(guān)鍵詞：關(guān)鍵詞：移動(dòng)機(jī)器人； 粒子濾波； 路徑規(guī)劃； 骨架提

2、取 1 引言 傳統(tǒng)的局部規(guī)劃的方法強(qiáng)調(diào)避碰行為，雖實(shí)時(shí)性好，但是由于缺乏規(guī)劃而 喪失優(yōu)化的優(yōu)點(diǎn)。如人工勢(shì)場(chǎng)法，不僅不容易找到最優(yōu)路徑，并且容易陷入局 部陷阱中。全局規(guī)劃的智能方法強(qiáng)調(diào)在可行路徑中找最優(yōu)的路徑，前提是能夠 很容易找到可行解，這樣對(duì)環(huán)境的要求就很高，不適合復(fù)雜環(huán)境的求解。如微 粒群算法，當(dāng)他們?cè)趶?fù)雜環(huán)境中，可行解的空間非常小，這樣它們很難有粒子 到達(dá)目標(biāo)。而在未到達(dá)目標(biāo)之前，無(wú)法寫出其適應(yīng)度函數(shù)，這就限制了微粒群 算法在復(fù)雜地圖中的路徑直接求解。 傳統(tǒng)的方法都是在沒有給出建議路徑的情況下進(jìn)行規(guī)劃的，因此會(huì)遇到以 上問(wèn)題的限制。由于機(jī)器人的運(yùn)行環(huán)境往往是全局已知，部分未知的，如果能

3、夠根據(jù)全局地圖給出建議路徑，然后在建議路徑的基礎(chǔ)上應(yīng)用優(yōu)化算法進(jìn)行優(yōu) 化就能夠得到機(jī)器人的優(yōu)化路線。機(jī)器人在實(shí)際運(yùn)行過(guò)程中會(huì)沿著建議路徑走， 并且會(huì)不斷的更新地圖，然后算法依據(jù)機(jī)器人當(dāng)前獲得的地圖重新進(jìn)行規(guī)劃， 保證機(jī)器人能夠避過(guò)規(guī)劃圖以外的障礙物，成功到達(dá)目的地。本文根據(jù)這種思 想，針對(duì)復(fù)雜地圖進(jìn)行路徑規(guī)劃和優(yōu)化。 2 基于粒子濾波的定位算法 定位是移動(dòng)機(jī)器人路徑規(guī)劃的基本環(huán)節(jié)，粒子濾波是從概率論的角度出發(fā)， 利用概率演算來(lái)明確的描述機(jī)器人的位置，能夠精確描述機(jī)器人的不確定性。 2.1 系統(tǒng)模型系統(tǒng)模型 機(jī)器人的每一運(yùn)動(dòng)周期，位姿變化模型如圖 1 所示： X Y 1t 1t 7540 30

4、t ),( 11tt yx ),( tt yx 1t 圖 1 移動(dòng)機(jī)器人的運(yùn)動(dòng)模型 移動(dòng)機(jī)器人在時(shí)刻的位姿為，并接受到控制命令：向 1 ( 1, 1, 1) 右轉(zhuǎn)度，向前行移動(dòng)米。根據(jù)移動(dòng)機(jī)器人坐標(biāo)變換，在 時(shí)刻到達(dá)的位 1 1 姿狀態(tài)為： = 1+ 1cos ( 1 1) = 1+ 1sin ( 1 1) （1） = 1 1 移動(dòng)機(jī)器人的概率運(yùn)動(dòng)模型利用隨機(jī)變量 來(lái)表示移動(dòng)機(jī)器人運(yùn)動(dòng)過(guò)程中的 不確定性信息 5 結(jié)論 建立了器人的概率運(yùn)動(dòng)模型、地圖模型、傳感器模型和粒子觀測(cè)模型，系 統(tǒng)地實(shí)現(xiàn)了基于粒子濾波算法的移動(dòng)機(jī)器人自定位方法；并深入討論了影響該 算法性能的一些因素，如粒子數(shù)目和重采樣方法

5、等。 提出了骨架提取算法，將二維平面轉(zhuǎn)化為可行路徑，解決了二維平面地圖 的一般路徑規(guī)劃問(wèn)題。針對(duì)骨架提取算法獲得的路徑，本文應(yīng)用了 A*算法進(jìn)行 搜索，找到連通起始點(diǎn)和終止點(diǎn)的路徑，并再次引入智能進(jìn)化算法微粒群 算法進(jìn)行優(yōu)化，使得二維路徑規(guī)劃及優(yōu)化問(wèn)題得到了較好的效果，并且用仿真 實(shí)驗(yàn)證明算法的有效性。 骨架提取算法還存在很多問(wèn)題，本文中提到的骨架提取算法，應(yīng)用的濾波 器是的，如果能夠用的濾波器，效果將會(huì)更佳，但這樣就會(huì)使算法更 3 35 5 加復(fù)雜，具體細(xì)節(jié)還有待進(jìn)一步討論。 參考文獻(xiàn) 1 蔡自興.機(jī)器人學(xué).北京：清華大學(xué)出版社，2000，2-3，6-7 2 Sebastian Thrun，

6、 Dieter Fox，Wolfram Burgard. Probabilistic Robotics. Cambridge，MA： The MIT Press. 2005 3 徐元昌.工業(yè)機(jī)器人.北京：中國(guó)輕工業(yè)出版社，1998，9-11 4 孫富春.機(jī)器人學(xué)導(dǎo)論.北京：電了工業(yè)出版社，2002，12-13 5 趙先章.一種基于粒子群算法的移動(dòng)機(jī)器人路徑規(guī)劃方法，計(jì)算機(jī)應(yīng)用研究，2007 6 劉京京.多目標(biāo)遺傳優(yōu)化及其在機(jī)器人路徑規(guī)劃中的應(yīng)用(碩士學(xué)位論文).南京：南京理 工大學(xué)，2007 7 王帥.基于強(qiáng)化學(xué)習(xí)算法的井下移動(dòng)機(jī)器人路徑規(guī)劃，電氣技術(shù)，2008 8 黃炳強(qiáng).基于模糊控制器的機(jī)

7、器人路徑規(guī)劃研究，測(cè)控技術(shù)，2007 9 張彥.完全未知環(huán)境下機(jī)器人路徑規(guī)劃的 RPC 算法，計(jì)算機(jī)工程與應(yīng)用，2007 10 Qussama Khatib， Mobile Robots. Real-Time Obstacle Avoidance for Manipulators and Proc of The 1994 IEEE 11 Cody Kwork， Dieter Fox， Marina Meila. Adaptive Real-time Particle Filters for Robot Localization. Proc. of the IEEE International

8、Conference on Robotics and Automation (ICRA)， 2003 12 袁澤劍，鄭南寧，賈新春.高斯-厄米特粒子濾波器.電子學(xué)報(bào)，Vol. 31， No. 7， 2003. 7 13 王寶安，盧煥章.粒子濾波器及其在目標(biāo)跟蹤中的應(yīng)用.雷達(dá)科學(xué)與技術(shù)，Vol. 1，No. 3，2003.10 14 莫以為，肖德云.基于進(jìn)化粒子濾波器的混合系統(tǒng)故障診斷.控制與決策，Vol. 19， No. 6，2004.6 15 N.J. Gordon，D.J. Salmond，C. Ewing. Bayesian state estimation for tracking a

9、nd guidance using the bootstrap filter.Journal of Guidance，Control and Dynamics，Vol.18，No. 6， 1995， 1434-1443 16 Simon Godsill，Tim Clapp. Improvement strategies for Monte Carlo particle filters D. Signal Processing Group， University of Cambridge，1998 17 李冰冰.基于粒子濾波的目標(biāo)跟蹤算法的應(yīng)用研究(碩士學(xué)位論文).長(zhǎng)春：東北師范大學(xué)， 2007

10、 18 A. Doucet，S. Godsill，and C. Andrieu. On sequential Monte Carlo sampling methods for Bayesian filtering. Statist. Computer， Vol. 10， 2000，197-208 19 A. Doucet， J. de Freitas， N. Gordon. Sequential Monte Carlo Methods in Practice. New- York： Springer-Verlag. 2001 20 盛驟等.概率論與數(shù)理統(tǒng)計(jì).北京：高等教育出版社，1989 21

11、 徐鐘濟(jì).蒙特卡羅方法.第一版.上海：上海科學(xué)技術(shù)出版社，1985 22 裴鹿成，張孝澤.蒙特卡羅方法及其在粒子輸運(yùn)問(wèn)題中的應(yīng)用.第一版，北京：科學(xué)出 版社，1980 23 P. Del Moral. Measure valued processes and interacting particle systems. Application to nonlinear filtering problems. Ann. Appl. Probab，1998 24 李慶揚(yáng)，關(guān)治，白峰杉.數(shù)值計(jì)算原理.北京：清華大學(xué)出版社，2000 25 Chatila R，Laumond J-P. Position

12、referencing and consistent world modeling for mobile robots. IEEE international Conference on Robotics and Automation. 1985，138-145 26 Kuipers B. The spatial semantic hierarchy. Artificial intelligence，2000，191-233 27 Crowley J L. Mathematical foundations of navigation and Perception for an autonomo

13、us mobile robot. International workshop on Reasoning with Uncertainty in Robotics. 1995，9-51 28 云曉.網(wǎng)絡(luò)移動(dòng)機(jī)器人粒子濾波定位研究.大津：大津大學(xué)，2006，43-45 29 蔡自興，徐光禱.人工智能及其應(yīng)用(第二版).清華大學(xué)出版社，1996 30 李長(zhǎng)青，安茂鵬，鄭征.人工智能.中國(guó)礦業(yè)出版社，2006 31 Kennedy J，Eberhart R. Particle Swarm Optimization. In： IEEE Intl Conf on Neural Networks Pert

14、h，Australia，1995： 1942-1948 32 Eberhart R，Kennedy J.A New Optimizer Using Particle Swarm Theory. In： Proc of the Sixth International Symposium on Micro Machine and Human Science，Nagoya，Japan，1995，39-43 33 Van den Bergh F. An Analysis of Particle Swarm Optimization. Ph. D Dissertation. South Africa：

15、Department of ComputernScience，University of Pretoria， 2002， 431-453 34 Kennedy J. The Particle Swarm： social adaptation of knowledge. IEEE Int. Conf. On Evolutionary Computation， Indianapolis，1N，1997，303-308 35 Shi Y，Eberhart R C.Parameter Selection in Particle Swarm Optimization. In ： Evolutionary Programming ： Proc. EP98. NewYork： Springer-Verlag， 1998， 591- 600 36 王衛(wèi)華，陳衛(wèi)東，席裕庚.基于不確定信息的移動(dòng)機(jī)器人地圖創(chuàng)建研究進(jìn)展，上海交通 大學(xué)自動(dòng)化研究所，2006 37 陳衛(wèi)東，張飛.移動(dòng)機(jī)器人的同步自定位與地圖創(chuàng)建研究進(jìn)展，上海交通大學(xué)，2005 38 賀偉，梁昔明.未知環(huán)境