# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.9 Ant Colony Optimization Algorithm  
Ant Colony Optimization (ACO) is a heuristic global optimization algorithm derived from the trajectory behavior of ants in the process of searching for food. The ant colony algorithm uses the trajectories of ants to represent the feasible solution of the problem to be optimized. All trajectories of the entire ant colony constitute the solution space of the problem to be optimized, and ants with shorter trajectories release more pheromones. The concentration of pheromone accumulated on the shorter trajectory gradually increases, and the number of ants choosing this trajectory increases; eventually, all the ants will concentrate on the best trajectory under the action of positive feedback, and the corresponding trajectory is the optimal solution to the problem. Figure 19 is a trajectory diagram of an Ant Colony Optimization algorithm (ACO). [PERSON] et al. [98] proposed a parallel Ant Colony Optimization algorithm (ACO) to calculate the trajectory of a UAV. This algorithm implements ACO on CUDA architecture, which gives full play to the parallel characteristics of ACO on GPU and solves the problem of slow convergence of a traditional ant colony algorithm. [PERSON] et al. [99] proposed an intelligent method based on the improved Ant Colony Optimization (ACO) algorithm, which cuts the trajectory generated by ACO and solves the problem that the trajectory of the traditional ACO algorithm may not be optimal. [PERSON] et al. [100] proposed a coordinated trajectory planning method for multiple UAVs based on K-degree smoothing. In this method, a Voronoi diagram is used to redefine the edge cost, and the redefined heuristic information function and pheromone updating method are used to change the Ant Colony Optimization algorithm. Finally, the K-degree smoothing method is used to smooth the trajectory, which solves the problem of strong coordination and weak coordination in the collaborative trajectory planning of multi-UAVs. [PERSON] [101] proposed a multi-UAV multi-communication target and message priority UAV cooperative communication trajectory method. This method combines a delay tolerant network (DTN), light grid and ant colony algorithm. The trajectory planning is carried out to solve the contradiction between the intermittent link of the underlying communication of multi-UAVs and the continuous demand of the upper-level communication in a highly hostile battlefield. [PERSON] et al. [102] proposed a new method based on the improvement of Ant Colony Optimization (ACO), which added a new minimum time search (MTS) heuristic  
Figure 19: An ACO trajectory diagram (“cell” is the map block after rasterizing the map, “number” is the number of the map block, and the black part represents obstacles.). function to ACO to solve the traditional ACO problem of slow algorithm convergence and low initial trajectory quality. [PERSON] et al. [103] proposed a multi-UAV cooperative search attack method (ISOA) based on an intelligent self-organizing algorithm, using a new state transition rule and a distributed method to improve the Ant Colony Optimization algorithm. Then, using the Dubins curve to smoothly connect the trajectory points generated by ACO, the trajectory planning problem of multiple UAVs under the constraints of maneuverability, collision avoidance and maximum range is solved. [PERSON] et al. [104] proposed an enhanced Ant Colony Optimization (ACO) algorithm, which performs multi-core computing on the parallel computing platform CUDA to solve the trajectory planning problem of multiple UAVs in complex environments. [PERSON] et al. [105] proposed a multi-objective optimization model of coverage and task time and introduced the similarity measure in an immune optimization algorithm into the Ant Colony Optimization algorithm to solve the problem that the traditional Ant Colony Optimization algorithm is insufficient in track repeatability. [PERSON] et al.