On the piano movers' problem: V. The case of a rod moving in three‐dimensional space amidst polyhedral obstacles

摘要

Abstract This paper, a fifth in a series, solves some additional 3‐D special cases of the „piano movers”︁ problem, which arises in robotics. The main problem solved in this paper is that of planning the motion of a rod moving amidst polyhedral obstacles. We present polynomial‐time motion‐planning algorithms for this case, using the connectivity‐graph technique described in the preceding papers. We also study certain more general polyhedral problems, which arise in the motion planning problem considered here but have application to other similar problems. Application of these techniques to the problem of planning the motion of a general polyhedral body moving in 3‐space amidst polyhedral obstacles is also described.