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

Testing for Removability (Joint work with Leo Joskowicz, Hebrew University, Jerusalem)

Description

The problem of finding a sequence of motions for removing one or more objects from a given set of objects arises in assembly planning, robotics, computer-aided design and pharmaceutical drug design. Given a set of parts (polygons or polyhedra), decide whether there is a motion (a sequence of arbitrary translations) for separating these parts. Conversely if you think a given set of parts interlock, output a proof that they indeed interlock.

We apply the analyis of linear constaint sets to this problem. The algorithms are based on incremental and efficient construction of cells in a high-dimensional arrangement of hyperplanes.

Examples

The following simple examples illustrate the translational removability problem. Given a set of parts (polygons or polyhedra), decide whether there is a motion (a sequence of arbitrary translations) for separating these parts. Conversely if you think a given set of polygons interlock, output a proof that they indeed interlock.

The animations show a series of problem examples, which have been solved by our program. Click on the images for animation applets.

1. In each of the three cases the goal is to remove one of the two boxes from the fixed container. The first two problems are feasible, the third is infeasible.

2. Here, the goal is to remove the small box from the fixed container. The bolt is restricted to move up and down in a limited range by the fixed black parts. If the bolt is too long, the problem is infeasible, which is demonstrated in the animations.

3. This problem has more degrees of freedom than the others. Two parts must move simultaneously into different directions and change directions several times to allow for separation.

4. ### Click here for more examples...

MPEG videos are available for some examples:
• Video.1 The parts can be separated. The computed motion and intermediate positions checked by the program are shown in the video. Compting time 12 seconds on a HP 700 Unix workstation. Video.1(218 KB).
• Video.2 The parts are similar to those in Example.1. In this case there is not removal motion. Compting time for finding a proof of infeasibility: 11 seconds. Video.2(326 KB).
• Video.3 (166 KB).
• Video.4 (105 KB).
• Video.5 (67 KB).
• Video.6 (59 KB).
• Video.7 (54 KB).