Tim Bailey, Juan Nieto and Eduardo Nebot

Consistency of the FastSLAM Algorithm

IEEE International Conference on Robotics and Automation, 2006


 

Description

The FastSLAM algorithm is an alternative stochastic mapping and localisation method to EKF-SLAM. It is based on particle filters rather than Kalman filters. This paper shows that FastSLAM is inconsistent as a statistical filter; it always underestimates its own error in the medium to long-term. However, it may give consistent estimates over a short time-period. If FastSLAM is viewed as a heuristic algorithm — as an online randomised search for the best map — and its estimates of uncertainty are understood to be optimistic or unreliable, it can often be an effective and highly accurate mapping method.
 

Abstract

This paper presents an analysis of FastSLAM — a Rao-Blackwellised particle filter formulation of simultaneous localisation and mapping. It shows that the algorithm degenerates with time, regardless of the number of particles used or the density of landmarks within the environment, and will always produce optimistic estimates of uncertainty in the long-term. In essence, FastSLAM behaves like a non-optimal local search algorithm; in the short-term it may produce consistent uncertainty estimates but, in the long-term, it is unable to adequately explore the state-space to be a reasonable Bayesian estimator. However, the number of particles and landmarks does affect the accuracy of the estimated mean and, given sufficient particles, FastSLAM can produce good non-stochastic estimates in practice. FastSLAM also has several practical advantages, particularly with regard to data association, and will probably work well in combination with other versions of stochastic SLAM, such as EKF-based SLAM.

Download

Full paper [pdf] (1,167 kb, 6 pages)

Addendum

I did not derive the FastSLAM algorithm in this paper. However, I here provide working for the partitioned recursive Bayes filter for the Rao-Blackwellised SLAM state. Also, for those who are rusty, I have a summary of the basic probability rules for continuous variables.

Errata

The paper makes the following statement:

... one-particle Fast-SLAM is virtually identical to performing EKF-SLAM while ignoring cross-correlations. The only difference is that FastSLAM 2.0 introduces a small random jitter into the pose estimate at each step, and so is slightly less accurate than its “no-correlation” EKF counterpart.
This is not quite correct; there are, in fact, two differences between one-particle FastSLAM 2.0 and no-correlation EKF-SLAM. The second difference is that when FastSLAM performs a landmark update, it does so with the vehicle pose particle absolutely fixed; only the landmark estimate can move even if the landmark variance is very small. An update for no-correlation EKF-SLAM, on the other hand, will move both the vehicle and landmark estimate. And as the landmark becomes very well-known, an update will tend to incur most movement in the vehicle estimate since its uncertainty, and hence flexibility, is ever inflated by process noise.


[Tim's Homepage]