Multi-dimensional path planning using evolutionary computation

Abstract

The paper describes a flexible and efficient multi-dimensional path planning algorithm based on evolutionary computation concepts. A novel iterative multi-resolution path representation is used as a basis for the GA coding. The use of a multi-resolution path representation can reduce the expected search length for the path planning problem. If a successful path is found early in the search hierarchy (at a low level of resolution), then further expansion of that portion of the path search is not necessary. This advantage is mapped into the encoded search space and adjusts the string length accordingly. The algorithm is flexible; it handles multi-dimensional path planning problems, accommodates different optimization criteria and changes in these criteria, and it utilizes domain specific knowledge for making decisions. In the evolutionary path planner, the individual candidates are evaluated with respect to the workspace so that computation of the configuration space is not required. The algorithm can be applied for planning paths for mobile robots, assembly, piano-movers problems and articulated manipulators. The effectiveness of the algorithm is demonstrated on a number of multi-dimensional path planning problems.