1 Simultaneous Localisation and Mapping (SLAM): Part II ...

1 1 simultaneous localisation and mapping ( slam ):Part II State of the ArtTim Bailey and Hugh Durrant-WhyteAbstract This tutorial provides an introduction to the Si- multaneous Localisation and Mapping ( slam ) method andthe extensive research on slam that has been I of this tutorial described the essential slam prob-lem. Part II of this tutorial (this paper) is concerned withrecent advances in computational methods and in new for-mulations of the slam problem for large scale and IntroductionSLAM is the process by which a mobile robot can builda map of the environment and at the same time use thismap to compute it s location.

2 The past decade has seenrapid and exciting progress in solving the slam problemtogether with many compelling implementations of slam methods. The great majority of work has focused on im-proving computational efficiency while ensuring consistentand accurate estimates for the map and vehicle pose. How-ever, there has also been much research on issues such asnon-linearity, data association and landmark characterisa-tion, all of which are vital in achieving a practical androbust slam tutorial focuses on the recursive Bayesian formula-tion of the slam problem in which probability distribu-tions or estimates of landmark locations and vehicle poseare obtained.

3 Part I of this tutorial surveyed the develop-ment of the essential slam algorithm in state-space form,described a number of key implementations and cited lo-cations of source code and real-world data for evaluationof slam algorithms. Part II of this tutorial (this paper)surveys the current state of the art in slam research witha focus on three key areas; computational complexity, dataassociation, and environment representation. Much of themathematical notation and essential concepts used in thispaper are defined in Part I and so are not repeated , in it s naive form, scales quadratically with thenumber of landmarks in a map.

4 For real-time implemen-tation, this scaling is potentially a substantial limitationin the use of slam methods. Section II surveys themany approaches that have been developed to reduce thiscomplexity. These include linear-time state augmentation,sparsification in information form, partitioned updates andsubmapping methods. A second major hurdle to overcomein implementation of slam methods is to correctly as-sociate observations of landmarks with landmarks held inTim Bailey and Hugh Durrant-Whyte are with the Aus-tralian Centre for Field Robotics (ACFR) J04, The University ofSydney, Sydney NSW 2006, Australia, map.

5 Incorrect association can lead to catastrophicfailure of the slam algorithm. Data association is par-ticularly important when a vehicle returns to a previouslymapped region after a long excursion; the so-called loop-closure problem. Section III surveys current data as-sociation methods used in slam . These include batch-validation methods that exploit constraints inherent in theSLAM formulation, appearance-based methods, and multi-hypothesis techniques. The third development discussed inthis tutorial is the trend towards richer appearance-basedmodels of landmarks and maps.

6 While initially motivatedby problems in data association and loop closure, thesemethods have resulted in qualitatively different methods ofdescribing the slam problem; focusing on trajectory esti-mation rather than landmark estimation. Section IV sur-veys current developments in this area along a number oflines including delayed Mapping , the use of non-geometriclandmarks, and trajectory estimation methods have now reached a state of consider-able maturity. Future challenges will centre on methodsenabling large scale implementations in increasingly un-structured environments and especially in situations whereGPS-like solutions are unavailable or unreliable; in urbancanyons, under foliage, underwater or on remote Computational ComplexityThe state-based formulation of the slam problem in-volves the estimation of a joint state composed of a ro-bot pose and the locations of observed stationary land-marks.

7 This problem formulation has a peculiar structure;the process model only affects vehicle pose states and theobservation model only makes reference to a single vehicle-landmark pair. A wide range of techniques have been de-veloped to exploit this special structure in limiting the com-putational complexity of the slam aimed at improving computational efficiencymay be characterised as being optimal or algorithms aim to reduce required computationwhile still resulting in estimates that are equal to the full-form slam algorithm (as presented in Part I of this tu-torial). Conservative algorithms result in estimates whichhave larger uncertainty or covariance than the optimal re-sult.

8 Usually conservative algorithms, while less accurate,are computationally more efficient and therefore of valuein real implementations. Algorithms with uncertaintiesor covariances less than those of the optimal solution aretermed inconsistent and are considered invalid solutions tothe slam (or any estimation) direct approach to reducing computational complex-ity involves exploiting the structure of the slam problemin re-formulating the essential time and observation up-date equations. The time-update computation can be lim-ited usingstate-augmentationmethods. The observation-update computation can be limited using apartitioned formof the update equations.

9 Both these steps result in an op-timal slam estimate with reduced computation. Refor-mulation of the standard state-space slam representationinto information form allowssparsificationof the resultinginformation matrix to be exploited in reducing computa-tion. Both optimal and conservative variations exist ofthese sparsification ex-ploit the idea that a map can be broken up into regionswith local coordinate systems and arranged in a hierarchi-cal manner. Updates occur mostly in a local frame withperiodic inter-frame updates. Submapping techniques gen-erally provide a conservative estimate in the global State AugmentationAt a timek, the joint slam state vectorxk=[xTvk,mT]Tcomprises two parts; the robot posexvkandthe set of map landmark locationsm.

10 The vehicle modelpropagates only the pose states according to a set of controlinputsukwhile leaving the map states unchanged:xk=f(xk 1,uk)= fv xvk 1,uk m (1)In a naive implementation of the extended Kalman filter(EKF) for slam , the covariance prediction is computedfromPk|k 1= fxPk 1|k 1 fTx+ fuUk fTu(2)where fx= f xk 1, fu= f ukandUkis a covariancecharacterising uncertainty on the control vector. This op-eration has cubic complexity in the number of landmarksdue to matrix multiplication of the Jacobian fxand thecovariance matrixPk 1|k 1. However, as only the posestates are affected by the vehicle model, the covarianceprediction can be re-written in a form which has linearcomplexity in the number of landmarks [56, Section ]:Pk|k 1= fvxPvv fTvx+ fvuUk fTvu fvxPvmPTvm fTvxPmm (3)where fvx= fv xvk 1, fvu= fv ukand wherePk 1|k 1= PvvPvmPTvmPmm The process of adding a new landmark to the state vectorhas a similar form.