Simultaneous localization and mapping (SLAM): part II 

Simultaneous localization and mapping (SLAM) is theprocess by which a mobile robot can build a map of theenvironment and, at the same time, use this map tocompute its location. The past decade has seen rapid andexciting progress in solving the SLAM problem together withmany compelling implementations of SLAM methods. Thegreat majority of work has focused on improving computational efficiency while ensuring consistent and accurate estimates for the map and vehicle pose. However, there has alsobeen much research on issues such as nonlinearity, data association, and landmark characterization, all of which are vital inachieving a practical and robust SLAM implementation.

This tutorial focuses on the recursive Bayesian formulationof the SLAM problem in which probability distributions orestimates of absolute or relative locations of landmarks andvehicle pose are obtained. Part I of this tutorial (IEEE Robotics& Auomation Magazine, vol. 13, no. 2) surveyed the development of the essential SLAM algorithm in state-space and particle-filter form, described a number of key implementations,and cited locations of source code and real-world data forevaluation of SLAM algorithms. Part II of this tutorial (thisarticle), surveys the current state of the art in SLAM researchwith a focus on three key areas: computational complexity,data association, and environment representation. Much ofthe mathematical notation and essential concepts used in thisarticle are defined in Part I of this tutorial and, therefore, arenot repeated here.

SLAM, in its naive form, scales quadratically with thenumber of landmarks in a map. For real-time implementation,this scaling is potentially a substantial limitation in the use ofSLAM methods. The complexity section surveys the manyapproaches that have been developed to reduce this complexity. These include linear-time state augmentation, sparsification in information form, partitioned updates, andsubmapping methods. A second major hurdle to overcome inthe implementation of SLAM methods is to correctly associateobservations of landmarks with landmarks held in the map.Incorrect association can lead to catastrophic failure of theSLAM algorithm. Data association is particularly importantwhen a vehicle returns to a previously mapped region after a long excursion, the so-called loop-closure problem. The dataassociation section surveys current data association methodsused in SLAM. These include batch-validation methods thatexploit constraints inherent in the SLAM formulation, appearance-based methods, and multihypothesis techniques. Thethird development discussed in this tutorial is the trendtowards richer appearance-based models of landmarks andmaps. While initially motivated by problems in data association and loop closure, these methods have resulted in qualitatively different methods of describing the SLAM problem,focusing on trajectory estimation rather than landmark estimation. The environment representation section surveys currentdevelopments in this area along a number of lines, includingdelayed mapping, the use of nongeometric landmarks, andtrajectory estimation methods.

SLAM methods have now reached a state of considerablematurity. Future challenges will center on methods enablinglarge-scale implementations in increasingly unstructured environments and especially in situations where GPS-like solutions are unavailable or unreliable: in urban canyons, underfoliage, under water, or on remote planets.

Computational Complexity

The state-based formulation of the SLAM problem involvesthe estimation of a joint state composed of a robot pose andthe locations of observed stationary landmarks. This problemformulation has a peculiar structure; the process model onlyaffects vehicle pose states and the observation model onlymakes reference to a single vehicle-landmark pair. A widerange of techniques have been developed to exploit this special structure in limiting the computational complexity of theSLAM algorithm.

Techniques aimed at improving computational efficiency may be characterized as being optimal or conservative. Optimal algorithms aim to reduce required computation whilestill resulting in estimates and covariances that are equal tothe full-form SLAM algorithm (as presented in Part I of thistutorial). Conservative algorithms result in estimates thathave larger uncertainty or covariance than the optimalresult. Usually, conservative algorithms, while less accurate,are computationally more efficient and, therefore, of valuein real implementations. Algorithms with uncertainties orcovariances less than those of the optimal solution aretermed inconsistent and are considered invalid solutions tothe SLAM (or any estimation) problem.

The direct approach to reducing computational complexity involves exploiting the structure of the SLAM problemin re-formulating the essential time- and observation-updateequations to limit required computation. The time-updatecomputation can be limited using state-augmentation methods.The observation-update computation can be limited using apartitioned form of the update equations. Both these stepsresult in an optimal SLAM estimate with reduced computation. Re-formulation of the standard space-space SLAMrepresentation into information form allows sparsification ofthe resulting information matrix to be exploited in reducingcomputation. The resulting algorithms are usually conservative but still yield good estimates with much reduced computational effort. Submapping methods exploit the idea that amap can be broken up into regions with local coordinatesystems and arranged in a hierarchical manner. Updates canoccur in a local frame with periodic interframe updates.Submapping techniques generally provide a conservativeestimate in the global frame.

State Augmentation

At a time k, the joint SLAM state

图片[1]-Simultaneous Localization and Mapping (SLAM): Part II
Simultaneous localization and mapping (SLAM): part II -AGV吧
Simultaneous localization and mapping (SLAM): part II 
© 版权声明
点赞13 分享
评论 抢沙发