本論文使用Pioneer 3-DX兩輪自走車搭載一台LMS-100雷射測距儀做未知環境的地圖建置，主要使用ICP演算法將每一筆雷射測距儀的掃描資訊疊合，但由於傳統ICP演算法本身容易受到雜訊與離散點影響，造成配對到不恰當的配對點，產生對齊有誤差，而在雷射掃描儀的連續掃描下，誤差的累積越來越多，導致整體的環境地圖對齊結果並不理想，故本論文提出使用PSO調整增強型ICP演算法來克服其問題，先使用PSO演算法將要對齊的兩集合做初步的對齊，避免兩集合落差太大產生區域最佳解，接著使用部分全域的地圖當作參考資訊，搭配篩選重疊資訊模組、權重模組及參考地圖間格模組，成為增強型ICP演算法，此演算法不但可以克服雜訊與離散點影響，還可以降低配對到不恰當的配對點，增加對齊效果，降低累積誤差，以獲得更佳的未知環境地圖。

This paper proposes a PSO-tuned enhanced iterative closest point algorithm (ICP) to build maps for an unknown environment using a Pioneer 3-DX wheeled mobile robot with a laser measure scanner (LMS-100). The proposed algorithm first aligns each scanned information by the ICP algorithm. Because traditional ICP algorithms are easily affected by noise and outliers, false matching points and alignment errors are therefore inevitable. As a result, there are more and more errors accumulated as the scanning process by the laser scanner continues, which results in imperfect alignment of the environmental map as a whole. Therefore, this paper proposes the use of Particle Swarm Optimization (PSO) to work with the Enhanced-ICP in order to effectively filter out outliers and avoid false matching points during the map building process, where PSO is used to align two data sets to avoid huge transformation that causes local optima. Then, we use part of global map as the reference data set with overlapping points for subsequent data matching. The proposed algorithm not only improves outlier and noise problem but also reduces false matching points so that it has better alignment and smaller accumulated errors. As a result, good environmental map is obtained.

[1]. 網昱多媒體，http://swf.com.tw
[2]. iRobot, http://store.irobot.com/home/index.jsp
[3]. 林士勛，以模糊理論為基礎應用超音波感測器未知環境地圖建置，台師大工業教育學系碩士論文，2011年。
[4]. P. Besl and N. McKay, “A Method for Registration of 3-D Shapes,” IEEE Trans. on Pattern Analysis and Machine Intel, 1992, pp. 239-256.
[5]. J. Minguez, F. Lamiraux, and L. Montesano,” Metric-Based Scan Matching Algorithms for Mobile Robot Displacement Estimation,” Proc. IEEE Int. Conf. on Robotics and Automation, Spain, 2005, pp. 3557-3563.
[6]. Sung-In Choi and Soon-Yong Park, “Robust ICP Registration Using Biunique Correspondence,” IEEE Int. Conf. on 3D Imaging, Modeling, Proc. Visualization and Transmission (3DIMPVT), South Korea, 2011, pp. 80-85.
[7]. D. Chetverikov, D. Svirko, D. Stepanov, and P. Krsek, “The trimmed iterative closest point algorithm,” Proc. Int. Conf. Pattern Recognition, Canada, 2002, pp. 545–548.
[8]. M. Tomono, “Robust Robot Localization and Map Building using a Global Scan Matching Method,” Proc. of IEEE Int. Conf. on Intelligent Robots and Systems (IROS), Japan, 2004, pp. 1059-1064.
[9]. F. Lu and E. Milios, “Globally Consistent Range Scan Alignment for Environment Mapping,” Autonomous Robots, Netherlands, 1997, pp. 333–349.
[10]. K. Lenac, E. Mumolo, and M. Nolich, “Fast genetic scan matching using corresponding point measurements in mobile robotics,” Lecture Notes in Computer Science, Berlin, 2007, pp. 375–382.
[11]. M. R. Kabuka and A.E. Arenas, “Position Verification of a Mobile Robot Using Standard Pattern,” IEEE Journal of Robotics and Automation, 1987, pp. 505-516.
[12]. A. Kosaka and A. C. Kak, “Fast Vision-Guided Mobile Robot Navigation Using Model-Based Reasoning and Prediction of Uncertainties,” Computer Vision, Graphics, and Image Proc. Image Understanding, 1992, pp. 271-329.
[13]. S. Atiya and G.D. Hager, “Real-Time Vision-Based Robot Localization,” IEEE Transactions on Robotics and Automation, 1993, pp. 785-800.
[14]. C. C. Tsai, S. M. Hu, H. C. Huang, and S. M. Hsieh, “Fuzzy Hybrid Navigation of an Active Mobile Robotic Assistant: A multisensory fusion approach,” Proceedings of CACS International Automatic Control Conference, Taichung, 2007, pp. 1280-1285.
[15]. H. P. Moravec and A. Elfes, “High Resolution Maps from Wide Angle Sonar,” Proceedings of IEEE International Conference on Robotics and Automation, Missouri, 1985, pp. 116-121.
[16]. S. Thrun, “Learning Metric-Topological Maps for Indoor Mobile Robot Navigation,” Artificial Intelligence, 1998, pp. 21-71.
[17]. N. Ayache and O. D. Faugeras, “Maintaining Representations of the Environment of a Mobile Robot,” IEEE Transactions on Robotics and Automation, 1998, pp. 804-819.
[18]. S. Se, D. Lowe, and J. Little, “Mobile robot localization and mapping with uncertainty using scale-invariant visual landmarks,” International Journal of Robotics Research, 2002, pp. 735–758.
[19]. S. Se, D. G. Lowe, and J. J. Little, “Vision-Based Global Localization and Mapping for Mobile Robots,” IEEE Transactions on Robotics, 2005, pp. 364-375.
[20]. S. Y. Chung and H. P. Huang, “Relative-Absolute Map Filter for Simultaneous Localization and Mapping,” Proceedings of IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, Beijing, 2006, pp. 436-441.
[21]. A. Segal, D. Haehnel, and S. Thrun, “Generalized-icp,” Proc. of Robotics: Science and Systems, Seattle, 2009, pp. 26–27.
[22]. Z. Zhang, “Iterative point matching for registration of free-form curves and surfaces,” Int. Journal of Computer Vision, Boston, 1994, pp. 119–152.
[23]. Godin, G., Rioux, M., and Baribeau, R. “Three-dimensional Registration Using Range and Intensity Information,” Proc. SPIE Videometrics III, Boston, 1994, pp. 279-290.
[24]. J .Kennedy, R.C. Eberhart, “Particle Swarm Optimization,” Proc. IEEE Int. Conf. on Neural Networks, USA, 1995, pp. 1942-1948.
[25]. M. Tomono, “Robust Robot Localization and Map Building using a Global Scan Matching Method,” Proc. of IEEE Int. Conf. on Intelligent Robots and Systems (IROS), Japan, 2004, pp. 1059-1064.
[26]. Mobile Robot, http://www.mobilerobots.com/Mobile_Robots.aspx
[27]. 台灣西克股份有限公司， http://www.sick.com.tw/
[28]. L. Shang, C. Kai, and A. Liang, “A map-coverage algorithm basing on particle swarm optimization,” Eighth Int. Conference on Embedded Computing, China, 2009, pp. 87-91.
[29]. S. Rusinkiewicz and M. Levoy. “Efficient variants of the ICP algorithm,” Proc. 3-D Digital Imaging and Modeling, CA, 2001, pp. 145-152.
[30]. F. Lu, E. Milos. “Robot Pose Estimation in Unknown Environments by Matching 2D Range Scans,” Journal of Intelligent Robotics Systems: Theory and Applicant, Netherlands, 1997, pp. 249-275.
[31]. 張家瑋，研製具有探索未知室內環境功能之影像導航自走車，聖約翰科技大學電機工程系碩士論文，2009年。