A lazy algorithm for planning motions in contact
U. Papegay, Hirohisa Hirukawa · 2002
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.>