本論文提出兩種改良型粒子濾波器(Enhanced Particle Filter, EPF) 演算法，分別混合競賽選擇法(Tournament Selection)以及單體搜尋法(Nelder-Mend Simplex Search, NM)之演算法，針對不同問題調整所需之競賽規模(tournament size)，以加快區域搜尋的速度，可以改善傳統粒子濾波器之準確性以及收斂速度，提升粒子濾波器之性能。為驗證所提出之演算法的效果，本文亦針對非線性一維函數追蹤的問題，估測每一時刻函數可能的狀態，並隨著時間重複計算每時刻的狀態之均方誤差(Root Mean Square Error, RMSE)，以此評估演算法之好壞，另外，對於非線性四維目標物函數追蹤問題，本論文所提出之方法亦有相當傑出的效果。本論文最後再以改良型粒子濾波器應用在輪型機器人之室內定位(indoor localization)之模擬，以一虛擬地圖模擬輪型機器人於室內環境中行走。模擬結果顯示，提出的改良型粒子濾波器在室內環境下，能夠有效並確地定位出機器人所在之位置與方向。

In this thesis, an enhanced particle filter incorporating tournament selection and Nelder-Mead (NM) simplex search method is proposed to improve the performance of function tracking for nonlinear functions. Simulation results show that more accurate results on state estimation for the nonlinear functions in terms of RMSE can be obtained by using the proposed particle filter in comparison with existing approaches. Finally, the enhanced particle filter is applied to indoor localization of mobile robot. The simulation result shows the method which estimates position and direction of mobile robot effectively.

中文摘要...........................................................................................................Ⅰ
英文摘要.......................................................................................................Ⅱ
目錄................................................................................................................Ⅲ
圖目錄...........................................................................................................Ⅴ
表目錄.........................................................................................................Ⅶ
第一章 前言..................................................................................................1
第二章 粒子濾波器法................................................................................5
第三章	 以粒子濾波器為基礎結合競賽選擇法之非線性函數追蹤......................................................................................................12
3.1常用粒子濾波中的重新取樣演算法.................................................12
3.2 競賽選取法.......................................................................................14
3.3 改良式粒子濾波器之架構...............................................................17
3.4 非線性函數追蹤之問題...................................................................19
第四章 以改良式粒子濾波器為基礎結合單體搜尋法之物體追
      蹤.......................................................................................................28
4.1 單體搜尋法之介紹...........................................................................28
4.2 結合單體搜尋法之改良式粒子濾波器之架構...............................33
4.3 物體追蹤問題...................................................................................35
第五章 以改良式粒子濾波器為基礎結合單體搜尋法之機器人
室內定位法......................................................................................40
5.1 問題描述.................................................................................................40
5.2 定位法之架構...................................................................................44
5.3 機器人室內定位模擬結果...............................................................48
第六章 結論與未來研究方向................................................................50
6.1 結論...................................................................................................50
6.2 未來研究方向...................................................................................52
參考文獻.......................................................................................................54
 
圖目錄
圖2.1 粒子濾波器動作說明圖........................................................................9
圖2.2 透過量測資訊與粒子群所計算出的機率密度分布..........................10
圖2.3 粒子濾波器流程圖..............................................................................11
圖3.1 競爭選取法動作說明圖......................................................................16
圖3.2 改良式粒子濾波器流程圖..................................................................18
圖3.3 實際函數狀態 對取樣時間 的模擬圖...........................................24
圖3.4 估測出之函數狀態 對取樣時間 的模擬圖...................................25
圖3.5 疊合圖3.與圖3.，實際函數的狀態 為虛線、估測之狀態 為實
      線.........................................................................................................26
圖4.1 NM單體搜尋法之反射程序示意圖....................................................29
圖4.2 NM單體搜尋法之擴張程序示意圖....................................................30
圖4.3 (a)NM單體搜尋法之向外收縮程序示意圖.......................................31
圖4.3 (b)NM單體搜尋法之向內收縮程序示意圖.......................................31
圖4.4 (a)當 更好於 時之NM單體搜尋法之縮小程序示意圖...…32
圖4.4 (b)當 更好於 時之NM單體搜尋法之縮小程序示意圖…...32
圖4.5 混合NM搜尋法之改良型粒子濾波器之程式流程圖......................34
圖4.6 在 平面的實際目標物軌跡..........................................................36
圖4.7 在 平面使用混合單體搜尋法之改良型粒子濾波器所估測出的
目標物軌跡.........................................................................................37
圖4.8 重疊圖4.6與圖4.7的軌跡追蹤模擬結果..........................................38
圖5.1 模擬之室內環境..................................................................................40
圖5.2 行動機器人位置角度關係圖..............................................................41
圖5.3 初始化粒子..........................................................................................42
圖5.4 第1次的迭代.......................................................................................43
圖5.5 第8次迭代，單體搜尋法之迭代模擬.................................................43
圖5.6 第12次迭代.........................................................................................44
圖5.7 混合NM搜尋法之改良型粒子濾波器之演算法流程圖..................47
圖6.1 室內環境地圖之長廊環境，容易造成定位誤差的產生....................53







 
表目錄
表3.1 在[3]中提到的各式演算法計算RMSE值(平均執行100次) ..........21
表3.2 所提出之改良型粒子濾波器演算法與其他粒子濾波器之比較(平均執行100次以上之結果) ....................................................................22
表3.3 提出之改良型粒子濾波器演算法與其他粒子濾波器之比較(平均執行100次以上之結果) ........................................................................27
表4.1 提出之混合NM搜尋法與改良式粒子濾波器和其他方法之比較(使用50個粒子，平均執行100次以上之結果) .....................................39
表5.1 嵌入單體搜尋法之改良型粒子濾波器與粒子濾波器之位置誤差比較.........................................................................................................48
表5.2 嵌入單體搜尋法之改良型粒子濾波器與粒子濾波器之角度誤差比較.........................................................................................................49

[1]  N. Chopin, “A sequential particle filter for static models,” Biometrika, vol. 89, no. 3, pp. 539–552, 2002.

[2]  M. Isard and A. Blake, “Condensation conditional density propagation for visual tracking,” International Journal of Computer Vision, 1998, pp. 5-28.

[3]   Z. Khan, T. Balch and F. Dellaert, “MCMC-based particle filtering for tracking a variable number of interacting targets,” IEEE Transactions on pattern analysis and machine intelligence, 2005, pp. 1805-1819.

[4]  A. Hermoso-Carazo and J. Linares-Pérez, “Different approaches for state filtering in nonlinear systems with uncertain observations,” Applied Mathematics and Computation, vol. 187, 2007, pp. 708-724.

[5]  Y. Rui and Y. Chen, “Better proposal distributions: object tracking using unscented particle filter,” IEEE Computer Vision and Pattern Recognition, pp. 786-793, 2001.

[6]  P. M. Djuric, J. H. Kotecha, J. Zhang, Y. Huang, T. Ghirmai, M. F. Bugallo, and J. M´ıguez, “Particle filtering,” IEEE Signal Processing Magazine, vol. 20, no. 5, pp. 19-38, 2003.

[7]  P. M. Djuric, T. Lu, and M. F. Bugallo, “Multiple particle filtering,” ICASSP’07, pp. III-1181-III-1184, 2007.

[8]  Y. C. Ho and R. C. K. Lee, “A Bayesian approach to problems in stochastic estimation and control,” IEEE Transactions on Automatic Control, vol. AC-9, pp. 333–339, 1964.

[9]  H. Jayesh, Kotecha and Petar M. Djuric, “Gaussian Particle Filtering,” IEEE Transactions on Signal Processing, vol. 51, No.10, 2003, pp. 2592-2601.

[10] N. de Freitas, “Rao-Blackwellised particle filtering for fault diagnosis,” IEEE Aerospace, 2002.

[11] F. J.  Pei, P. Y. Cui and Y. Z. Chen, “Adaptive MCMC Particle Filter for Nonlinear and Non-Gaussian State Estimation,” Innovative Computing Information and Control, pp. 494-494. 2008.

[12]	G. Kitagawa and W. Gersch, Smoothness Priors Analysis of Time Series, New York: Springer-Verlag, 1996.

[13] Brad L. Miller and David E. Goldberg, “Genetic Algorithms, Tournament Selection, and the Effects of Noise,” IlliGAL Report No. 95006 July 1995.

[14]	M. Sanjeev Arulampalam, Simon Maskell, Neil Gordon, and Tim Clapp, “A Tutorial on Particle Flters for Online Nonlinear/Non-Gaussian Bayesian Tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174-188, 2002.

[15]	N. Gordon, D. Salmond, and A. F. M. Smith, “Novel approach to nonlinear and non-Gaussian Bayesian state estimation,” IEE Proceedings F Radar and Signal Processing, vol. 140, pp. 107–113, 1993.

[16]	Ruixin Niu, Pramod K. Varshney, Mark Alford, Adnan Bubalo, Eric Jones, and Maria Scalzo, “Curvature nonlinearity measure and filter divergence detector for nonlinear tracking problems,” Information Fusion, pp. 1-8, 2008.

[17] P. M. Djuric and M. F. Bugallo, ”Improved target tracking with particle filtering,” IEEE Aerospace, pp. 1-7, 2009.

[18] M. F. Bugallo, T. Lu, and P. M. Djuric, “Target tracking by multiple particle filtering,” IEEE Aerospace, pp. 1-7, 2007.

[19] Xu Shifang, Xie Li and Liu Jilin, “Robot localization based on MCMC particle filter,” Joural of Zhejiang University(Engineering Science), 2007, pp. 1083-1087.

[20]	Y. Zhou, W. Liu, and P. Huang, “Laser-activated RFID-based Indoor Localization System for Mobile Robots,” Robotics and Automation, pp. 4600-4605, 2007.

[21] S. Lenser and M. Veloso, “Sensor resetting localization for poorly modelled mobile robots,” Robotics and Automation, 2000.

[22]	H. Andreasson, A. Treptow, and T. Duckett, “Self-localization in non-stationary environments using omni-directional vision,” Robotics and Autonomous Systems, vol. 55, 2007, pp. 541-551.

[23]	H. Kim, J. Choi, and M. Park, “Indoor localization system using multi-modulation of ultrasonic sensors and digital compass,” Intelligent Robots and Systems, pp. 1359-1364, 2008.

[24]	G. Jin, X. Lu, and M. Park, “An indoor localization mechanism using active RFID tag,” Sensor Networks, Ubiquitous, and Trustworthy Computing, vol. 1, 2006. 

[25]	J. González, J. Blanco, C. Galindo, A. Ortiz-de-Galisteo, J. Fernández-Madrigal, F. Moreno, and J. Martínez, “Mobile robot localization based on Ultra-Wide-Band ranging: A particle filter approach,” Robotics and Autonomous Systems, vol. 57, 2009, pp. 496-507.

[26]	鍾鎮謙、宋開泰，運用雷射測距儀之機器人定位設計，國立交通大學電機與控制工程學系碩士論文，台灣，民國96年。

[27]	F. Yan, Y. Zhuang, and W. Wang, “Large-scale Topological Environmental Model Based Particle Filters for Mobile Robot Indoor Localization,” Robotics and Biomimetics, pp. 858-863, 2006.

[28] N. A. Nelder and R. Mead, “A Simplex Method for Function Minimization,” Computer Journal, vol. 7, 1965, pp. 308-313.

[29] C. Andrieu, M. Davy, and A. Doucet, “Improved auxiliary particle filtering: applications to time-varying spectral analysis,” IEEE Workshop on Statistical Signal Processing, pp. 309-312, 2001.

[30] R. Kurazume, H. Yamada, K. Murakami, Y. Iwashita, and T. Hasegawa, ”Target tracking using SIR and MCMC particle filters by multiple cameras and laser range finders,” Intelligent Robots and Systems, pp. 3838-3844 , 2008.

[31] Georges Oppenheim, Anne Philippe, and Jean de Rigal “The particle filters and their applications,” Chemometrics and Intelligent Laboratory Systems, vol. 91, pp. 87-93, 2008. 

[32] G. Kitagawa, “Monte Carlo filter and smoother for non-Gaussian nonlinear state space models,” Computational and Graphical Statistics, vol. 5, no. 1, 1996, pp. 1-25.

[33] F. Daum and J. Huang, “Curse of dimensionality and particle filters,” IEEE Aerospace, 2003.

[34] Miroslav Simandl, Ondřej Straka, ” Functional sampling density design for particle filters,” Signal Processing, vol 88, 2008, pp. 2784-2789.

[35] O. Straka and M. Simandl, “Using the Bhattacharyya distance in functional sampling density of particle filter,” IFAC World Congress, pp. 1006-1011, 2005.

[36] M. Simandl and O. Straka, “Sampling density design for particle filters,” IFAC Symposium on System Identification, vol. 1, 2003.

[37] B. Carlin, N. Polson, and D. Stoffer, “A Monte Carlo approach to nonnormal and nonlinear state-space modeling,” American Statistical Association, vol. 87, no. 418, pp. 493–500, 1992.

[38] Marco A. Luersen and Rodolphe Le Riche, “Globalized Nelder–Mead method for engineering optimization,” Computers and Structures, vol. 82, pp. 2251-2260, 2004.

[39] S. Thrun , W. Burgard, and D. Fox, Probabilistic Robotics, MIT Press, Cambridge, MA, 2005.

[40] John Lin, Ying Wu, and Thomas S. Huang “Articulate hand motion capturing based on a Monte Carlo Nelder-Mead simplex tracker,” Pattern Recognition, vol. 4, pp. 975-978, 2004.

[41] F. Walters, L. R. Parker, S.L. Morgan, and S. N. Deming, Sequential Simplex Optimization, CRC Press, Boca Raton, USA, 1991.