WPE-II: Theoretical Robot Exploration

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: