DOC PREVIEW
Berkeley COMPSCI 287 - Simultaneous Localisation and Mapping

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Simultaneous 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 undertaken.Part I of this tutorial described the essential SLAM prob-lem. Part II of this tutorial (this paper) is concerned withrecent advances in computational method s and in new for-mulations of the SLAM problem for large scale and complexenvironments.I. 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. The past decade has seenrapid and exciting progress in solving the SLAM problemtogether with many compelling implementations of SLAMmethods. 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 implementation.This 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. 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 here.SLAM, in it’s naive form, scales quadratically with thenumber of landmarks in a map. 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, [email protected],[email protected] map. 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. 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.SLAM 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 planets.II. 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. 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 algorithm.Techniques aimed at improving computational efficiencymay be characterised as being optimal or conservative.Optimal 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. 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) problem.2The 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 using state-augmentation methods. The observation-update computation can be limited using a partitioned formof the update equations. Both these steps result in an op-timal SLAM estimate with reduced computation. Refor-mulation of the standard state-space SLAM representationinto information form allows sparsification of the resultinginformation matrix to be exploited in reducing computa-tion. Both optimal and conservative variations exist ofthese sparsification algorithms. Submapping methods 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 frame.A. State AugmentationAt a time k, the joint SLAM state vector xk=[xTvk, mT]Tcomprises two parts; the robot pose xvkandthe set of map landmark locations m. The vehicle modelpropagates only the pose states according to a set of controlinputs


View Full Document
Download Simultaneous Localisation and Mapping
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Simultaneous Localisation and Mapping and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Simultaneous Localisation and Mapping 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?