de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Report

#### Exploring unknown environments

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons43989

Albers,  Susanne
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### 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.