**Authors: Baruch Awerbuch, Margrit Betke, Ronald L. Rivest, Mona Singh**

**Source: ***Information & Computation* Vol. **152**, No. 2,
1999, 155 - 172.

**Abstract.**
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, while
satisfying the constraint that it must return every so often to its
starting position (for refueling, say). The environment is modeled as an
arbitrary, undirected graph, which is initially unknown to the robot. We assume
that the robot can distinguish vertices and edges that it has already
explored. We present a surprisingly efficient algorithm for piecemeal learning
an unknown undirected graph *G=(V, E)* in which the robot explores every
vertex and edge in the graph 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 give an application of piecemeal learning to the problem of searching a
graph for a ``treasure.''

©Copyright 1999, Academic Press