On the Movement of Robot Arms in 2-Dimensional Bounded Regions

摘要

The mover’s problem is the following: can an object in 3-dimensional space be moved from one given position to another while avoiding obstacles? It is known that the general version of this problem involving objects with movable joints is PSPACE hard, even for a simple tree-like structure moving in a 3-dimensional region. In this paper, we investigate a 2-dimensional mover’s problem in which the object is a robot arm with an arbitrary number of joints. In particular, we give a polynomial time algorithm for moving an arm confined within a circle from one given configuration to another. We also give a polynomial time algorithm for moving the arm from its initial position to a position in which the end of the arm reaches a given point within the circle. Finally, we show that 148 circles suffice to cover the boundary of the reachable region of a joint in an arm enclosed in a circle and that the boundary can be computed in polynomial time.