Exploring unknown undirected graphs

A robot has to construct a complete map of an unknown environment modeled a s 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 a n exploration algorithm running on a graph G = (V(G), E(G)) is the worst-ca se number of traversals in excess of the lower bound \E(G)\ that it must pe rform in order to explore the entire graph. We give an exploration algorith m whose penalty is O(\V(G)\) for every graph. We also show that some natura l exploration algorithms cannot achieve this efficiency. (C) 1999 Academic Press.