FastSLAM是目前解決即時定位與建圖的熱門方法。雖然FastSLAM2.0的執行速度已經比EKF-SLAM快，但是當地標越來越多的時候，FastSLAM2.0也會因為需要多次比對量測資訊與已存在粒子中之地標，造成執行速度過慢，無法達成即時處理的目標。因此，本論文提出一種新的SLAM架構，稱之為「具有高計算效率之及時定位與建圖演算法(CESLAM)」，捨棄一開始在FastSLAM2.0中利用環境資訊更新粒子位置的階段，改成跟FastSLAM1.0一樣，先用里程計資訊更新粒子，在更新完粒子資訊後，選擇跟量測資訊似然性最高的已存地標更新粒子狀態後，再更新地標位置。模擬結果顯示，我們所提出的演算法可克服多次比對而造成執行速度過慢的問題，同時也提升了定位與建圖的準確度。實驗方面，我們使用Pioneer 3-DX機器人作為移動平台，搭配Kinect感測器進行以SURF為基礎的視覺型即時定位與建圖(V-CESLAM)，實驗結果證明，本方法可以即時地讓機器人在經過大幅的移動及旋轉後，依舊能定位出自己所在的位置，並成功建立出機器人周圍的環境地圖。

FastSLAM is a popular method to solve the problem of simultaneous localization and mapping. However, when the number of landmarks present in real environments increases, there are excessive comparisons of the measurement with all the existing landmarks in each particle. As a result, the execution speed would be too slow to achieve the objective of real-time navigation.

As an attempt to solve this problem, this thesis presents an enhanced architecture for FastSLAM called computationally efficient SLAM (CESLAM), where odometer information is considered for updating the robot’s pose in particles. When a measurement has a maximum likelihood with the known landmark in the particle, the particle state is updated before updating the landmark estimates. Simulation results show that the proposed algorithm can overcome the problem of the time-consuming process due to unnecessary comparisons and improve the accuracy of localization and mapping. To practically evaluate the performance of the proposed method, we use Pioneer 3-DX robot with Kinect sensor to conduct the experiment of the V-CESLAM based on SURF. Experimental results have confirmed that our method can successfully locate the robot and build the map with satisfactory accuracy after a series of movements of the robot.

[1]. H. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping: Part I,” IEEE Robot Autom. Mag., vol. 13, no. 2, pp. 99–108, Jun. 2006.
[2]. J.J. Leonard and H.F. Durrant-Whyte, “Mobile robot localization by tracking geometric beacons,” IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 376-382, 1991.
[3]. H. Durrant-Whyte, D. Rye, and E. Nebot, “Localisation of automatic guided vehicles,” The 7th International Symposium on Robotics Research (ISRR’95), 1996, pp. 613-625.
[4]. J.J. Leonard and H.J.S. Feder, “A computationally efficient method for large-scale concurrent mapping and localization,” The Ninth International Symposium on Robotics Research (ISRR’99), 2000, pp. 169-176.
[5]. J. Guivant, E. Nebot, and S. Baiker, “Localization and map building using laser range sensors in outdoor applications,” Journal of Robotic Systems, vol. 17, no. 10, pp. 565-583, 2000.
[6]. S.B. Williams, P. Newman, G. Dissanayake, and H.F. Durrant-Whyte, “Autonomous underwater simultaneous localisation and map building,” IEEE International Conference on Robotics and Automation (ICRA), San Francisco, 2000, vol. 2, pp. 1793-1798.
[7]. F. Lu and E. Milios, “Robot pose estimation in unknown environments by matching 2D range scans,” Journal of Intelligent and Robotic Systems: Theory and Applications, vol. 18, no. 3, pp. 249-275, 1997.
[8]. T. Duckett, S. Marsland, and J. Shapiro, “Fast, on-line learning of globally consistent maps,” Autonomous Robots, vol. 12, no. 3, pp. 287-300, 2002.
[9]. K. Pathak, M. Pfingsthorn, N. Vaskevicius, and A. Birk, “Relaxing loop-closing errors in 3D maps based on planar surface patches,” 2009 International Conference on Advanced Robotics (ICAR 2009), Munich, Germany, 2009, pp. 1-6.
[10]. K. Pathak, N. Vaskevicius, and A. Birk, “Uncertainty analysis for optimum plane extraction from noisy 3D range-sensor point-clouds,” Intelligent Service Robotics, vol. 3, no. 1, pp. 37-48, 2009.
[11]. F. Masson, J. Guivant, and E. Nebot, “Hybrid architecture for simultaneous localization and map building in large outdoor areas,” IEEE International Conference on Intelligent Robots and Systems, vol. 1, pp. 570-575, 2002.
[12]. J.E. Guivant, F.R. Masson, and E.M. Nebot, “Simultaneous localization and map building using natural features and absolute information,” Robotics and Autonomous Systems, vol. 40, no. 2-3, pp. 79-90, 2002.
[13]. R.C. Smith and P. Cheeseman, “On the representation and estimation of spatial uncertainty,” International Journal of Robotics, vol. 5, no. 4, pp. 56-58, 1986.
[14]. S.B. Williams, G. Dissanayake, and H.F. Durrant-Whyte, “An efficient approach to the simultaneous localisation and mapping problem,” IEEE International Conference on Robotics and Automation, Washington, USA, 2002, vol. 1, pp. 406-411.
[15]. G. Dissanayake, S.B. Williams, H.F. Durrant-Whyte, and T. Bailey, “Map management for efficient simultaneous localization and mapping (SLAM),” Autonomous Robots, vol. 12, no. 3, pp. 267-286, 2002.
[16]. A. Chatterjee, “Differential evolution tuned fuzzy supervisor adapted, extended Kalman filtering for SLAM problems in mobile robots,” Robotica, vol. 27, pp. 411-423, 2009.
[17]. A. Chatterjee and F. Matsuno, “A neuro-fuzzy assisted extended Kalman filter based approach for Simultaneous Localization and Mapping (SLAM) problems,” IEEE Transactions on Fuzzy Systems, vol. 15, pp. 984-997, 2007.
[18]. A. Chatterjee and F. Matsuno, “A Geese PSO tuned fuzzy supervisor for EKF based solutions of simultaneous localization and mapping (SLAM) problems in mobile robots,” Expert Systems with Applications, vol. 37, pp. 5542-5548, 2010.
[19]. A. Stentz, D. Fox and M. Montemerlo, “FastSLAM: A factored solution to the simultaneous localization and mapping problem with unknown data association,” In Proceedings of the AAAI National Conference on Artificial Intelligence, 2003, pp. 593-598.
[20]. G. Dissanayake, P. Newman, H.F. Durrant-Whyte, S. Clark, and M. Csobra, “An experimental and theoretical into simultaneous localization and map building (SLAM),” Lecture Notes in Control and Information Sciences, Experimental Robotics VI, 2000, pp. 265-274.
[21]. K. Murphy, “Bayesian map learning in dynamic environments,” Neural Information Proceedings System, vol. 12, pp. 1015–1021, 2000.
[22]. M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, “FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges,” International Joint Conference on Artificial Intelligence, 2003, pp. 1151-1156.
[23]. M. Montemerlo and S. Thrun, “Simultaneous localization and mapping with unknown data association using FastSLAM,” Proc. IEEE Int. Conf. Robotics and Automation, 2003, pp. 1985–1991.
[24]. 鄧宏志，結合粒子群最佳化法之雙層粒子濾波器於移動機器人的定位與地圖建置，博士論文，淡江大學電機工程學系，民國100年。
[25]. 陳雨政，分離更新式FastSLAM之設計與實現，博士論文，機械與機電工程學系，民國101年。
[26]. A. J. Dacison, I. D. Reid, N. Molton, and O. Stasse, “Monoslam: Real-time single camera slam, ” IEEE transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 6, pp. 1052-1067, June 2007.
[27]. L. M. Paz, P. Pinies, J. D. Tardos and J. Neira, “Large-Scale 6-DOF SLAM with Stereo-in-Hand, ” IEEE transactions on Robotics and Automation, vol. 24, no. 5, pp. 946-957, 2008.
[28]. P. Henry, M. Krainin, E. Herbst, X. Ren, and D. Fox, “RGB-D Mapping: Using depth cameras for dense 3D modeling of indoor environments,” in the 12th International Symposium on Experimental Robotics (ISER), 2010.
[29]. T. Emter, A. Stein, “Simultaneous Localization and Mapping with the Kinect sensor,” Proceedings of ROBOTIK, Munich, Germany, 2012, pp. 239-244.
[30]. J. Hartmann, D. Forouher, M. Litza, J. H. Klüssendorff and E. Maehle, “Real-Time Visual SLAM Using FastSLAM and the Microsoft Kinect Camera,” Proceedings of ROBOTIK, Munich, Germany, 2012, pp. 458-463.
[31]. Y. C. Ho and R. Lee, “A Bayesian approach to problems in stochastic estimation and control,” IEEE Transaction on Automatic Control, 2001, vol. AC-9, pp. 333-339.
[32]. S. J. Julier and J. K. Uhlmann “A New Extension of the Kalman Filter to Nonlinear Systems,” Proc. of AeroSense: The 11th Int. Symp. on Aerospace/Defence Sensing, Simulation and Controls, Orlando, USA, 1997, vol. 3068, pp. 182-193.
[33]. M.S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174-188, 2002.
[34]. G. Kitagawa, “Monte Carlo filter and smoother for non-Gaussian nonlinear state space models,” Journal of Computational and Graphical Statistics, vol. 5, no. 1, pp. 1-25, 1996.
[35]. F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” IEEE International Conference on Robotics and Automation, 1999, pp. 1322-1328.
[36]. S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics, the MIT Press, 2005.
[37]. 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.
[38]. Chen-Chien Hsu, Ching-Chang Wong, Hung-Chih Teng, and Cheng-Yao 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.
[39]. H. Bay, T. Tuytelaars, and L. Van Gool, “SURF: Speeded up robust features,” Proceedings of European Conference on Computer Vision, 2006, pp. 404-417.
[40]. D. G. Lowe, “Object recognition from local scale-invariant,” International Conference of Computer Vision, 2004, vol. 60, pp. 1150-1157.
[41]. P. Viola and M. Jones, “Rapid object detection using a boosted cascade of simple features,” Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003, vol. 2, pp. 1403-1410.
[42]. D. Lowe, “Distinctive image features from scale-invariant keypoints,” International Journal of Computer Vision, vol.60, no.2, pp.91-110, 2004.
[43]. R. Lienhart and J. Maydt, “An Extended Set of Haar-Like Features for Rapid Object Detection,” Proc. IEEE Int’l Conf. Image Processing, 2002, vol. 1, pp. 900-903.
[44]. H. P. Moravec, “Towards Automatic Visual Obstacle Avoidance,” Proc. 5th International Joint Conference on Artificial Intelligence, 1977, pp. 584.
[45]. C. Harris and M. Stephens, “A Combined Corner and Edge Detector,” Proceedings of Alvey Vision Conference, Manchedter, 1988, pp. 147-151.
[46]. K. Mikolajczyk and C. Schmid, “A Performance Evaluation of Local Descriptors,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 27, no. 10, pp. 1615-1630, 2005.
[47]. http://www.xbox.com/zh-TW/Kinect