Juan Nieto, Tim Bailey and Eduardo Nebot

Scan-SLAM: Combining EKF-SLAM and Scan Correlation

International Conference on Field and Service Robotics, 2005


 

Description

This paper attempts to combine the best of EKF-SLAM and scan-matching. The idea is that EKF-SLAM has nice convergence properties, while scan-matching allows us to define landmarks without resorting to geometric feature models. The result is EKF-SLAM with arbitrary shaped landmarks. This work is a first step, and serves to introduce the concept and its basic implementation, but a lot of work remains in terms of computing accurate Gaussian likelihoods, scan segmentation, and performing reliable data association etc.

It is important to keep in mind that the contribution of this paper is not its implementation, which is somewhat ad hoc, but rather the concept that EKF-SLAM is not limited to analytical geometric landmark models. This paper proposes that any set of observed data can provide an approximately Gaussian observation model amenable to the EKF. The universal observation model for SLAM is that the location of any object can observed by a relative measurement of one local coordinate frame (a landmark) from another local frame (the robot). A landmark can have arbitrary shape, but will always have a point location defined by an embedded local frame.
 

Abstract

This paper presents a new generalisation of simultaneous localisation and mapping (SLAM). SLAM implementations based on extended Kalman filter (EKF) data fusion have traditionally relied on simple geometric models for defining landmarks. This limits EKF-SLAM to environments suited to such models and tends to discard much potentially useful data. The approach presented in this paper is a marriage of EKF-SLAM with scan correlation. Instead of geometric models, landmarks are defined by templates composed of raw sensed data, and scan correlation is shown to produce landmark observations compatible with the standard EKF-SLAM framework. The resulting Scan-SLAM combines the general applicability of scan correlation with the established advantages of an EKF implementation: recursive data fusion that produces a convergent map of landmarks and maintains an estimate of uncertainties and correlations. Experimental results are presented which validate the algorithm.

Download

Full paper [pdf] (2,867 kb, 12 pages)

Addendum

In Section 1.4 of the paper, the least-squares solution is found using SVD. This is not essential, and the normal equations may be used instead: x = inv(A'*A)*A'*b. However, the SVD solution will tend to be better conditioned.

The method for approximating the scan-match variance in Section 1.4 was invented by the authors, and various alternative (and probably better) methods exist. One such method is Laplace's approximation, which computes the Hessian of the log-likelihood function about the point of maximum likelihood.


[Tim's Homepage]