@Article{ABRS99,
author = { Baruch Awerbuch and Margrit Betke and Ronald L. Rivest and Mona Singh },
title = { Piecemeal graph exploration by a mobile robot },
pages = { 155--172 },
doi = { 10.1006/inco.1999.2795 },
journal = { Information and Computation },
date = { 1999-08 },
issn = { 0890-5401 },
publisher = { Academic Press },
OPTyear = { 1999 },
OPTmonth = { August },
volume = { 152 },
number = { 2 },
url = { http://www.sciencedirect.com/science/article/pii/S0890540199927955 },
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.''
}
}