簡易檢索 / 詳目顯示

研究生: 張華恩
CHANG,Hua-En
論文名稱: 使用PSO調整之增強型ICP演算法於未知環境地圖之建立
Map Building of Unknown Environment Using PSO-Tuned Enhanced Iterative Closest Point Algorithm
指導教授: 許陳鑑
Hsu, Chen-Chien
學位類別: 碩士
Master
系所名稱: 電機工程學系
Department of Electrical Engineering
論文出版年: 2013
畢業學年度: 101
語文別: 中文
論文頁數: 72
中文關鍵詞: 迭代最近點粒子群聚最佳化地圖建立
英文關鍵詞: Iterative Closest Point, Particle swarm optimization, map building
論文種類: 學術論文
相關次數: 點閱:217下載:5
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報
  • 本論文使用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 1.1. 研究背景與動機 1 1.2. 研究目的 2 1.3. 研究問題與方法 2 1.4. 論文結構 4 第二章 文獻探討 5 2.1. 機器人建立地圖之探討 5 2.2. 迭代最近點演算法 5 2.3. 標準ICP演算法 12 2.4. 加權式ICP 14 2.5. 粒子群聚演算法(PSO) 15 第三章 增強型 ICP演算法 18 3.1. 全域地圖資訊 18 3.2. 尋找重疊的資訊點 20 3.3. 全域地圖門檻值 24 3.4. 加權增強型 ICP 29 3.5. 增強型 ICP建立地圖 30 第四章 PSO調整增強型 ICP演算法 33 4.1. PSO輔助對齊 33 4.2. 使用PSO調整增強型ICP演算法建立環境地圖 38 第五章 實驗結果 40 5.1. 實驗設備與環境 40 5.2. 環境地圖建立結果與分析 48 5.3. 建立環境地圖 64 第六章 結 論 69 參 考 文 獻 70

    [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年。

    下載圖示
    QR CODE