Colloquium Speaker

Speaker: Christian A.Duncan
Department of Computer Science
University of Miami
Topic:Optimal Constrained Graph Exploration From (firemen to treasure hunters)
Date:Thursday, March 8, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701

Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


In this talk, we address the problem of constrained exploration of an unknown graph G=(V,E) from a given start node S with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both variations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length L, then the robot must remain within distance L from the start node S. In the second variation, a fuel tank of limited capacity forces the robot to return to S after traversing C edges. The efficiency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in O(|E|) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a O(|E|) algorithm. This improves on the previous best known bound of O(|E| + |V| log^2|V|). Since the lower bound for the graph exploration problems is |E|, our algorithm is optimal, thus answering the open problem of Awerbuch, Betke, Rivest, and Singh.

We also extend our results to a modified version of the shortest path problem called the treasure hunting problem. Here a robot wishes to quickly discover some treasure from an unknown graph. We conclude our talk with some interesting open problems.