A lazy algorithm for planning motions in contact

Planning the motion of objects in contact is an important stage of the analysis of mechanical assembly tasks. This paper concerns with the case of a polyhedron moving within a polyhedral environment. It presents an algorithm to plan the motion of a convex polyhedron translating and rotating in contact with a neither necessarily convex nor connected polyhedral obstacle. This algorithm uses a new description of the obstacle in the configuration space-the C-obstacle-with the help of several contact predicates and of a topological adjacency graph. However, in the nonconvex case, the complete computation of the boundary of the C-obstacle is usually intractable. Our algorithm is lazy: it takes into account progressively and only if it is necessary the nonconvexity of the polyhedra. Indeed, the main idea is to describe the C-obstacle as if it were convex, in order to perform as few computations as possible to find a motion and, in case of failure, to build a new description of the C-obstacle incorporating “some” nonconvexity features, and to repeat this process until a correct motion is planned. We also describe a prototype of implementation of this algorithm and an example it can solve