POLYHEDRAL ASSEMBLY PARTITIONING USING MAXIMALLY COVERED CELLS IN ARRANGEMENTS OF CONVEX POLYTOPES

We study the following problem: Given a collection A of polyhedral par ts in 3D, determine whether there exists a subset S of the parts that can be moved as a rigid body by infinitesimal translation and rotation , without colliding with the rest of the parts, A \ S. A negative resu lt implies that the object whose constituent parts are the collection A cannot be taken apart with two hands. A positive result, together wi th the list of movable parts in S and a direction of motion for S, can be used by an assembly sequence planner (it does not, however, give t he complete specification of an assembly operation). This problem can be transformed into that of traversing an arrangement of convex polyto pes in the space of directions of rigid motions. We identify a special type of cells in that arrangement, which we call the maximally covere d cells, and we show that it suffices for the problem at hand to consi der a representative point in each of these special cells rather than to compute the entire arrangement. Using this observation, we devise a n algorithm which is complete (in the sense that it is guaranteed to f ind a solution if one exists), simple, and improves significantly over the best previously known solutions. We describe an implementation of our algorithm and report experimental results obtained with this impl ementation.