On the Piano Movers' problem: IV. Various decomposable two‐dimensional motion‐planning problems

Abstract Various special motion‐planning problems involving arbitrarily many degrees of freedom are shown to admit relatively simple solutions by techniques based on the connectivity graph approach described by Schwartz and Sharir. The solutions exploit the particularly simple configuration space structure of the robot systems considered. A typical problem is that of planning motions for a 2‐dimensional robot system consisting of several arms all jointed at one common endpoint and free to rotate past each other. The algorithm given for solving this problem runs in time O ( n k+4 ), where k is the number of arms.