ROBOTIC EXPLORATION AS GRAPH CONSTRUCTION

We address the problem of robotic exploration of a graph-like world, where no distance or orientation metric is assumed of the world. The robot is assumed to be able to autonomously traverse graph edges, recognize when it has reached a vertex, and enumerate edges incident upon the current vertex relative to the edge via which it entered the current vertex. The robot cannot measure distances, and it does not have a compass. We demonstrate that this exploration problem is unsolvable in general without markers, and, to solve it, we equip the robot with one or more distinct markers that can be put down or picked up at will and that can be recognized by the robot if they are at the same vertex as the robot. We develop and prove correct an exploration algorithm, we show its performance on several example worlds, and we discuss heuristics for improving its performance.