Solving spherical multi-aircraft path planning problem using self-adaptive update strategy differential evolution algorithm
Lun Zhu, Yongquan Zhou, Zhou Guo, Qifang Luo, Yuanfei Wei
Abstract
The path planning problem is a class of NP-hard problems, and in recent years, researchers have endeavored to address path planning issues in various environments. This paper addresses, for the first time, a spherical multi-aircraft path planning problem (SMAPPP), which is proposed to simulate future research on path planning for spacecraft exploring extraterrestrial planets or missile trajectories. The differential evolution (DE) algorithm, a classic meta-heuristic algorithm, does not yield satisfactory results when applied to the SMAPPP. Constrained by the imbalance between the global and local search capabilities of DE, this paper proposes a self-adaptive update strategy differential evolution algorithm (SaUSDE) to enhance its performance in solving global optimization problems. The SaUSDE algorithm incorporates four distinct DE variant strategies. Among these strategies, the algorithm adaptively and frequently selects the more suitable strategy for different problems, thereby effectively balancing global and local search capabilities. To validate the algorithm's efficacy, tests were conducted on the CEC2017 benchmark functions at 10D, 30D, 50D, and 100D, as well as 48 real-world constrained optimization problems from CEC2020. Based on these problems, our algorithm was compared with several advanced DE variants and a few algorithms that won the CEC2020 competition. Compared with these advanced algorithms, the proposed algorithm generally achieved superior results. Finally, SaUSDE was applied to a simulated spherical multi-aircraft path planning problem. In scenarios involving 3 to 12 aircraft, the SaUSDE algorithm effectively avoided collisions between each aircraft and certain no-fly zones (static obstacles) as well as unknown flying objects (dynamic obstacles). The source code for the algorithm is available at: https://ww2.mathworks.cn/matlabcentral/fileexchange/173495-sausde