McGill University - School of Computer Science

Algorithms Seminar Winter 2001

Everybody is welcome!

DATE: Wednesday, April 4th
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: The Power of a Pebble: Exploring and Mapping Directed Graphs
SPEAKER: Michael Bender, SUNY Stony Brook

Exploring and mapping an unknown environment is a fundamental problem with applications ranging from robot navigation to searching the World Wide Web. As such, a large body of work has focused on finding efficient solutions to variants of the problem, with restrictive assumptions on the form of the environment. In this work, we consider a model that makes very limited assumptions about the environment, and give efficient algorithms to solve the mapping problem in this general setting.

We view the environment as an unknown strongly-connected directed graph $G$ and consider the problem of a robot exploring and mapping $G$. Since the vertices of $G$ may not be labeled, the robot is provided with a pebble (or several pebbles) that it can use to mark and identify verticies. We develop exploration algorithms for the robot and show tight lower bounds. Even though the graph may have a complicated directed structure, surprisingly few pebbles are needed for the robot to explore the graph efficiently.

This is joint work with Antonio Fernandez, Dana Ron, Amit Sahai, and Salil Vadhan.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.