本論文提出一套改良式SLAM系統，利用雷射測距儀取得實際環境資訊，此資訊可被視為環境物體幾何特徵資訊，然後將此特徵資訊應用在同時定位與地圖建置(SLAM)問題。在環境曲率特徵擷取模組上，本文採用改進K-Value演算法抓取環境特徵，將感測資訊視為一包含環境物體幾何特徵資訊之曲率線段，然後透過識別出基於不連續面所產生的斷點，並計算兩斷點間線段的曲率值，將高於門檻值之環境曲率特徵，將其視為環境地標群。在同時定位與地圖建置模組上，本文提出一套改良式FastSLAM演算法，以FastSLAM演算法做為架構，著重於加快運算速度，經過前處理後，利用高可信地標群之三角定位法更新機器人狀態，如此可維持地圖建置之精確率。經過模擬與實驗驗證，本文所提出之改良式SLAM系統，在於移動機器人之同時定位與地圖建置上，具有較佳的性能與提昇執行效率。

In this thesis, a modified SLAM system is proposed. This system use a laser range finder to accesses to environmental information, which represents the geometric features of objects in the environment and then it is applied on simultaneous localization and mapping (SLAM) problem. In the environmental curvature features extraction module, capturing environmental features use an improved adaptive K-Value algorithm. Sensor data is considered a curve segment which included geometric features and then extracted breakpoints based on discontinuous plane. Computing a curvature of a line segment between two breakpoints is considered environmental landmarks when the curvature over the threshold. In the SLAM module, a   proposed modified FastSLAM algorithm is based on FastSLAM algorithm, it focuses on improving computing speed. After pre-processing, updating robot status by high reliability landmark swarm triangulation method can be maintained accurately on mapping. Simulation and experimental results show that the proposed modified SLAM system has a better performance and enhancing efficiency for the SLAM of the mobile robot.

目 錄
目 錄	III
圖目錄	IV
表目錄	VI
第一章 緒論	1
1.1 研究背景	1
1.2 研究動機	5
1.3 論文架構	8
第二章 居家保全機器人系統	9
2.1 居家保全機器人系統介紹	9
2.2 蒙地卡羅定位	11
2.3 FastSLAM 1.0	14
2.4 FastSLAM 2.0	19
第三章 環境曲率特徵擷取	26
3.1 環境曲率特徵擷取演算法	26
3.2 改進K-Value曲率計算	28
3.3 曲率特徵特性	34
3.4 環境曲率特徵擷取模擬	36
第四章 改良式FastSLAM	39
4.1 機器人狀態預測	39
4.2 環境特徵與地標量測資料關聯	40
4.3 高可信地標群之三角定位法	41
4.4 機器人狀態更新	45
4.5 地標資料更新	46
4.6 改良式FastSLAM模擬	49
第五章 模擬與實驗結果	53
5.1 FastSLAM模擬結果與分析	53
5.2 環境曲率特徵擷取實驗結果	58
5.3 FastSLAM於居家環境實驗結果	66
第六章 結論與未來展望	78
參考文獻	80


圖目錄
圖 1.1、機器人領域三大研究範圍之涵蓋示意圖	2
圖 1.2、蒙地卡羅定位法應用於足球機器人定位	6
圖 1.3、同時定位與地圖建置運作示意圖	6
圖 2.1、居家保全機器人系統架構圖	9
圖 2.2、系統架構圖	10
圖 2.3、競爭法重取樣示意圖	13
圖 3.1、環境曲率特徵擷取流程圖	28
圖 3.2、真實轉角與虛擬轉角示意圖	29
圖 3.3、斷點判斷示意圖	29
圖 3.4、K-Value曲率(a)感測資訊圖與(b)K=5與K=15曲率比較圖	31
圖 3.5、向量長度與累積向量長度誤差圖	32
圖 3.6、改進K-Value曲率演算法	33
圖 3.7、曲率特徵特性(a)感測資訊圖與(b)轉角與圓弧曲率特徵特性	34
圖 3.8、曲率特徵值差異(a)感測資訊圖(b)轉角與圓弧Ci差異圖	35
圖 3.9、模擬環境示意圖	36
圖 3.10、斷點與環境曲率特徵示意圖	37
圖 3.11、環境曲率表	37
圖 4.1、三角定位示意圖	42
圖 4.2、最大似然性示意圖	44
圖 4.3、改進FastSLAM流程圖	48
圖 4.4、改良式FastSLAM模擬結果	50
圖 4.5、FastSLAM 1.0模擬結果	51
圖 4.6、FastSLAM 2.0模擬結果	51
圖 5.1、模仿實驗場地之虛擬平面地圖	53
圖 5.2、FastSLAM1.0模擬結果	55
圖 5.3、FastSLAM2.0模擬結果	56
圖 5.4、改良式FastSLAM模擬結果	57
圖 5.5、居家保全機器人	58
圖 5.6、環境曲率特徵擷取實驗場地一(a)幾何特徵物(b)實驗場地一	59
圖 5.7、實驗場地二平面圖	60
圖 5.8、雷射測距儀感測原理	61
圖 5.9、HOKUYO UTM-30LX雷射測距儀	61
圖 5.10、 ， ，斷點偵測之實驗結果	63
圖 5.11、 ， ，曲率特徵偵測之實驗結果	64
圖 5.12、 ， ，斷點偵測之實驗結果	65
圖 5.13、 ， ，曲率特徵偵測之實驗結果	65
圖 5.14、實驗場地實拍圖	67
圖 5.15、實驗場地隔間平面圖	67
圖 5.16、改良式FastSLAM於直線移動定位實驗結果	70
圖 5.17、改良式FastSLAM於旋轉移動定位實驗結果	72
圖 5.18、改良式FastSLAM於巡邏移動定位實驗結果	77


表目錄
表 1.1、圖 1.3符號圖表說明	7
表 2.1、第二章使用符號之彙整表	24
表 3.1、第三章使用符號之彙整表	38
表 4.1、模擬環境參數設定	49
表 4.2、FastSLAM模擬數據誤差統計	49
表 4.3、第四章使用符號之彙整表	52
表 5.1、FastSLAM模擬參數表	54
表 5.2、 FastSLAM模擬結果比較表	54
表 5.3、HOKUYO UTM-30LX規格表	62
表 5.4、環境曲率特徵擷取資訊穩定度	62
表 5.5、環境曲率特徵擷取執行時間	63
表 5.6、直線移動定位實驗結果	68
表 5.7、旋轉移動定位實驗結果	70
表 5.8、巡邏移動定位實驗結果	73

[1].	Google Puts Money on Robots, Using the Man Behind Android – from The New York Times
Website http://www.nytimes.com/2013/12/04/technology/google-puts-money-on-robots-using-the-man-behind-android.html
[2].	Google Adds to Its Menagerie of Robots– from The New York Times
Website http://www.nytimes.com/2013/12/14/technology/google-adds-to-its-menagerie-of-robots.html
[3].	H.F. Durrant-Whyte and T. Bailey, “Simultaneous localization and mapping (SLAM): Part I,” IEEE Robotics and Automation Magazine, Vol. 13, No.2, pp. 99-110, 2006.
[4].	H.F. Durrant-Whyte, “Uncertain geometry in robotics,” IEEE Transaction on Robotics and Automation, Vol. 6, No. 1, pp. 23-31, 1988.
[5].	R.C. Smith, “On the representation and estimation of spatial uncertainty,” International Journal of Robotics Research, Vol. 5, No. 4, pp. 56-68, 1986
[6].	N. Ayache and O. Faugeras, “Building, registrating, and fusing noisy visual maps,” International Journal of Robotics Research, Vol. 7, No.6, pp. 45-65, 1988
[7].	J.L. Crowley, “World modeling and position estimation for a mobile robot using ultrasonic ranging,” IEEE International Conference on Robotics and Automation, Vol. 2, pp. 674-680, 1989.
[8].	R. Chatila and J. Laumond, “Position referencing and consistent world modeling for mobile robots,” IEEE International Conference on Robotics and Automation, Vol. 2, pp. 138-145, 1985.
[9].	H.F. Durrant-Whyte, D. Rye and E. Nebot, “Localisation of automatic guided vehicles,” The 7th International Symposium on Robotics Research (ISRR’95), pp. 613-625, 1996.
[10].	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.
[11].	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.
[12].	J.J. Leonard and H.J.S. Feder, “A computational efficient method for large-scale concurrent mapping and localization,” The Ninth International Symposium on Robotics Research (ISRR’99), pp. 169-176, 2000.
[13].	M. Johnson-Roberson, O. Pizarro, S.B. Williams and I. Mahon, “Generation and visualization of large-scale three-dimensional reconstructions from underwater robotic surveys,” Journal of Field Robotics, Vol. 27, No. 1, pp. 21-51, 2010.
[14].	M.F. Fallon, J. Folkesson, H. McClelland and J.J. Leonard, “Relocating Underwater Features Autonomously Using Sonar-Based SLAM, ” IEEE Journal of Oceanic Engineering, Vol.38, No.3, pp.500,513, 2013.
[15].	J. Hollerbach and D. Koditscheck (Editors). The Ninth International Symposium on Robotics Research (ISRR’99), Springer-Verlag, 2000.
[16].	F. Lu and E. Milios, “Globally consistent range scan alignment for environment mapping,” Autonomous Robots, Vol. 4, No. 4, pp. 333-349, 1997.
[17].	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.
[18].	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.
[19].	K. Pathak, A. Birk, N. Vaskevicius and J. Poppinga, “Fast registration based on noisy planes with unknown correspondences for 3-D mapping,” IEEE Transactions on Robotics, Vol. 26, No. 3, pp. 424-441, 2010.
[20].	K. Pathak, N. Vaskevicius, J. Poppinga, M. Pfingsthorn, S. Schwertfeger and A. Birk, “Fast 3D mapping by matching planes extracted from range sensor point-clouds,” 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2009), pp. 1150-1155, 2009.
[21].	P. Nunez, R. Vazquez-Martin, J.C. del Toro, A. Bandera and F. Sandoval,  “Feature extraction from laser scan data based on curvature estimation for mobile robotics,” 2006 IEEE International Conference on Robotics and Automation (ICRA 2006)Proceedings, pp. 1167,1172, 2006.
[22].	R. Vazquez-Martin, P. Nunez, A. Bandera and Sandoval, “F. Curvature-Based Environment Description for Robot Navigation Using Laser Range Sensors,” Sensors, Vol. 9, pp. 5894-5918, 2009.
[23].	J.C. Noyer, R. Lherbier and B.Fortin, “Automatic feature extraction in laser rangefinder data using geometric invariance,” 2010 Conference Record of the Forty Fourth Asilomar Conference on Systems and Computers (ASILOMAR), pp. 199,203, 2010.
[24].	B. Fortin, R. Lherbier and J.C. Noyer, “Feature Extraction in Scanning Laser Range Data Using Invariant Parameters: Application to Vehicle Detection,” IEEE Transactions on Vehicular Technology, Vol. 61, pp.  3838,3850, 2012.
[25].	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.
[26].	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.
[27].	P.S. Maybeck. Stochastic Models, Estimation and Control, Vol. I., Academic Press, 1979.
[28].	M.W.M.G. Dissanayake, P. Newman, S. Clark, H.F. Durrant-Whyte and M. Csobra, “A solution to the simultaneous localisation and map building (SLAM) problem,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 3, pp. 229-241, 2001.
[29].	J.E. Guivant and E.M. Nebot, “Optimization of the simultaneous localization and map-building algorithm for real-time implementation,” IEEE Transactions on Robotics and Automation, Vol. 17, pp. 242-257, 2001.
[30].	J. Neira and J.D. Tardós, “Data association in stochastic mapping using the joint compatibility test,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 3, pp. 890-897, 2001.
[31].	M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, “FastSLAM: A factored solution to the simultaneous localization and mapping problem,” The National Conference on Artificial Intelligence, pp. 593-598, 2002.
[32].	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,” International Joint Conference on Artificial Intelligence, pp. 1151-1156, 2003.
[33].	R. Sim, P. Elinas, and J.J. Little, “A study of the Rao-Blackwellised particle filter for efficient and accurate vision-based SLAM,” International Journal of Computer Vision, Vol. 74, No. 3, pp. 303-318, 2007.
[34].	A. Doucet, N. De Freitas, N.J. Gordon, Sequential Monte Carlo Methods in Practice, Springer, 2001.
[35].	F. Dellaert, D. Fox, W. Burgard, and S. Thrun, “Monte Carlo localization for mobile robots,” IEEE International Conference on Robotics and Automation, Vol. 2, pp. 1322-1328, 1999.
[36].	S. Thrun, D. Fox, W. Burgard, and F. Dellaert, “Robust Monte Carlo localization for mobile robots,” Artificial Intelligence, Vol. 128, No. 1-2, pp. 99-141, 2001.
[37].	C. Harris and M. Stephens, “A Combined Corner and Edge Detector,” Paper presented at the meeting of the Proceedings of the 4th Alvey Vision Conference, 1988.
[38].	H. Bay, A. Ess, T. Tuytelaars and L. Van Gool, “Speeded-Up robust features (SURF),” Comput. Vis. Image Underst., Vol. 110, No. 3, pp. 346–359, 2008.
[39].	J. Forsberg, U. Larsson and A. Wernersson, “Mobile robot navigation using the range-weighted Hough transform,” Robotics & Automation Magazine, IEEE , Vol. 2, No.1, pp. 18,26, 1995.
[40].	G.A. Borges and M. Aldon, “Line extraction in 2D range images for mobile robotics,” Journal of Intelligentand Robotic Systems 40, pp.  67-297,  2004.
[41].	何丞堯，全方位視覺足球機器人之自我定位系統的設計與實現，淡江大學電機工程學系碩士論文(指導教授：翁慶昌)，2009。
[42].	陳家陽，粒子濾波器於具有全方位影像系統之足球機器人的定位設計，淡江大學電機工程學系碩士論文(指導教授：翁慶昌)，2010。
[43].	鄧宏志，結合粒子群最佳化法之雙層粒子濾波器於移動機器人的定位與地圖建置，淡江大學電機工程學系博士論文(指導教授：翁慶昌)，2011。
[44].	陳雨政，分離更新式FastSLAM之設計與實現，淡江大學機械與機電工程學系博士論文(指導教授：王銀添)，2012。
[45].	楊誠愷，具有高計算效率之視覺型即時定位與建圖演算法，國立師範大學應用電子科技學系碩士論文(指導教授：許陳鑑)，2013。
[46].	雷射光電研習會，雷射光電︰工業量測、控制、感測之應用，行政院國家科學委員會光電小組，1985