MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


Exploring unknown environments

Albers, Susanne and Henzinger, Monika R.

July 1997, 23 pages.

Status: available - back from printing

We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number $R$ of edge traversals. Koutsoupias~\cite{K} gave a lower bound for $R$ of $\Omega(d^2 m)$, and Deng and Papadimitriou~\cite{DP} showed an upper bound of $d^{O(d)} m$, where $m$ is the number edges in the graph and $d$ is the minimum number of edges that have to be added to make the graph Eulerian. We give the first sub-exponential algorithm for this exploration problem, which achieves an upper bound of $d^{O(\log d)} m$. We also show a matching lower bound of $d^{\Omega(\log d)}m$ for our algorithm. Additionally, we give lower bounds of $2^{\Omega(d)}m$, resp.\ $d^{\Omega(\log d)}m$ for various other natural exploration algorithms.

  • Attachement: (314 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Albers, Susanne and Henzinger, Monika R.},
  TITLE = {Exploring unknown environments},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-97-1-017},
  MONTH = {July},
  YEAR = {1997},
  ISSN = {0946-011X},