MOTION PLANNING IN THE PRESENCE OF MOVING OBSTACLES.

Published

Journal Article

The authors investigate the computational complexity of planning the motion of a body B in 2-D or 3-D space, so as to avoid collision with moving obstacles of known, easily computed, trajectories. Dynamic movement problems are of fundamental importance to robotics, but their computational complexity has not previously been investigated. Evidence is provided that the 3-D dynamic movement problem is intractable even if B has only a constant number of degrees of freedom of movement. In particular, it is proved that the problem is PSPACE-hard if B is given a velocity modulus bound on its movements and is NP hard even if B has no velocity modulus bound, where in both cases B has 6 degrees of freedom. These results are proved using a unique method of simulation of a Turning machine that uses time to encode configurations.

Duke Authors

Cited Authors

  • Reif, J; Sharir, M

Published Date

  • December 1, 1985

Published In

Start / End Page

  • 144 - 154

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus