REACHING A GOAL WITH DIRECTIONAL UNCERTAINTY

We study two problems related to planar motion planning for robots wit h imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement wi ll be confined in a cone of angle alpha centered around the specified direction. First, we consider a single goal region, namely the ''regio n at infinity'', and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region R(alpha)(S) from w here we can reach infinity with a directional uncertainty of alpha. We prove that the maximum complexity of R(alpha)(S) is O(n/alpha(5)). Se cond, we consider a collection of k polygonal goal regions of total co mplexity m, but without any obstacles. Here we prove an O(k(3)m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of alpha. For both situations we also prove lower bounds on the maximum complexity, and we give efficient al gorithms for computing the regions.