Planning multiple paths with evolutionary speciation

This paper demonstrates a new approach to multidimensional path planning that is based on multiresolution path representation, where explicit configuration space computation is not required, and incorporates an evolutionary algorithm for solving the multimodal optimization problem, generating multiple alternative paths simultaneously. The multiresolution path representation reduces the expected search length for the path-planning problem and accordingly reduces the overall computational complexity. Resolution independent constraints due to obstacle proximity and path length are introduced into the evaluation function. The system can be applied for planning paths for mobile robots, assembly, and articulated manipulators. The resulting path-planning system has been evaluated on problems of two, three, four, and six degrees of freedom. The resulting paths are practical, consistent, and have acceptable execution times. The multipath algorithm is demonstrated on a number of 2D path-planning problems.

I. Introduction

Creating autonomous systems is of great interest in a wide variety of application domains such as manufacturing, space exploration, Fig. 1. 2-D path-planning example. Diagram shows a collision-free path from initial position of the robot to the goal position. construction, undersea exploration, and medical surgery. Developing such complex autonomous systems requires research in areas of control, automated reasoning, and perception. Current and future research efforts in this area will continue to strive for increased robustness and flexibility, better reliability, and greater autonomy. The path-planning problem arises in attempts to develop more autonomous robotic systems. This capability is necessary for autonomous robots since it is essential for a robot to accomplish tasks by moving in the real world. This requires the ability to plan a path. The path-planning problem involves determining if a continuous and obstacle-avoiding sequence of positions and orientations of the robot exists from the initial position and orientation of the robot to the goal position and orientation and if so, to specify such a path. Fig. 1 shows a simple two-dimensional (2-D) path-planning example. The path-planning problem is computationally very expensive. In fact, it is an NP-hard problem [1]. An upper bound on the complexity of the degree-of-freedom path-planning problem is O(), which means that the complexity of the path-planning problem grows exponentially with the number of degrees of freedom [1] [2] [3]. Thus, researchers are actively seeking satisfactory, computationally efficient solutions to the path-planning problem.