# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.3 Evolutionary Algorithm
[52] proposed a Genetic Algorithm for the trajectory planning of multiple UAVs in message ferry networks. The Genetic Algorithm is used to create node clusters, and then, node scheduling in each cluster is defined according to the traffic between nodes and the message load in nodes. The problem of the average message passing delay of traditional mTSP schemes is solved. [PERSON] et al. [53] established a global optimization model that takes into account UAVs with various sensors located in different bases and multiple constraints, converts the time into an easily measurable way, and then uses the Genetic Algorithm analysis to solve the optimal detection track problem in the case of a multi-base. [PERSON] et al. [54] proposed a coordination optimization algorithm combining the Genetic Algorithm and clustering algorithm, using the task time constraint method to determine the number of UAVs required. They find the optimal trajectory for each UAV, solving the problem of multi-task assignment and trajectory planning of multiple UAVs. [PERSON] et al. [55] proposed an improved trajectory planning algorithm based on GA. On the basis of a Genetic Algorithm, the optimal trajectory is obtained by the K-means target clustering algorithm and multi-chromosomal Genetic Algorithm, which solves the trajectory planning problem of multi-UAV maritime target search. [PERSON] et al. [56] proposed a trajectory planning algorithm based on Genetic Algorithm with adaptive interference operators. The algorithm can realize the multi-directional attack target by setting intermediate points around the target point. A reasonable fitness function is designed by using the regionalization method, and the adaptive disturbance operator is added to plan the trajectory of each UAV, which solves the trajectory planning problem of multiple UAVs attacking targets in a complex combat environment. [PERSON] et al. [57] proposed an optimized Genetic Algorithm method, which applied the augmented stochastic framework to evaluate the task completion probability (PoC) of the strategy in a three-dimensional grid environment, and then, they used the Genetic Algorithm optimization method to find feasible trajectories that maximize PoC, addressing the Reliability-Aware Multi-Agent Coverage Trajectory Planning (RA-MCTP) problem. [PERSON] et al. [58] proposed a gray Genetic Algorithm, which iteratively uses the Genetic Algorithm to continuously find the agent trajectory that maximizes the PoC and solves the reliability-aware multi-agent coverage trajectory planning in continuous time (RA- MCTP) problem. [PERSON] et al. [59] proposed a collaborative trajectory planning model, introduced decision variables into the trajectory cost model, and then improved the Genetic Algorithm to generate a formation flight trajectory, which solved the problems of short effective flight time and low mission success rate when multiple UAVs were threatened. [PERSON] et al. [60] proposed a variable population size genetic trajectory planning algorithm (GTPA-VP), which improves the Genetic Algorithm through three operators of insertion, replacement and deletion, and updates the stop point adaptively. Using the number and location, on this basis, a multi-color Genetic Algorithm is used to find the association between UAVs and stopping points, the optimal number of UAVs and the optimal order of UAV stopping points. Finally, a Genetic Algorithm is used to construct the flight trajectory of all drones, solving the problem of high energy consumption of drones hovering and flying in IoT services. [PERSON] et al. [61] proposed an improved Particle Swarm Optimization and Genetic Algorithm (GA-PSO), which introduced partial matching crossover and secondary transposition mutation to the traditional Particle Swarm Optimization (PSO) algorithm and solved the intelligent marine task assignment problem and trajectory planning problem for multiple UAVs. [PERSON] et al. [62] proposed a trajectory planning method based on the Genetic Algorithm (GA).