|
Abstract : |
We propose a combinatorial approach to plan noncolliding motions for a planar robot arm. The approach works even with certain types of movable polygonal obstacles and exible polygonal fences. This yields a very ecient deterministic algorithm for a category of robot arm motion planning problems with many degrees of freedom, for which the known general roadmap techniques have exponential complexity. The main result is an ecient algorithm for convexifying a simple (open or closed) polygonal path with rigid non-intersecting motions in the plane. It works by computing in O(n 2) time a monotone mechanism with one degree of freedom, whose motion is controlled by the rotation of a single edge around one of its endpoints. As it moves, all the interdistances between pairs of points not joined by a bar are nondecreasing, thus guaranteeing non-collision. At most O(n, |
