Evolutionary path planning using multiresolution path representation

Abstract

A multiresolution representation of robot paths is introduced as a basis for path planning where explicit configuration-space computation is not feasible. This multiresolution representation is computationally efficient since the path representation depends on the complexity of the problem space-therefore, a simple path will be found quickly if one exists. An evolutionary algorithm uses a variable-length string to encode the path, and this length is systematically varied as the evolutionary search proceeds. Resolution independent constraints due to obstacle proximity, and path length are introduced into the evolutionary evaluation function. The resulting algorithm has been evaluated on problems of 2, 3, 4, and 6 degrees of freedom, including mobile articulated robots and six degree-of-freedom assembly trajectory problems. The resulting paths are practical and consistent with acceptable execution times.