__Abstract__

The Shortest Watchman Route Problem, namely 'Given a polygon find the shortest route in the polygon with the property that each point in the polygon is visible from at least one point along the route', was solved in 1991. In order to model real-life situations, for example as encountered by a scout that must efficiently explore an unknown terrain, one must consider the online version of the problem. Exploration has been one of the major areas of research in Robotics but theoretical results on tractability, efficiency, and correctness of exploration algorithms are relatively recent. In this report, we will review the approaches to explore an unknown environment. We will first present some essential concepts and review the lemmata that have been used in all exploration algorithms. Then, we will describe the solution to the Watchman Route Problem, since this algorithm forms the basis of all succesive exploration algorithms. The first solution for the unknown environments was for the rectilinear case. We also consider the situation faced by a robot with a finite line of sight, which also has to return to the starting point every so often to refuel. The existance of a competitive algorithm for a rectilinear environment with an arbitrary number of polygons can be constructively refuted. Finally, we present the algorithm for a simple polygon with no obstacles and we conclude by discussing the open problems and future areas of research.

Download the paper: (ps)(ps.gz) (pdf)

**Main Papers**:

- How to learn an unknown environment. I: the rectilinear case

Xiaotie Deng, Tiko Kameda and Christos Papadimitriou

http://www.acm.org/pubs/citations/journals/jacm/1998-45-2/p215-deng/

Exploring unknown environments with obstacles

Susanne Albers, Klaus Kursawe and Sven Schuierer

http://www.acm.org/pubs/citations/proceedings/soda/314500/p842-albers/

Long version: http://www.mpi-sb.mpg.de/~albers/soda99b.ps.gz

The Polygon Exploration Problem I : A Competitive Strategy

Frank Hoffmann and Christian Icking and Rolf Klein and Klaus

Kriegel

http://wwwpi6.fernuni-hagen.de/Publikationen/tr241.pdf

Conference version: http://www.acm.org/pubs/citations/proceedings/soda/314161/p166-hoffmann/