Formation flight of unmanned aerial vehicles (UAVs) poses significant challenges in terms of safety and formation keeping, particularly in cluttered environments. However, existing methods often struggle to simultaneously satisfy these two critical requirements. To address this issue, this paper proposes a sampling-based trajectory planning method with a hierarchical structure for formation flight in dense obstacle environments. To ensure reliable local sensing information sharing among UAVs, each UAV generates a safe flight corridor (SFC), which is transmitted to the leader UAV. Subsequently, a sampling-based formation guidance path generation method is designed as the front-end strategy, steering the formation to fly in the desired shape safely with the formation connectivity provided by the SFCs. Furthermore, a model predictive path integral (MPPI) based distributed trajectory optimization method is developed as the back-end part, which ensures the smoothness, safety and dynamics feasibility of the executable trajectory. To validate the efficiency of the developed algorithm, comprehensive simulation comparisons are conducted. The supplementary simulation video can be seen at https://www.youtube.com/watch?v=xSxbUN0tn1M.

The formation trajectory planning using complete graphs to model collaborative constraints becomes computationally intractable as the number of drones increases due to the curse of dimensionality. To tackle this issue, this paper presents a sparse graph construction method for formation planning to realize better efficiency-performance trade-off. Firstly, a sparsification mechanism for complete graphs is designed to ensure the global rigidity of sparsified graphs, which is a necessary condition for uniquely corresponding to a geometric shape. Secondly, a good sparse graph is constructed to preserve the main structural feature of complete graphs sufficiently. Since the graph-based formation constraint is described by Laplacian matrix, the sparse graph construction problem is equivalent to submatrix selection, which has combinatorial time complexity and needs a scoring metric. Via comparative simulations, the Max-Trace matrix-revealing metric shows the promising performance. The sparse graph is integrated into the formation planning. Simulation results with 72 drones in complex environments demonstrate that when preserving 30\% connection edges, our method has comparative formation error and recovery performance w.r.t. complete graphs. Meanwhile, the planning efficiency is improved by approximate an order of magnitude. Benchmark comparisons and ablation studies are conducted to fully validate the merits of our method.