臺灣博碩士論文加值系統

即時定位與地圖構建(Simultaneous localization and mapping, SLAM)，也就是讓機器人在即時定位過程中同時對陌生環境進行構圖，近年來是機器人領域重要的課題之一，特別是無人車與無人機的廣泛使用，使機器人更貼近人類的日常生活。本篇論文針對SLAM中的即時定位分成兩大主題並進行探討：一、狀態預測部分，預測機器人現在所在位置並校正，其中包含了測距(Odometry)輸入以及掃描匹配(Scan matching)輸入，在各種路徑、環境還有障礙物因素下兩者各有其優劣之處；二、狀態更新部分，將參數透過擴展型卡爾曼濾波器(Extended Kalman Filter, EKF)配合地標(Landmark)設計來更新機器人在下個時間點狀態的位置點校正，由以上兩步驟達到機器人的定位同步更新。
本論文於狀態預測中的掃描匹配(Scan-matching)中使用了疊代最近點(Iterative Closest Point, ICP)演算法進行兩個時間點的環境資料進行配準比較，因為在SLAM的計算過程中，時常因為龐大的計算資料輸入而導致定位偏移，若無法有效將其引導至正確的狀態預測，必然在更新步驟中會產生嚴重的累積誤差，ICP(Iterative Closests Point)演算法疊代中，點集與點集間的搜索使用的是德勞內三角剖分(Delaunay triangulation)及奇異值分解法來判斷是否有合適的環境點集資料，提高掃描匹配的效率以及協助測距輸入來互相補足在狀態預測時的不佳成效，特別是在複雜地形時可看出其差異，實驗證明兩者的搭配可有效提升狀態預測時的位置校正，更能幫助EKF演算法提升狀態更新後的準確度，進而達到更好的即時定位。

Simultaneous localization and mapping (SLAM) is a method that let robotics construct or update a map of an unknown environment while simultaneously locating the position of robots itself. It is gradually become a important issue these days, especially unmanned aerial vehicle. This kind of robots make our livelihood more convenient and efficient. In this paper we divide simultaneously locate of SLAM into two parts for discussion. The first is about state prediction in robotics which including odometry and scan-matching, these two types of function can assist robotics guiding to a better state prediction. The second is about the state update. Robots execute state update through Extended Kalman Filter (EKF) and design of landmark to maintain the correction of position and revise the bias of location. After these two step of state, robotics ultimately complete the simultaneously locate.
Because the bias of position may become large after a complex calculation, we need a better state predict to make sure the better state update. In this paper we use Iterative closest point (ICP) to execute scan-matching to assist state prediction. ICP algorithm is used to compare the environmental point sets at two time-points. By using Delaunay triangulation and singular value decomposition to raise ICP’s point sets searching speed then assist Odomtry to complete a perfect state prediction. The experimental results proof that scan-matching and odometry can support each other at some situations; especially, in complicated terrain architecture. As a result, the proposed EKF-SLAM algorithm improves the accuracy of locating the position of robots and thus achieving a higher efficiency SLAM.

摘要...I
ABSTRACT...II
誌謝...III
第一章 緒論...1
1.1前言...1
1.2 研究動機與目的...2
1.3 各章提要...2
第二章 機器人定位與預測的概念...3
2.1機器人的不確定性與機率機器人...3
2.2 遞歸狀態的預測...5
2.3貝氏定理(Bayes' theorem)...5
第三章 狀態預測...7
3.1運動學概述...7
3.2測距輸入介紹...8
3.3掃描匹配輸入之疊代最近點...10
3.3.1德勞內三角化...12
3.3.2德勞內三角剖分...13
3.3.3奇異值分解...17
3.3.4主成分分析...18
3.4德勞內疊代最近點...20
第四章 狀態更新與SLAM地圖環境...22
4.1卡爾曼濾波器介紹...22
4.2擴展式卡爾曼濾波器介紹...24
4.3地圖地標介紹...29
第五章 實驗架構與結果分析...35
5.1程式架構...35
5.2實驗模擬分析...37
5.2.1機器人於單純地圖移動模擬...38
5.2.2機器人於複雜地圖移動模擬─十字路...42
5.2.3機器人於複雜地圖移動模擬─五邊形...46
第六章 結論與展望...50
參考文獻...52

[1]APRIL GLASER. ” Watch Amazon’s Prime Air make its first public U.S. drone delivery”, Recode newsletter,MAR 24, 2017,from https://www.recode.net/2017/3/24/15054884/amazon-prime-air-public-us-drone-delivery
[2]APRIL GLASER. ” Virginia is the first state to pass a law allowing robots to deliver straight to your door”, Recode newsletter,MAR 1, 2017,from https://www.recode.net/2017/3/1/14782518/virginia-robot-law-first-state-delivery-starship
[3]Paz, Lina M., Juan D. Tardós, and José Neira. “Divide and Conquer: EKF SLAM in O(n) ” IEEE Transactions on Robotics 24.5 (2008),P1107-1120,2008
[4]Mur-Artal, Raúl, and Juan D. Tardós. “Probabilistic Semi-Dense Mapping from Highly Accurate Feature-Based Monocular SLAM”, Robotics: Science and Systems. 2015.
[5]Mikael Norrl¨of . ” Iterative Learning Control Analysis, Design, and Experiments”.Link¨oping Studies in Science and Technology, Sweden, Dissertations No. 653, 2000.
[6]Oh, S-R., Zeungnam Bien, and Il Hong Suh. “An iterative learning control method with application to robot manipulators”, IEEE Journal on Robotics and Automation 4.5 (1988),P508-514,1988.
[7]J. Guivant, E. Nebot. “Optimization of the simultaneous localization and map building algorithm for real time implementation”, IEEE Transactions on Robotics and Automation, Vol.17(3),P242–257, 2001.
[8]Bailey, Tim, and Hugh Durrant-Whyte. “Simultaneous localization and mapping (SLAM): Part II”, IEEE Robotics & Automation Magazine 13.3 (2006),P108-117,2006.
[9]Thrun, Sebastian. “Is robotics going statistics? The field of probabilistic robotics”, Communications of the ACM 45.3 (2001),P1-8,2001.
[10]Puga JL, Krzywinski M, Altman N. “Bayes' theorem”,Nature Methods, Vol.12 (4), P277–278, 2015.
[11]Meinhold, Richard J., and Nozer D. Singpurwalla. “Understanding the Kalman filter”, The American Statistician 37.2 (1983): 123-127,1983.
[12]Sciavicco, Lorenzo, and Bruno Siciliano. “Modelling and control of robot manipulators”, Springer Science & Business Media, 2012.
[13]Guibas, Leonidas J., Rajeev Motwani, and Prabhakar Raghavan. “The robot localization problem in two dimensions”,Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1992.
[14]David Valiente García, Lorenzo Fernández Rojo, Arturo Gil Aparicio, Luis Payá Castelló, and Oscar Reinoso García. ” Visual Odometry through Appearance- and Feature-Based Method with Omnidirectional Images”, Journal of Robotics Vol.2012, 2012.
[15]Weiß, Gerhard, Christopher Wetzler, and Ewald Von Puttkamer. “Keeping track of position and orientation of moving indoor systems by correlation of range-finder scans”, Intelligent Robots and Systems 94. Advanced Robotic Systems and the Real World, IROS 94. Proceedings of the IEEE/RSJ/GI International Conference,Vol.1, IEEE,1994.
[16]Besl, Paul J., and Neil D. McKay. “A method for registration of 3-D shapes”, IEEE Transactions on pattern analysis and machine intelligence14.2,P239-256,1992.
[17]Faugeras, O. and Hebert, M. “The Representation, Recognition,and Locating of 3-D Objects” Int. J. Robotic Res, Vol. 5(3), 1986.
[18]S. Rusinkiewicz, M. Levoy.” Efficient variants of the ICP algorithm View Document”, In 3-D Digital Imaging and Modeling. 2001,Proceedings Third International Conference, Quebec City, Quebec, Canada, Canada , 2002.
[19]William Farish. “On Isometrical Perspective”. In Cambridge Philosophical Transactions, Vol.1,1822.
[20]許克平(2014)。一種改進的用於三維DT剖分的三角網生長算法。2014年微型機與應用第15期。
[21]紙異獸(2015)。三角剖分算法(delaunay)。 2015年4月16日，取自http://www.cnblogs.com/zhiyishou/p/4430017.html
[22]王婷(2009)。Delaunay三角剖分及算法基本知識。2009年2月24日，取自http://blog.sciencenet.cn/blog-116465-216935.html
[23]Lee, Der-Tsai, and Bruce J. Schachter. “Two algorithms for constructing a Delaunay triangulation”,International Journal of Computer & Information Sciences 9.3 (1980),P219-242,1980.
[24]A. Bowyer. ” Computing Dirichlet tessellations” , The Comput Journal ,Vol.24 (2), P162-166, 1981.
[25]Watson, David F. “Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes”,The computer journal 24.2,P167-172,1981.
[26]Shamos, Michael Ian, and Dan Hoey. “Closest-point problems”, Foundations of Computer Science, 1975., 16th Annual Symposium on. IEEE, 1975.
[27]Shamos, Michael Ian. “Geometric complexity”, Proceedings of seventh annual ACM symposium on Theory of computing. ACM, 1975.
[28]劉剛、李永樹、張永艦(2011)。基於不規則三角網構建的網格生長算法。計算機工程，37(12)，P56-58。
[29]Hasan, Md Mosaddik, Biswajit Bala, and Atsuo Yoshitaka. “SVD aided eigenvector decomposition to compute PCA and it's application in image denoising”, Informatics, Electronics & Vision (ICIEV), 2015 International Conference on. IEEE, 2015.
[30]Sorkine, Olga. “Least-squares rigid motion using svd”, Technical notes 120.3 (2009): 52,2009
[31]Dou, Jianfang, Qin Qin, and Zimei Tu. "Improved SVD matching based on Delaunay triangulation and belief propagation" ,Optik-International Journal for Light and Electron Optics 126.24 (2015): 4861-4867,2015.
[32]Henderson, Geoff. “Fundamentals of Kalman Filtering: a Practical Approach–Third edition”, The Aeronautical Journal,114.1152 (2010), P121-122,2010.
[33]Bishop, Gary, and Greg Welch. “An introduction to the kalman filter”, Proc of SIGGRAPH, Course 8.27599-23175 (2001): 41,2001.
[34]Duerinckx, A., et al. “Study of the Jacobian of an Extended Kalman Filter for soil analysis in SURFEXv5”, Geoscientific Model Development Discussions 7.5 ,2014.
[35]Thrun, Sebastian. “Probabilistic robotics”,Communications of the ACM 45.3 (2002), P52-57,2002.
[36]Julier, Simon J., and Jeffrey K. Uhlmann. “Unscented filtering and nonlinear estimation”, Proceedings of the IEEE 92.3 (2004): 401-422,2004.