37. Simultaneous Localization and Mapping Simultaneous

1 Springer Handbook of RoboticsSiciliano, Khatib (Eds.) Springer 20081871 Simultaneous37. Simultaneous Localization and MappingSebastian Thrun, John J. LeonardThis chapter provides a comprehensive intro-duction in to thesimultaneous Localization andmapping problem, better known in its abbrevi-ated form the problemof a robot navigating an unknown navigating the environment, the robot seeksto acquire a map thereof, and at the same time itwishes to localize itself using its map. The use ofSLAM problems can be motivated in two differentways: one might be interested in detailed envi-ronment models, or one might seek to maintainan accurate sense of a mobile robot s both of these review three major paradigms of algorithmsfrom which a huge number of recently publishedmethods are derived.

2 First comes the traditionalapproach, which relies on the extended Kalmanfilter (EKF) for representing the robot s best es-timate. The second paradigm draws its intuitionfrom the fact that theSLAM problem can be viewedas a sparse graph of constraints, and it appliesnonlinear optimization for recovering the map andthe robot s locations. Finally, we survey the particlefilter paradigm, which applies : Problem Mathematical Example: SLAM in Landmark Taxonomy of the SLAM Three Main SLAM Extended Kalman Graph-Based Particle Relation of and Future for Further estimation and efficient factorizationmethods to theSLAM problem. This chapter dis-cusses extensions of these basic methods.

3 Itelucidates variants of theSLAM problem andproposes a taxonomy for the field. Relevant re-search is referenced extensively, and open researchproblems are OverviewThis chapter provides a comprehensive introductioninto one of the key enabling technologies of mo-bile robot navigation: Simultaneous Localization andmapping(SLAM).SLAM addresses the problem of ac-quiring a spatial map of a mobile robot environmentwhile simultaneously localizing the robot relative tothis model. TheSLAM problem is generally regardedas one of the most important problems in the pursuitof building truly autonomous mobile robots. Despitesignificant progress in this area, it still poses greatchallenges.

4 At present, we have robust methods formapping environments that are static, structured, and oflimited size. Mapping unstructured, dynamic, or large-scale environments remains largely an open historical roots ofSLAMcan be traced back toGauss[ ], who is largely credited with inventing theleast-squares method, for calculating planetary the 20th century, a number of fields outside roboticshave studied the making of environment models froma moving sensor platform, most notably inphotogram-metry[ ]andcomputer vision[ ,4].SLAM buildsPart E37 Springer Handbook of RoboticsSiciliano, Khatib (Eds.) Springer 20081872 Part EMobile and Distributed Roboticson this work, often extending the basic paradigms intomore scalable chapter begins with a definition of theSLAM problem, which shall include a brief taxonomy of dif-ferent versions of the problem.

5 The centerpiece of thischapter is a layman s introduction into the three majorparadigms in this field, and the various extensions thatexist. As the reader will quickly recognize, there is nosingle best solution to theSLAM problem. The methodchosen by the practitioner will depend on a number offactors, such as the desired map resolution, the updatetime, the nature of the features in the map, and so , the three methods discussed in this chaptercover the major paradigms in this field. For an in-depthstudy ofSLAM algorithms, we refer the reader to a re-cent textbook on probabilistic robotics, which dedicatesa number of chapters to the topic ofSLAM[ ]. Alsosee [ ,7] for a recent in-depth tutorial SLAM: Problem Mathematical BasisTheSLAM problem is defined as follows.

6 A mobilerobot roams an unknown environment, starting at a lo-cation with known coordinates. Its motion is uncertain,making it gradually more difficult to determine its globalcoordinates. As it roams, the robot can sense its envi-ronment. TheSLAM problem is the problem of buildinga map the environment while simultaneously determin-ing the robot s position relative to this ,SLAMis best described in probabilisticterminology. Let us denote time byt, and the robotlocation byxt. For mobile robots on a flat ground,xtis usually a three-dimensional vector, consisting ofits two-dimensional coordinate in the plane plus a sin-gle rotational value for its orientation. The sequence oflocations, orpath, is then given asXT={x0,x1,x2.}

7 XT}.( )HereTis some terminal time (Tmight be ). The initiallocationx0is known; other positions cannot be provides relative information betweentwo consecutive locations. Letutdenote the odome-try that characterized the motion between timet 1andtimet; such data might be obtained from the robot swheel encoders or from the controls given to thosemotors. Then the sequenceUT={u1,u2, }( )characterizes the relative motion of the robot. For noise-free motion,UTwould be sufficient to recover the pastXTfrom the initial locationx0. However, odometrymeasurements are noisy, and path-integration techniquesinevitably diverge from the , the robot senses objects in the thetruemap of the environment.

8 Theenvironment may be comprised of landmarks, objects,surfaces, etc., andmdescribes their locations. The envi-ronment mapmis typically assumed to be time invariant(i. e., static).The robot measurements establish information be-tween features inmand the robot ,without loss of generality, assume that the robot takesexactly one measurement at each point in time, thesequence of measurements is given asZT={z1,z2,z3,.. ,zT}.( ) the variables involved in theSLAM problem. It shows the sequence of locations andsensor measurements, and the causal relationships be-tween these variables. Such a diagram is known asagraphical model. It is useful in understanding thedependencies in is now the problem of recov-ering a model of the worldmand the sequence ofrobot locationsXTfrom the odometry and measure-zt+1xt+1xtxt 1ztzt 1ut+1utut 1mFig.

9 Model of causal relationships, andshaded nodesare directlyobservable to the robot. InSLAM, the robot seeks to recoverthe unobservable variablesPart Handbook of RoboticsSiciliano, Khatib (Eds.) Springer 20081 Simultaneous Localization and : Problem Definition873ment data. The literature distinguishes two main formsof theSLAM problem, which are both of equal practi-cal importance. One is known as thefullSLAM problem:it involves estimating the posterior over the entire robotpath together with the map:p(XT,m|ZT,UT).( )Written in this way, the fullSLAM problem is the prob-lem of calculating the joint posterior probability overXTandmfrom the available data. Notice that the variablesright of the conditioning bar are all directly observable tothe robot, whereas those on the left are the ones that wewant.

10 As we shall see, algorithms for the offlineSLAM problem are often batch, that is, they process all data atthe same second, equally importantSLAM problem is theonlineSLAM problem. This problem is defined viap(xt,m|ZT,UT).( )OnlineSLAM seeks to recover the present robot loca-tion, instead of the entire path. Algorithms that addressthe online problem are usually incremental and canprocess one data item at a time. In the literature suchalgorithms are typically , the robot needs to beendowed with two more models: a mathematical modelthat relates odometry measurementsutto robot locationsxt 1andxtand a model that relates measurementsztto the environmentmand the robot locationxt.