An Optimal Competitive Strategy for Looking Around a Corner

Abstract

We consider a problem of motion planning under uncertainty. A robot can navigate freely in the plane and, using a built-in vision system, can determine distances and angles. Initially, the robot stands at a point close to a an edge of a polygonal obstacle (e. g. a wall of a huge building) and faces a corner at distance 1 from its position. The other wall which forms the corner is invisible from the starting position and the robot does not know the angle of the corner. The task of the robot is to move on a short path to a point where that wall becomes visible. We show that there is a competitive strategy which guarantees that, for any possible value of the angle, the length of the path the robot walks until it can look around the corner is bounded by the length of the shortest path to do so, times the constant c 1:21218. Furthermore, we prove that our strategy is optimal in that no smaller competitive factor than c can be achieved. We give a simple formula for the robot to nd the optimal path. A more general problem arises if the robot’s starting point is not required to lie directly at the visible wall. We provide optimal competitive strategies for all such cases; the competitive factor varies between 1 and c, depending on the angle between the visible wall and the line through the starting point and the corner. Key words. Motion planning, navigation, competitive algorithms, uncer-tainty, robotics. 1