June 1, Sunday
12:00 – 13:00
Exploring Unknown Polygonal Environments with Discrete Visibility
Computer Science seminar
Lecturer : Subir Gosh
Affiliation : Tata Institute of Fundamental Research, Mumbai
Location : 201/37
Host : Prof. Matya Katz
In this talk, we present on-line algorithms that can be
used to explore an unknown polygonal environment by a point robot.
Our algorithms compute visibility polygons only from a set of chosen
points on the path of a robot, and the criteria for minimizing the
cost for robotic exploration is to reduce the number of visibility
polygons that the algorithms compute. Efficiency of these algorithms
are measured using competitive ratio. We show that these exploration
algorithms are also approximation algorithms for the art gallery
problem with an additional visibility constraint.