A Discussion of Simultaneous Localization and Mapping
SLAM is a difficult subject, so the community spent quite some time to figure out the structure of the problem itself. The analysis was not strictly formal but based both on thought experiments and mathematical derivation. A central question is the structure of uncertainty of an estimated map with the key result being
Certainty of Relations despite Uncertainty of Positions
This idea is illustrated by the two videos below, that show the uncertainty structure of a map estimate before and after closing a loop. The uncertainty is illustrated by concatenating several random outcomes of the same simulated mapping experiment. While the small room in the right lower corner moves around tremendously, its shape stays quite the same. So its pose is uncertainty, while its shape is certain.
Formally this idea is underpinned by a proof for approximate sparsity of so-called information matrices occurring in SLAM. It supports the above mentioned characterization and provides a foundation for algorithms based on sparse information matrices. It is based on close examination of information matrices, covariance matrices, and their relation as sketched in the diagram above.
A more detailed treatment is found in U. Frese's Ph.D. thesis (2004) and the ICRA (2005) paper and the corresponding ICRA 2005 talk.