# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.3 Evolutionary Algorithm  
The Evolutionary Algorithm (EA) is a stochastic optimization search algorithm summed up on the basis of biological evolution in nature. The most widely used algorithm is the Genetic Algorithm (GA). Its main idea is to rasterize the flight space first, find the area covered by obstacles or conflict with obstacles, and then randomly generate starting points in the map. To ensure the collision-free trajectory to the target point, in the trajectory planning process, each collision-free trajectory from the starting point to the goal point is represented as an individual, and each individual has a chromosome, so each collision-free trajectory can also become a chromosome. Each segment in the trajectory is represented  
Figure 12: Trajectory diagram of A* algorithm (dots: nodes; lines: trajectories; black areas: obstacles; green dotted line: optimized trajectory). as a gene. The collection of all individuals, that is, all generated collision-free trajectories from the starting point to the target point, are called the population. We design the corresponding fitness function to screen out the required individuals from the population. Individuals with high fitness are elite individuals; through the cross-mutation operation between elite individuals, better elite individuals are continuously screened until the termination conditions are met, and finally, what remains is the required obstacle avoidance route. Figure 13 is a diagram of a cross-mutation operation and a trajectory diagram of an Evolutionary Algorithm (EA). [PERSON] et al. [40] proposed an algorithm based on model predictive control (MPC) and the Genetic Algorithm (GA) for multiple UAVs to search for unknown areas cooperatively, combining the flexibility of the Genetic Algorithm and the predictive ability of MPC. The combination avoids the problem where the search process enters into local optimality. [PERSON] et al. [41] proposed a method based on Genetic Algorithm (GA) to solve the multi-UAV cooperative reconnaissance mission planning problem, introduced integer string chromosome representation and designed a new subsequence crossover algorithm to meet the requirements of reconnaissance resolution. They also inserted mutation operators forward to increase the population diversity, which solves the problems of reconnaissance resolution and the time window when UAV formations perform reconnaissance missions. [PERSON] et al. [42] proposed a trajectory planner suitable for a group of cooperative UAVs to avoid collisions with environmental obstacles, combining b-spline curves, potential fields, and differential evolution (DE) to generate smooth the trajectory curve of the UAV formation, which solves the trajectory planning problem of the UAV formation in a known or unknown static environment. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Reference** & **Challenge** & **Optimization Criteria** & **Method** & **Dimension** \\ \hline T. [PERSON] et al. [32] & Trajectory & Parallel computing & SA & 2D \\ [PERSON]. [PERSON] and [PERSON] [33] & coverage problem & K-means & SA & 2D \\ Y. [PERSON] et al. [34] & Trajectory & Speed perception, collision prediction & A* & 3D \\ H. [PERSON] et al. [35] & UAV clustering & Constraint model & A* & 2D \\ [PERSON] et al. [36] & UAV clustering & Hierarchy & A* & 3D \\ [PERSON] et al. [37] & Trajectory and & Revisit Time & A* & 3D \\ [PERSON] et al. [38] & Environment & Fuzzy c-means method & A* & 3D \\ [PERSON] et al. [39] & Environment & parent node, seventh-order & & \\  & & polynomial interpolation & JPS + APF & 3D \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Summary of simulated annealing algorithm and A* algorithm in our review. Figure 13: A cross-variation operation diagram and EA trajectory diagram. (**a**) A cross-mutation operation diagram; (**b**) An Evolutionary Algorithm (EA) trajectory diagram (red circles: obstacles; blue line: optimal trajectory). [PERSON] et al.