This thesis addresses the problems of planning highly coordinated collision-free translational motions of multiple objects (general polygons or polyhedra) and finding sequences of translations that allow for the removal of one or more objects. These problems are known to be PSPACE-hard in general. Our main focus is therefore on the design and analysis of adaptive algorithms that can cope with practically relevant cases such as tightly interlaced placements. Exact and complete algorithms are important, for example in the field of computer aided mechanical assembly planning: a valid plan for separating a given placement of rigid non deformable objects (parts) can be reversed to assemble the individual components. Our algorithms are exact and complete and can prove in practical cases that no separating motions exist. We present our discussion within the uniform framework of the composite configuration space of multiple translating objects. The general dimension of this space, which is proportional to the number of parts, causes certain combinatorial problems that are treated in detail. First, we consider single simultaneous ('one-shot') translations. For the special case of a single moving subset of parts, a polynomial time algorithm was known before this work. However, it was not clear if the underlying principles could be generalized to obtain a polynomial time algorithm for more than a single moving subset. We show that the problem becomes NP-complete when two or more different directions of simultaneous translation are allowed. We analyze in detail under which conditions translational one-shot separability is NP-hard, and derive a new polynomial-time algorithm for separating placements of polygons in which no pair of parts is separated. For general instances of one-shot separability, we propose heuristic reductions on a high level of abstraction. Translational one-shot separability is closely related to high-dimensional linear unboundedness testing. We present a new efficient algorithm for linear unboundedness testing that consists of solving a single homogeneous system of equations followed by a single linear feasibility test. It is shown that our algorithm is optimal if optimal algorithms are used for these two main steps. Efficient unboundedness testing is also one of the keys to practical algorithms for general translational separability. In the context of the latter problem, arbitrary sequences of translations may be required to remove one or more parts. We propose opportunistic incremental algorithms that take advantage of the fact that for many practical instances, the set of feasible translations is quite constrained. The salient features of our algorithms are exact implicit convex cell decomposition of the composite configuration space, complete incremental expansion of a single connected component, and elimination of redundancies by cell defragmentation. We show that additional effective heuristic improvements can be formulated on a high level of abstraction, which makes them relevant for a whole variety of problem instances. The presented algorithms have been implemented and tested on several planar and spatial examples of differing complexity. Our experimental results confirm the practicality of the approach. Observed running times are dominated by the discrete number of reachable critical placements which are usually very limited in assembly planning applications. The algorithms are exact and complete. For several examples with many degrees of freedom, it was possible to compute a complete proof that no separating translations exist. Extensions of practical importance can be integrated directly into our implementation. These include linear tolerance models, parameters that permit small bounded overlap, and methods to identify features of parts that would have to be slightly modified to allow for overlap-free separation of otherwise non separable placements.
«
Login
BibTeX