# UAV Formation Trajectory Planning Algorithms: A Review
## 5 Local Trajectory Planning Algorithm
### Mathematical Optimization Algorithm
The algorithm conceives the multi-UAV formation as a reconfigurable distributed system and then introduces methods such as edge definition and cost evaluation, custom target assignment, UAV timing and polynomial trajectory (PT) for formation trajectory planning. It solves the problem of low efficiency of UAV formation trajectory planning task assignment in a three-dimensional heterogeneous environment. [PERSON] et al. [149] proposed an optimal trajectory planning method for multiple UAVs based on the pseudospectral method. This method uses the pseudospectral method to transform the optimal control problem with complex constraints into a nonlinear programming problem; at the same time, it uses the distributed solution and the Nash optimal coordination strategy to solve the multi-UAV trajectory planning problem under complex and multi-constrained conditions. [PERSON] et al. [150] proposed a trajectory planning method for multi-UAV scan coverage with minimum time maximum coverage. This method introduces a Weighted Target Scan Coverage (WTSC) algorithm for greedy target assignment, which solves the problem of insufficient task time and coverage performance of two algorithms, CycleSplit and G-MSCR [151]. [PERSON] et al. [152] proposed a gradient-based sequential minimum optimization (GB-SMO) algorithm, which uses time segmentation instead of traditional waypoint segmentation to establish a trajectory optimization model and introduces virtual line segments to adapt to the trajectory length. Constraints are converted into cost functions and then minimized using GBSMO, which solves the problem of insufficient computational performance of commonly used trajectory planning algorithms considering constraints. Figure 27: A mathematical optimization algorithm model. [PERSON] et al. [153] proposed a real-time trajectory planning method for UAV formation transformation based on safe flight corridors, introducing safe flight corridors to avoid UAV collisions, while considering time and space efficiency models. They addressed an issue where drones could collide when performing a formation change. [PERSON] et al. [154] proposed a multi-UAV search trajectory planning method covering nodes in the shortest time. The method introduces a mixed integer linear programming (MILP) model of hexagonal grid decomposition and at the same time uses the optimization time as a search function to obtain the trajectory of the formation UAVs in iterations. The trajectory planning problem of UAV formation searching for catastrophic marine accidents is solved. [PERSON] et al. [155] proposed a 4D trajectory planning method with temporal and spatial constraints. This method transforms the arrival time into state adaptation and at the same time transforms the collaborative penetration trajectory planning into a single-objective optimization problem. Then, it uses the multi-leader search distribution estimation algorithm (MLSEDA) to solve the problem, which solves the trajectory planning problem of UAV cooperative penetration. [PERSON] et al. [156] proposed a decentralized multi-UAV trajectory planning method for obstacle environments. In this method, the UAV rendezvous trajectory planning problem under constraints is modeled as a non-convex optimal control problem, and then, the consensus protocol and sequential convex programming two-layer collaborative framework are used to solve the UAV formation trajectory. It solves the problems of low calculation efficiency and poor adaptive ability of the traditional UAV formation trajectory planning method. [PERSON] [157] proposed a hybrid planner that uses joint optimization methods, decoupling optimization methods, and hybrid methods to calculate UAV formations. They generated feasible trajectories under two different requirements of time constraints and connectivity, solving the problem where the connection parameters are difficult to trade off and the resource utilization rate is low in the formation task.