Map validation and robot self-location in a graph-like world

Abstract This paper deals with the validation of topological maps of an environment by an active agent (such as a mobile robot), and the localization of an agent in a given map. The agent is assumed to have neither compass nor other instruments for measuring orientation or distance, and, therefore, no associated metrics. The topological maps considered are similar to conventional graphs. The robot is assumed to have enough sensory capability to traverse graph edges autonomously, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex, locating them relative to the edge via which it entered the current vertex. In addition, the robot has access to a set of visually detectable, portable, distinct markers. We present algorithms, along with worst case complexity bounds and experimental results for representative classes of graphs for two fundamental problems. The first problem is the validation problem : if the robot is given an input map and its current position and orientation with respect to the map, determine whether the map is correct. The second problem is the self-location problem : Given only a map of the environment, determine the position of the robot and its “orientation” (i.e., the correspondence between edges of the map and edges in the world at the robot's position). Finally, we consider the power of some other non-metric aids in exploration.