ASME 07 Notes

Simutaneous Localization and Mapping (SLAM)

This is a method of robotic exploration and navigation in unknown environments.

--Authors of Problem Statement:

(1) Smith and Cheeseman 1987, (2) Leonard et al. 1992b, (3) Thrun 2003, (4) Thrun et al. 2005.

Kalman Filtering

(See also Russell and Norvig pp. 551 - 559)

For "landmark-based SLAM:"

from Square root SAM: simultaneous localization and mapping via square root information smoothing. Frank Dellaert and Michael Kaess. The International Journal of Robotics Research 25.12 (Dec 2006): p1181(23). (10275 words)

"We will primarily be concerned with landmark-based SLAM, for which the earliest and most popular methods are based on the extended Kalman filter (EKF) (Smith et al. 1987, 1990; Moutarlier and Chatila 1989a, 1989b;Ayache and Faugeras 1989; Leonard and Durrant-Whyte 1992, Leonard et al. 1992). The EKF recursively estimates a Gaussian density over the current pose of the robot and the position of all landmarks (the map). However, it is well known that the computational complexity of the EKF becomes intractable fairly quickly, and hence much effort has been focused on modifying and extending the filtering approach to cope with larger-scale environments (Newman 1999; Deans and Hebert 2000; Dissanayake et al. 2001; Castellanos et al. 1999; Julier and Uhlman 2001b; Leonard and Feder 2001; Guivant and Nebot 2001; Paskin 2003; Leonard and Newman 2003; Bosse et al. 2003; Thrun et al. 2004; Guivant et al 2004; Tardos et al. 2002; Williams et al. 2002; Rodriguez-Losada et al. 2004). However, filtering itself has been shown to be inconsistent when applied to the inherently non-linear SLAM problem (Julier and Uhlman 2001a), i.e., even the average taken over a large number of experiments diverges from the true solution. Since this is mainly due to linearization choices that cannot be undone in a filtering framework, there has recently been considerable interest in the smoothing version of the SLAM problem."

Tools used for computation

MATLAB for mathematical computation of the algorithms. 2-D world with dot landmarks and simulated noise.

Extended Information Filter (EIF)

from Visually mapping the RMS Titanic: conservative covariance estimates for SLAM information filters.(simultaneous localization and mapping ). Ryan M. Eustice, Hanumant Singh, John J. Leonard and Matthew R. Walter. The International Journal of Robotics Research 25.12 (Dec 2006): p1223(20). (8549 words)

"A number of recent SLAM algorithms have explored reformulating the estimation problem within the context of an extended information filter (EIF), which is the dual of the extended Kalman filter (EKF) (Bar Shalom et al. 2001). The information form is often called the canonical or natural representation of the Gaussian distribution because it stems from expanding the quadratic in the exponential."

Particle Filter

from Multi-robot simultaneous localization and mapping using particle filters. Andrew Howard. The International Journal of Robotics Research 25.12 (Dec 2006): p1243(14). (6983 words)

"The starting point of our analysis is the Rao-Blackwellized particle filter described by Hahnel et al. (2003). This algorithm uses a particle filter to approximate the posterior probability distribution over possible maps, and adds robot observations incrementally using a Bayesian update step. This algorithm can readily be generalized to solve the multi-robot SLAM problem, assuming that the initial pose of all robots is known. More precisely, one must know at least the initial relative pose of all but one of the robots, with the pose of the remaining robot being chosen arbitrarily. This assumption is extremely limiting in practice: it implies either that all robots have started from the same location, or that the initial locations of the robots have been surveyed by some external means."