本研究基於二維光達（Light Detection and Ranging，LiDAR），開發同步定位建圖（Simultaneous Localization and Mapping，SLAM）與地圖閉環（loop closure）演算法，利用最近點疊代法（Iterative Closest Point，ICP）將LiDAR掃描點群與地圖障礙物點群進行匹配與對齊，不依靠地面載具輪編碼器的資訊，就能達成感測器的位姿估測；為了達成強健的SLAM技術，本研究利用二元貝氏濾波器（binary Bayes filter）對占據格點地圖（occupancy grid map）進行更新，達成高強健性的地圖建置；利用主成分分析（Principal Component Analysis，PCA）判斷LiDAR掃描點點群外形，進行長廊偵測，並以此設計自動調整門檻值之不穩定掃描點剔除機制；利用萊文貝格－馬夸特演算法（Levenberg–Marquardt algorithm，LM演算法）實現地圖閉環（loop closure），消弭定位建圖的累積誤差。最後，為了測試本論文的定位建圖精度，研究中使用了美國麻省理工學院（Massachusetts Institute of Technology，MIT）計算機科學與人工智慧實驗室（Computer Science and Artificial Intelligence Laboratory，CSAIL）所提供的掃描數據與定位正解（ground truth），進行演算法定位精度的驗證，最後測得定位建圖演算法在掃描路徑長達約350公尺的掃描數據中，最大追蹤誤差約為40公分，經地圖閉環後，最大誤差可下壓至約20公分。

This research intends to develop Simultaneous Localization and Mapping (SLAM) and loop closure algorithm based on 2D Light Detection and Ranging (LiDAR). For sensor localization, Iterative Closest Point (ICP) is applied to the alignment between the scan points dataset from LiDAR and model datasets from map in order to estimate LiDAR pose without odometry. For map construction, binary Bayes filter is used to update occupancy grid map with high robustness. For LiDAR scan points processing, an unstable point filter is designed with adaptive threshold according to corridor detector based on Principal Component Analysis (PCA). To correct the drift error in SLAM, loop closure is implemented by Levenberg–Marquardt algorithm. At last, the scan data and its ground truth provided by Massachusetts Institute of Technology (MIT) Computer Science and Artificial Intelligence Laboratory (CSAIL) is used to verify the localization accuracy of our algorithm. After verification, our SLAM algorithm produces about 0.4 meters of maximum following error during the 350 meter scan path. After loop closure, the maximum following error can be reduced to 0.2 meters.

[1] A. Elfes, "Sonar-based real-world mapping and navigation," IEEE Journal on Robotics and Automation, vol. 3, no. 3, pp. 249-265, June 1987.
[2] A. Elfes, "Using occupancy grids for mobile robot perception and navigation," Computer, vol. 22, no. 6, pp. 46-57, 1989.
[3] J. Leonard and H. Durrant-Whyte, "Mobile robot localization by tracking geometric beacons," Robotics and Automation, IEEE Transactions on, vol. 7, pp. 376-382, 1991.
[4] J. Castellanos and J. Tard´os, Mobile Robot Localization and Map Building: A Multisensor Fusion Approach. Kluwer Academic Publishers, Boston, MA, 2000.
[5] M. Csorba, "Simultaneous localisation and map building," PhD dissertation, University of Oxford, 1997.
[6] G. Dissanayake, P. Newman, S. Clark, H. Durrant-Whyte, and M. Csorba, "A solution to the simultaneous localization and map building (SLAM) problem," IEEE Transactions of Robotics and Automation, 2001
[7] J. Guivant and E. Nebot, "Optimization of the simultaneous localization and map building algorithm for real time implementation," IEEE Transaction of Robotic and Automation, 2001.
[8] J. Leonard, H. Durrant-Whyte, and I. Cox, "Dynamic map building for an autonomous mobile robot," International Journal of Robotics Research, vol. 11, no. 4, pp. 89–96, 1992.
[9] P. Newman, "On the structure and solution of the simultaneous localisation and map building problem," PhD dissertation, Australian Centre for Field Robotics, University of Sydney, Sydney, Australia, 2000.
[10] S. Williams, G. Dissanayake, and H. Durrant-Whyte, "Towards terrain-aided navigation for underwater robotics," Advanced Robotics, vol. 15, no. 5, 2001.
[11] C. Wang, C. Thorpe, S. Thrun, M. Hebert and H. Durrant-Whyte, "Simultaneous localization, mapping and moving object tracking," The International Journal of Robotics Research, vol. 26, no. 9, pp. 889-916, 2007.
[12] M. Bosse and R. Zlot, “Map matching and data association for large-scale two-dimensional laser scan-based SLAM,” The International Journal of Robotics Research, vol. 27, Issue 6, pp. 667 – 691, 2008.
[13] P. Besl and N. McKay, "A method for registration of 3-D shapes," in IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 14, no. 2, pp. 239-256, Feb. 1992.
[14] H. Moravec, "Sensor fusion in certainty grids for mobile robots," AI Magazine, vol. 9, no. 2, pp.61–74, 1988.
[15] S. Thrun, "Learning occupancy grids with forward models," Proceedings 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems. Expanding the Societal Role of Robotics in the the Next Millennium (Cat. No.01CH37180), Maui, HI, 2001, pp. 1676-1681 vol.3.
[16] J. Borenstein and Y. Koren, "The vector field histogram-fast obstacle avoidance for mobile robots," IEEE Transactions on Robotics and Automation, vol. 7, no. 3, pp. 278-288, 1991.
[17] J. Buhmann, W. Burgard, A.B. Cremers, D. Fox, T. Hofmann, F. Schneider, J. Strikos, and S. Thrun, "The mobile robot Rhino," AI Magazine, vol. 16, no. 1, 1995
[18] W. Burgard, A. Cremers, D. Fox, D. Hähnel, G. Lakemeyer, D. Schulz, W. Steiner and S. Thrun, "Experiences with an interactive museum tour-guide robot," Artificial Intelligence, vol. 114, no. 1-2, pp. 3-55, 1999.
[19] D. Guzzoni, A. Cheyer, L. Julia, and K. Konolige, "Many robots make short work," AI Magazine, vol. 18, no. 1, pp. 55–64, 1997
[20] S. Thrun, M. Beetz, M. Bennewitz, W. Burgard, A. Cremers, F. Dellaert, D. Fox, D. H¨ahnel, C. Rosenberg, N. Roy, J. Schulte, and D. Schulz, "Probabilistic algorithms and the interactive museum tour-guide robot minerva," International Journal of Robotics Research, vol. 19, no. 11, pp. 972–999, 2000.
[21] B. Yamauchi and P. Langley, "Place recognition in dynamic environments," Journal of Robotic Systems, vol. 14, no. 2, pp. 107–120, 1997.
[22] B. Yamauchi, P. Langley, A. Schultz, J. Grefenstette and W. Adams, "Magellan: An integrated adaptive architecture for mobile robots," Technical Report 98-2, Institute for the Study of Learning and Expertise (ISLE), Palo Alto, CA, 1998.
[23] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics (Intelligent Robotics and Autonomous Agents), MIT Press, 2005.
[24] D. Marquardt, "An algorithm for least-squares estimation of nonlinear Parameters," Journal of the Society for Industrial and Applied Mathematics, vol. 11, no. 2, pp. 431-441, 1963.
[25] MIT CSAIL, "MIT Stata Center Data Set," 2018. [Online]. Available: http://projects.csail.mit.edu/stata/. [Accessed: 07- Jun- 2018].
[26] M. Fallon, H. Johannsson, M. Kaess and J. Leonard, "The MIT Stata Center dataset," The International Journal of Robotics Research, vol. 32, no. 14, pp. 1695-1699, 2013.
[27] A. Bachrach, S. Prentice, R. He and N. Roy, "RANGE-robust autonomous navigation in GPS-denied environments," Journal of Field Robotics, vol. 28, no. 5, pp. 644-666, 2011.
[28] M. Kaess, A. Ranganathan and F. Dellaert, "iSAM: incremental smoothing and mapping," IEEE Transactions on Robotics, vol. 24, no. 6, pp. 1365-1378, 2008.