# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.4 Particle Swarm Optimization
[65] proposed a system for automatically planning collision-free four-dimensional trajectories; the system is based on the Particle Swarm Optimization (PSO) algorithm of axis-aligned minimum bounding boxes and stochastic global optimization techniques, and it uses a strategy to quickly calculate the initial point, solving the problems of high computational overhead and slow convergence in evolutionary algorithms. [PERSON] et al. [66] proposed a cooperative competitive Particle Swarm Optimization (PSO) algorithm, which uses two-stage optimization to reduce the dimensionality of the problem and generates the optimal collaborative trajectory for multiple UAVs in three-dimensional space, solving the trajectory planning problem for UAV formation in cooperative and competitive situations. [PERSON] et al. [67] designed an improved PSO algorithm (IPSO), which used a binary value coding matrix and adaptive inertial weight adjustment strategy to generate a feasible trajectory for multiple UAVs, solving the decision-making problem of a multi-UAVs cooperative reconnaissance mission. In this paper, [PERSON] et al. [68] proposed a new trajectory planning method for multiple UAVs by introducing a variable neighborhood drop (VND)-enhanced genetic Particle Swarm Optimization algorithm to optimize flight trajectory with minimum span and solve the problem of limited flight endurance of UAVs in agricultural applications. [PERSON] et al. [69] proposed an angle-encoded Particle Swarm Optimization method, which realized the communication between UAVs through the Internet of Things board, minimized the cost function of multiple constraints including the shortest trajectory and the safe operation of UAVs, and found a feasible and frictionless trajectory for the whole formation. The trajectory planning problem of UAV formation in building infrastructure inspection is solved. [PERSON] et al. [70] proposed a trajectory planning method based on Dubins trajectory and the Particle Swarm Optimization (PSO) algorithm, using Dubins trajectory to reduce the dimensionality of the aircraft kinematics model. Then, using the Particle Swarm Optimization algorithm to optimize the trajectory after the formation reconstruction, it solves the trajectory planning problem when the task adjustment or the environment changes in the UAV formation. [PERSON] et al. [71] proposed an improved Particle Swarm Optimization method (ODPSO) based on orthogonal design and formulated a point sequence strategy to redefine the objective function. They searched for each the three-dimensional trajectory points within the time step, used the relative particle directivity to improve the search accuracy, and solved the trajectory planning problem of the UAV formation under the conditions of threats and terrain constraints. [PERSON] et al. [72] proposed a 3D trajectory planning algorithm for UAV formation based on Comprehensive Improved Particle Swarm Optimization (CIPSO). This method uses chaos-based logical mapping to improve the initial distribution of particles, designs commonly used constant acceleration coefficients and maximum speeds to adapt to linear change coefficients, and uses a mutation strategy in which the desired particles replace undesired particles, solving the terrain and threat constraints problems of UAV formation trajectory planning under the condition. [PERSON] et al. [73] proposed a 4D coordinated trajectory planning algorithm for multiple UAVs, which constructed the solution boundary of the search space and the distance to the destination based on the properties of all threats, and then designed a spatial refinement voting mechanism that solves the problems of local optimum and slow convergence of the standard Particle Swarm Optimization algorithm. [PERSON] et al. [74] proposed a Distributed Cooperative Particle Swarm Optimization (DCPSO) algorithm with an elite-preserving strategy, which parameterizes the trajectory using a Pythagorean Heatmap (PH) curve.