Fast computation of minimum distance among convex three-dimensional objects

A major issue in robotic control is the avoidance of collisions with the workspace or with other active robots in the case of cooperative systems. Many control and motion planning methods use some form of distance metric to determine how close the manipulator is to its environment. As a result, rapid calculation of distances between robot components and workspace obstacles is crucial to efforts in on-line collision avoidance. While efficient methods exist, further refinement is always desirable.; The computation of distances between convex polyhedra in 3D space can be presented as a Quadratic Programming problem. The DQP3 (Distance via Quadratic Programming, 3D-specific) algorithm for computing the distance between convex polyhedra is presented, based on the primal active set QP algorithm. The DQP3 algorithm enhances the primal active set method by using geometric solutions to its core calculations, instead of generalized matrix methods. Several variants of the DQP3 algorithm are presented with relative timing information. Comparison to algorithms from the literature is also performed, with CPU times scaled according to the Unpack benchmark of the CPU used. The most detailed comparison is to Cameron's Enhanced GJK (Gilbert, Johnson and Keerthi) algorithm, running his code on the same test machine as the DQP3 code.; In addition to robot components that typically have a simple polyhedral representation, ellipsoid representations of objects are also of interest, partly because of their simplicity. Three different methods of handling the ellipsoid distance are presented: a simple point to ellipsoid iteration, the use of high-definition polyhedral models (with DQP3), and an iterative process for refining the polyhedral model only in the area of interest. Comparison to the scarce results from the literature is done, but the main comparison of interest is among the proposed methods, which showed the point to ellipsoid method to be the most reliable, although the iterative refinement technique shows promise.