# MPI-I-97-1-017

## Exploring unknown environments

### Albers, Susanne and Henzinger, Monika R.

**MPI-I-97-1-017**. July** **1997, 23 pages. | Status:** **available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

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.

Acknowledgement:** **

References to related material:

To download this research report, please select the type of document that fits best your needs. | Attachement Size(s): |

| 314 KBytes |

Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView |

**URL to this document: **http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1997-1-017

**BibTeX**
`@TECHREPORT{``AlbersHenzinger97``,`

` 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},`

`}`