本文探討一嶄新技術求取戶外自走式機器人之定位與週遭地圖(Simultaneous Localization and Map Building, SLAM)建立，而所使用感測器只是一個一個雷射測距儀(Laser Range Finder)。不使用複雜且大計算量，如格子佔據(Occupancy Grid)，與線搜(Line Search)來建立機器人週遭環境。我們使用靜態的里程碑建構機器人的環境。它們提供了一種方式，如EKF的辦法來管理不確定性的定位與地圖。擴展型卡門濾波器(Extended Kalman Filter, EKF)已經成為在許多非線性的系統動態與量測方程式使用方面的一種標準技術，這方法被用來處理裝置在自走式機器人身上的感測器所獲得的資訊。然而，在近幾年，一個強靭之濾波器，即擴張型卡門粒子濾波器(Extended Particle Filter, EPF)來對付高度非線性的系統動態與量測方程式。
在粒子濾波器重新取樣部分，我們探討許多演算方法，例如剩餘值重新取樣演算法、分層式重新取樣演算法、和隨機取樣演算法....等。最後，我們創造出一個新的演算方法稱為剩餘分層重新取樣演算法。剩餘分層重新取樣演算法擁有剩餘值演算的優點和分層式演算法的特性，因此它能夠令粒子濾波器的估測更加精確。在收尋里程碑部分，我們使用spike landmark方法原理尋找里程碑。

This paper discussion novel technique, using only a single Laser Range Finder (LRF), is presented to resolve the task of Simultaneous Localization and Map Building (SLAM) for indoor mobile robot navigation problem.
Instead of using sophisticated, computationally intensive techniques like occupancy grid and line search for the construction of robot's environment. We use static landmark construction of robot's environment. They provide a way such as the EKF approaches to administer uncertainty of localization and mapping. The Extended Kalman Filter (EKF) has become a standard technique used in several nonlinear system dynamics and measurement process. This approach is used to process the information acquired by the sensors mounted on the mobile robot. However, in recently years, a more robust filtering scheme, so-called Extended Particle Filter (EPF), is adopted to accomplish the tracking job.
In EPF particle resample item, we discussion manys algorithm approach, such as Residual Resampling algorithm, Systematic Resampling algorithm, Random Resample algorithm, etc. Final, we create a new resample algorithm be called Residual Systematic Resampling.The RSR algorithm has the Residual algorithm benefits and Systematic algorithm property, wherefore it enables particle filter estimation more accurate. In finding for landmark part, we use the spike landmark method to find landmark.

摘 要 I
ABSTRACT II
表目錄 VI
圖目錄 VII
第一章 1
緒論 1
1.1 動機 1
1.2 論文大綱 3
第二章 基本概念 4
2.1 同時定位和地圖建構 4
2.1.1 主要設備 4
2.1.2 導航 5
2.2 量測裝置 6
2.2.1 雷射感測器 6
2.2.2 聲納感測器 7
2.2.3 視覺感測器 8
2.3繪圖方法 9
2.3.1 利用特徵點的方法 9
2.3.2 利用格子的方法 10
2.3.3 直接方法 10
2.3.4 比較結果 11
2.4 同時定位與繪圖的程序 12
2.5 里程碑定義 16
2.6 偵測里程碑的方法 16
2.6.1 Spike演算法 17
2.6.2 RANSAC 演算法 18
2.7 資料結合 18
第三章 同時定位與繪圖估測方法 21
3.1擴展式卡爾曼濾波器 21
3.1.1 移動式自走車的運動模型 23
3.1.2 程序模型 24
3.1.3 觀測模型 25
3.1.4 估測過程 26
3.2 粒子濾波器演算法 27
3.3 重新取樣 29
3.3.1 隨機重新取樣演算法 29
3.3.2 多項式重新取樣演算法 31
3.3.3 系統重新取樣演算法 33
3.3.4 剩餘值重新取樣演算法 35
3.4.5 剩餘值系統重新取樣演算法 39
第四章 模擬結果 42
參考文獻 55

[Dudek and Zhang, 1996]
G. Dudek and C. Zhang. Vision-Based Robot Localization without Explicit Object Models. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, pp. 76-81, 1996.
[Elfes, 1987]
A. Elfes. Sonar-Based Real-World Mapping and Navigation. Proceedings of the IEEE Journal of Robotics and Automation, vol. 3, no. 3, pp. 249-265, 1987.
[Cox, 1991]
J. Cox. Blanche-an Experiment in Guidance and Navigation of an Autonomous Robot Vehicle. Proceedings of the IEEE Transactions on Robotics and Proceedings of the IEEE International Conference on Robotics and Automation Society, vol. 7, no. 2, pp.193-204, 1991.
[Welch and Bishop, 2006]
G. Welch and G. Bishop. An Introduction to the Kalman Filter. http://www.cs.unc.edu/~welch/kalman/, 2006.
[ Maheswararajah and Halgamuge, 2007]
S. Maheswararajah and S. Halgamuge. Mobile Sensor Management for Ttarget Tracking. ISWPC '07. 2nd International Symposium on Wireless Pervasive Computing, pp. 506-510, 2007.
[Boers and Driessen, 1974]
Y. Boers and J. N. Driessen. Particle Flter Base Detection for Tacking. ACC Proceedings of the American Control conference, vol. 6, pp. 4393-4397, 2001.
[Gelb, 1974]
A.Gelb. Applied Optimal Estimation. MIT Press, 1974.
[Martinerie, 1997]
F. Martinerie. Data Fsion and Tracking Using HMMs in a Distributed Sensor Network. Proceedings of the IEEE Transactions on Aerospace and Electronic System, vol. 33, pp. 11-28, 1997.
[Cheeseman et al., 1987]
P. Cheeseman, R. Smith, and M. Self. A Stochastic Map for Uncertain Spatial Relationships. In 4th International Symposium on Robotics Research. MIT Press, 1987.
[Clark et al., 2001]
S. Clark, G. Dissanayake, P. Newman, and H. Durrant-Whyte. A Solution to Simultaneous Localisation and Map Building (SLAM) Problem. Proceedings of the IEEE Journal of Robotics and Automaton, vol. 17, no. 3, pp. 229-241, 2001.
[Guivant and Nebot, 2001]
J. Guivant and E. Nebot. Optimization of Smultaneous Localization and Map Building Algorithm for Real Time Implementation. Proceedings of the IEEE Journal of Robotics and Automaton, vol. 17, no. 3, pp. 731–747, 2001.
[Leonard and Feder, 2001]
J. Leonard and H. Feder. Decoupled Stochastic Mapping for Mobile Robot and Air Navigation. Proceedings of the IEEE Journal of Oceanic Engineering, vol. 66, no. 4, pp. 561–571, 2001.
[Neira and Tardos, 2001]
J. Neira and J.D. Tardos. Data Association in Stochastic Mapping Using the Joint Compatibility Test. Proceedings of the IEEE Transaction of Robotics and Automation, vol. 17, pp. 890–897, 2001.


[Zunino, 2002]
G. Zunino. Simultaneous Localization and Mapping for Navigation in RealisticEnvironments. ww.nada.kth.se/utbildning/forsk.utb/avhandlingar/lic/020220.pdf, 2002.
[Hoppen et al., 1990]
P. Hoppen, T. Knieriemen, and E. Puttkamer. Laser-Radar Based Mapping and Navigation for an Autonomous Mobile Robot. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, pp. 948–953, 1990.
[Borthwick et al., 1993]
S. Borthwick, M. Stevens, and H. Durrant-Whyte. Position Estimation and Tracking Using Optical Range Data. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 3, pp. 2172–2177, 1993.
[Buchberger et al., 1993]
M. Buchberger, K. W. Jorg, and E. Puttkamer. Laser-Radar and Sonar Based World Modeling and Motion Control for Fast Obstacle Avoidance of an Autonomous Robot Mobot-IV. Proceedings of the IEEE International Conference on Robotics and Automation, no. 1, pp. 534–540, 1993.
[Weiss and Puttkamer, 1995]
G. Weiss and E. Puttkamer. A Map Based on Laser Scans Without Geometric Interpretation. Intelligent Autonomous Systems, pp. 403–407, 1995.
[Forsberg et al., 1993]
J. Forsberg, P. A. Hman, and A. Wernersson. The Hough Transform Inside the Feedback Loop of a Mobile Robot. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, pp. 791–798, 1993.

[Guttman et al., 1998]
J.-S. Guttman, W. Burgard, D. Fox, and K. Konolige. An Experimental Comparison of Localization Methods. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, no. 2, pp. 736–743, 1998.
[Fox et al., 1999]
D. Fox, W. Burgard, and S. Thrun. Markov Localization for Mobile Robots in Dynamic Environments. Proceedings of the IEEE Journal of Artificial Intelligence Research, vol. 11, pp. 391–427, 1999.
[Jensfelt, 1999]
P. Jensfelt. Localization Using Laser Scanning and Minimalistic Environmental Models. Licentiate Thesis, Automatic Control Dept, Royal Institute of Technology, Stockholm, SE-100 44 Stockholm, Sweden, 1999.
[Jensfelt, 2001]
P. Jensfelt. Approaches to Mobile Robot Localization in Indoor Environments. Ph.D. thesis, Automatic Control Dep, Royal Institute of Technology, SE-100 44 Stockholm, Sweden, 2001.
[Kleeman, 1992]
L. Kleeman. Optimal Estimation of Position and Heading for Mobile Robots Using Ultrasonic Beacons and Dead-Reckoning. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 2582–2587, 1992.
[Kleeman and Kuc, 1994]
L. Kleeman and R. Kuc. An Optimal Sonar Array for Target Localization and Classification. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 4, pp. 3130–3135, 1994.
[Kleeman, 1999]
L. Kleeman. Fast and Accurate Sonar Trackers Using Double Pulse Coding. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1185–1190, Kyongju, Korea, 1999.
[Akbarally and Kleeman, 1995]
H. Akbarally and L. Kleeman. A Sonar Sensor for Accurate 3d Target Localisation and Classification. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 3003–3008, 1995.
[Peremans, 1994]
H. Peremans. A Maximum Likelihood Algorithm for Solving the Correspondence Problem in Tri-Aural Perception. Proceedings of the IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems, pp. 485–492, 1994.
[Audenaert et al., 1992]
K. Audenaert, H. Peremans, Y. Kawahara, and J. V. Campenhout. Accurate Ranging of Multiple Objects Using Ultrasonic Sensors. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, pp. 1733–1738, 1992.
[Heale and Kleeman, 2000]
A. Heale and L. Kleeman. A Real Time Dsp Sonar Echo Processor. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 1261-1266, Takamatsu, Japan, 2000.
[Stanley and McKerrow, 1997]
B. Stanley and P. McKerrow. Measuring Range and Bearing with a Binaural Ultrasonic Sensor. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 2, pp. 565–571, 1997.
[Barshan and Kuc, 1990]
B. Barshan and R. Kuc. Differentiating Sonar Reflections from Corners and Planes Employing an Intelligent Sensor. Proceedings of the IEEE International Conference on Pattern Analysis and Machine Intelligence, vol. 12, pp. 560–569, 1990.
[Barshan and Kuc, 1991]
B. Barshan and R. Kuc. Bat-Like Sonar System Strategies for Mobile Robots. Proceedings of the IEEE International Conference on Systems, on Man and Cybernetics, vol. 2, pp. 905–910, 1991.
[Kuc and Barshan, 1992]
R. Kuc and B. Barshan. Bat-Like Sonar for Guiding Mobile Robots. Proceedings of the IEEE International Conference on Control Systems Magazin, vol. 12, pp. 4–12, 1992.
[McKerrow and Zhu, 1996]
P. McKerrow and S. Zhu. Modelling Multiple Reflection Paths in Ultrasonic Sensing. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 1, pp. 284–291, 1996.
[Taylor and Kriegman, 1998]
C. Taylor and D. Kriegman. Vision-Based Motion Planning and Exploration Algorithms for Mobile Robots. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 14, no. 3, pp. 417-426, 1998.
[Buffa et al., 1992]
M. Buffa, O. Faugeras, and Z. Zhang. A Complete Navigation System for a Mobile Robot, Using Real-Time Stereovision and the Delaunay Triangulation. Proceedings of MVA92, IAPR Workshop on Machine Vision Applications, 1992.

[Murray and Jennings, 1997]
D. Murray and C. Jennings. Stereo Vision Based Mapping and Navigation for Mobile Robots. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, pp. 1694-1699, 1997.
[Pfister et al., 2003]
S. T. Pfister, S. I. Roumeliotis, and J.W. Burdick. Weighted Line Fitting Algorithms for Mobile Robot Map Building and Efficient Data Representation. Proceedings of the IEEE International Conference on Robotics and Automation, Taipei, vol. 1, pp. 1304-1311, Taiwan, 2003.
[Matthies and Elfes, 1988]
L. Matthies and A. Elfes. Integration of Sonar and Stereo Range Data Using a Grid-Based Representation. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 2, pp. 727–733, Philadelphia, Pennsylvania, USA, 1988.
[Martin and Moravec, 1996]
C. Martin and H. Moravec. Robot Evidence Grids. Technical Report CMU-RI-TR-96-06, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, March, 1996.
[Konolige and Chou, 1999]
K. Konolige and K. Chou. Markov Localization Using Correlation. Proceedings of the International Joint Conference on Artificia Intelligence, pp. 1154–1169, 1999.




[Kelly and Unnikrishnan, 2003]
A. Kelly and R. Unnikrishnan. Efficient Construction of Optimal and Consistent Ladar Maps Using Pose Network Topology and Nonlinear Programming. Proceedings of the 11th International Symposium of Robotics Research, Siena, Italy, 2003.
[Gutmann and Konolige, 1999]
J.-S. Gutmann and K. Konolige. Incremental Mapping of Large Cyclic Environments. Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, pp. 318-325, 1999.
[Thrun et al., 2000]
S. Thrun, W. Burgard, and D. Fox. A Real-Time Algorithm for Mobile Robot Mapping with Applications to Multi-Robot and 3D Mapping. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, pp. 321-328, San Francisco, CA, 2000.
[Besl and McKay, 1992]
P.J. Besl, H.D. McKay. A Method for Registration of 3-D Shapes. Proceedings of the IEEE Transaction on Pattern Analysis and Machine Intelligence, vol. 14, pp. 239–256, 1992.
[Chen and Medioni, 1991]
Y. Chen and G. Medioni. Object Modeling by Registration of Multiple Range Images. Proceedings of the IEEE International Conference on Robotics and Automation, vol. 3, pp. 2724-2729, 1991.
[Zhang, 1994]
Z. Zhang. Iterative Point Matching for Registration of Free-form Curves and Surfaces. Proceedings of the IEEE International Conference on pattern analysis and machine intelligence, vol. 13, pp. 119–152, 1994.
[Rusinkiewicz and Levoy, 2001]
S. Rusinkiewicz and M. Levoy. Efficient Variants of the Icp Algorithms. Proceedings of the International Conference on 3-D Digital Imaging and Modeling, pp. 145–152, 2001.
[Johnson, 1997]
A. Johnson. Spin-Images: A Representation for 3-D Surface Matching. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, 1997.
[Potmesil, 1983]
M. Potmesil. Generating Models of Solid Objects by Matching 3d Surface Segments. Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1089–1093, 1983.
[Feldmar and Ayache, 1994]
J. Feldmar and N. Ayache. Rigid and Affine Registration of Smooth Surfaces Using Differential Properties. Proceedings of the European Conference on Computer Vision, pp. 397–406, Stockholm, Sweden, 1994.
[Garland and Heckbert, 1998]
M. Garland and P. Heckbert. Simplifying Surfaces with Color and Texture Using Quadric Error Metrics. Proceedings of the IEEE International Conference on Visualization 98, pp. 263–269, 1998.
[Turk and Levoy, 1994]
G. Turk and M. Levoy. Zippered Polygon Meshes from Range Images. Proceedings of the SIG-GRAPH, pp. 311–318, Orlando, FL, 1994.
[Menq et al., 1992]
C. H. Menq, H. T. Yau, and G. Y. Lai. Automated Precision Measurement of Surface Profile in CAD-Directed Inspection. Proceedings of the IEEE Transaction on Robotics and Automation, vol. 8, pp. 268–278, 1992.
[Champleboux et al., 1992]
G. Champleboux, S. Lavallee, and R. L. Szeliski. From Accurate Range Imaging Sensor Calibration to Accurate Model-Based 3-D Object Localization. Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition, pp. 83–89, 1992.
[Gutmann and Schlegel, 1996]
J.-S. Gutmann and C. Schlegel. AMOS: Comparison of Scan Matching Approaches for Selflocalization in Indoor Environments. In First European workshop on advanced mobile robots, 1996.
[Simon, 1996]
D. Simon. Fast and Accurate Shape-Based Registration. Ph.D. thesis, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, 1996.
[Lee et al., 2002]
B. U. Lee, C. M. Kim, and R. H. Park. An Orientation Reliability Matrix for the Iterative Closest Point Algorithm. Proceedings of the IEEE International Conference on Pattern Analysis and Machine intelligence, vol. 32, pp. 1205-1208, 2002.
[Bengtsson and Baerveldt, 2001]
O. Bengtsson and A.-J. Baerveldt. Localization in Changing Environments - Estimations of a Covariance Matrix for the IDC Algorithm. Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, vol. 4, pp. 1931-1937, 2001.
[Pennec and Thirion, 1997]
X. Pennec and J.-P. Thirion. Validation of 3-D RegistrationMethods Based on Points and Frames. International Journal of Computer Vision, vol. 3, pp. 203-229, 1997.
[Smith and Cheesman, 1987]
R. C. Smith and P. Cheesman. On the Representation of Spatial Uncertainty. International Journal of Robotics Research, vol. 5, no. 4, pp. 56–68, 1987.
[Smith et al., 1990]
R. Smith, M. Self, and P. Cheeseman. Estimating Uncertain Spatial Relationships in Robotics. Proceedings of the IEEE International Conference on Autonomous Robot Vehicles, pp. 167-193, 1990.
[Lewis, 1986]
F. L. Lewis. Optimal Estimation with an Introduction to Stochastic Control Theory. John Wiley & Sons, Inc., 1986
[Bar-Shalom and Fortmann, 1988]
Y. Bar-Shalom and T. E. Fortmann. Tracking and Data Association. Artech House, 1988
[Feder, 1999]
H. J. S. Feder. Simultaneous Stochastic Mapping and Localization. Ph.D. Thesis. Massachusetts Institute of Technology. June 1999.
[Arulampalam et al., 2002]
S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp. A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking. Proceedings of the IEEE Transactions on Signal Processing, vol. 50, pp. 174-188, 2002.
[Schulz et al., 2001]
D. Schulz, W. Burgard, D. Fox, and A. Cremers. Tracking Multiple Moving Target with a Mobile Robot Using Particles Filters and Statistical Data Association. Proceedings of the IEEE International Conference on Robotics and Automation, Seoul, Korea, vol. 2, pp. 1665-1670, 2001.

[Yilin, 2009]
S. S. Yilin. Localization and Mapping for an Ultrasonic Positioning System. http://pc01.lib.ntust.edu.tw:1793/ETD-db/ETD-search-c/view_etd?URN=etd-0704109-131902, 2009