Analysis of Linear Constraints
Prof. Dr. A. Schweikard, F. Schwarzer

The analysis of linear constraint sets has a large number of applications. We have investigated this analysis in the context of

General Translational Assembly Planning

Description

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).
Shelf Model

This is a model of a shelf consisting of 17 tightly fitting parts. Several parts must undergo a sequence of translations to be removed. Especially all clamps are hooked both into the side-panels and the shelves and cannot be removed by single translations. For this reason the blocking graph algorithm and all other previously known approaches for assembly planning cannot solve this example. Our new algorithm took about one minute to generate a complete disassembly plan.

Click on the image for an animated disassembly sequence (350 kB).

Interlocking Parts

Our algorithm is exact and complete, i.e. it can detect interlocking parts by an exhaustive search of reachable critical key placements. This example shows a very simple lock/bolt-mechanism. The program takes only a short fraction of a second to detect the interlocking condition.

Click on the image for a larger view (33 kB).

Desk Model

This is a model of a desk with 8 tightly fitting drawers. The topmost drawers must be removed first before any of the other drawers can be taken out. In the given example, the back panels of the topmost drawers are too high, implying that none of the drawers can be removed. This can be detected with our program in a few seconds.

Click on the image for more details.

m-handed Assembly

Our techniques can also handle cases in which several moving parts must be moved simultaneously into different directions with different velocities. Specifically, this example illustrates the m-handed assembly problem: "Find a simultaneuos one-shot translation that separates the parts or show that no such motion exists"

Click on the image for an animated disassembly motion (537 kB).