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 |
Simple Example
This simple example can be disassembled by a sequence of 2-handed one-shot translations. All moving parts move in the same direction with the same velocity. The well-known blocking graph algorithm can be used to solve problems like this. Our new techniques allow for generation of a plan within about one second. Click on the image for an animated disassembly sequence (130 kB). |
Cube Puzzle (individual parts)
This more complex example is a model of a wooden cube puzzle. It consists of 12 tightly fitting parts and requires complex coupled motions. During disassembly, several parts have to be shifted back and forth to unlock other parts. For this reason the blocking graph algorithm and all other previously known approaches for assembly planning fail to solve this example. Our new algorithm found a complete disassembly plan in less than 15 seconds. Click on the image for an animated disassembly
sequence (225 kB). |