Penetration distances and their applications to path planning

The proximal relationship of two objects is of interest for many reasons, e.g., the interference detection problem in robot motion planning. When the mathematical representations of two objects are separated, the natural measure of the proximal relationship is the shortest Euclidean distance. However, much less is known when the representations intersect. In this dissertation, one of the main foci is the characterization and computation of measures of the proximal relationship between two intersecting objects. We call these measures penetration distances.;A formal exposition of penetration distances and their mathematical properties is given. A penetration distance is defined by the least 'movement' needed to separate the two objects. In general, 'movement' involves both rotation and translation. Several ways of measuring the degree of rotation and translation are introduced and each yields a different definition of penetration distance. In the special case of convex objects, it is shown that the various penetration distances are the same and are determined from translational motion alone.;The above-mentioned penetration distances are difficult to compute. An important contribution of this thesis is the development of a new penetration distance based on ideas of 'growing' the mathematical representations of objects. It is called the growth distance and can be computed easily for a pair of convex objects. The mathematical properties and computational aspects of the growth distance are developed at length. For instance, its relationship to the other penetration distances is determined. When two objects are separated, the growth distance is also a measure of separation.;An important application of the growth distance is to path finding for robotic systems in the presence of obstacles. Our approach is to convert the path finding problem into an optimization problem. The objective is to minimize the 'amount' of collision along the path. This novel approach involves searching among collision paths. Problems unique to this formulation are discussed. Our approach has several advantages over existing approaches and has performed well in several examples.