1 A Solution to the Simultaneous Localisation and Map ...

1 1 ASolutiontotheSimultaneousLocalisationan dMapBuilding(SLAM) Dissanayake, , S. Clark, Durrant-Whyte and M. CsorbaAustralian Centre for Field RoboticsDepartment o fMechanical and Mechatronic EngineeringThe University o fSydneyNSW 2006, AustraliaAbstract The Simultaneous Localisation and map building (SLAM) problem asks if it is possible for an autonomous ve-hicle to start in an unknown location in an unknown environ-ment and then to incrementally build a map of this environ-ment while simultaneously using this map to compute abso-lute vehicle location .Starting from the estimation-theoreticfoundations of this problem developed in [1], [2], [3], this pa-per proves that a Solution to the SLAM problem is indeedpossible .The underlying structure of the SLAM problem isfirst elucidated.

2 A proof that the estimated map convergesmonotonically to a relative map with zero uncertainty isthen developed .It is then shown that the absolute accuracyof the map and the vehicle location reach a lower bound de-fined only by the initial vehicle uncertainty .Together, theseresults show that it is possible for an autonomous vehicle tostart in an unknown location in an unknown environmentand, using relative observations only, incrementally build aperfect map of the world and to compute simultaneously abounded estimate of vehicle paper also describes a substantial implementationof the SLAM algorithm on a vehicle operating in an out-door environment using millimeter-wave (MMW) radar toprovide relative map observations.

3 This implementation isused to demonstrate how some key issues such as map man-agement and data association can be handled in a practicalenvironment .The results obtained are cross-compared withabsolute locations of the map landmarks obtained by sur-veying .In conclusion, this paper discusses a number of keyissues raised by the Solution to the SLAM problem includingsub-optimal map- building algorithms and map IntroductionThe Solution to the Simultaneous Localisation and mapbuilding (SLAM) problem is, in many respects, a HolyGrail of the autonomous vehicle research community. Theability to place an autonomous vehicle at an unknown lo-cation in an unknown environment and then have it builda map, using only relative observations of the environment,and then to use this map simultaneously to navigate wouldindeed make such a robot autonomous.

4 Thus the mainadvantage of SLAM is that it eliminates the need for artifi-cial infrastructures or a priori topological knowledge of theenvironment. A Solution to the SLAM problem would beof inestimable value in a range of applications where abso-lute position or precise map information is unobtainable,including, amongst others, autonomous planetary explo-ration, subsea autonomous vehicles, autonomous air-bornevehicles, and autonomous all-terrain vehicles in tasks suchas mining and general SLAM problem has been the subject ofsubstantial research since the inception of a robotics re-search community and indeed before this in areas such asmanned vehicle navigation systems and geophysical sur-veying. A number of approaches have been proposed toaddress both the SLAM problem and also more simpli-fied navigation problems where additional map or vehiclelocation information is made available.

5 Broadly, these ap-proaches adopt one of three main philosophies. The mostpopular of these is the estimation-theoretic or Kalman-filter based approach. The popularity of this approach isdue to two main factors. Firstly, it directly provides both arecursive Solution to the navigation problem and a meansof computing consistent estimates for the uncertainty invehicle and map landmark locations on the basis of statis-tical models for vehicle motion and relative landmark ob-servations. Secondly, a substantial corpus of method andexperience has been developed in aerospace, maritime andother navigation applications, from which the autonomousvehicle community can draw. A second philosophy is to es-chew the need for absolute position estimates and for pre-cise measures of uncertainty and instead to employ morequalitative knowledge of the relative location of landmarksand vehicle to build maps and guide motion.

6 This generalphilosophy has been developed by a number of differentgroups in a number of different ways; see ([4][5] and [6]).The qualitative approach to navigation and the generalSLAM problem has many potential advantages over theestimation-theoretic methodology in terms of limiting theneed for accurate models and the resulting computationalrequirements, and in its significant anthropomorphic ap-peal . The third, very broad philosophy, doesawaywiththe rigorous Kalman filter or statistical formalism while re-taining an essentially numerical or computational approachto the navigation and SLAM problem. Such approaches in-clude the use of iconic landmark matching ([7]), global mapregistration ([8]), bounded regions ([9]) and other measuresto describe uncertainty.

7 Notable are the work by Thrunet. al. [10] and Yamauchi et. al. [11]. Thrun et. a bayesian approach to map building that does notassume Gaussian probability distributions as required bythe Kalman filter. This technique while very effective for2localisation with respect to maps, does not lend itself toprovide an incremental Solution to SLAM where a map isgradually built as information is received from sensors. Ya-mauchi et. al. use a evidence grid approach that requiresthat the environment is decomposed to a number of estimation-theoretic or Kalman filter based approachto the SLAM problem is adopted in this paper. A majoradvantage of this approach is that it is possible to developa complete proof of the various properties of the SLAM problem and to study systematically the evolution of themap and the uncertainty in the map and vehicle proof of existence and convergence for a Solution of theSLAM problem within a formal estimation-theoretic frame-work also encompasses the widest possible range of navi-gation problems and implies that solutions to the problemusing other approaches are study of estimation-theoretic solutions to the SLAM problem within the robotics community has an interestinghistory.

8 Initial work by Smith et al. [12] and Durrant-Whyte [13] established a statistical basis for describing re-lationships between landmarks and manipulating geomet-ric uncertainty. A key element of this work was to showthat there must be a high degree of correlation betweenestimates of the location of different landmarks in a mapand that indeed these correlations would grow to unity fol-lowing successive observations. At the same time Ayacheand Faugeras [14] and Chatila and Laumond [15] were un-dertaking early work in visual navigation of mobile robotsusing Kalman filter-type algorithms. These two strandsof research had much in common and resulted soon af-ter in the key paper by Smith, Self and Cheeseman [1].This paper showed that as a mobile robot moves throughan unknown environment taking relative observations oflandmarks, the estimates of these landmarks are all neces-sarily correlated with each other because of the commonerror in estimated vehicle location.

9 This paper was fol-lowed by a series of related work developing a number ofaspects of the essential SLAM problem ( [2] and [3] for ex-ample). The main conclusion of this work was two accounting for correlations between landmarks in amap is important if filter consistency is to be that a full SLAM Solution requires that a statevector consisting of all states in the vehicle modelandallstates of every landmark in the map needs to be maintainedand updated following each observation if a complete solu-tion to the SLAM problem is required. The consequenceof this in any real application is that the Kalman filterneeds to employ a huge state vector (of order the num-ber of landmarks maintained in the map) and is in gen-eral, computationally intractable.

10 Crucially, this work didnot look at the convergence properties of the map or itssteady-state behaviour. Indeed, it was widely assumed atthe time that the estimated map errors would not convergeand would instead execute a random walk behaviour withunbounded error growth. Given the computational com-plexity of the SLAM problem and without knowledge ofthe convergence behaviour of the map, a series of approx-imations to the full SLAM Solution were proposed whichassumed that the correlations between landmarks could beminimised or eliminated thus reducing the full filter to aseries of decoupled landmark to vehicle filters (see Renken[16], ,Leonard and Durrant-Whyte [3] for example). Alsofor these reasons, theoretical work on the full estimation-theoretic SLAM problem largely ceased, with effort insteadbeing expended in map-based navigation and alternativetheoretical approaches to the SLAM paper starts from the original estimation-theoreticwork of Smith, Self and Cheeseman.