# UAV Formation Trajectory Planning Algorithms: A Review
## 5 Local Trajectory Planning Algorithm
### Model Predictive Control  
Model Predictive Control (MPC) is a typical online planning method with planning and execution at the same time. In other words, it is a rolling time window approach. In the local planning process, the algorithm first updates the environmental information in the current trajectory search domain and predicts the information change trend in the trajectory search domain on this basis. Then, it searches out the local reference trajectory according \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Reference** & **Challenge** & **Optimization Criteria** & **Method** & **Dimension** \\ \hline [PERSON] et al. [143] & Trajectory, Time & New cost function, Variable weight factor, Lead–follow & A* + DWA & 2D \\ [PERSON] et al. [144] & UAV & Failure probability, Task selection & CPLEX & 2D \\ [PERSON] and [PERSON] [145] & UAV clustering & Area divided and computer, Computational scan & PADEC & 2D \\ [PERSON] et al. [146] & Trajectory & DESI, CRIB & 2D \\ [PERSON] et al. [147] & Trajectory & Non-convex optimal, Parallel solution & SCP & 2D \\ [PERSON] et al. [148] & Environment & GNSS, Custom target allocation & Multiple step & 3D \\ [PERSON] et al. [149] & UAV, Environment & Distributed solutions and Nash optimal coordination & Pseudo-spectral & 3D \\ [PERSON] et al. [150] & Trajectory & Greedy goal assignment & WTSC & 2D \\ [PERSON] et al. [152] & Computing performance & Time division, Constraint transformation & GB-SMO & 3D \\ [PERSON] et al. [153] & Environment, UAV clustering & Efficiency model & Safe flight & 2D \\ S.-[PERSON]. [PERSON] et al. [154] & Environment & Hexagonal grid decomposition & MILP & 2D \\ [PERSON] et al. [155] & Environment, Time & State adaptation, Single objective optimization & MISEDA & 4D \\ [PERSON] et al. [156] & Trajectory & Consensus protocol, Sequential convex programming & Non-convex & 3D \\ [PERSON] [157] & Resource utilization & Joint optimization, Decoupling optimization, Hybrid planner & 2D \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Summary of dynamic windowing methods and mathematical optimization algorithms in our survey. to the motion model of the UAV and executes. In the process, the trajectory is corrected according to the motion constraints and control errors of the UAV so as to make full use of real-time feedback information to gradually generate a global trajectory. Figure 28 is a schematic diagram of MPC. [PERSON] et al. [158] proposed a decentralized nonlinear model predictive control trajectory planning strategy (DNMPC), which introduces filtering technology and decentralized optimization into MPC to realize UAV formation for trajectory planning in relay communication to solve the problem of poor connectivity of the wireless network between the fleet of naval ships. [PERSON] et al. [159] proposed a multi-object tracking algorithm based on task assignment consensus. It uses the dynamic task allocation model to update the tracking tasks and uses the intermittent asynchronous communication principle to realize the sharing of local observation information. At the same time, it uses the MPC algorithm to complete the tracking trajectory planning and solved the problem of UAV formation tracking multiple moving targets within a limited communication range. [PERSON] et al. [160] proposed a UAV trajectory planning model (Poc-KF) based on collision probability and Kalman filter. The model uses the collision probability algorithm and the Kalman filter algorithm for UAV collision probability calculation and formation state estimation, and it calculates feasible trajectories for UAV formation in real time. It also addressed possible trajectory conflicts in high-density drone formations. [PERSON] et al. [161] proposed a behavior tree (BT) model. The specific operation is to combine the model prediction with the decision tree to obtain the behavior tree (BT). Then, they add the virtual target-based tracking (VTB-T) method and use the behavior tree (BT) organization trajectory planning method to construct a feasible trajectory for the UAV.