REACHING A POLYGON WITH DIRECTIONAL UNCERTAINTY

Abstract

Assume a robot that, when directed to move in a particular direction, is guaranteed to move inside a cone of angle α centered at the specified direction. The robot has to reach a convex polygonal goal G, while avoiding polygonal obstacles of complexity n. We show that the complexity of the safe region, from where the robot can reach the goal with a single motion with uncertainty α, is O(m+n), and can be computed in time O((m+n) log (m+n)), if α is assumed constant.