# UAV Formation Trajectory Planning Algorithms: A Review
## 1 Introduction
Under the premise of satisfying multiple constraints, the specified performance index can be optimized or better so that all UAVs in the formation can safely reach the target from the starting point. The trajectory planning of UAV formation is a complex multi-objective optimization and decision problem under multiple constraints. With the increasing number of UAVs, the analytic space of the problem will increase exponentially. In the study of UAV trajectory planning, the algorithm is the soul of UAV trajectory planning, which is directly related to the efficiency and results of trajectory planning. Compared with single UAV trajectory planning, the complexity of UAV formation trajectory planning is mainly reflected as follows:  
1. In many cases, the scope of planning space is large and complex: for example, there are various spatial obstacles and dynamic threats in the modern battlefield environment;
2. There are many constraints. Not only should the planned flyable trajectory conform to the actual dynamics and kinematic characteristics of the UAV, but also the coordination between time and space and the concealment of the trajectory should be considered;
3. Multi-UAV trajectory planning can adapt to battlefield dynamic changes and adjust trajectories online in real time. For the trajectory planning of UAV formation, many papers have proposed solutions from different perspectives, but there are still many unsolved problems and many limitations, resulting in numerous and complex papers without a comprehensive and systematic classification, which is not conducive to research and reading. The reference [9] classifies and statistically analyzes the cooperative flight path planning of various UAV formations from the three elements of a UAV system (mission, UAV crew and environment) and the three elements of UAV formation cooperative flight path planning (UAV flight path, target and constraint), but it does not discuss the flight path planning algorithm of UAV formation. Stochastic Heuristic Algorithms (SHA) are reviewed in reference [10], and the characteristics, improvements, applications, advantages and disadvantages of some of them are discussed, but non-SHA algorithms in UAV formation flight paths are not discussed. The reference [11] divides the flight path planning algorithms of UAV formation into five categories, including optimal algorithm, graph theories-based planning method, heuristic information-based planning algorithm, swarm intelligence algorithm and neural network algorithm. Then, a simple description is given to these categories, but no specific algorithms are discussed. Reference [12] reviews swarm intelligence algorithms from four aspects, such as collision avoidance processing, task allocation, track planning and formation recombination, and it discusses classical algorithms among them. However, it does not discuss non-swarm intelligence algorithms, which has certain limitations. Compared with many studies in the literature on UAV formation trajectory planning [9; 10; 11; 12], the contributions of this paper are as follows. In this review, the UAV formation trajectory planning algorithms used in recent decades are classified in detail, and the basic principles of these algorithms are described and compared so as to find out the shortcomings of UAV formation trajectory planning algorithms. The challenges and future research directions of the algorithm are summarized and prospected, which provides reference information for researchers and workers engaged in the formation flight of UAVs. This paper can be divided into the following parts: Firstly, a simple classification framework of the UAV formation trajectory planning algorithm is introduced in Section 2. Then, the global trajectory planning algorithms are summarized in time order in Sections 3 and 4. Among them, Section 3 summarizes the traditional algorithm and Section 4 summarizes the intelligent algorithm. Section 5 summarizes the local trajectory planning algorithm. Section 6 summarizes the challenges the algorithm faces.