The SAM problem as an MRF

Loopy Belief Propagation on the MRF solves the SAM problem. Only the nodes near the robot (in red) are updated here.

When the factorization of matrix (here the triangular matrix R of a QR factorization) is updated incrementally upon the addition of a few rows to the original matrix, only a small portion of the entries get changed (shown in red).


  1. Fast Incremental Square Root Smoothing
    Michael Kaess, Ananth Ranganathan, and Frank Dellaert, IJCAI 2007.

    This paper introduces a matrix factorization approach to SAM by incrementally updating the Cholesky factor of the Hessian matrix for the SLAM problem. New measurements involve the addition of new rows to the Hessian. The Cholesky factor can be updated through incremental QR factorization using Givens rotations. This results in an extremely  fast algorithm.

  2. Loopy SAM
    Ananth Ranganathan, Michael Kaess, and Frank Dellaert, IJCAI 2007.

    This paper formulates the SLAM problem as a Markov Random Field (MRF) on which inference is done through loopy belief propagation to obtain the estimates of the robot and landmark locations. We show that when the robot is not closing a loop, each step involves the addition of a few nodes to the MRF. The resulting loopy belief update does not affect the whole MRF graph when messages are thresholded, resulting in a fast algorithm. We also provide a theoretical proof showing the equality between Gauss-Seidel elimination on the MRF matrix and loopy belief propagation on the MRF graph.