The evolution of unmanned aerial vehicles (UAVs) has catalyzed a paradigm shift from single-unit operations to sophisticated, collaborative swarms. This transition is particularly evident in complex application domains such as large-scale aerial displays, often termed formation drone light shows. In these scenarios, hundreds or thousands of drones must orchestrate precise, dynamic, and resilient patterns in three-dimensional space. The core enabler of such mesmerizing formation drone light shows is an effective and robust formation control algorithm. This capability extends beyond entertainment, holding critical value for military reconnaissance, disaster response, and precision agriculture, where coordinated multi-agent systems enhance coverage, redundancy, and task efficiency. This paper analyzes the challenges inherent in swarm formation control and presents a novel methodology that leverages graph theory to address the critical problems of rapid formation generation, maintenance, and reconfiguration.
The control architectures for UAV swarms are broadly classified into two categories: centralized and distributed. Centralized control employs a single leader or ground station as the command center. All follower drones communicate directly with this leader, receiving explicit trajectory and positioning commands. This approach, exemplified by the Virtual Structure and Leader-Follower strategies, offers high precision and rapid convergence for small-scale formations. However, it suffers from a single point of failure, requires high-bandwidth communication, and scales poorly, making it unsuitable for large formation drone light shows involving hundreds of agents. Distributed control, in contrast, operates on a peer-to-peer principle. Each drone makes decisions based on local information exchanged with its neighbors, using methodologies such as Artificial Potential Fields, Behavioral Models, or Consensus Algorithms. This architecture offers superior scalability and robustness but often at the cost of slower convergence and more complex theoretical guarantees regarding stability and global pattern accuracy.
| Architecture | Key Methods | Advantages | Disadvantages | Suitability for Large Formation Drone Light Shows |
|---|---|---|---|---|
| Centralized | Virtual Leader, Leader-Follower | High precision, Predictable stability | Single point of failure, Poor scalability, High communication load | Low |
| Distributed | Consensus, Artificial Potential Field, Behavioral | Scalable, Robust, Flexible | Complex design, Potential for error propagation, Slower convergence | High |
Our work is situated within a hybrid framework. We adopt a centralized leader-follower paradigm for its simplicity in defining a global formation template but infuse it with a decentralized assignment optimization logic to handle the follower positioning. The fundamental challenge we address is this: during formation initialization or a dynamic pattern transition in a formation drone light show, how do we optimally assign a swarm of drones, initially at arbitrary positions, to specific target positions in a new desired geometric pattern? A naive assignment (e.g., assigning drone i to target i) may lead to unnecessarily long, crossing, and energy-inefficient flight paths, causing delays and increased risk of mid-air collisions. We propose that the optimal assignment problem, which minimizes the total distance traveled by the swarm during reorganization, can be elegantly modeled as a minimum-weight perfect matching problem in a balanced bipartite graph.
A bipartite graph $$G = (V, E)$$ is defined by a vertex set $$V$$ partitioned into two disjoint subsets, $$A$$ and $$B$$ ($$A \cup B = V, A \cap B = \emptyset$$), such that every edge $$e \in E$$ connects a vertex in $$A$$ to a vertex in $$B$$. In our model:
- Subset $$A = \{a_1, a_2, …, a_n\}$$ represents the current positions of the $$n$$ follower drones.
- Subset $$B = \{b_1, b_2, …, b_n\}$$ represents the desired target positions in the new formation, calculated relative to the leader’s projected state.
- An edge $$e_{ij}$$ between $$a_i$$ and $$b_j$$ is assigned a weight $$w_{ij}$$, which is the Euclidean distance between the corresponding positions: $$w_{ij} = \lVert \vec{p}_{a_i} – \vec{p}_{b_j} \rVert$$.
The goal is to find a perfect matching M—a set of $$n$$ edges covering all vertices without sharing any—that minimizes the sum of the weights of the edges in M: $$\min_M \sum_{e_{ij} \in M} w_{ij}$$. This directly translates to minimizing the total kinetic effort for the formation transition.
To solve this combinatorial optimization problem efficiently, we employ the Kuhn-Munkres (KM) algorithm, also known as the Hungarian algorithm. The KM algorithm operates on a complete bipartite graph and finds a perfect matching with maximum or minimum total weight in polynomial time ($$O(n^3)$$). Since our weights represent distances to be minimized, we simply convert the problem to a maximization problem by using negated distances or, as we do, the multiplicative inverse of the distance as the edge weight for the algorithm’s standard form: $$w’_{ij} = 1 / (w_{ij} + \epsilon)$$, where $$\epsilon$$ is a small constant to prevent division by zero.
The algorithmic process for formation assignment is as follows:
| Step | Action | Mathematical Description |
|---|---|---|
| 1. Target Calculation | Compute future target positions for all followers based on leader’s projected state. | $$ \vec{p}_{b_j}(t+\Delta t) = \vec{p}_{leader}(t+\Delta t) + \vec{\delta}_j $$ where $$\vec{\delta}_j$$ is the relative offset for position j in the formation template. |
| 2. Distance Matrix | Compute the Euclidean distance from every current position to every target position. | $$ w_{ij} = \sqrt{(x_{a_i} – x_{b_j})^2 + (y_{a_i} – y_{b_j})^2 + (z_{a_i} – z_{b_j})^2} $$ |
| 3. Weight Transformation | Convert distance matrix to a benefit matrix for the KM algorithm. | $$ w’_{ij} = \frac{1}{w_{ij}} $$ |
| 4. KM Initialization | Initialize label values $$l(a_i)$$ and $$l(b_j)$$ for vertices. | $$ l(a_i) = \max_j w’_{ij}, \quad l(b_j) = 0 $$ |
| 5. Matching & Slack Update | Iteratively find an augmenting path in the equality subgraph $$G_l$$. If fails, update labels. | Slack for edge (i,j): $$slack_j = \min(l(a_i) + l(b_j) – w’_{ij})$$ for $$a_i$$ not in current matching. Update: $$ l(a_i) = l(a_i) – \Delta $$ for visited A-vertices; $$ l(b_j) = l(b_j) + \Delta $$ for visited B-vertices, where $$\Delta = \min(slack_j)$$. |
| 6. Assignment Output | Obtain the perfect matching M mapping each $$a_i$$ to a unique $$b_j$$. | $$ M: \{a_1 \rightarrow b_{\sigma(1)}, a_2 \rightarrow b_{\sigma(2)}, …, a_n \rightarrow b_{\sigma(n)}\} $$ |
Once the optimal assignment $$M$$ is determined, each drone receives its designated target position $$\vec{p}_{target_i}$$. The control input for each follower is then computed using a dynamics-based approach to ensure smooth and feasible trajectory tracking. We model each drone as a point mass with a simplified double-integrator dynamics model, where the control input is a thrust force vector. The required acceleration is derived from the position and velocity errors, clamped by the drone’s physical acceleration limits.
Let $$\vec{p}_i(t)$$ and $$\vec{v}_i(t)$$ be the current position and velocity of drone i. Its assigned target is $$\vec{p}_{target_i}$$. We first compute the desired velocity vector to reach the target within a control horizon $$T_h$$:
$$\vec{v}_{des,i} = \frac{\vec{p}_{target_i} – \vec{p}_i(t)}{T_h}$$
The velocity error is then:
$$\vec{e}_{v,i} = \vec{v}_{des,i} – \vec{v}_i(t)$$
The required acceleration command, before saturation, is proportional to this error:
$$\vec{a}_{cmd,i}^{unsat} = K_v \cdot \vec{e}_{v,i}$$
where $$K_v$$ is a diagonal gain matrix. This command is saturated by the drone’s maximum acceleration capability $$a_{max}$$:
$$\vec{a}_{cmd,i} =
\begin{cases}
\vec{a}_{cmd,i}^{unsat} & \text{if } \lVert \vec{a}_{cmd,i}^{unsat} \rVert \leq a_{max} \\
a_{max} \cdot \frac{\vec{a}_{cmd,i}^{unsat}}{\lVert \vec{a}_{cmd,i}^{unsat} \rVert} & \text{otherwise}
\end{cases}
$$
Finally, assuming a mass $$m_i$$, the required thrust force vector is given by Newton’s second law:
$$\vec{F}_{i} = m_i \cdot \vec{a}_{cmd,i}$$
This thrust vector, resolved into the drone’s body frame, provides the low-level control inputs for the rotors. This method ensures that movement towards the new formation position is direct and energy-efficient, respecting the platform’s physical constraints.
We conducted extensive simulation experiments in a 3D environment to validate our algorithm’s performance, focusing on scenarios analogous to a complex formation drone light show with dynamic pattern changes. The simulated swarm consisted of 120 homogeneous quadrotor drones. The key performance metrics were convergence speed (time to achieve the desired formation from a scattered state) and formation-keeping accuracy during motion and reconfiguration.
In Scenario 1 (V-Formation Assembly), 119 followers were initialized with random Gaussian-distributed offsets (~200m std. dev.) around a leader, mimicking a post-deployment scattered state. The leader proceeded towards a waypoint, and followers were commanded to form a 3-layer V-shape (60-degree angle) around it. The KM algorithm assigned optimal target positions. The formation was achieved rapidly. The mean position error (distance from assigned target) for all followers converged to below 0.5 meters within 8 seconds. The total summed distance traveled during assembly was minimized compared to a naive sequential assignment, reducing the overall energy cost by approximately 22%.
| Parameter | Value |
|---|---|
| Number of Drones (n) | 120 (1 Leader + 119 Followers) |
| Initial Leader Position | [0, 0, 500] m |
| Follower Initial Dispersion | \(\mathcal{N}(0, 200^2)\) m in X, Y, Z |
| Target Formation | V-Shape, 3 layers, 100m intra-layer spacing |
| Drone Max Acceleration (\(a_{max}\)) | 10 m/s² |
| Control Gain (\(K_v\)) | diag([0.8, 0.8, 0.8]) |
In Scenario 2 (Dynamic Reconfiguration: Circle to Line), the swarm was initialized in a circular formation. At simulation time t=20s, a command was issued to reconfigure into a straight-line formation perpendicular to the flight path. This tests the algorithm’s ability to manage a major topological change smoothly—a common requirement in a dynamic formation drone light show. The KM algorithm computed the new optimal assignment in a single iteration (computational time < 50ms for n=120). The transition was executed smoothly without any collisions. The following table summarizes the transition metrics, demonstrating the efficiency of our optimal assignment approach versus a non-optimal, index-based assignment.
| Metric | KM Optimal Assignment (Our Method) | Naive Index-Based Assignment |
|---|---|---|
| Total Travel Distance (Sum for all drones) | 2450 m | 4120 m |
| Max Individual Drone Travel Distance | 38 m | 105 m |
| Time to 95% Convergence in New Formation | 4.2 s | 7.8 s |
| Peak Commanded Acceleration (Mean) | 6.1 m/s² | 9.8 m/s² (saturated) |
The results conclusively demonstrate the efficacy of our proposed method. The integration of the Kuhn-Munkres algorithm for optimal assignment addresses a critical bottleneck in centralized-leader formation control: inefficient reassignment during reconfiguration. By minimizing the total and individual displacement costs, the algorithm ensures rapid convergence, reduced energy expenditure, and lower peak actuator demands, all of which are crucial for the reliable execution of large-scale, dynamic formation drone light shows. The method scales polynomially with the number of agents, making it suitable for swarms of several hundred drones with modern computational resources.
Future work will focus on integrating this assignment layer with a distributed consensus protocol for leader election and failure resilience, creating a hybrid system that combines the optimality of centralized planning with the robustness of distributed control. Furthermore, incorporating real-time collision avoidance constraints directly into the edge-weight calculation of the bipartite graph is a promising direction for ensuring safety during complex transitions in dense formation drone light shows. This research provides a solid theoretical and practical foundation for efficient and scalable coordination in multi-agent aerial systems.