The analysis of linear constraint sets has a large number of applications. We have investigated this analysis in the context of
General Translational Assembly PlanningDescription
Under the assumption of rigid parts, the assembly of a product can be planned by finding a sequence of disassembly motions and reversing it. Here we address the following problem: Given a set of polyhedral models in their final spatial positions, decide whether there is a sequence of motions (arbitrary translations) for separating these parts. Conversely if you think a given set of polyhedra interlock (cannot be separated), output a proof that they indeed interlock. Previous work on assembly planning is either limited to infinitesimal motions, single translations (i.e. the assembly has to be partitioned by one-shot translations and all moving parts have to be moved simultaneously) or based on random techniques (i.e. extremely unlikely to succeed for small clearances between parts and not capable of proving infeasibility). Our new algorithms are based on incremental and efficient construction of cells in a high-dimensional arrangement of hyperplanes. They are exact and complete in the sense that infeasibility of assemblies can be proved by a program. The basics are discussed in our work on "Testing for Removability". A recent extension called "ghost plane elimination" makes the partitioning significantly coarser and allows for generation of complex plans for 3-dimensional assemblies with several parts.
Examples
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
Simple | Cube | Shelf | Lock | Desk | m-handed |