Exploring unknown environments

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. Deng and Papadimitriou showed an upper bound for R of d_O_(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of _O_(d2m), where m is the number of 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 subexponential algorithm for this exploration problem, which achieves an upper bound of dO(log d)m. We also show a matching lower bound of dOmega(log d)m for our algorithm. Additionally, we give lower bounds of 2_O_(d)m, respectively, d_O_(log d)m for various other natural exploration algorithms.

Published in:
SIAM J Comput, 29, 4, 1164-1188
Other identifiers:
Scopus: 2-s2.0-0033714291

 Record created 2007-01-18, last modified 2018-03-17

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)