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 alpha 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 a, is O(m + n), and can be computed in time O((m + n) log(m + n)), if a is assumed constant.