# Item

ITEM ACTIONSEXPORT

Released

Report

#### Exploring unknown environments

##### Locator

There are no locators available

##### Fulltext (public)

1997-1-017

(Any fulltext), 10KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Albers, S., & Henzinger, M. R.(1997). *Exploring unknown
environments* (MPI-I-1997-1-017). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-9D82-5

##### Abstract

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.