基于点集群体的进化算法求解复杂3D环境中无人机路径规划问题

UAV Path Planning Based on Point Set Evolution in 3D Complex Environment

摘要: 随着无人机应用的日益广泛，对无人机路径规划的需求也越来越大，但大多数现有的基于进化算法的路径规划将整条路径作为一个个体进行优化，这可能导致一些潜在的路径点被忽视。此外，由于3D环境难以网格化，传统的基于网格的智能搜索算法，如蚁群算法等，在复杂3D环境中难以有效解决无人机路径规划问题。鉴于此，本文提出一种基于点集进化的无人机路径规划算法，该算法将每个控制点作为一个个体，根据路径的有序性设计了一种高效的杂交算子来生成新的控制点，基于控制点集使用经典的Dijkstra算法搜索并构建路径，从而计算每个控制点的适应度用来更新控制点集。该算法将经典路径规划算法与进化算法相结合，既具有经典算法的高搜索效率，又具有进化算法的全局搜索能力。实验结果表明，所提算法在解决复杂3D环境中的无人机路径规划问题时表现良好且稳定。

Abstract: With the increasing application of Unmanned Aerial Vehicle (UAV), there is a growing demand for UAV path planning. However, most existing path planning based on evolutionary algorithm opti-mize the whole path as an individual, which causes some potential waypoints are ignored. Addi-tionally, traditional algorithms, e.g. Ant Colony Optimization (ACO) struggle to effectively solve UAV path planning in complex 3D environments, where grid-based approaches are difficult to implement. Therefore, this paper proposes a UAV path planning based on Point Set Evolution (PSEA). In the proposed algorithm, each control point is treated as an individual, and Dijkstra algorithm is utilized to search and construct paths, thus calculating the fitness value for each control point. Fur-thermore, an efficient crossover operator is designed based on the order of the paths, and Evolu-tionary algorithm is employed to update the set of control points. The proposed algorithm features the efficiency of classical path planning algorithms with the global search capability of Evolutionary algorithm. The experiment results demonstrate that the proposed PSEA performs well and remains stable in solving UAV path planning in complex 3D environment.