Scan matching, the problem of registering two laser scans in order to determine the relative positions from which the scans were obtained, is one of the most heavily relied-upon tools for mobile robots. The design of current algorithms is strongly influenced by the need for real-time operation: heuristics are employed in order to reduce the complexity of the search. Of course, these heuristics are imperfect, and can result in poor results--- especially in cases where the prior is weak or absent... (more)