| 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.