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.

Literature and folklore is rife with a range of oracles that have been used by explorers to explore unknown environments. But how effective are these various oracles? This paper considers the power of string and string-like oracles to map an unknown embedded topological environment. We demonstrate that for undirected graphs, even very short strings can be used to explore an unknown environment but that significant performance improvements can be found when longer strings are available.