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 nod es and edges of the graph using the minimum number R of edge traversals. De ng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R of d(O( d))m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower boun d of Ohm(d(2)m), where m is the number of edges in the graph and d is the m inimum number of edges that have to be added to make the graph Eulerian. We give the first subexponential algorithm for this exploration problem, whic h achieves an upper bound of d(O(log d))m. We also show a matching lower bo und of d(Ohm(log d))m for our algorithm. Additionally, we give lower bounds of 2(Ohm(d))m, respectively, d(Ohm(log d))m for various other natural expl oration algorithms.