FastSLAM是目前解決同時定位與建圖最主要的方法，其中FastSLAM 2.0隨著地標的不斷增加，量測資訊與粒子內所存地標的比對次數也會大幅增加，導致計算效率降低。因此本論文提出一改良方法，稱之為「適應性計算之同時定位與建圖演算法(ACSLAM)」，在一開始的粒子更新階段係與FastSLAM 1.0相同，只採用里程計資訊，接下來在更新地標的階段，先選擇與量測資訊有最大相似性的地標先更新粒子狀態，再來更新地標。並且在重新取樣的階段使用「有效取樣大小」的值來決定下一次演算法的粒子數目，透過此方法來提高計算效率以及定位的精確度。然而單純運用SLAM演算法並無法進行環境探索與路徑規劃，因此本論文將ACSLAM整合基於邊緣偵測(frontier-based)之環境探索方法以及向量場路徑規劃，使機器人能完全自主性的執行任務。在實作方面，我們選擇了Pioneer 3-DX機器人作為移動平台，並搭配SICK感測器來偵測周圍環境，實驗結果證明，本方法可以使機器人在完全未知的環境下，自主地將環境探索完畢，並且完成建圖定位以及路徑規劃的任務。

FastSLAM is a popular method to solve the Simultaneous Localization and Mapping (SLAM) problem. FastSLAM 2.0 adds the recent sensor measurement to improve the estimation accuracy compared to previous approaches. However, there is a runtime penalty when the number of landmarks becomes excessively large. To solve this problem, this thesis proposes a modified version for FastSLAM called adaptive computation SLAM (ACSLAM). In the beginning, ACSLAM only uses odometry information to estimate the robot’s pose. Particle state and landmark information are updated when a measurement has a maximum likelihood. To improve the computational efficiency, ACSLAM uses the effective sample size (ESS) to decide the number of particle for the next generation. The robot system is also extended with an exploration algorithm that uses the information generated by the SLAM system. By integrating the frontier-based exploration with ACSLAM and a path planning algorithm via potential field, the robot is capable of exploring an unknown environment safely in full autonomy. To practically evaluate the performance of the proposed method, a Pioneer 3-DX robot with a SICK laser scanner is used to validate the performance of the system both in simulation as well as practical experiments. Experimental results demonstrated that the proposed ACSLAM performed 40% faster than FastSLAM 2.0 with better accuracy.

[1] H. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping: Part I,” IEEE Robot Automation Mag., vol. 13, no. 2, pp. 99-108, 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,” in Proc. of The 7th International Symposium on Robotics Research (ISRR’95), New York, Oct. 1995, pp. 613-625.
[4] J.J. Leonard and H.J.S. Feder, “A computationally efficient method for large-scale concurrent mapping and localization,” in Proc. of The Ninth International on Robotics Research (ISRR’99), Snowbird, Utah, Oct. 1999, 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), vol. 2, pp. 1793-1798, 2000.
[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,” in Proc. of 2009 International Conference on Advanced Robotics (ICAR 2009), Munich, Germany, June 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] J. Neira and J. D. Tardos, “Data association in stochastic mapping using the joint compatibility test,” IEEE Transactions on Robotics and Automation, vol. 17, no. 6, pp. 890-897, 2001.
[15] M. Montemerlo and S. Thrun, “Simultaneous localization and mapping with unknown data association using FastSLAM,” in Proc. of IEEE International Conference Robotics and Automation, Taipei, Taiwan, Sept. 2003, pp. 1985–1991.
[16] 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,” in Proc. of International Conference on Artificial Intelligence, Acpulco, Mexico, Aug. 2003, pp. 1151-1156.
[17] Z. K. Yavuz and S. Yavuz, “A comparison of EKF, UKF, FastSLAM 2.0, and UKF-based FastSLAM algorithms,” in Proc. of INES, Lisbon, June 2003, pp. 37-43.
[18] 鄧宏志，“結合粒子群最佳化法之雙層粒子濾波器於移動機器人的定位與地圖建置”，淡江大學電機工程學系，博士論文，民國 100 年。
[19] C.-K. Yang, C.-C. Hsu, and Y.-T. Wang, “Computationally efficient algorithm for simultaneous localization and mapping (SLAM),” in Proc. of IEEE International Conference on Networking, Sensing and Control (ICNSC), Evry, April 2013, pp. 328-332.
[20] B. Yamauchi, “Frontier-based exploration using multiple robot,” in Proc. of the Second International Conference on Autonomous Agents, Minneapolis, May 1998, pp. 47-53.
[21] B. Yamauchi, “A frontier-based approach for Autonomous exploration,” in Proc. of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, CA, July 1997, pp. 146-151.
[22] M. Keidar and G. Kaminka, “Robot exploration with fast frontier detection: theory and experiments,” in Proc. of AAMAS, Valencia, June 2012, pp. 113–120.
[23] E. Uslu, F. Cakmak, M. Balcilar, A. Akinci, M. F. Amasyali and S. Yavuz, “Implementation of frontier-based exploration algorithm for an autonomous robot,” in Proc. of INISTA, Madrid, Sept. 2015, pp. 1–7.
[24] M. A. Goodrich, Potential fields tutorial, 2000.
[25] L. Tang, S. Dian, G. Gu, K. Zhou, S. Wang and X. Feng, “A novel potential field method for obstacle avoidance and path planning of mobile robot,” in Proc. of ICCSIT, Chengdu, July 2010, pp. 633-637
[26] C. Tingbin and Z. Qisong, “Robot motion planning based on improved artificial potential field,” in Proc. of ICCSNT, Dalian, Oct. 2013, pp. 1208-1211
[27] Y. C. Ho and R. Lee, “A Bayesian approach to problems in stochastic estimation and control,” IEEE Transaction on Automatic Control, vol. AC-9, pp. 333-339, 2001.
[28] S. J. Julier and J. K. Uhlmann “A New Extension of the Kalman Filter to Nonlinear Systems,” AeroSense: The 11th International Symposium on Aerospace/Defence Sensing, Simulation and Controls, vol. 3068, pp. 182-193, 1997.
[29] 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.
[30] 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.
[31] F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” in Proc. of IEEE International Conference on Robotics and Automation, Detroit, MI, May 1999, pp. 1322-1328.
[32] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics. the MIT Press, 2005.
[33] 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.
[34] 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.
[35] J. S. Liu, A theoretical framework for sequential importance sampling and resampling. New York, 2001.
[36] M. Bennewitz, W. Burgard, and S. Thrun, “Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots,” Robotics and Autonomous Systems, vol. 41, pp.89–99, 2002.
[37] J. Guo, L. Liu, Q. Liu, and Y. Qu, “An Improvement of D* Algorithm for Mobile Robot Path Planning in Partial Unknown Environment,” in Proc. of Second International Conference on Intelligent Computation Technology and Automation, Wuhan, China, Oct. 2009, pp.394–397.
[38] H. Choset, K. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. Kavraki, and S. Thrun, Principles of Robot Motion - Theory, Algorithms, and Implementations. The MIT Press, 2005.
[39] https://www.sick.com/de/en/product-portfolio/detection-and-ranging-solutions/2d-laser-scanners/lms1xx/c/g91901
[40] http://www.mobilerobots.com/Libraries/Downloads/Pioneer3DX-P3DX-RevA.sflb.ashx