TY - JOUR

T1 - Reaching a goal with directional uncertainty

AU - Berg, de, M.

AU - Guibas, L.J.

AU - Halperin, D.

AU - Overmars, M.H.

AU - Schwarzkopf, O.

AU - Sharir, M.

AU - Teillaud, M.

PY - 1995

Y1 - 1995

N2 - We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle a centered around the specified direction.
First, we consider a single goal region, namely the "region at infinity", and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of a. We prove that the maximum complexity of is O(n/a5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of a. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

AB - We study two problems related to planar motion planning for robots with imperfect control, where, if the robot starts a linear movement in a certain commanded direction, we only know that its actual movement will be confined in a cone of angle a centered around the specified direction.
First, we consider a single goal region, namely the "region at infinity", and a set of polygonal obstacles, modeled as a set S of n line segments. We are interested in the region from where we can reach infinity with a directional uncertainty of a. We prove that the maximum complexity of is O(n/a5). Second, we consider a collection of k polygonal goal regions of total complexity m, but without any obstacles. Here we prove an O(k3m) bound on the complexity of the region from where we can reach a goal region with a directional uncertainty of a. For both situations we also prove lower bounds on the maximum complexity, and we give efficient algorithms for computing the regions.

U2 - 10.1016/0304-3975(94)00237-D

DO - 10.1016/0304-3975(94)00237-D

M3 - Article

SN - 0304-3975

VL - 140

SP - 301

EP - 317

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2

ER -