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

Incremental construction of 3-dimensional C-Space cells Configuration space is a well-known concept in robotics. The set of forbidden configurations of two or more objects (placements with interpenetration) is called configuration obstacle. For two polyhedra that are only allowed to translate but not rotate the configuration obstacle is also a polyhedron which can be described mathematically by the Minkowski difference of the two polyhedra. However, in most practical applications a description of free space rather than blocked space is required. Our new algorithm avoids computing parts of the configuration obstacle that are not visible from the current placement of the two polyhedra. Instead, a convex cell in free configuration space that contains the given configuration is constructed incrementally. The algorithm fits well into the paradigm of incremental c-space construction for General Translational Assembly Planning and can be used as a basis for deriving the basic pairwise constraints from realistic part models.

Example: (Click here for an animation of another example)
The two parts below consist of 300 and 588 surface triangles. Thus 176400 pairs of triangles must be prevented from interpenetration. By a sequence of hierarchical filters we can substantially reduce the number of pairs that must actually be considered for a specific class of configurations.

We consider the following configuration (the second part is shown transparent):

The next figure shows the computed cell that is a subset of free C-Space. It contains the origin which represents the given configuration. The cell is defined by the intersection of 17 halfspaces. 16 of them form a channel parallel to the z-axis and one delimits it in negative z direction. The program directly computes the set of defining halfspace-inequalities in the form ax + by + cz >= d which can be used for further analysis (e.g. C-Space composition, see Testing for Removability for more details on this topic).

The cell is unbounded in positive z direction which means that the second part can translate to infinity along the positive z axis. Along the negative z-axis, however, there is only a finite volume of free C-Space since the parts will collide during a translation of the second part in this direction.

The channel has non-zero diameter which indicates play between the parts in x- and y-directions.

The next figure shows a cross section of the cell at some positive z-value.

In the example we can additionally compute a convex cone of free directions. Each vector in the cone specifies a direction in which the second part can be translated arbitrarily far away from the first part. The next two figures show the cell from the previous figures and the computed cone of allowed translations to infinity. Note that the set of all allowed directions need not be convex for all configurations (consider a placement in which the two parts can be separated by a plane).