ISSN:
1573-7470
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract In this paper we develop an algorithm for planning the motion of a planar “rod” (a line segment) amidst obstacles bounded by simple, closed polygons. The exact shape, number and location of the obstacles are assumed unknown to the planning algorithm, which can only obtain information about the obstacles by detecting points of contact with the obstacles. The ability to detect contact with obstacles is formalized by move primitives that we callguarded moves. We call ours theon-line motion planning problem as opposed to the usualoff-line version. This is a significant departure from the usual setting for motion planning problems. What we demonstrate is that the retraction method can be applied, although new issues arise that have no counterparts in the usual setting. We are able to obtain an algorithm with path complexityO(n 2) guarded moves, wheren is the number of obstacle corners. This matches the known lower bound. The computational complexityO(n 2logn) of our algorithm matches the best known algorithm for the off-line version.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01530886
