# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.4 Particle Swarm Optimization
Then, evolutionary theory is used to improve the Particle Swarm Optimization algorithm to generate a flyable and safe trajectory for each UAV, which solves the kinematic constraint problem of multi-UAV trajectory planning. [PERSON] and [PERSON] [75] proposed an algorithm based on Dubins trajectory and Coevolutionary Particle Swarm Optimization (CCPSO). This algorithm determines the initial reference trajectory by the Dubins trajectory and then converts the time co-constraint into an equal trajectory length, and the trajectory parameters are optimized by CCPSO, which solves the problem of multi-UAV collaborative trajectory planning. [PERSON] et al. [76] proposed a new hybrid Particle Swarm Optimization and improved symbiotic search algorithm (HIPSO-MSOS), which introduces a time-stamp segmentation (TSS) model and a multi-objective optimization function to simplify the cost. Using HIPSO-MSOS to generate feasible trajectories and then smoothing trajectories by cubic b-spline curves, the problem of coordinated trajectory planning for multiple UAVs in complex 3D environments is solved. [PERSON] et al. [77] proposed a trajectory planner based on the Particle Swarm Optimization (PSO) algorithm, which uses distributed full coverage and dynamic fitness function to generate the optimal trajectory and solves the problem of trajectory planning for multiple UAVs. [PERSON] et al. [78] proposed an improved Particle Swarm Optimization method, improved the optimization problem by using evolutionary computing technology, added parallel recombination into trajectory planning, and solved the problems of long processing time and non-optimal trajectory in the dynamic trajectory planning of UAV formation. [PERSON] et al. [79] proposed a Heterogeneous Adaptive Comprehensive Learning Dynamic Multi-population Particle Swarm Optimization algorithm (HACLDMS-PSO), which incorporated a population dynamic adjustment strategy, disturbance mechanism and adaptive learning probability mechanism into the Particle Swarm Optimization algorithm, which better solved the NP-hard problem in multi-UAV trajectory planning. [PERSON] et al. [80] proposed a tracking planning method based on multi-strategy improved symbiosis search (MSISOS); this method uses an adaptive strategy and interference strategy to assist the search trajectory and coordinates space-time through UAV information interaction layer constraints. Then, a distributed method is designed for formation trajectory planning, which solves the problems of poor accuracy and slow convergence in multi-UAV trajectory planning in complex battlefield environments. [PERSON] et al. [81] proposed a trajectory planning algorithm that combines gradient descent-based trajectory planning (GBPP) and Particle Swarm Optimization. The initial trajectory of the algorithm is defined as the input of GBPP, and the hierarchical concept is added to the Particle Swarm Optimization algorithm (HPSO) to generate a feasible trajectory, which solves the problem of long calculation time of the Genetic Algorithm and Particle Swarm Optimization algorithm. [PERSON] et al. [82] proposed a distributed hybrid Particle Swarm Optimization and differential evolution (DE) technique; this technique adds the nonlinear time-varying method to the Particle Swarm Optimization algorithm (NTVPSO) and adds the adaptive mechanism to the differential evolution (DE) evolution (ADE). Finally, it adopts the distributed method, uses NTVPSO-ADE to realize the collaborative trajectory planning of multiple UAVs, and solves the problem of difficult model establishment and large amount of calculation in formation trajectory planning. Table 4 summarizes the content of PSO algorithms in our review.