Piecemeal graph exploration by a mobile robot (extended abstract)

Abstract

) Baruch Awerbuch y Margrit Betke Ronald L. Rivest Mona Singh Laboratory for Computer Science Massachusetts Institute of Technology Cambridge, MA 02139 Abstract We study the problem of learning a graph by piecemeal exploration, in which a mobile robot must return every so often to its starting point (for refueling, say). We assume that the robot can distinguish vertices and edges which it has already explored. We present an algorithm for piecemeal learning an unknown undirected graph G = (V; E) in which the robot explores every vertex and edge in G by traversing at most O(E + V 1+o(1) ) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V 2 ) edges. We also address the related problem of searching a graph for a particular distinguished location or treasure. If this location or treasure is known to be near the starting point, then the robot should search in a breadth-first manner from the starting point. We gi...