Path Planning for Large-scale UAV Formation Based on Improved SA-APF Algorithm

An improved simulated annealing-artificial potential field (SA-APF) algorithm is proposed to solve the problem of large-scale dense unmanned aerial vehicle (UAV) formation path planning in three-dimensional space. First, the artificial potential field (APF) method is extended to three dimensions and combined with the kinematics of the drone to constrain the step length, a path that meets the kinematics of the drone is generated and all UAVs can reach the target synchronously. By designing a double-layer repulsive potential field, establishing a collision prediction and obstacle avoidance mechanism, the defects of the shock path of the traditional APF are overcome. In order to reduce the computational complexity of dense formation path planning, the simulated annealing (SA) algorithm is used to optimize the distance cost, and the optimal allocation is calculated to replace the initial task allocation for path planning. Finally, the improved SA-APF algorithm is used for simulations and flight experiments on 1,000 UAVs. The results show that the path generated by SA-APF is smoother and has lower complexity. The algorithm can greatly reduce resource consumption in actual application.