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."

Localization

"In the literature, the localization task is generally divided into two phases: (a) the first step consists in the integration of dead reckoning sensors to predict the vehicle location; (b) the second phase, which is usually activated at a much slower rate, uses an absolute exteroceptive sensing mechanism to update the predicted position. Many research works are related to road vehicle applications, in which an Inertial Measurement Unit (IMU) is used to provide higher update rate of the position between two consecutive GPS data acquisitions (Nebot et al. 1997). In Bevly et al. (2001) the same pair of sensors is used for both localization and estimation of wheel diameter change and vehicle sideslip. Dissanayake et al. (2001) propose to use the non-holonomic constraints that govern the motion of a vehicle on a surface to align the IMU and significantly improve the accuracy of the localization.

Most applications tackle the problem of vehicle localization on flat and smooth soil. In such conditions, relatively accurate vehicle models can be developed, which lead to good state prediction. However, such models are not available in challenging environments such as forests, mines or craters on the surface of Mars. For these types of application the full 3D state of the rover has to be estimated and absolute positioning means such as GPS are not available. When the state prediction model is not well known and when no absolute sensing mechanism is accessible to correct the vehicle position, accurate dead reckoning becomes crucial to prevent the position error increasing too quickly. Scheding et al. (1999) present interesting results for an underground mining vehicle. In particular, they demonstrate that inertial sensors can be used to correct non-systematic errors due to soil irregularities when fused with other sensors such as wheel encoders and laser scanners. In Strelow and Singh (2003), the 6 DOFs of a vehicle are estimated using an IMU and features tracked in images taken by an omnidirectional vision system. In Mallet et al. (2000) and Olson et al. (2001) the 3D state of rough terrain rovers is tracked on the sole base of features tracking and stereovision."

from 3D position tracking in challenging terrain. Pierre Lamon and Roland Siegwart. The International Journal of Robotics Research 26.2 (Feb 2007): p167(20). (9685 words)