Simultaneous localization and mapping with unknown data association using FastSLAM
Montemerlo, M. Thrun, S.
Robotics Inst., Carnegie Mellon Univ., Pittsburgh, PA, USA
Simultaneous localization and mapping with unknown data ass.pdfThis paper appears in: Robotics and Automation, 2003. Proceedings. ICRA '03. IEEE International Conference on
Publication Date: 14-19 Sept. 2003
Volume: 2
On page(s): 1985 - 1991 vol.2
Number of Pages: 3 vol.lii+4450
ISSN: 1050-4729
ISBN: 0-7803-7736-2
INSPEC Accession Number:7877180
Digital Object Identifier: 10.1109/ROBOT.2003.1241885
Current Version Published: 2003-11-10
Michael Montemerlo @ Field Robotics Center, Carnegie Mellon University
http://en.wikipedia.org/wiki/Michael_Montemerlo
Sebastian Thrun @ Stanford Artificial Intelligence Laboratory, Stanford University
http://en.wikipedia.org/wiki/Sebastian_Thrun
http://www.probabilistic-robotics.org/
FastSLAM
http://robots.stanford.edu/probabilistic-robotics/ppt/fastslam.ppt
Rao-Blackwellized Particle Filter
http://en.wikipedia.org/wiki/Particle_filter
I. Introduction
mobile robotics
the problem of building a map of an unknown environment from a sequence of noisy landmark measurements obtained from a moving robot + a robot localization problem => SLAM
autonomous robots operating in environments where precise maps and positioning are not available
: used for incrementally estimating the joint posterior distribution over robot pose and landmark positions
limitations of EKF
1) Quadratic complexity (: sensor updates require time quadratic in the total number of landmarks in the map)
=> limiting the number of landmarks to only a few hundred (whereas natural environment models frequently contain millions of features
2) Data association / correspondence (: mapping of observations to landmarks)
=> associating a small numver of observations with incorrect landmarks to cause the filter to diverge
FastSLAM decomposes the SLAM problem into a robot localization problem, and a collection of landmark estimation problems that are conditioned on the robot pose estimate.
ref. Montemerlo & Thrun & Koller & Wegbreit <FastSLAM: A factored solution to the simultaneous localization and mapping problem> In Proceedings of the AAAI National Conference on Artificial Intelligence, Edmonton, Canada, 2002. AAAI.
> a modified particle filter to estimate the posterior over robot paths
> each particle possessing K independent Kalman filters that estimate the landmark locations conditioned on the particle's path
=> an instance of the Rao-Blackwellized particle filter
Representing particles as binary trees of Kalman Filters
-> Incorporating observations into FastSLAM in O(MlogK) time (M, # of particles; K, # of landmarks)
Each particle represents a different robot pose hypothesis.
=> Data association can be considered separately for every particle.
=> 1) The noise of robot motion does not affect the accuracy of data association.
2) Incorrectly associated particls will receive lower probabilities and will be removed in future resampling steps.
Adding extra odometric noise
( Odometry is the use of data from the movement of actuators to estimate change in position over time. )
Estimating an accurate map without any odometry in the environment in which the Kalman Filter inevitably diverges.
How to incorporate negative information resulting in a measurable increase in the accuracy of the resulting map
II. SLAM Problem Definition
probabilistic Markov chain
http://en.wikipedia.org/wiki/Markov_chain
robot's position & heading orientation, s
K landmarks' locations, θ
i) The robot's current pose is a probabilistic function of the robot control and the previous pose at time t.
ii) The sensor measurement, range and bearing to landmarks, is a probabilistic function of the robot's current pose and the landmakr being at time t.
=> SLAM is the problem of determining the locations of all landmarks and robot poses from measurements and controls.
III. Data Association
uncertainty in the SLAM posterior, mapping between observations and landmarks
=> ambiguity in data association
i) measurement noise: uncertain landmark positions
<= 1) measurement ambiquity
2) confusion between nearby landmarks
ii) motion noise: robot pose uncertainty after incorporating a control
=> 1) adding a large amount of error to the robot's pose
2) causing a filter to diverge
IV. FastSLAM with Known Data Association
dynamic Bayes network
http://en.wikipedia.org/wiki/Dynamic_Bayesian_network
conditional independece
: The problem of determining the landmark locations could be decoupled into K independent estimation problems, one for each landmark.
FastSLAM estimates the factored SLAM posterior using a modified particle filter, with K independent Kalman Filters for each particle to estimate the landmark positions conditioned on the hypothesized robot paths. The resulting algorithm is an instance of the Rao-Blackwellized particle filter.
A. Particle Filter Path Estimation
Monte Carlo Localization (MCL) algorithm
http://en.wikipedia.org/wiki/Monte_Carlo_localization
particle set, representing the posterior ("guess") of a robot path
proposal distribution of particle filtering