The relative power of immovable markers in topological mapping

The fundamental problem in robotic exploration and mapping of an unknown environment is answering the question ´have I been here before?´, which involves disambiguating the robot´s current location from previously visited or known locations. One approach to answering this problem in embedded topological worlds is to resort to the use of an external aid that can help the robot disambiguate places. Here we investigate the power of different marker-based aids in exploring undirected topological graphs. We demonstrate that for undirected graphs, certain marker aids are insufficient, while others have powers that are sufficient to develop asymptotically optimal exploration algorithms.