An Improved Multi-Objective Evolutionary Algorithm for Grid Map Path Planning

Multi-objective path planning on large-scale grid maps is characterized by a large number of nodes and multiple targets. Existing algorithms struggle to balance the speed and quality of solving the Pareto front (PF). Therefore, studying efficient optimization algorithms based on the PF has certain theoretical significance. First, a weighted graph modeling method based on cost vector is proposed, and optimization algorithms for solving large-scale problems are studied accordingly, which significantly saves time and costs compared with graph search algorithms. Then, to address the issue of low quality of the PF solutions, an improved multi-objective evolutionary algorithm is proposed, which includes a new initialization strategy. Individual and environment selection strategies are designed based on the concepts of angle and shift-based density. These improvements take both population diversity and convergence into account, thereby improving the solving efficiency. Finally, comparative simulation experiments are conducted to verify the effectiveness of the improved algorithm.