Exploring unknown undirected graphs

Abstract

A robot has to construct a complete map of an unknown environment modeled as an undirected connected graph. The task is to explore all nodes and edges of the graph using the minimum number of edge traversals. The penalty of an exploration algorithm running on a graph G = (V(G), E(G)) is the worst-case number of traversals in excess of the lower bound |E(G)| that it must perform in order to explore the entire graph. We give an exploration algorithm whose penalty is O(|V(G)|) for every graph. We also show that some natural exploration algorithms cannot achieve this efficiency.