Collin Johnson and Benjamin Kuipers. 2012.
Efficient search for correct and useful topological maps.
IEEE/RSJ Int. Conf. on Intelligent Robots and Systems (IROS), 2012.


We present an algorithm for probabilistic topological mapping that heuristically searches a tree of map hypotheses to provide a usable map hypothesis online, while still guaranteeing the correct map will eventually be found. Our algorithm annotates each leaf of the tree with a posterior probability. When a new place is encountered, we expand hypotheses based on their posterior probability, which means only the most probable hypotheses are expanded. By focusing on the most probable hypotheses, we dramatically reduce the number of hypotheses evaluated allowing real-time operation. Additionally, our approach never prunes consistent hypotheses from the tree, which means the correct hypothesis always exists within the tree.