Piecemeal graph exploration by a mobile robot

We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot's goal is to learn a complete map of its environment, wh ile satisfying the constraint that it must return every so often to its sta rting position (for refueling, say). The environment is modeled as an arbit rary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explo red. We present a surprisingly efficient algorithm for piecemeal learning a n unknown undirected graph G = (V, E) in which the robot explores every ver tex and edge in the graph by traversing at most O(E + V1+0(1))edges. This n early linear algorithm improves on the best previous algorithm, in which th e robot traverses at most O(E + V-2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a "treasure." (C ) 1999 Academic Press.