The Power of a Pebble: Exploring and Mapping Directed Graphs
Michael Bender ,
Ron ,Amit Sahai ,
and Salil Vadhan.
Exploring and mapping an unknown environment is a fundamental problem that
is studied in a variety of contexts. Many results have focused on finding
efficient solutions to restricted versions of the problem. In this paper,
we consider a model that makes very limited assumptions about the environment
and solve the mapping problem in this general setting.
We model the environment by an unknown directed graph G, and consider
the problem of a robot exploring and mapping G. The edges emanating from
each vertex are numbered from `1' to `d', but we do not assume that the
vertices of G are labeled. Since the robot has no way of distinguishing
between vertices, it has no hope of succeeding unless it is given some
means of distinguishing between vertices. For this reason we provide the
robot with a "pebble" --- a device that it can place on a vertex and use
to identify the vertex later.
In this paper we show:
In both cases our algorithms are deterministic.
If the robot knows an upper bound on the number of vertices then it can
learn the graph efficiently with only one pebble.
If the robot does not know an upper bound on the number of vertices n,
then Theta(loglog n) pebbles are both necessary and sufficient.
back to Salil Vadhan's research interests ]