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