On-line motion planning: Case of a planar rod

James Cox, Chee Keng Yap

Research output: Contribution to journalArticlepeer-review


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(n2) guarded moves, where n is the number of obstacle corners. This matches the known lower bound. The computational complexity O(n2log n) of our algorithm matches the best known algorithm for the off-line version.

Original languageEnglish (US)
Pages (from-to)1-20
Number of pages20
JournalAnnals of Mathematics and Artificial Intelligence
Issue number1
StatePublished - Mar 1991

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics


Dive into the research topics of 'On-line motion planning: Case of a planar rod'. Together they form a unique fingerprint.

Cite this