Title:   Online Algorithms for Searching and Exploration in the Plane

Speaker: Subir Kumar Ghosh,
        School of Technology & Computer Science
        Tata Institute of Fundamental Research
        Mumbai 400005, India

Date:    January 1, 2012

Consider a natural scenario when a robot does not have the complete
knowledge of the geometry of the environment a priori, and  also does
not know the location of the  target point, but the target can be
recognized by the robot. In such a situation, the robot is asked to
reach the target point from its starting position  using its sensory
input provided by acoustic, visual, or tactile sensors of  its
on-board sensor system. The problem here is to design an efficient
algorithm which a robot can use to search for the target point. This
is called  an "online problem" of a robot path planning  for a target
searching problem in an unknown environment, and the algorithms for
these types of online problems are known as "online algorithms".
Observe that any such algorithm is `online' in the sense that decisions
must be made based only on what the robot has received input so far
from its sensor system.  If a robot is asked to explore or see all
points of an  unknown environment rather than searching for a particular
target point, the problem is known as "online exploration problem" of
a robot, and algorithms for these type of problems are known as "online
exploration algorithms".

In this lecture, we present an overview of online algorithms in
computational geometry that have been designed for mobile point robots
for searching a target and for exploring a region in the plane.