The Polygon Exploration Problem: A New Strategy and a New Analysis Technique

摘要

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.