Path Planning for Single Unmanned Aerial Vehicle by Separately Evolving Waypoints

Evolutionary algorithm-based unmanned aerial vehicle (UAV) path planners have been extensively studied for their effectiveness and flexibility. However, they still suffer from a drawback that the high-quality waypoints in previous candidate paths can hardly be exploited for further evolution, since they regard all the waypoints of a path as an integrated individual. Due to this drawback, the previous planners usually fail when encountering lots of obstacles. In this paper, a new idea of separately evaluating and evolving waypoints is presented to solve this problem. Concretely, the original objective and constraint functions of UAVs path planning are decomposed into a set of new evaluation functions, with which waypoints on a path can be evaluated separately. The new evaluation functions allow waypoints on a path to be evolved separately and, thus, high-quality waypoints can be better exploited. On this basis, the waypoints are encoded in a rotated coordinate system with an external restriction and evolved with JADE, a state-of-the-art variant of the differential evolution algorithm. To test the capabilities of the new planner on planning obstacle-free paths, five scenarios with increasing numbers of obstacles are constructed. Three existing planners and four variants of the proposed planner are compared to assess the effectiveness and efficiency of the proposed planner. The results demonstrate the superiority of the proposed planner and the idea of separate evolution.