Michael Kaess
Center for Robotics and Intelligent Machines, Georgia Tech GT CoC IC GVU RIM@GT BORG

please see my MIT page for up-to-date information

iSAM (incremental Smoothing and Mapping)

Update Aug 29, 2010: Open source iSAM library released

Update Oct 15, 2010: Our work on the Bayes tree provides a fully incremental algorithm

Summary

iSAM is a novel approach to simultaneous localization and mapping (SLAM), which is the problem of mapping an unknown environment with a mobile robot, which simultaneously requires localizing the robot in this incomplete map. iSAM provides an efficient incremental solution to the full SLAM problem (trajectory included, no filtering) based on updating a matrix factorization. Based on this factorized information matrix, iSAM also provides efficient access to the exact uncertainties needed for data association.

Publications

  • “Square Root SAM: Simultaneous Localization and Mapping via Square Root Information Smoothing” by F. Dellaert and M. Kaess. Intl. J. of Robotics Research, vol. 25, no. 12, Dec. 2006, pp. 1181-1204. Details. Download: PDF.
  • “Fast Incremental Square Root Information Smoothing” by M. Kaess, A. Ranganathan, and F. Dellaert. In Intl. Joint Conf. on Artificial Intelligence, IJCAI, (Hyderabad, India), Jan. 2007, pp. 2129-2134. Oral presentation acceptance ratio 15.7% (212 of 1353). Details. Download: PDF.
  • “Loopy SAM” by A. Ranganathan, M. Kaess, and F. Dellaert. In Intl. Joint Conf. on Artificial Intelligence, IJCAI, (Hyderabad, India), Jan. 2007, pp. 2191-2196. Oral presentation acceptance ratio 15.7% (212 of 1353). Details. Download: PDF.
  • “iSAM: Fast Incremental Smoothing and Mapping with Efficient Data Association” by M. Kaess, A. Ranganathan, and F. Dellaert. In IEEE Intl. Conf. on Robotics and Automation, ICRA, (Rome, Italy), Apr. 2007, pp. 1670-1677. Details. Download: PDF.
  • “iSAM: Incremental Smoothing and Mapping” by M. Kaess, A. Ranganathan, and F. Dellaert. IEEE Trans. on Robotics, vol. 24, no. 6, Dec. 2008, pp. 1365-1378. Details. Download: PDF.
  • “Covariance Recovery from a Square Root Information Matrix for Data Association” by M. Kaess and F. Dellaert. Journal of Robotics and Autonomous Systems, RAS, vol. 57, Dec. 2009, pp. 1198-1210. Details. Download: PDF.

Live Demo

I have demonstrated my visual odometry and visual SLAM work to the DARPA LAGR program manager in San Antonio, Texas. Visual SLAM performs faster than real-time, using only 20 "interesting" features per frame for efficiency (red iSAM optimized, blue: visual odometry, magenta: IMU+wheel encoder, black: GPS, which drifted outside range).

Live demo of iSAM

Overview

Simultaneous Localization and Mapping (SLAM) is a chicken-and-egg problem that is typically solved by filtering-based methods. In contrast, we focus on smoothing, which avoids approximations and allows relinearization. There are two important parts to our work: Efficiency for real-time solutions as well as data association.

Efficiency is achieved by incrementally updating a factored representation of the smoothing information matrix. New measurement rows are added by Givens rotations:

Updating a factored representation of the smoothing information matrix

In the presence of loops, a good variable ordering is essential to avoid fill-in in the factor matrix:

Comparison of different variable orderings

For data association, it is essential to realize that only a small number of entries of the dense covariance matrix are needed (shown in gray). Our factored representation allows efficient access to these entries, without the need to calculate the complete covariance matrix:

Marginal covariances

Exact and conservative covariances

Results

In addition to simulation examples (see paper), we have evaluated iSAM on several publicly available sequences. The Victoria park sequence has a very loopy trajectory, on which iSAM performed 3 times faster than real-time, including data association, and running on a laptop. As can be seen on the right, the square root factor R is indeed very sparse:

Results based on Victoria Park sequence Sparse R factor

iSAM also works on pose-only data, here obtained by laser scan matching from the Intel lab sequence, again with the sparse R factor:

Results based on Intel Lab sequence Sparse R factor