Title: Robot Localization in a Grid

Speaker: Dana Angluin, Computer Science Department, Yale University

We consider the problem of localizing a mobile robot in a bounded connected
two-dimensional grid environment containing arbitrary obstructions.  The robot
is initially given the height and width of the grid, and is started in an
unknown cell of the grid.  The robot has odometry and can locally sense
obstructions and move into any unobstructed space it chooses to visit.  The
robot's task is to move around in the environment until it figures out its
current location.  We present a new algorithm for this task, the Homing Robot,
that successfully localizes using O(log n) bits of memory and no more than
4n moves, where n is the number of unobstructed cells in the grid.

This is joint work with Chinda Wongngamnit.