A 4-competitive strategy for exploring unknown polygons

摘要

We present a new, on-line strategy for a mobile robot to explore an unknown simple polygon with n vertices, starting at a boundary point s, which outputs a so-called watchman route such that every interior point of P is visible from at least one point along the route. The length of the robot's route is guaranteed to be at most 4 times that of the shortest watchman route that could be computed off-line. This gives a significant improvement upon the previously known 26.5-competitive strategy, and also confirms a conjecture due to Hoffmann et al [5]. A novelty of our competitive strategy is a recursive procedure that reduces the polygon exploration problem to the subproblems of exploring two different types of reflex vertices, which are classified by their turning directions in the shortest path tree of s. The other is a mixture of techniques, including the off-line approximation algorithm for the watchman route problem [7], a geometric structure called the angle hull [5], and the paradiam for making the off-line techniques be on-line.