A Proximity Metric for Continuum Path Planning

Abstract

The problern of planning motions of robot manipulators and similar mechanical devices in the presence of obstacles is one of keen interest to the artificial intelligence co mmunity. Most of the algorithms previously reported for solving such problems have been combinatorial algo· rithms, whieb work by partitioning the problern domain continuum into a finite set of equivalence classes, and applying combinatorial search algorithms to plan transitions among them. However, the few continuum a/gorithma that have been reported, which do not rely on such a partitioning, have shown greater promise when applied to problems of comp le xity equivalent to that of planning a true manipulator motion. This is true even though the heuristics employed in these continuum algorithrns have heen extremely simple in nature. A significant barrier to the development of more refined heuristics for use in continuum algorithms is the uncertainty over how to characterize the proximal relationship between rigid bodies. In this paper, a new measurement function is reported which permits such charactcrization. An introduction is made to a new type of path planninr; algorithm which this function makes possible, wbich promises to significantly increase the capahililies of continuum path planning softwa.re.