The evolution of Unmanned Aerial Vehicle (UAV) technology, marked by significant enhancements in individual performance, a paradigm shift from single-unit to swarm-based operational models, and the increasing complexity of application scenarios, has presented formidable new challenges for swarm coordination. The capability to effectively control drone formation—encompassing generation, maintenance, and dynamic reconfiguration—is pivotal for realizing the full potential of UAV clusters in modern contexts, particularly in defense, logistics, and surveillance. This operational efficiency hinges on sophisticated control algorithms that ensure robustness, scalability, and rapid adaptation. This article analyzes the current landscape of drone formation control research. Focusing on the leader-follower control paradigm, it abstracts the core problems of formation generation, holding, and reconfiguration into a graph-theoretic framework, specifically a weighted bipartite graph perfect matching problem. Subsequently, it details the application of the Kuhn-Munkres (KM) algorithm to solve this matching, enabling optimal assignment of follower drones to target positions within a new formation shape. This assignment is coupled with a Newtonian dynamics model for thrust calculation to achieve precise cluster control. The efficacy, rapidity, and stability of the proposed integrated methodology are conclusively validated through extensive simulation experiments.
The contemporary research into drone formation control algorithms is broadly categorized into centralized and distributed architectures, each with distinct trade-offs concerning scalability, robustness, and communication demands. Centralized approaches, such as those employing a virtual structure or a dedicated physical leader, offer high precision and fast response by processing all information at a single point. A virtual leader defines a reference frame for the entire drone formation, with each follower maintaining a predefined offset. Similarly, explicit leader-follower strategies involve direct command and feedback loops between a leading agent and its followers. Hierarchical or grouped control architectures can also be considered semi-centralized. While effective for small-scale formations, these methods suffer from a single point of failure and face significant computational and communication bandwidth bottlenecks when scaled to large clusters, making them less suitable for expansive drone formation scenarios.
In contrast, distributed control algorithms embody a decentralized philosophy, enhancing system robustness and scalability. In these systems, each drone makes decisions based on local information exchanged with neighboring agents. Methodologies include behavior-based approaches, artificial potential fields, consensus theory, and more recently, deep reinforcement learning. Behavior-based methods combine primitive behaviors like collision avoidance and flocking; potential field methods use virtual forces for attraction and repulsion; consensus algorithms ensure state agreement across the network; and learning-based methods seek optimal policies through interaction. Although highly scalable and fault-tolerant, distributed algorithms can be complex to design, may exhibit slower convergence, and are sensitive to communication delays, potentially leading to reduced formation precision compared to their centralized counterparts. A summary of this comparison is presented in Table 1.
| Architecture | Key Advantages | Key Disadvantages | Typical Methods |
|---|---|---|---|
| Centralized | High precision, Fast response, Simple design logic | Single point of failure, Poor scalability, High communication load | Virtual Leader, Leader-Follower, Hierarchical Control |
| Distributed | High robustness, Good scalability, No single point of failure | Complex design, Possible slower convergence, Sensitive to communication delays | Behavior-Based, Artificial Potential Field, Consensus, Reinforcement Learning |
While substantial progress has been made in fundamental formation shape control and generation, the specific challenge of rapid and optimal drone formation reconfiguration—determining which drone should move to which new position when the formation shape changes—warrants further exploration. This problem is critical for mission adaptability, such as switching from a wide surveillance pattern to a narrow penetration column. Addressing this gap, the methodology proposed herein leverages graph theory within a leader-follower framework to provide an efficient solution.
Formation Control Methodology
Problem Abstraction as a Bipartite Graph Matching
The core challenge during drone formation reconfiguration is to assign n follower drones from their current positions to n target positions defined by the new desired formation geometry. To minimize total energy expenditure and time, and to avoid unnecessary cross-traffic, the objective is to find the assignment that minimizes the sum of distances each drone must travel. This is precisely the classic assignment problem.
This problem can be elegantly modeled as a weighted complete bipartite graph \(G = (V, E)\). The vertex set \(V\) is partitioned into two disjoint subsets: \(A = \{a_1, a_2, …, a_n\}\), representing the current positions of the follower drones, and \(B = \{b_1, b_2, …, b_n\}\), representing the target positions in the new formation. For every pair \((a_i, b_j)\), there exists an edge \(e_{ij} \in E\) with a weight \(w_{ij}\). The goal is to find a perfect matching—a one-to-one pairing of all vertices in \(A\) to all vertices in \(B\)—that minimizes the total weight (sum of distances).
Let the 3D position of follower drone \(i\) at time \(t\) be \(\vec{p}_i(t) = (p_{xi}, p_{yi}, p_{zi})\). The target position \(j\) for a follower in the new formation, relative to the leader’s projected position \(\vec{p}_L(t+\Delta t)\), is \(\vec{p}’_j = (p’_{xj}, p’_{yj}, p’_{zj})\). The Euclidean distance (weight) for edge \(e_{ij}\) is:
$$
\Delta \vec{P}_{ij} = \vec{p}’_j – \vec{p}_i(t)
$$
$$
w_{ij} = \| \Delta \vec{P}_{ij} \| = \sqrt{(p’_{xj} – p_{xi})^2 + (p’_{yj} – p_{yi})^2 + (p’_{zj} – p_{zi})^2}
$$
Therefore, the optimal reconfiguration problem is: Find a bijection \(\pi: A \rightarrow B\) that minimizes \(\sum_{i=1}^{n} w_{i,\pi(i)}\).
Position Assignment via the Kuhn-Munkres (KM) Algorithm
The KM algorithm (also known as the Hungarian algorithm) is a well-established combinatorial optimization algorithm that solves the assignment problem in polynomial time (\(O(n^3)\)). It finds the minimum-weight perfect matching in a balanced bipartite graph. The operational workflow for its integration into drone formation control is as follows, with the sequence also depicted in the logical flowchart:
Step 1: Calculate Future Formation Geometry. Based on the leader’s current state (position \(\vec{p}_L(t)\), velocity \(\vec{v}_L(t)\)) and the desired formation template, compute the absolute target positions for all follower slots at time \(t + \Delta t\). The leader’s projected position is:
$$
\vec{p}_L(t+\Delta t) = \vec{p}_L(t) + \vec{v}_L(t) \cdot \Delta t
$$
Each target position \(\vec{p}’_j\) is then \(\vec{p}_L(t+\Delta t) + \vec{d}_j\), where \(\vec{d}_j\) is the static offset for slot \(j\) in the formation template.
Step 2: Compute Pairwise Distance Matrix. For all \(i, j\) in \([1, n]\), calculate the distance \(w_{ij} = \| \vec{p}’_j – \vec{p}_i(t) \|\).
Step 3: Transform for KM Algorithm. The standard KM algorithm finds a maximum-weight matching. Since we seek a minimum-weight matching, we transform the weights. A simple and effective transformation is to use the reciprocal (or a large constant minus the weight). We define a new weight \(w’_{ij} = 1 / w_{ij}\) (with a small epsilon to avoid division by zero). Maximizing the sum of \(w’_{ij}\) now effectively minimizes the sum of the original distances \(w_{ij}\).
$$
w’_{ij} = \frac{1}{w_{ij} + \epsilon}
$$
Step 4: Initialize Labels. The KM algorithm uses a labeling technique. Each vertex \(a_i \in A\) is given a label \(l(a_i)\), and each vertex \(b_j \in B\) a label \(l(b_j)\). Initial labels are set as:
$$ l(a_i) = \max_{j} w’_{ij} \quad \text{for } i=1,…,n $$
$$ l(b_j) = 0 \quad \text{for } j=1,…,n $$
These labels must satisfy the feasibility condition: \(l(a_i) + l(b_j) \geq w’_{ij}\) for all edges.
Step 5 & 6: Find Perfect Matching via Augmenting Paths. The core of the algorithm iteratively tries to find a perfect matching in the equality subgraph \(G_l\) (the graph containing only edges where \(l(a_i) + l(b_j) = w’_{ij}\)). It uses a depth/breadth-first search to find augmenting paths from unmatched \(A\)-vertices. If a full matching cannot be found, the labels are adjusted by subtracting a value \(d\) from all \(A\)-vertices in the search and adding \(d\) to all \(B\)-vertices in the search, which adds new edges to \(G_l\). This process repeats until a perfect matching \(M^*\) is found.
Step 7: Extract Position Assignment. The perfect matching \(M^*\) provides the optimal assignment: follower drone at \(a_i\) (current position \(i\)) is assigned to move to target position \(b_{\pi(i)}\).
Thrust Calculation for Dynamics Control
Once the target position \(\vec{p}’_{\pi(i)}\) for drone \(i\) is determined, a low-level controller must calculate the required thrust to achieve this movement within \(\Delta t\), respecting the drone’s dynamics. We model each drone as a point mass with a maximum acceleration capability, applying Newton’s second law.
Step 1: Compute Required Displacement Vector.
$$
\vec{d}_i = \vec{p}’_{\pi(i)} – \vec{p}_i(t)
$$
Step 2: Compute Desired Velocity Vector. The average velocity needed over the interval is:
$$
\vec{v}_{des,i} = \frac{\vec{d}_i}{\Delta t}
$$
Step 3: Compute Required Acceleration Vector. The acceleration needed to change the drone’s current velocity \(\vec{v}_i(t)\) to \(\vec{v}_{des,i}\) is capped by the drone’s maximum achievable acceleration \(\vec{a}_{max}\). The required acceleration direction is along \(\vec{v}_{des,i} – \vec{v}_i(t)\). The magnitude is the smaller of the needed magnitude and the maximum:
$$
\vec{a}_{req,i} = \min\left( \frac{\| \vec{v}_{des,i} – \vec{v}_i(t) \|}{\Delta t},\ \| \vec{a}_{max} \| \right) \cdot \frac{(\vec{v}_{des,i} – \vec{v}_i(t))}{\| \vec{v}_{des,i} – \vec{v}_i(t) \| + \epsilon}
$$
Step 4: Compute Thrust Vector. Assuming thrust is the primary force for acceleration (neglecting detailed aerodynamics for this high-level control), the required thrust \(\vec{F}_i\) is:
$$
\vec{F}_i = m_i \cdot \vec{a}_{req,i}
$$
where \(m_i\) is the mass of the drone. This thrust vector is then decomposed into the drone’s actuator commands (e.g., rotor speeds for a multirotor).
Simulation Experiments and Analysis
To validate the proposed methodology, two simulation experiments were conducted, focusing on formation assembly speed and reconfiguration capability—key metrics for evaluating any drone formation control algorithm.
Experiment 1: V-Formation Assembly and Keeping
This experiment tests the algorithm’s ability to quickly assemble a dispersed cluster into a structured V-formation and maintain it during transit.
Simulation Setup: A swarm of 120 homogeneous drones is simulated. Parameters are listed in Table 2. At time \(t=0\), one drone is designated as the leader. The 119 followers’ initial positions are randomly distributed around the leader following a 3D Gaussian distribution, simulating a post-deployment scattered state. The leader is commanded to fly from an initial point to a target point. The followers are required to form and maintain a 3-layer V-formation with a 60-degree included angle.
| Parameter | Value |
|---|---|
| Initial Leader Position | [0, 0, 5000] m |
| Follower Initial Position Noise | 200 * \(\mathcal{N}(0,1)\) m per axis |
| Initial Velocity | 200 m/s |
| Target Position | [4000, 6000, 0] m |
| Target Velocity | 100 m/s |
| Number of Drones (n) | 120 |
| V-Formation Angle | 60 deg |
| Formation Layers | 3 |
| Inter-Layer Spacing | 50 m |
| Intra-Layer Spacing | 100 m |
Results and Analysis: The trajectory plots in the XOY and XOZ planes show the swarm initializing in a cloud, after which the followers rapidly converge to their assigned slots in the V-formation as the leader proceeds toward the target. The flight paths are smooth and collision-free. The topology of the drone formation remains stable throughout the journey.
The tracking performance for a sample follower (ID 1) is analyzed. Figure 5 (conceptual plot) would show its positional error relative to its assigned slot in the formation. Initially, the error is large (~1000 m on the X-axis). Under the control of the proposed algorithm, the errors on the X, Y, and Z axes converge to near zero within approximately 7, 3, and 2 seconds, respectively. Subsequently, the errors remain minimal, demonstrating excellent formation-keeping precision. This confirms the rapid assembly and precise maintenance capabilities of the KM-based control method.
Experiment 2: Formation Reconfiguration (Circular to Linear)
This experiment evaluates the algorithm’s performance during a dynamic drone formation shape change.
Simulation Setup: The initial formation is a 3-layer circular pattern. At simulation time \(t = 20\) seconds, a command is issued to reconfigure into a 3-line, linear (column) formation. The key parameters are in Table 3.
| Phase | Parameter | Value |
|---|---|---|
| Initial (Circular) | Number of Drones | 120 |
| Formation Layers | 3 | |
| Inter-Layer Spacing | 50 m | |
| Circle Radius (per layer) | ~200 m spacing | |
| Reconfigured (Linear) | Reconfiguration Time | \(t = 20\) s |
| Formation Shape | Three Parallel Lines | |
| Inter-Layer Spacing | 50 m | |
| Intra-Line Spacing | 100 m |
Results and Analysis: The trajectory plot shows the swarm holding the circular formation until \(t=20s\). At the moment of reconfiguration, the KM algorithm is executed. Each follower is assigned to the nearest target position in the new linear formation pattern, minimizing total movement. The snapshot at \(t=20s\) shows the transitional state, and the final snapshot at the target location confirms the successful achievement of the new, precise linear drone formation. The paths during reconfiguration are direct and efficient, with no oscillatory or conflicting maneuvers, validating the algorithm’s effectiveness in managing complex formation transitions.
Conclusion
This article has presented a robust and efficient methodology for drone formation control, specifically addressing the challenges of optimal formation assembly, maintenance, and reconfiguration. By leveraging graph theory, the problem was abstracted into a bipartite graph matching framework. The integration of the Kuhn-Munkres algorithm provides an optimal, polynomial-time solution for assigning drones to target positions during formation changes, ensuring minimal total movement. Coupled with a Newtonian dynamics model for thrust calculation, this forms a complete control loop. Simulation experiments on large-scale swarms (120 drones) demonstrated the method’s key strengths: rapid convergence from dispersed states, exceptional precision in formation-keeping, and smooth, optimal transitions during dynamic reconfiguration. The proposed approach offers a significant contribution to the field of swarm coordination, providing a solid foundation that can be integrated with higher-level mission planning, real-time path finding, and obstacle avoidance modules to create comprehensive and intelligent drone formation systems for complex real-world applications.