Efficiently testing for unboundedness and m-handed assembly

Fabian Schwarzer, Florian Bieberbach, Achim Schweikard, Leo Joskowicz

Abstract

We address the problem of efficiently determining if the intersection of a given set of d-dimensional half-spaces is unbounded. It is shown that detecting unboundedness can be reduced to a single linear range computation followed by a single linear feasibility test. In contrast, detecting unboundedness is at least as hard as linear feasibility testing and maximization. Our analysis suggests that algorithms for establishing linear unboundedness can be used as a basis of simple and practical algorithms in motion planning, insertability analysis and assembly planning. We show that m-handed assembly planning can be reduced to testing for unboundedness. A valid motion sequence can be computed in polynomial time, if the parts are not already separated in their initial placement. No polynomial algorithms were previously known for this problem. We present experimental results obtained with an implementation of our algorithms.

OriginalspracheEnglisch
Seiten1164-1169
Seitenumfang6
DOIs
PublikationsstatusVeröffentlicht - 01.12.1998
VeranstaltungProceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems - Victoria, Kanada
Dauer: 13.10.199817.10.1998
Konferenznummer: 49406

Tagung, Konferenz, Kongress

Tagung, Konferenz, KongressProceedings of the 1998 IEEE/RSJ International Conference on Intelligent Robots and Systems
Land/GebietKanada
OrtVictoria
Zeitraum13.10.9817.10.98

Fingerprint

Untersuchen Sie die Forschungsthemen von „Efficiently testing for unboundedness and m-handed assembly“. Zusammen bilden sie einen einzigartigen Fingerprint.

Zitieren