A Proximity Metric for Continuum Path Planning

Abstract

The problem of planning motions of robot manipulators and similar mechanical devices in the presence of obstacles is one of keen interest to the artificial intelligence community. Most of the algorithms previously reported for solving such problems have been combinatorial algorithms, which work by partitioning the problem domain continuum into a finite set of equivalence classes, and applying combinatorial search algorithms to plan transitions among them. However, the few continuum algorithms that have been reported, which do not rely on such a partitioning, have shown greater promise when applied to problems of complexity equivalent to that of planning a true manipulator motion. This is true even though the heuristics employed in these continuum algorithms have been extremely simple in nature. A significant barrier to the development of more refined heuristics for use in continum algorithms is the uncertainty over how to characterise the proximal relationship between rigid bodies. In this paper, a new measurement function is reported which permits such characterisation. An introduction is made to a new type of path planning algorithm which this function makes possible, which promises to significantly increase the capabilities of continuum path planning software.