機器人定位是行動機器人導航的核心技術，為了讓機器人順利執行任務，首要目標即是即時獲得機器人位置。要得到機器人位置則必須考慮三大問題：全域定位、位置追蹤、以及機器人綁架。機器人定位發展已久，最廣為人知且最普遍採用的演算法為蒙地卡羅定位法(Monte Carlo Localization, MCL)，MCL是利用粒子濾波器作為主要架構的機器人定位法，透過粒子濾波器逐漸淘汰不良粒子，進而估測出機器人所在位置。儘管MCL被廣泛的採用，其無法從機器人綁架問題中恢復及運算大量粒子資訊造成計算負擔過大，成為MCL最大的缺點。為了解決此一問題，自調適蒙地卡羅演算法(Self-Adaptive Monte Carlo Localization, SAMCL)加入了相似能量區域(Similar Energy region, SER)及預先存取(Pre-caching)機制，解決了機器人綁架重新搜尋的問題，並提高即時運算速度，但MCL與SAMCL兩者仍存在共同的缺點：粒子淘汰過程中容易受超強粒子影響而陷入區域最佳解，粒子數量在位置追蹤及全域搜尋上的不平衡也會造成搜尋效果不好或追蹤過程計算負擔過大，再者，由於機器人的方向估測不易，導致即便粒子位置正確，但因為方向錯誤而被淘汰的可能性。因此，本論文提出一種改良式蒙地卡羅定位法，稱之為「具強健方向估測之蒙地卡羅定位法」(Improved Monte Carlo Localization with Robust Orientation Estimation, IMCLROE)，加入了方向估測機制來避免粒子位置正確卻被淘汰的問題，以及粒子數量平衡機制來平衡搜尋與追蹤的粒子數量，並且利用競爭選取法避免陷入區域最佳解，以提高粒子分布的多樣性。實驗證明IMCLROE有效解決了MCL及SAMCL在搜尋追蹤及綁架上的不足。

This paper proposes an improved Monte Carlo Localization algorithm with robust orientation estimation (IMCLROE) by incorporating an orientation estimate and weight calculation mechanism to determine an optimal orientation for particles and a particles size balancing mechanism to regulate the number of particles for position tracking and global localization. Based on previously established sensory information, the proposed IMCLROE can improve the computational efficiency of robot localization. Position tracking accuracy and global localization successful rate are also significantly improved while maintaining a minimal population of particles. Simulation and experimental results have confirmed the effectiveness of the proposed approach.

[1]D. Fox, W. Burgard, and S. Thrun, “Markov Localization for Mobile Robots in Dynamic Environments,” Journal of Artificial Intelligence Research, pp. 391-427, Nov. 1999.
[2]R.E. Kalman. “ A new approach to linear filtering and prediction problems,” Trans. of the ASM - Journal of basic engineering, no. 82, pp. 35-45, March 1960.
[3]K. Basye, T. Dean, J. Kirman, and M. Lejter. “A decision-theoretic approach to planning, perception, and control,” IEEE Expert, vol.7, no. 4, pp. 58-65, Aug. 1992.
[4]Y. C. Ho, and R. Lee, “A Bayesian approach to problems in stochastic estimation and control,” IEEE Transactions on Automatic Control, vol. 9, no 4, pp333-339, 2001.
[5]M.S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “ A Tutorial on Particle Filters for OnlineNonlinear/Non-Gaussian Bayesian Tracking,” IEEE Transactions on signal processing, Feb. 2002, vol. 50, no. 2, pp. 174-188.
[6]F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “ Monte Carlo localization for mobile robots,” IEEE International Conference on Robotics and Automation, Detroit, Michigan, May 1999, vol. 2, pp. 1322-1328.
[7]S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics, the MIT Press, 2005.
[8]C.C. Hsu, C.C. Wong, H.C. Teng, and C.Y. Ho, “ Localization of Mobile Robots via an Enhanced Particle Filter Incorporating Tournament Selection and Nelder-Mead Simplex Search,” International Journal of Innovative Computing, Information and Control, vol. 7, no. 7A, pp. 3725-3737, July 2011.
[9]I. Rekleitis, “A Particle Filter Tutorial for Mobile Robot Localization,” Technical Report TR-CIM-04-02, Centre for Intelligent Machines, McGill University, Montreal, Quebec, Canada, 2004.
[10]T. Li, S. Sun, and J. Duan, “Monte Carlo Localization for Mobile Robot Using Adaptive Particle Merging and Splitting Technique,” 2010 IEEE International Conference on Information and Automation, pp.1913-1918, Harbin, China, June 2010.
[11]J. Xu, F. Bu, W. Si, Y. Qiu, and Z. Chen, “An Algorithm of Weighted Monte Carlo Localization Based on Smallest Enclosing Circle,” 2011 International Conference on Internet of Things and Cyber, Physical and Social Computing, Dalian, China, October 2011, pp.157-161.
[12]D. Fox, “Adapting the sample size in particle filters through KLD-sampling,” International Journal of Robotics Research, vol. 22, no.12, pp. 985-1003, 2003.
[13]C. Kwok, D. Fox, and M.Meila. “Adaptive real-time particle filters for robot localization,” IEEE International Conference on Robotics and Automation, Sept. 2003, vol. 2, pp. 2836-2841.
[14]T. Li, S. Sun and T.P. Sattar, “Adapting sample size in particle filters through KLD-resampling,” Electronics Letters, vol.49, no. 12, pp.740-742, June 2013.
[15]T. Pencheva, K. Atanassov, and A. Shannon, “Modelling of a Stochastic Universal Sampling Selection Operator in Genetic Algorithms Using Generalized Nets,” Tenth Int. Workshop on Generalized Nets, pp1-7, Sofia, December 2009.
[16]J. Baker, “Reducing Bias and Inefficiency in the Selection Algorithm,” Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, New Jersey, 1987, pp. 14-21.
[17]Z. Liu, Z.Shi, M. Zhao, and W.Xu, “Mobile Robots Global Localization Using Adaptive Dynamic Clustered Particle Filters,” IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego, USA, Oct. 2007, pp.1059-1064.
[18]F. Bori , A. Gasparri and S. Panzieri, “A Fitness-Sharing based Genetic Algorithm for Collaborative Multi Robot Localization,” IEEE/RSJ International Conference on Intelligent Robots and Systems, St. Louis, USA, Oct. 2009, pp.3968-3973.
[19]X. Kang, K. Li and W. Zhu, “A New Localization Method for Mobile Robots Using Genetic Simulated Annealing Monte Carlo Localization,” IEEE International Conference on Mechatronics and Automation, Beijing, China, Aug. 2011, pp.1780-1785.
[20]T.B. Kwon, J.H. Yang, J.B. Song, and W. Chung, “Efficiency Improvement in Monte Carlo Localization through Topological Information.” IEEE/RSJInternational Conference on Intelligent Robots and Systems, Beijing, China, Oct. 2011, pp.424-429.
[21]L. Zhang, R. Zapata, and P. Lepinay, “Self-adaptive Monte Carlo Localization for Mobile Robots Using Range Sensors,” 2009 IEEE/RSJ nternational Conference on Intelligent Robots and Systems, St. Louis, USA, October 2009, pp.1541-1546.
[22]L. Zhang, R. Zapata, and P. Lepinay, “Self-Adaptive Monte Carlo for Single-Robot and Multi-Robot Localization,” in International Conference on Automation and Logistics (ICAL’09), Shenyang, China, August 5-7, 2009, pp.1927-1933.
[23]H. Choset and J. Burdick. “Sensor Based Planning. Part I: The Generalized Voronoi Graph,” IEEE/IRSJ International Conference on Intelligent Robots and Systems, 1995, pp. 1649-1655.
[24]黎乃仁， “結合單體搜尋法之改良式粒子濾波器及其在非線性函數追蹤及機器人定位之研究”，淡江大學，碩士論文，98年6月。
[25]T. Pencheva, K. Atanassov, A. Shannon, “Modelling of a Stochastic Universal Sampling Selection Operator in Genetic Algorithms Using Generalized Nets,” Proceedings of the Tenth International Workshop on Generalized Nets, Sofia, Bulgaria, December 5, 2009, 1-7.
[26]C.C Hsu, C.J. Kuo, and W.C. Kao, “Improved Monte Carlo Localization with Robust Orientation Estimation for Mobile Robots,” IEEE International Conference on Systems, Man, and Cybernetics (SMC), Oct. 2013 pp.3651-3656.
[27]H. Xie and M. Zhang, “Parent Selection Pressure Auto-Tuning for Tournament Selection in Genetic Programming,” IEEE Transactions on Evolutionary Computation, vol. 17, no. 1, pp.1-19, Feb. 2013.
[28]Y. Hong, S. Kwong, Q. Ren, and X.Wang, “A Comprehensive Comparison Between Real Population Based Tournament Selection and Virtual PopulationBased Tournament Selection,” IEEE Congress on Evolutionary Computation, Sept. 2007, pp.445-452.
[29]S. Legg , M. Hutter , and A. Kumar, “Tournament versus Fitness Uniform Selection” CEC 2004 Congress on Evolutionary Computation, June 2004, vol. 2, pp.2144-2151.
[30]C.Kwok, D. Fox, and M.Meili, “Adaptive Real-time Particle Filters for Robot Localization,” IEEE International Conference on Robotics and Automation, Sept. 2003, vol. 2, pp.2836-2841.
[31]J. Wolf, W. Burgard, and H. Burkhardt, “Robust Vision-Based Localization by Combining an Image-Retrieval System With Monte Carlo Localization,” IEEE Transactions on Robotics, vol. 21, no. 2,pp.208-216, Apr. 2005.
[32]L. Armesto, J. Tornero and L. Domenech, “Improving Self-Localisation of Mobile Robots Based on Asynchronous Monte-Carlo Localization,” IEEE Conference on Emerging Technologies and Factory Automation, Prague, Sept. 2006, pp.1028-1035.
[33]G.Cen, H.Nakamoto, N. Matsuhira and I. Hagiwara, “Effective Application of Monte Carlo Localization for Service Robot,” 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, San Diego,USA, Oct. 2007, pp.1914-1919.
[34]L. Zhang and R. Zapata, “Probabilistic Localization Methods of a Mobile Robot Using Ultrasonic Perception System,” 2009 IEEE International Conference on Information and Automation, Macau, China, June 2009, pp.1062-1067.
[35]B.Liu, X. Zheng, X. Wu and Y. Liu, “Quasi Monte Carlo localization for mobile robots,” 2012 12th International Conference on Control Automation Robotics & Vision (ICARCV), Guangzhou, China, Dec. 2012, pp.620-625.