Exploring an unknown polygonal environment with bounded visibility

Abstract

This paper integrates constraints from visual processing and robot navigation into the well-studied computational geometry problem of exploring unknown polygonal environments with obstacles. In particular, we impose two constraints. First, we consider a robot with limited visibility, which can reliably "see" its environment only within a certain range R. Second, we allow the computation of visibility only from discrete number of points on the path. Both these constraints arise from real life cost constraints associated with robotic exploration and robot vision processing. We present an online algorithm for exploration under such constraints and show that the maximum number of views needed to explore the unknown polygon (with obstacles) P, is bounded by ]2^×Perimeter(P)/R]+2^×Area(P)/R²+3n + 3n, where n is the number of sides of the polygon. We also show that the competitive ratio of the algorithm is 6π+ 6π+4r+3n/max([Area(P)/ΤR²,[Perimeter(P)-2Rr)/2ΤR].