Considers fast algorithms for computing the Euclidean distance between objects that are modeled by convex polytopes in three-dimensional space. The algorithms, designated by RGJK, are modifications of the Gilbert-Johnson-Keerthi algorithm that follow the scheme originated by Cameron (1997). Each polytope is represented by its vertices and a list of adjacent vertices for each vertex. When the algorithms are appropriately applied to a pair of objects that have small incremental motions, they share the advantage of the closest-feature algorithm introduced by Lin and Canny (1991): computational time is very small and does not depend significantly on the total number of object vertices. However, when the objects contain complex vertices or faces, the time can increase drastically. Reasons for this problem are analyzed and algorithmic fixes for them are given. Other contributions to algorithmic performance include a procedure for reducing computational time in the presence of collisions. Comprehensive numerical experiments illuminate the dependence of computational time on algorithmic details, object complexity, and the size of incremental motions. The experiments include direct comparisons of RGJK with the closest-feature algorithms of Lin and Canny and of Mirtich (1998).

This paper introduces a novel heuristic roadmap method for path planning, one that is inspired by the Voronoi diagram concept, but easily applicable to general configuration spaces. The roadmap is formed by connecting the local maxima of a clearance function which is defined using distance functions. Reaching the roadmap from any free configuration is achieved by applying the continuous active-set optimization algorithm to the maximization of the clearance function. Preliminary experiments with the new roadmap algorithm point to its potential utility in solving practical path planning problems.

An algorithm is presented for computing the Euclidean distance between a pair of objects represented by convex polytopes in three dimensional space. It is a fast version of the well known algorithm by Gilbert, Johnson and Keerthi (1988) in which the polytopes are characterized by their vertices. The improvement in speed comes from the inclusion of additional structural information on the objects; for each vertex there is a list of adjacent vertices. No other information or preprocessing of data is needed. Following Cameron, the adjacency structures are used to greatly reduce the number of inner product evaluations needed to compute the polytope support functions used in the original Gilbert-Johnson-Keerthi algorithm. When the algorithm is applied to a pair of objects that move incrementally along smooth paths, it shares the advantage of the incremental distance algorithm introduced by Lin and Canny (1991). Algorithmic details and performance issues are developed fully. Computational experiments provide quantitative data on the effects of object complexity and the size of incremental object motions.

Quantitative measures for the separation and penetration of two convex objects are formulated, These measures, called separation and penetration growth distances, are closely related to traditional translational distance measures and share many of their desirable properties. The solution of a single optimization problem yields both the separation and penetration distances. For 3D polytopes the optimization problem is a linear program in four variables whose asymptotic computational time is O(m), where m is the number of linear inequalities required to specify the two polytopes. This equals or far betters the known times required to compute translational distances: O(m) for separation and 0(m/sup 2/ log m) for penetration. When the positioning of the two objects depends on configuration variables, the partial derivatives of the growth distances with respect to the configuration variables exist almost everywhere. Derivatives of the penetration growth distance can be used to construct motions which separate the objects. An application to path finding is described.

New quantitative measures for the separation and penetration of two convex objects are formulated. These measures, called separation and penetration growth distances, are closely related to traditional distance measures and share many of their desirable properties. The solution of a single optimization problem yields both the separation and penetration distances. For polytopal objects the optimization problem is a simple linear program whose computational time is O(m), where m is the number of linear inequalities required to specify the two polytopes. Numerical experiments with three dimensional polytopes demonstrate that the growth distances can be computed more rapidly than the traditional distances with a large advantage in the case of penetration distances.>

An algorithmic approach to path finding is considered for a general class of robotic systems. The basic idea is to formulate an optimization problem over a family of continuous paths which satisfy the specified end conditions and possess robot-obstacle collisions. The cost to be minimized depends on the penetration growth distance, a new measure for the depth of intersection between a pair of object models. The growth distance and its derivatives with respect to configuration variables describing the orientation and position of the objects can be computed quickly. This is a key factor in attaining acceptable computational times. Variations of the initial strategy, which improve computational efficiency and reliability, are discussed. Significant reductions in computational time are easily obtained by parallel processing.>

A methodology for computing the distance between objects in three-dimensional space is presented. The convex polytope is replaced by a general convex set, avoiding the errors caused by the usual polytope approximations and actually reducing the overall computational time. The basic algorithm is a simple extension of the polytope distance algorithm described by E.G. Gilbert et al. (1988). It utilizes the support mappings of the sets representing the objects. A calculus for evaluating these mappings that allows the extended algorithm to be applied to a rich family of nonpolytopal objects is presented. While the convergence of the algorithm is not finite, it is fast and an effective stopping condition that guarantees the accuracy of the numerical solution is available. Extensive numerical experiments support the claimed efficiency.>

A methodology for computing the distance between smooth objects in three-dimensional space is presented. The convex polytope, which is the basic solid modeling tool of prior developments, is replaced by a general convex set. This permits the direct treatment of objects with curved surfaces, eliminating the errors caused by polytope approximations. The computational procedure is a simple extension of the efficient distance algorithm described by E.G. Gilbert et al. (1988). While the convergence of the algorithm is not finite, it is fast and an effective stopping condition is available. Procedures for treating a rich family of smooth objects are given. Extensive numerical experiments support the claimed efficiency.>

Iterative algorithms for detecting the collision of convex objects whose motion is characterized by a path in configuration space are described. They use as an essential substep the computation of the distance between the two objects. When the objects are polytopes in either two-dimensional or three-dimensional space, an algorithm is given which terminates in a finite number of iterations. It either determines that no collision occurs or locates the first collision point on the path. For practical problems it appears that the computational time is short and grows only linearly in the total number of vertices of the two polytopes. Numerical examples are presented.>

An algorithm for computing the Euclidean distance between a pair of convex sets in R/sup m/ is described. Extensive numerical experience with a broad family of polytopes in R/sup 3/ shows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which makes its application in a variety of robotics problems attractive. These features are discussed and an example of collision detection is given.>

An efficient and reliable algorithm for computing the Euclidean distance between a pair of convex sets in Rmdescribed. Extensive numerical experience with a broad family of polytopes in Rsshows that the computational cost is approximately linear in the total number of vertices specifying the two polytopes. The algorithm has special features which make its application in a variety of robotics problems attractive. These are discussed and an example of collision detection is given.

An approach to robotic path planning, which allows optimization of useful performance indices in the presence of obstacles, is given. The main idea is to express obstacle avoidance in terms of the distances between potentially colliding parts. Mathematical properties of the distance functions are studied and it is seen that various types of derivatives of the distance functions are easily characterized. The results lead to the formulation of path planning problems as problems in optimal control and suggest numerical procedures for their solution. A simple numerical example involving a three-degree-of-freedom Cartesian manipulator is described.

A control problem involving a mechanical system with generalized coordinatesq∈Rmis considered. The error in tracking a desired inputyd∈Rpise=E(q,yd)∈Rm. IfEsatisfies simple conditions, it leads to a nonlinear control law that assurese(t)→0 ast→∞. The law is robust in that small changes in it do not produce large steady-state errors or loss of stability. In this theory a unified framework is presented for treating a number of problems in the control of mechanical manipulators.

Various analytic procedures have been proposed for minimum integral-square-error approximation of prescribed linear systems; however, they often involve computational difficulties. In the procedure developed in this paper, a group of N linear approximating systems with orthonormal impulse responses øn(t) are realized by operational amplifier circuits. When h(-t) forces the systems (h(t) is the impulse response of the prescribed system) it is found that their outputs at t = 0 are an, the coefficients in {see the Equation in PDF File} the approximate impulse response. The following points relative to the approximation procedure are developed: constrained and weighted integral-square-error approximations, derivation and realization of orthonormal functions, physical realization of h*(t), evaluation of error h(t)-h*(t), and analysis of computer errors. Several approximation examples are given.

A method of generating sine and cosine functions in analog computers by means of multiplier elements and integrators is discussed. Static accuracy of the method is analyzed and found to be essentially equal to the accuracy of the multipliers employed. The system accepts dθ/dt as the input and generates output voltages of sinθ and cos θ. Amplitude-stabilizing loops are employed to maintain sin2θ+cos2θ = 1. Advantages of the method include representation of unlimited range in angles, dynamic capabilities far beyond that of the multipliers alone, and possibility of employing electronic multipliers. The method has been successfully used to compute Euler angles in analog computer solutions of the three-dimensional flight equations.