A competitive strategy for learning a polygon

Abstract

We provide a competitive strategy for a mobile robot with vision, that has to explore an unknown simple polygon starting from and returning to a given point on the boundary. Our strategy creates a tour that does not exceed in length 133 times the length of the optimal watchman route. This paper is the first to describe a complete strategy and to give a proof for such a constant competitive factor.