TABLE OF CONTENTS Hirohisa Hirukawa, Electrotechnical Laboratory, Tsukuba, Japan
This paper studies motion planning of polyhedra in contact, which has a crucial role to automate mechanical assembly processes. We have been attacking this problem based on an algebraic formulation. We first revisit our complete and implemented algorithm for motion planning of convex polyhedra in contact to see that the complexity of the algebraic part heavily depends how the geometric problem is reduced to it. Then we present a predicate for nonconvex polyhedra in contact without overlapping, give algorithms to be applied to the non-convex case, and investigate their geometric and algebraic complexity.
Motion planning of objects in contact has a crucial role to automate mechanical assembly processes. It is also interesting from a theoretical viewpoint, since exact motion planning approaches seems to be more appropriate when the clearance between the objects is tight. This problem is closely related to that of finding the boundary of configuration space obstacles (C-obstacles in short), which is the image of fixed objects in the configuration space of a moving object, because a path on this boundary corresponds to the motion of the object in contact with the fixed ones.
Avnaim, Boissonnat and Faverjon proposed an algorithm to find the boundary of C-obstacles when a polygon moves within polygonal obstacles in 2-space[2], together with an algorithm for motion planning of...
