TY - JOUR
T1 - Detecting geometric infeasibility
AU - Schweikard, Achim
AU - Schwarzer, Fabian
PY - 1998/1/1
Y1 - 1998/1/1
N2 - The problem of deciding whether one or more objects can be removed from a set of other planar or spatial objects arises in assembly planning, computer-aided design, robotics and pharmaceutical drug design. In this context, it will be shown that certain D-dimensional arrangements of hyperplanes can be analyzed in the following way: only a single connected component is traversed, and the arrangement is analyzed as an arrangement of surface patches rather than full hyperplanes. In special cases, this reduction allows for polynomial time bounds, even if the boundary of the set of reachable placements has exponential complexity. The described techniques provide the basis for an exact method for translational assembly planning with many degrees of freedom. Experiments obtained with an implementation suggest that problems with random planning methods, which are related to the choice of internal parameters can be avoided with this exact method. In addition, unsolvability can be established and the program can be applied to the verification of symbolic rules describing the geometry.
AB - The problem of deciding whether one or more objects can be removed from a set of other planar or spatial objects arises in assembly planning, computer-aided design, robotics and pharmaceutical drug design. In this context, it will be shown that certain D-dimensional arrangements of hyperplanes can be analyzed in the following way: only a single connected component is traversed, and the arrangement is analyzed as an arrangement of surface patches rather than full hyperplanes. In special cases, this reduction allows for polynomial time bounds, even if the boundary of the set of reachable placements has exponential complexity. The described techniques provide the basis for an exact method for translational assembly planning with many degrees of freedom. Experiments obtained with an implementation suggest that problems with random planning methods, which are related to the choice of internal parameters can be avoided with this exact method. In addition, unsolvability can be established and the program can be applied to the verification of symbolic rules describing the geometry.
UR - http://www.scopus.com/inward/record.url?scp=0032179623&partnerID=8YFLogxK
U2 - 10.1016/S0004-3702(98)00076-9
DO - 10.1016/S0004-3702(98)00076-9
M3 - Journal articles
AN - SCOPUS:0032179623
SN - 0004-3702
VL - 105
SP - 139
EP - 159
JO - Artificial Intelligence
JF - Artificial Intelligence
IS - 1-2
ER -