Publications
Courses
Links
Contact
Personal
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 algorithmSummary
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).
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:
In the presence of loops, a good variable ordering is essential to avoid fill-in in the factor matrix:
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:
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:
iSAM also works on pose-only data, here obtained by laser scan matching from the Intel lab sequence, again with the sparse R factor:
