A Generalized 3-D Path Planning Method for Robots Using Genetic Algorithm with An Adaptive Evolution Process

摘要

Traditionally, path planning for robots is modeled as optimization problems. One of the most commonly used optimization strategies is Genetic Algorithm (GA) since it always guarantees a nearly shortest path even a global path can not be obtained within a reasonable time. In fact, the performance enhancement of GA is still an open topic for researchers by designing different genetic operators. In addition to this, we propose a new criterion for the selection of genetic operators during evolution in order to further facilitate the searching efficiency. In this paper, we propose a generalized 3-D path planning method for robots using GA with an adaptive evolution process. Based on the framework of traditional GA, we first introduce a new genetic operator, called Bind-NN which randomly divides and recombines an elitist chromosome based on nearest neighbor. We also show that by choosing the fitness variance of the shortest path in last generations as a guidance in selecting genetic operators during evolution, the search efficiency can be significantly improved, thus proposing a genetic operators selection scheme. In the latter part of this paper, we present the algorithm evaluation by stimulating a sample path planning problem on a structural frame. With the use of the proposed genetic operator and selection scheme, experimental results show a significant improvement in terms of search effectiveness and efficiency.