On-line motion planning: Case of a planar rod

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 call guarded moves. We call ours the on-line motion planning problem as opposed to the usual off-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 complexity O(n²) guarded moves, where n is the number of obstacle corners. This matches the known lower bound. The computational complexity O(n²log n) of our algorithm matches the best known algorithm for the off-line version.