# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.1 Simulated Annealing Algorithm  
The Simulated Annealing Algorithm (SA) is derived from the annealing of solid matter in physics. Usually, when a solid material is annealed, it is heated to allow its particles to move freely, and then, the particle system descends slowly enough to slow down sufficiently. The system is approximately at a thermodynamic equilibrium point, and finally, the particle system will reach its lowest energy state, the ground state, which corresponds to the global minimum of the energy function. The objective function of the optimization problem is equivalent to the energy, and the optimal solution is equivalent to the lowest energy state. The simulated annealing algorithm changes randomly from one state to another state at a given temperature and uses the random acceptance criterion to judge. When the temperature slowly drops to a very low value, it remains at the optimal solution with a probability of 1. When the UAV formation is performing trajectory planning, we first define a solution space, arrange the fixed starting point to the end point by unit, use the Monte Carlo method as the initial solution, and iterate to create a new solution for the next trajectory point program. The exchange order of the two trajectory points in the obtained solution will generate a new solution. Then, we set the target function of the trajectory length of the UAV and use the simulated annealing criterion to test the cost function according to the data of the distance matrix. We use the difference between the cost functions to determine whether to accept the new trajectory planning and set the cooling process control parameters, initial temperature, cooling coefficient, end temperature, and current temperature iteration number. When the temperature drops to the end temperature, the algorithm stops, reaches the minimum temperature, and outputs the formation. The  
\begin{table}
\begin{tabular}{c c c c c} \hline
**Reference** & **Challenge** & **Optimization Criteria** & **Method** & **Dimension** \\ \hline [PERSON]. [PERSON] et al. [23] & coverage problem & Distributed coverage & Voronoi & 2D \\ [PERSON] et al. [24] & Environment, & Consistency theory & Voronoi & 2D \\ [PERSON] et al. [25] & UAV clustering & Target switching & Voronoi + APF & 3D \\ [PERSON] et al. [26] & Trajectory & Multiple trajectories & PRM & 2D/3D \\ [PERSON] et al. [27] & Environment & Anytime, Guide rate & RRT & 2D \\ [PERSON] et al. [28] & Environment & pruning & RRT & 2D \\ [PERSON] and [PERSON] [29] & Environment & Greedy strategy, Adaptive step size & RRT & 3D \\ [PERSON]. [PERSON] et al. [30] & Environment & Minimum snap, Flight corridor & RRT & 2D \\ \hline \end{tabular}
\end{table}
Table 1: _Cont._optimal trajectory of the UAV using a simulated annealing algorithm trajectory is shown in Figure 11.  
[PERSON] et al. [32] proposed an alternative method to effectively calculate the cost-fair flight path of a single-station multi-UAV system, using a data parallel computing mechanism to improve the simulated annealing algorithm, and solve the problem of the UAV formation trajectory planning calculation time index problem of growth.  
[PERSON] and [PERSON] [33] proposed a method of UAV formation trajectory planning based on the K-means algorithm and Simulated Annealing (SA) algorithm, using decomposition technology to reasonably decompose the effective area into multiple sub-target points. They use the K-means algorithm to cluster the UAV cruise target points and then use the Simulated Annealing (SA) algorithm for similar sub-target trajectory planning, which solves the problem of UAV cruise distance and scheduling under complex constraints and leads to improved coverage of drones in the sub-target area of the cruise effective area.