(1) Institut fur Informatik, Technische Universitat Munchen, Germany
(2) School of Computer Science and Engineering, The Hebrew University of Jerusalem, Israel

We address the problem of efficiently testing for linear unboundedness and its applications to translational assembly planning. We describe a new algorithm that performs the test by solving a single homogeneous system of equations followed by a single linear feasibility test. We show that testing for unboundedness is computationally at least as hard as these two subproblems. The new algorithm is the fastest known algorithm and is practical. We then present a framework for general translational assembly planning based on linear constraints. We show that $m$-handed assembly planning can be reduced to testing for unboundedness, and present the first polynomial-time algorithm for $m$-handed assembly of polygonal part assemblies with no initially separated pairs of parts. For the general translational assembly planning problem, we present a new output-sensitive algorithm that uses unboundedness testing and a cell reduction technique to significantly increase the search efficiency. Experimental results of our implementation on a variety of planar and spatial assemblies demonstrate the practicality of the algorithms.

Keywords: linear programming, unboundedness testing, translational assembly planning, motion planning.

Int. Journal of Robotics Research 19(9), September 2000, pp 817-834.