# UAV Formation Trajectory Planning Algorithms: A Review
## 3 Traditional Algorithm
### Rapidly Exploring Random Trees  
Rapidly exploring Random Trees (RRT) is a single query random search algorithm based on sampling. Its basic idea is to randomly sample in the state space, use the graph structure or tree structure extension to build a feasible trajectory set, and then find a complete feasible trajectory from the trajectory set. The RRT algorithm takes the starting  
Figure 9: A PRM trajectory map (color areas: obstacles; black lines: feasible trajectories; red line: optimal trajectory). point in the state space as the root node and then generates a random extended tree by gradually increasing the leaf nodes at random. If the newly generated node conflicts with the obstacle area during the generation process, the node is discarded and reselected. When the target point is included in the leaf node of the random tree, the expansion of the random tree stops, and an obstacle avoidance route from the starting point to the target point can be obtained. A fast random search tree locus is shown in Figure 10.  
Aiming at the trajectory planning problem of UAV formation with static, ejection and dynamic obstacles, [PERSON] et al. [27] proposed a trajectory planning algorithm based on fast search random tree (RRTs) and introduced an anytime algorithm and guidance law based on tracking and line of sight into the algorithm to generate low-cost UAV formation trajectories under kinematic constraints in real time. [PERSON] et al. [28] proposed an improved Rapid Exploration Random Trees (RRTs) UAV formation collaborative trajectory planning algorithm, using a trajectory pruning method to delete redundant nodes on the trajectory. The UAV uses a trajectory planner, which enables the UAV to share information within the communication range. When UAV formation faces sudden threat trajectory replanning, the classical RRT algorithm has some problems such as low efficiency, large storage space and slow convergence. [PERSON] and [PERSON] [29] proposed a bidirectional fast search random tree algorithm based on greedy strategy, improved the expansion mode of algorithm nodes, and adopted an adaptive step size rolling detection method to improve the sensitivity of UAV formation to sudden threats. In addition, the traditional RRT algorithm also has the problem that it cannot adapt to the possible changes in the high-order dynamic characteristics of the autonomous movement of the UAV and the mission process during trajectory planning. In response to this problem, [PERSON] et al. [30] proposed a trajectory generation algorithm based on the integration of the RRT algorithm and the minimum capture algorithm, using the RRT algorithm to generate the initial trajectory, and then using the minimum capture algorithm to smooth the initial trajectory, and using the concept of flight corridors to limit the flight trajectory of drones. Table 1 summarizes the contents of our survey on traditional trajectory planning algorithms. \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Reference** & **Challenge** & **Optimization Criteria** & **Method** & **Dimension** \\ \hline [PERSON] and [PERSON] [13] & Environment & Trajectory of deviation & KSP & 2D \\ [PERSON] [14] & Information, Environment & AMSP & [PERSON] & 2D \\ [PERSON] and [PERSON] [15] & Time, Optimality & Optimal control & [PERSON] & 2D \\ [PERSON] et al. [16] & Security & LARAC & [PERSON] & 2D \\ [PERSON], [PERSON], and [PERSON] [17] & Environment & RVG, Bi-level optimization & [PERSON] & 3D \\ [PERSON] et al. [18] & Resources & PFHI & [PERSON] & 2D \\ [PERSON] and [PERSON] [19] & Environment & Short path & [PERSON] & 2D \\ [PERSON] et al. [20,21] & Trajectory & Lead–Follow, Multiple applications & [PERSON] & 3D \\ B.-b. [PERSON] et al. [22] & Environment & Task allocation & [PERSON] + [PERSON] & 2D \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Content of traditional trajectory planning algorithm in our survey. Figure 10: A RRT trajectory diagram (black areas: obstacles; pink lines: feasible trajectories; blue line: optimal trajectory; green: starting point; red: end point).