近年來，機器人相關領域一直是熱門的研究課題，而機器人的自主式同步定位與地圖建立演算法也是研究對象之一。其演算法的目的在於利用可預測狀態的濾波器輔助排除系統及觀測之雜訊，並同步進行就機器人其所在位置之定位與建立其週遭之地圖，精確的機器人自我位置之定位及地圖之建立對於機器人探索未知環境與對周遭環境之互動有所幫助。不同的機器人同步定位與地圖建立演算法通常搭配既定的地圖表達方式，而地圖表達方式與演算法搭配的選擇則與機器人所在的環境有所關係。本論文提出一可適用於室內與室外的機器人自主式同步定位與地圖建立演算法系統。本系統設定二維雷射測距儀做為機器人對於其環境之觀測資料來源，演算法將收到之連續資料分類為類似牆狀的室內與類似錨狀的室外觀測資料群，針對類似室外之觀測資料群使用混合Rao-Blackwellized 粒子濾波器與擴展式卡爾曼濾波器的FastSLAM進行濾波，針對類似室內之觀測資料群則是採取以線段做為基底的表達方式做為地圖儲存與更新，並使用格狀的概念針對線段內的每個量測點進行權重的計算。根據本論文的模擬結果顯示，此一演算法可有效降低誤差與運算時間。

In the recent decade, the field of robotic has been a popular issue and the robot simultaneously localization and mapping (SLAM) algorithm is one of the part. The goal of the algorithm is to use the estimation filter to reduce the measurement and process noise, locate the position of the robot and build the map. A precisely localization of robot position and the built of the map will benefit for robot to explore unknown area and react with the environment nearby. Different SLAM algorithm often matches fixed representations of the map, and the choices of the representations and algorithms have to do with the real environment the robot is in. The thesis develops an SLAM algorithm which can suit both indoor and outdoor environment, it uses laser range finder as the measurement device to receive data of the environment. The algorithm classifies the serial data into wall-like indoor and anchor-like outdoor part. The anchor-like part is filtered with FastSLAM which combines Rao-Blackwellized particle filter and extended Kalman filter, while the wall-like part is stored and rearranged with a segment-based representation and calculated weight with a grid concept. According to the simulation result of the thesis, the algorithm can efficiently reduce the error and calculating time.

[1] D. Blackwell, “Conditional expectation and unbiased sequential estimation,”The Annals of Mathematical Statistics, Vol. 18, 1947, page 105-110.

[2] T. Bailey, J. Nieto, and E. Nebot, “Consistency of the FastSLAM algorithm,” in Proceedings of IEEE International Conference Robot. Automation, 2006, page 424-429.

[3] P. Cheeseman and R.C. Smith, “On the representation and estimation of spatial uncertainty,” International Journal of Robotics, Vol. 5, 1986, page 56-58.

[4] Y.H. Choi, T.K. Lee, and S.Y. Oh, “A line feature based SLAM with low grade range sensors using geometric constraints and active exploration for mobile robot.” Autonomous Robots, Vol. 24, 2005, page 13-27.

[5] J. Crowley, “World modeling and position estimation for a mobile robot using ultrasonic ranging,” in Proceedings of IEEE Conference on Robotics and Automation, Scottsdale AZ, USA, Vol. 3, 1989 , page 1574-1579.

[6] M. Csorba, Simultaneous Localisation and Map Building, PhD dissentation, University of Oxford, 1997.

[7] M. Cugliari and F. Martinelli, “A FastSLAM algorithm based on the unscented filtering with adaptive selective resampling,”Field and Service Robotics, Vol. 42, 2008, page 359–368.

[8] Doucet, J.F.G. de Freitas, K. Murphy, and S. Russel. “Rao-Blackwellized particle filtering for dynamic bayesian networks,” in Proceedings of the Conference on Uncertainty in Artificial Intelligence, Stanford, CA, USA, 2000, page 176–183.

[9] A. Elfes, “Sonar-Based Real-World Mapping and Navigation,” IEEE Journals of Robotics and automation, Vol. 3, No. 3, June 1987, page 249-265.

[10] A. Eliazar and R. Parr, ”DP-SLAM: Fast, robust simultainous localization and mapping without predetermined landmarks”. in Proceedings of the International Joint Conference on Artificial Intelligence, Acapulco, Mexico, 2003, page 1135–1142.

[11] R. Eustice, H. Singh, and J.J. Leonard, “Exactly sparse delayed-state filters,” in Proceedings of the IEEE International Conference on Robotics & Automation, Barcelona, Spain, 2005, page 2428–2435.

[12] U. Frese and G. Hirzinger, “Simultaneous localization and mapping - a discussion,” in Proceedings of the IJCAI Workshop on Reasoning with Uncertainty in Robotics, Seattle, WA, USA, 2001, page 17–26.

[13] C. Fulgenzi, G. Ippoliti, S. Longhi, “Experimental validation of FastSLAM algorithm integrated with a linear features based map,” Mechatronics, Vol. 19, Issue 5, August 2009, page 609-616

[14] J. Guivant, E. Nebot, J. Nieto, and F. Masson, “Navigation and mapping in large unstructured Environments,” The International Journal of Robotics Research, Vol. 23, No. 4-5 , April 2004, page 449-472.

[15] D. Hähnel, W. Burgard, D. Fox, and S. Thrun, “A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements,” in Proceedings IEEERSJ International Conference on Intelligent Robots and Systems, 2003, page 206-211.

[16] K.L. Ho and P.M. Newman, “Loop closure detection in slam by combining visual and spatial appearance,” Robotics and Autonomous Systems, Vol. 54, No. 9, 2006, page 740–749.

[17] J. Hoffmann, M. Spranger, D. Gohring, M. Jungel, and H. Burkhard, “Further studies on the use of negative information in mobile robot localization,” in Proceedings of the IEEE International Conference on Robotics and Automation, Orlando,Florida , 2006, page 62-67.

[18] S. Julier, J. Uhlmann, and H.F. Durrant-Whyte, “A new approach for filtering nonlinear systems,” in Proceedings of the American Control Conference, Seattle, WA, USA, 1995, page 1628–1632.

[19] N. Kwak, G.W. Kim and B.H. Lee, “A new compensation technique based on analysis of resampling process in FastSLAM,” Robotica, Vol. 26, 2008, page 205–217.

[20] C. S. G. Lee, H. J. Chang, Yung-Hsiang Lu, and Y. C. Hu, “P-SLAM: Simultaneous localization and mapping with environmental-structure prediction” , IEEE transections on Robotics, Vol.23, No. 2, 2007, page 281-293.

[21] J. Leonard and P. Newman, “Consistent, convergent, and constant-time SLAM,” in Proceedings of 18th International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 2003, page 1143–1150.

[22] J. J. Leonard and H. F. Durrant-Whyte, “Mobile robot localization by tracking geometric beacons,” IEEE Transactions in Robotics and Automation, Vol. 7, 1991, page 376-382.

[23] J.S. Liu, “Metropolized independent sampling with comparisons to rejection sampling and importance sampling,” Statistics and Computing, Vol. 6, 1996, page 113–119.

[24] Y. Liu and S. Thrun, “Results for outdoor-SLAM using sparse extended information filters,” in Proceedings of the International Conference on Robotics and Automation, Vol. 1, 2003, page 1227-1233.

[25] M. Montemerlo, S. Thrun, D. Koller, and B. Wegbreit, ”FastSLAM: A factored solution to simultaneous localization and mapping,” In Proceedings of the National Conference on Artificial Intelligence, Edmonton, Canada, 2002, page 593–598.

[26] 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,” in Proceedings of the International Joint Conference on Artificial Intelligence, 2003, pages 1151–1156.

[27] M. Montemerlo and S. Thrun, “Simultaneous localization and mapping with unknown data association using FastSLAM,” in Proceedings of the IEEE International Conference on Robotics and Automation, Vol. 2, Taipei, Taiwan, 2003, page 1985-1991.

[28] H.P. Moravec and A.E. Elfes, “High resolution maps from wide angle sonar,” in Proceeding of the IEEE International. Conference on Robotics & Automation, St.Louis, MO, USA, 1985, page 116–121.

[29] H. P. Moravec, “Sensor fusion in certainty grids for mobile robots,” AI Magazine,Vol. 9, No. 2, 1988, page 61-74.

[30] P. Moutarlier and R.Chatila, “An experimental system for incremental environment modelling by an autonomous mobile robot,” Lecture Notes in Control and Information Sciences, Vol. 139, 1990, page 327-346.

[31] P. Moutarlier and R.Chatila, “Stochastic multisensory data fusion for mobile robot location and environment modeling,” in 5th International Symposium on Robotics Research, 1989, page 85-94.

[32] K. Murphy, “Bayesian map learning in dynamic environments,” in Proceedings of the Conference on Neural Information Processing Systems, Denver, CO, USA, 1999, page 1015–1021.

[33] E. M. Nebot, J. I. Nieto, and J. E. Guivant,” The hybrid metric maps (HYMMs): A novel map representation for denseslam,” in Proceedings of the IEEE International Conference on Robotics & Automation, Vol. 1, 2004, page 391-396.

[34] J. Neira and J.D. Tard´os, “Data association in stochastic mapping using the joint compatibility test,” IEEE Transactions on Robotics and Automation, Vol. 17, No. 6, 2001, page 890–897.

[35] V. Nguyen, A. Martinelli, N. Tomatis, and R. Siegwart, “A comparison of line extraction algorithms using 2D laser rangefinder for indoor mobile robotics,” In IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS, Edmonton, Canada, 2005, page 1929 – 1934.

[36] CR Rao, “Information and the accuracy attainable in the estimation of statistical parameters,” Bulletin of the Calcutta Mathematical. Society 37, 1945, page 81-91.

[37] R Smith, M. Self, and P. Cheeseman, ”Estimating uncertain spatial relationships in robotics,” Autonomous Robot Vehicles, Springer-Verlag, 1990, page 167-193.

[38] R. Sim and J.J. Little, “Autonomous vision-based exploration and mapping using hybrid maps and Rao-Blackwellised particle filters,” Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference, Oct. 2006, page 2082–2089.

[39] G. S. Sukhatme, A. Howard, and M. J. Mataric´, “Multirobot Simultaneous Localization and Mapping Using Manifold Representations,” In Proceedings of the IEEE - Special Issue on Multi-robot Systems, Vol. 94, No. 7, 2006, page 1360–1369.

[40] S,Thrun, “A probabilistic on-line mapping algorithm for teams of mobile robots,” The International Journal of Robotics Research, Vol. 20, 2001, page 335-363.

[41] S. Thrun and A. Bücken, “Integrating grid-based and topological maps for mobile robot navigation,” In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Portland, OR, August 1996, page 944-950.

[42] S. Thrun, Y. Liu, D. Koller, A.Y. Ng, Z. Ghahramani, and H.F. Durrant-Whyte, “Simultaneous localization and mapping with sparse extended information filters,” International Journals of Robotics Research, Vol. 23, 2004, page 693–716.

[43] S. Thrun, “Towards programming tools for robots that integrate probabilistic computation and learning,” in Proceedings of the IEEE International Conference in Robotics and Automation, San Francisco, CA, Vol. 1, 2000, page 306 – 312.

[44] S. Thrun, W. Burgard, and D. Fox, "Probabilistic Robotics". MIT Press, ISBN 0-262-20162-3, 2005.

[45] S. H. Tseng, W. J. Kuo, J. Y. Yu, and L. C. Fu, “A hybrid approach to RBPF based SLAM with grid mapping enhanced by line matching,” Intelligent Robots and Systems,2009, page 1523-1528.

[46] K.M.Wurm, C. Stachniss, and G. Grisetti, “Bridging the Gap Between Feature- and Grid-based SLAM,” Robotics and Autonomous Systems, Vol. 58, Issue 2, 2010, page 140-148.

[47] L.Zhang and B.K. Ghosh, “Line segment based map building and localization using 2D laser rangefinder,” in Proceedings of the 2000 IEEE International Conference on Robotics & Automation, vol.3,San Francisco, CA, April 2000, page 2538 – 2543.