Robot path planning with penetration growth distance

Abstract

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 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. Strategies that improve the efficiency and reliability of picking the initial paths are considered. Significant reductions in computational time are easily obtained by parallel processing. Numerical examples, including a 6 degrees-of-freedom robot moving in a three-dimensional work space, substantiate the approach. © 1998 John Wiley & Sons, Inc. 15: 57–74, 1998