# UAV Formation Trajectory Planning Algorithms: A Review
## 4 Intelligent Algorithm
### Heuristic Algorithm
#### 4.1.2 A* Algorithm  
The A* algorithm is a graph search algorithm that introduces heuristic information factors into the target information of the problem to be solved, making the search direction more accurate and reducing the convergence time. The basic idea of this algorithm for UAV formation trajectory planning is as follows: firstly, the flight space is rasterized and decomposed into some units with regular shapes, and it is judged whether these units are covered by obstacles or intersected with obstacles. Then, find the unit containing the starting point and the target point and use the A* algorithm to find a series of connected units to connect the starting unit and the target unit. The search process of the A* algorithm is based on the value of the heuristic function in the direction of the lower cost; that is, for the node n, the algorithm uses the cost function to evaluate its surrounding nodes and selects the point with the smallest estimated value as the next node. The expression of the cost function is:  
\[f(n)=g(n)+h(n) \tag{2}\]  
where \(h(n)\) is the heuristic function; \(g(n)\) represents the prediction cost function from the current node position to the target point and represents the trajectory cost from the starting point to the current node n; and \(f(n)\) is the estimated value, which is obtained by adding \(h(n)\) and \(g(n)\). In the grid graph, the heuristic function is usually expressed by the distance between two points. The calculation process of algorithm A* is a step-by-step search process, continuously extending to the direction of the minimum estimated value trajectory, calculating the optimal solution and outputting the optimal trajectory. Figure 12 is a trajectory diagram of an A* algorithm. The traditional A* algorithm convergence speed is slow, and the trajectory may not be optimal. [PERSON] et al. [34] proposed a distributed velocity perception and trajectory planning  
Figure 11: Trajectory diagram of a simulated annealing algorithm (dots: nodes; lines: trajectories; numbers: the distance between vertices). algorithm, which introduced a velocity perception strategy and collision prediction into the A* algorithm and carried out trajectory planning of UAV formation. [PERSON] et al. [35] proposed a cooperative search A* algorithm, which introduced cooperation strategies, cooperation constraints and cooperation costs into the constraint model, and they solved the problem of multi-aircraft formation trajectory planning with complex space-time constraints. [PERSON] et al. [36] proposed a collaborative tactical planning method of UAV formation based on hierarchical structure, which introduced a hierarchical structure into UAV formation collaborative combat and solved the autonomous control problem of UAV formation in modern air combat. [PERSON] et al. [37] proposed a method based on the cell revisit time value and other effective cost functions such as height, minimum distance, collision avoidance and turning cost to realize multi-objective collaborative trajectory planning of multiple UAVs. A modification of the A* algorithm (MA*) was made to define a new criterion for individual revisit time unit values and extend it to the entire 3D mountain environment area, introducing revisit time and application-specific settings to reduce the computational complexity degree, which solves the problems of the traditional A* algorithm, such as high computational complexity, small number of extension units and low ratio of coverage. [PERSON] et al. [38] proposed a multi-UAV trajectory planning method in the case of three-dimensional building damage investigation or disaster, which combined the fuzzy c-means method of assigning positioning points to UAVs and the A* algorithm to calculate the access sequence of each UAV camera positioning point so as to obtain the feasible trajectory of multiple UAVs, which solves the problem of multi-UAV coverage trajectory planning for the 3D reconstruction of damaged buildings after disasters. [PERSON] et al.