TABLE OF CONTENTS Frank Hoffmann, Freie Universit t Berlin, Berlin, Germany
Christian Icking, Fernllniversit t Hagen, Hagen, Germany
Rolf Klein, Fernllniversit t Hagen, Hagen, Germany
Klaus Kriegel, Freie Universit t Berlin, Berlin, Germany
We provide a new on-line strategy that enables a mobile robot with vision to explore an unknown polygon by a tour less than 26.5 times as long as the shortest watchman tour. This improves considerably on the best upper bound of 133 known so far. Our strategy uses a new way of dynamically decomposing the polygon. The analysis is based on a novel geometric structure called the angle hull.
Suppose a mobile robot has to explore an unknown simple polygon. The robot starts walking at a given boundary point, s; it is equipped with a vision system that continuously provides the visibility polygon of the robot's current position. When each point of the polygon has been visible at least once, the robot returns to s.
The problem is in designing a competitive exploration strategy, i.e. one that guarantees the robot's path never to exceed in length a fixed constant times the length of the shortest watchman tour through s.
The off-line version of this problem, where the polygon is known, has been extensively studied. Chin and Ntafos [3] have shown that it is sufficient and necessary for the shortest watchman tour from s to visit the prolongations of some edges, the so-called essential cuts. Moreover, they have shown that the shortest watchman tour can be computed...
