Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2008 | OriginalPaper | Chapter

37. Simultaneous Localization and Mapping

Authors : Sebastian Thrun, Prof, John J. Leonard, Prof

Published in: Springer Handbook of Robotics

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This chapter provides a comprehensive introduction in to the simultaneous localization and mapping problem, better known in its abbreviated form as SLAM. SLAM addresses the problem of a robot navigating an unknown environment. While navigating the environment, the robot seeks to acquire a map thereof, and at the same time it wishes to localize itself using its map. The use of SLAM problems can be motivated in two different ways: one might be interested in detailed environment models, or one might seek to maintain an accurate sense of a mobile robotʼs location. SLAM serves both of these purposes.
We review three major paradigms of algorithms from which a huge number of recently published methods are derived. First comes the traditional approach, which relies on the extended Kalman filter (EKF) for representing the robotʼs best estimate. The second paradigm draws its intuition from the fact that the SLAM problem can be viewed as a sparse graph of constraints, and it applies nonlinear optimization for recovering the map and the robotʼs locations. Finally, we survey the particle filter paradigm, which applies nonparametric density estimation and efficient factorization methods to the SLAM problem. This chapter discusses extensions of these basic methods. It elucidates variants of the SLAM problem and proposes a taxonomy for the field. Relevant research is referenced extensively, and open research problems are discussed.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter World Modeling
next chapter Behavior-Based Systems
Literature
37.1.
K.F. Gauss: Theoria Motus Corporum Coelestium (Theory of the Motion of the Heavenly Bodies Moving about the Sun in Conic Sections) (Little, Brown, and Co., Republished in 1857, and by Dover in 1963, 1809)
37.2.
G. Konecny: Geoinformation: Remote Sensing, Photogrammetry and Geographical Information Systems (Taylor Francis, New York 2002)
37.3.
C. Tomasi, T. Kanade: Shape and motion from image streams under orthography: A factorization method, Int. J. Comput. Vis. 9(2), 137–154 (1992)CrossRef
37.4.
S. Soatto, R. Brockett: Optimal structure from motion: Local ambiguities and global estimates, Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR) (Santa Barbara 1998) pp. 282–288
37.5.
S. Thrun, W. Burgard, D. Fox: Probabilistic Robotics (MIT, Cambridge 2005)MATH
37.6.
H. Durrant-Whyte, T. Bailey: Simultaneous localization and mapping: Part I, IEEE Robot. Autom. Mag. (2006) pp. 99–108
37.7.
T. Bailey, H. Durrant-Whyte: Simultaneous localization and mapping: Part II, IEEE Robot. Autom. Mag. (2006) pp. 108–117
37.8.
P. Cheeseman, P. Smith: On the representation and estimation of spatial uncertainty, Int. J. Robot. 5, 56–68 (1986)CrossRef
37.9.
R.C. Smith, P. Cheeseman: On the representation and estimation of spatial uncertainty, Int. J. Robot. Res. 5(4), 56–68 (1986)CrossRef
37.10.
R. Smith, M. Self, P. Cheeseman: Estimating uncertain spatial relationships in robotics, Autonomous Robot Vehicles, ed. by I.J. Cox, G.T. Wilfong (Springer, Berlin, Heidelberg 1990) pp. 167–193
37.11.
P. Moutarlier, R. Chatila: An experimental system for incremental environment modeling by an autonomous mobile robot, 1st International Symposium on Experimental Robotics (Montreal 1989)
37.12.
P. Moutarlier, R. Chatila: Stochastic multisensory data fusion for mobile robot location and environment modeling, 5th Int. Symposium on Robotics Research (Tokyo 1989)
37.13.
A.M. Jazwinsky: Stochastic Processes and Filtering Theory (Academic, New York 1970)
37.14.
R.E. Kalman: A new approach to linear filtering and prediction problems, Trans. ASME J. Basic Eng. 82, 35–45 (1960)
37.15.
P.S. Maybeck: The Kalman filter: An introduction to concepts. In: Autonomous Robot Vehicles, ed. by I.J. Cox, G.T. Wilfong (Springer, Berlin, Heidelberg 1990)
37.16.
M. Csorba: Simultaneous Localisation and Map Building. Ph.D. Thesis (University of Oxford, Oxford 1997)
37.17.
J. Neira, J.D. Tardós: Data association in stochastic mapping using the joint compatibility test, IEEE Trans. Robot. Autom. 17(6), 890–897 (2001)CrossRef
37.18.
J. Neira, J.D. Tardós, J.A. Castellanos: Linear time vehicle relocation in SLAM, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Taiwan 2003)
37.19.
T. Bailey: Mobile Robot Localisation and Mapping in Extensive Outdoor Environments. Ph.D. Thesis (University of Sydney, Sydney 2002)
37.20.
G. Dissanayake, P. Newman, S. Clark, H.F. Durrant-Whyte, M. Csorba: A solution to the simultaneous localisation and map building (SLAM) problem, IEEE Trans. Robot. Autom. 17(3), 229–241 (2001)CrossRef
37.21.
G. Dissanayake, S.B. Williams, H. Durrant-Whyte, T. Bailey: Map management for efficient simultaneous localization and mapping (SLAM), Autonom. Robot. 12, 267–286 (2002)CrossRefMATH
37.22.
S. Williams, G. Dissanayake, H.F. Durrant-Whyte: Constrained initialization of the simultaneous localization and mapping algorithm, Proceedings of the Symposium on Field and Service Robotics (Helsinki 2001)
37.23.
J.J. Leonard, R.J. Rikoski, P.M. Newman, M. Bosse: Mapping partially observable features from multiple uncertain vantage points, Int. J. Robot. Res. 21(10), 943–975 (2002)CrossRef
37.24.
A.J. Davison: Real-Time Simultaneous Localisation and Mapping with a Single Camera, International Conference on Computer Vision (Nice 2003) pp. 1403–1410
37.25.
J.M.M. Montiel, J. Civera, A.J. Davison: Unified inverse depth parametrization for monocular SLAM, Proc. of the Robotics Science and Systems Conference (RSS06), Vol. 1 (Philadelphia 2006)
37.26.
M. Bosse, P. Newman, J. Leonard, S. Teller: Simultaneous localization and map building in large-scale cyclic environments using the atlas framework, Int. J. Robot. Res. 23(12), 1113–1139 (2004)CrossRef
37.27.
J. Nieto, T. Bailey, E. Nebot: Scan-SLAM: Combining ekf-slam and scan correlation, Proc. IEEE Int. Conf. Robotics and Automation (Barcelona 2005)
37.28.
J. Folkesson, H.I. Christensen: Outdoor exploration and slam using a compressed filter, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Taiwan 2003) pp. 419–427
37.29.
J. Guivant, E. Nebot: Optimization of the simultaneous localization and map building algorithm for real time implementation, IEEE Trans. Robot. Autom. 17(3), 242–257 (2001)CrossRef
37.30.
J.J. Leonard, H.J.S. Feder: A computationally efficient method for large-scale concurrent mapping and localization, Proceedings of the Ninth International Symposium on Robotics Research, ed. by J. Hollerbach, D. Koditschek (Salt Lake City 1999)
37.31.
S.B. Williams, G. Dissanayake, H. Durrant-Whyte: An efficient approach to the simultaneous localisation and mapping problem, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Washington 2002) pp. 406–411
37.32.
J.D. Tardós, J. Neira, P.M. Newman, J.J. Leonard: Robust mapping and localization in indoor environments using sonar data, Int. J. Robot. Res. 21(4), 311–330 (2002)CrossRef
37.33.
S. Betgé-Brezetz, R. Chatila, M. Devy: Object-based modelling and localization in natural environments, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Osaka 1995)
37.34.
S. Betgé-Brezetz, P. Hébert, R. Chatila, M. Devy: Uncertain map making in natural environments, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Minneapolis 1996)
37.35.
J.E. Guivant, E.M. Nebot, J. Nieto, F. Masson: Navigation and mapping in large unstructured environments, Int. J. Robot. Res. 23(4), 449–472 (2004)CrossRef
37.36.
J. Nieto, J.E. Guivant, E.M. Nebot: The hybrid metric maps (HYMMs): A novel map representation for dense SLAM, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (New Orleans 2004)
37.37.
W. Burgard, D. Fox, H. Jans, C. Matenar, S. Thrun: Sonar-based mapping of large-scale mobile robot environments using EM, Proceedings of the International Conference on Machine Learning (Bled 1999)
37.38.
H. Shatkay, L. Kaelbling: Learning topological maps with weak local odometric information, Proceedings of IJCAI-97 (Nagoya 1997)
37.39.
S. Thrun, D. Fox, W. Burgard: A probabilistic approach to concurrent mapping and localization for mobile robots, Machine Learn. 31, 29–53 (1998), Also appeared in Autonomous Robots 5, 253–271 (joint issue)CrossRefMATH
37.40.
A.P. Dempster, A.N. Laird, D.B. Rubin: Maximum likelihood from incomplete data via the EM algorithm, J. R. Statist. Soc. Ser. B 39(1), 1–38 (1977)MATHMathSciNet
37.41.
H.F. Durrant-Whyte: Uncertain geometry in robotics, IEEE Trans. Robot. Autom. 4(1), 23–31 (1988)CrossRef
37.42.
F. Lu, E. Milios: Globally consistent range scan alignment for environment mapping, Autonom. Robot. 4, 333–349 (1997)CrossRef
37.43.
F. Dellaert: Square root SAM, Proceedings of the Robotics Science and Systems Conference, ed. by S. Thrun, G. Sukhatme, S. Schaal, O. Brock (Cambridge 2005)
37.44.
T. Duckett, S. Marsland, J. Shapiro: Learning globally consistent maps by relaxation, Proceedings of the IEEE International Conference on Robotics and Automation (San Francisco 2000) pp. 3841–3846
37.45.
T. Duckett, S. Marsland, J. Shapiro: Fast, on-line learning of globally consistent maps, Auton. Robot. 12(3), 287–300 (2002)CrossRefMATH
37.46.
J. Folkesson, H.I. Christensen: Graphical SLAM: A self-correcting map, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (New Orleans 2004)
37.47.
J. Folkesson, H.I. Christensen: Robust SLAM, Proceedings of the International Symposium on Autonomous Vehicles (Lisboa 2004)
37.48.
U. Frese, G. Hirzinger: Simultaneous localization and mapping – a discussion, Proceedings of the IJCAI Workshop on Reasoning with Uncertainty in Robotics (Seattle 2001) pp. 17–26
37.49.
U. Frese, P. Larsson, T. Duckett: A multigrid algorithm for simultaneous localization and mapping, IEEE Trans. Robot. 21(2), 196–207 (2005)CrossRef
37.50.
M. Golfarelli, D. Maio, S. Rizzi: Elastic correction of dead-reckoning errors in map building, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (Victoria 1998) pp. 905–911
37.51.
K. Konolige: Large-scale map-making, Proceedings of the AAAI National Conference on Artificial Intelligence (San Jose 2004) pp. 457–463
37.52.
M. Montemerlo, S. Thrun: Large-scale robotic 3-d mapping of urban structures, Proceedings of the International Symposium on Experimental Robotics (ISER) (Singapore 2004)
37.53.
Y. Liu, S. Thrun: Results for outdoor-SLAM using sparse extended information filters, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Taiwan 2003)
37.54.
M.A. Fischler, R.C. Bolles: Random sample consensus: A paradigm for model fitting with applications to image analysis and automated cartography, Commun. ACM 24, 381–395 (1981)CrossRefMathSciNet
37.55.
D. Hähnel, W. Burgard, B. Wegbreit, S. Thrun: Towards lazy data association in SLAM, Proceedings of the 11th International Symposium of Robotics Research (ISRRʼ03) (Sienna 2003)
37.56.
B. Kuipers, J. Modayil, P. Beeson, M. MacMahon, F. Savelli: Local metrical and global topological maps in the hybrid spatial semantic hierarchy, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (New Orleans 2004)
37.57.
S. Thrun, S. Thayer, W. Whittaker, C. Baker, W. Burgard, D. Ferguson, D. Hähnel, M. Montemerlo, A. Morris, Z. Omohundro, C. Reverte, W. Whittaker: Autonomous exploration and mapping of abandoned mines, IEEE Robot. Autom. Mag. 11(4), 79–91 (2004)CrossRef
37.58.
A. Elfes: Sonar-based real-world mapping and navigation, IEEE J. Robot. Autom. RA-3(3), 249–265 (1987)CrossRef
37.59.
H.P. Moravec: Sensor fusion in certainty grids for mobile robots, AI Mag. 9(2), 61–74 (1988)
37.60.
37.61.
P. Newman, J.L.R. Rikoski: Towards constant-time slam on an autonomous underwater vehicle using synthetic aperture sonar, Proceedings of the International Symposium of Robotics Research (Sienna 2003)
37.62.
M.A. Paskin: Thin junction tree filters for simultaneous localization and mapping, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI) (Acapulco 2003)
37.63.
S. Thrun, D. Koller, Z. Ghahramani, H. Durrant-Whyte, A.Y. Ng: Simultaneous mapping and localization with sparse extended information filters, Proceedings of the Fifth International Workshop on Algorithmic Foundations of Robotics, ed. by J.-D. Boissonnat, J. Burdick, K. Goldberg, S. Hutchinson (Nice 2002)
37.64.
E. Nettleton, S. Thrun, H. Durrant-Whyte: Decentralised slam with low-bandwidth communication for teams of airborne vehicles, Proceedings of the International Conference on Field and Service Robotics (Lake Yamanaka 2003)
37.65.
P. Newman: On the Structure and Solution of the Simultaneous Localisation and Map Building Problem. Ph.D. Thesis (Australian Centre for Field Robotics, University of Sydney, Sydney 2000)
37.66.
P.M. Newman, H.F. Durrant-Whyte: Geometric projection filter: An efficient solution to the SLAM problem, Proc. SPIE 4571 (2001)
37.67.
S. Thrun, Y. Liu, D. Koller, A.Y. Ng, Z. Ghahramani, H. Durrant-Whyte: Simultaneous localization and mapping with sparse extended information filters, Int. J. Robot. Res. 23(7–8), 693–716 (2004)CrossRef
37.68.
S.B. Williams: Efficient Solutions to Autonomous Mapping and Navigation Problems. Ph.D. Thesis (University of Sydney, Sydney 2001)
37.69.
37.70.
D.B. Rubin: Using the SIR algorithm to simulate posterior distributions, Bayesian Statistics 3, ed. by M.H. Bernardo, K.M. DeGroot, D.V. Lindley, A.F.M. Smith (Oxford Univ. Press, Oxford 1988)
37.71.
A. Doucet: On sequential simulation-based methods for Bayesian filtering. Technical Report CUED/F-INFENG/TR 310 (Cambridge University, Cambridge 1998)
37.72.
G. Kitagawa: Monte Carlo filter and smoother for non-Gaussian nonlinear state space models, J. Comput. Graph. Statist. 5(1), 1–25 (1996)CrossRefMathSciNet
37.73.
J. Liu, R. Chen: Sequential monte carlo methods for dynamic systems, J. Am. Stat. Assoc. 93, 1032–1044 (1998)CrossRefMATH
37.74.
37.75.
37.76.
C.R. Rao: Information and accuracy obtainable in estimation of statistical parameters, Bull. Calcutta Math. Soc. 37, 81–91 (1945)MATHMathSciNet
37.77.
K. Murphy, S. Russell: Rao-Blackwellized particle filtering for dynamic Bayesian networks. In: Sequential Monte Carlo Methods in Practice, ed. by A. Doucet, N. de Freitas, N. Gordon (Springer, Berlin, Heidelberg 2001) pp. 499–516
37.78.
M. Montemerlo, S. Thrun, D. Koller, B. Wegbreit: FastSLAM: A factored solution to the simultaneous localization and mapping problem, Proceedings of the AAAI National Conference on Artificial Intelligence (Edmonton 2002)
37.79.
J. Pearl: Probabilistic reasoning in intelligent systems: networks of plausible inference (Morgan Kaufmann, San Mateo 1988)
37.80.
J. Guivant, E. Nebot, S. Baiker: Autonomous navigation and map building using laser range sensors in outdoor applications, J. Robot. Syst. 17(10), 565–583 (2000)CrossRefMATH
37.81.
D. Hähnel, D. Fox, W. Burgard, S. Thrun: A highly efficient FastSLAM algorithm for generating cyclic maps of large-scale environments from raw laser range measurements, Proceedings of the Conference on Intelligent Robots and Systems (IROS) (Las Vegas 2003)
37.82.
A. Eliazar, R. Parr: DP-SLAM: Fast, robust simultaneous localization and mapping without predetermined landmarks, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI) (Acapulco 2003)
37.83.
A. Eliazar, R. Parr: DP-SLAM 2.0, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (New Orleans 2004)
37.84.
M. Montemerlo, S. Thrun, D. Koller, B. Wegbreit: FastSLAM 2.0: An improved particle filtering algorithm for simultaneous localization and mapping that provably converges, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI) (Acapulco 2003)
37.85.
R. van der Merwe, N. de Freitas, A. Doucet, E. Wan: The unscented particle filter. In: Adv. in Neural Inform. Process. Syst. 13 (2001)
37.86.
D. Hähnel, D. Schulz, W. Burgard: Mobile robot mapping in populated environments, Autonom. Robot. 17(7), 579–598 (2003)
37.87.
C.-C. Wang, C. Thorpe, S. Thrun: Online simultaneous localization and mapping with detection and tracking of moving objects: Theory and results from a ground vehicle in crowded urban areas, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Taiwan 2003)
37.88.
D.F. Wolf, G.S. Sukhatme: Mobile robot simultaneous localization and mapping in dynamic environments, Autonom. Robot. 19(1), 53–65 (2005)CrossRef
37.89.
J.-S. Gutmann, K. Konolige: Incremental mapping of large cyclic environments, Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA) (2000)
37.90.
E.W. Nettleton, P.W. Gibbens, H.F. Durrant-Whyte: Closed form solutions to the multiple platform simultaneous localisation and map building (slam) problem, Sensor Fusion: Architectures, Algorithms, and Applications IV, Vol. 4051, ed. by Bulur V. Dasarathy (Bellingham 2000) pp. 428–437
37.91.
J. Fenwick, P. Newman, J. Leonard: Collaborative concurrent mapping and localization, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Washington 2002)
37.92.
I.M. Rekleitis, G. Dudek, E.E. Milios: Multi-robot collaboration for robust exploration, Ann. Math. Artif. Intell. 31(1-4), 7–40 (2001)CrossRef
37.93.
S. Thrun, Y. Liu: Multi-robot SLAM with sparse extended information filers, Proceedings of the 11th International Symposium of Robotics Research (ISRRʼ03) (Sienna 2003)
37.94.
C. Frueh, A. Zakhor: Constructing 3d city models by merging ground-based and airborne views, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR) (Madison 2003)
37.95.
M. Devy, C. Parra: 3-d scene modelling and curve-based localization in natural environments, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (Leuven 1998)
37.96.
L. Iocchi, K. Konolige, M. Bajracharya: Visually realistic mapping of a planar environment with stereo, Proceesings of the 2000 International Symposium on Experimental Robotics (Waikiki 2000)
37.97.
S. Teller, M. Antone, Z. Bodnar, M. Bosse, S. Coorg, M. Jethwa, N. Master: Calibrated, registered images of an extended urban area, Proceedings of the Conference on Computer Vision and Pattern Recognition (CVPR) (Kauai 2001)
37.98.
R. Eustice, H. Singh, J. Leonard, M. Walter, R. Ballard: Visually navigating the RMS Titanic with SLAM information filters, Proceedings of the Robotics Science and Systems Conference, ed. by S. Thrun, G. Sukhatme, S. Schaal, O. Brock (Cambridge 2005)
37.99.
R. Rikoski, J. Leonard, P. Newman, H. Schmidt: Trajectory sonar perception in the ligurian sea, Proceedings of the International Symposium on Experimental Robotics (ISER) (Singapore 2004)
Metadata
Title
Simultaneous Localization and Mapping
Authors
Sebastian Thrun, Prof
John J. Leonard, Prof
Copyright Year
2008
Book
Springer Handbook of Robotics

Print ISBN: 978-3-540-23957-4

Electronic ISBN: 978-3-540-30301-5

Copyright Year: 2008

DOI
https://doi.org/10.1007/978-3-540-30301-5_38