New algorithms for detecting collision between moving objects

A family of iterative algorithms is developed for detecting the collision of two convex objects, whose motion is characterized by a specified continuous path in a suitable configuration space. One of the main motivations of this work is its application to collision-free motion synthesis for industrial manipulators.; It is proved that the algorithms report no collision in a finite number of steps, or that they generate a sequence of points along the path converging upward to the first collision point. When the objects are polytopes in either two or three dimensional space, a special algorithm is given which terminates in a finite number of iterations. The proof of finite convergence, which is quite lengthy, represents one of the major contributions of the dissertation.; The algorithms compute at each iteration the Euclidean distance between the objects. If the distance is positive, the objects do not intersect and are, in fact, separated by a slab of thickness equal to the distance. This means further collision-free motion along the path is possible: the motion can be continued until the thickness of the separating slab shrinks to zero. The algorithmic process consists of successive steps of this type. The normal to the defining hyperplanes of the separating slab is adjusted as the objects continue to move, so that the convergence of the sequence is either fast or finite and, at the same time, the computational effort of each iteration step is reduced.; The slab shrinks to zero at the smallest root of a family of smooth functions which are defined on an interval of real numbers. When the objects are polytopes and they have either a translational motion or a relative motion which is rotational, the roots of the functions are given by simple formulas, thereby simplifying the determination of the least root. Otherwise, a special root finding algorithm is necessary. Such an algorithm is described. It uses adaptively chosen polynomial fits and has proved to be efficient and highly reliable.; While there is no theoretical bound on the computational complexity of the collision detection algorithms, extensive numerical experiments show that they are fast. In the case of moving polytopes, the computational time is proportional to {dollar}Msb1{dollar} + {dollar}Msb2{dollar} where {dollar}Msb1{dollar} and {dollar}Msb2{dollar} are the number of vertices in each of the polytopes. Previously described algorithms apply to less general problems and have a computational time proportional to {dollar}Msb1{dollar} {dollar}cdot{dollar} {dollar}Msb2{dollar}.