An Initialization Method of Genetic Algorithm for Robot Path Planning Based on Directed Acyclic Graph and Effective Obstacles*

Genetic algorithm (GA) has received widespread attention in robot path planning with its advantages of parallel computing. The quality of the initial population is a key factor in improving the efficiency of GA, so related research is required. This paper proposes a novel initialization method, which is characterized by two directed acyclic graphs (DAGs) and effective obstacles. Each DAG generates half of the initial population. Besides, an improved GA is proposed, combining the initialization method with existing excellent operators. To verify the performance of the proposed methods, two kinds of simulation experiments are carried out. One is to compare the proposed initialization method with the other three initialization methods, and the other is to compare the proposed GA with four other state-of-the-art improved GAs. Simulation results verify that the proposed methods outperform the other methods, not only in terms of convergence rate and optimal path length at convergence but also in the quality of the initial population.