The increasing capabilities of Unmanned Aerial Vehicles (UAVs), coupled with the paradigm shift from single-unit operations to coordinated swarm deployments and the growing complexity of operational scenarios, present significant new challenges for drone formation control. Efficient and robust control algorithms are paramount to harnessing the full potential of UAV swarms, enabling enhanced mission efficiency, expanded reconnaissance coverage, and improved system resilience. This capability is critical for meeting the demands of modern battlefields, which require immediate situational awareness and real-time, cross-domain strike capabilities.
This study analyzes the current state of research in drone formation control. We focus on the leader-follower control architecture as our point of departure, abstracting the problems of formation generation, maintenance, and reconfiguration into a bipartite graph perfect matching problem. Subsequently, the Kuhn-Munkres (KM) algorithm is employed to achieve optimal position assignment for the follower UAVs within the formation. This assignment is then integrated with control laws derived from Newton’s second law to realize precise cluster formation control. Finally, simulation experiments are conducted to validate the method’s effectiveness, demonstrating its rapid convergence and stable performance.
Current Research Landscape in Drone Formation Control
Contemporary research into algorithms for drone formation control can be broadly categorized into two paradigms: centralized and distributed control, both aiming to achieve autonomous formation control for multi-task scenarios.
Centralized Control Algorithms operate with a single designated leader acting as the control center. This leader disseminates control commands and formation information to the follower agents, which in turn provide feedback. The leader can be pre-defined or selected autonomously. Centralized approaches are known for their high precision and rapid response, making them suitable for drone formation of limited size. However, their requirement for substantial computational power and robust, high-bandwidth communication links renders them less scalable for large-scale drone formation control. Predominant centralized methods include the Virtual Structure approach, Leader-Follower formation optimization, and Hierarchical Grouping architectures. These methods primarily address formation shape generation, shape maintenance, and overall formation control.
Distributed Control Algorithms are characterized by their decentralized nature. In this paradigm, each agent within the drone formation can exchange and share information with its neighboring agents, achieving coordinated control through local interaction rules. Distributed methods offer high robustness and excellent scalability, making them well-suited for controlling large-scale formations in complex, dynamic environments. The trade-off lies in increased algorithmic complexity, stringent requirements for communication timeliness, and the potential for error accumulation, which can lead to relatively lower formation precision compared to centralized schemes. Key distributed strategies encompass Behavior-Based methods, Artificial Potential Fields, Deep Reinforcement Learning, and Consensus Theory. These techniques enable capabilities such as formation keeping with obstacle avoidance, seamless formation shape transitions, autonomous formation assembly, and rapid swarm aggregation and reconfiguration.
While significant progress has been made in algorithms concerning the overall structure, generation, and control of drone formation, research specifically addressing the rapid maintenance and reconfiguration of formations during shape transitions remains relatively less explored. This study tackles this gap by building upon the leader-follower framework and incorporating graph-theoretic principles to achieve fast position assignment for UAVs during formation keeping and reconfiguration. This is combined with Newtonian mechanics to deliver effective cluster control.
The Proposed Formation Control Methodology
Problem Abstraction as a Graph Matching Problem
When a drone formation undergoes a transformation or reconfiguration, it is equivalent to multiple UAVs relocating from their current positions to designated target positions in the subsequent formation state. To ensure the rapid completion of this reconfiguration, the objective is to minimize the total displacement of the entire UAV swarm. This problem can be abstractly formulated as a weighted bipartite graph perfect matching problem, where the goal is to compute the weights for each edge in the bipartite graph and find the optimal matching that minimizes the total cost (or maximizes the inverse of displacement).
A Bipartite Graph is a special model in graph theory. Mathematically, for an undirected graph $G = (V, E)$, its vertex set $V$ can be partitioned into two disjoint subsets $(A, B)$, such that every edge $(i, j)$ in $E$ connects a vertex in $A$ to a vertex in $B$. There are no edges between vertices within the same subset. In our context:
- Subset $A$ represents the current positions of the follower UAVs.
- Subset $B$ represents the target positions for the followers in the next formation state.
- The weight of an edge $(i, j)$, connecting current position $i$ to target position $j$, is defined as the inverse of the Euclidean displacement between them, i.e., $w_{ij} = 1 / \Delta P_{ij}$.
The solution involves finding a perfect matching (a one-to-one assignment of all current positions to all target positions) that maximizes the sum of these edge weights, which consequently minimizes the total displacement.
Optimal Position Assignment via the KM Algorithm
This research adopts a leader-follower strategy as the foundational drone formation control method and utilizes the KM algorithm to solve the bipartite graph perfect matching problem abstracted from the formation transition and reconfiguration scenario. The KM algorithm efficiently solves the assignment problem for maximum weight matching in balanced bipartite graphs. The procedural flowchart is detailed below, followed by a step-by-step explanation integrated with the drone formation context.
Step 1: Compute Target Formation Positions. Based on the leader’s current position $\vec{P}_L$, velocity $\vec{v}_L$, and the desired formation geometry (defined by relative offsets $\vec{\delta}_k$ for each follower position $k$), calculate the target position $\vec{P}’_k$ for each slot in the new formation at time $t + \Delta t$.
$$
\vec{P}’_L = \vec{P}_L + \vec{v}_L \cdot \Delta t
$$
$$
\vec{P}’_k = \vec{P}’_L + \vec{\delta}_k \quad \text{for } k = 1, 2, …, n-1
$$
where $n$ is the total number of UAVs in the swarm.
Step 2: Calculate Displacement Matrix. For each physical follower UAV $i$ (at current position $\vec{p}_i$) and each target formation slot $j$ (with calculated position $\vec{P}’_j$), compute the Euclidean displacement $\Delta P_{ij}$.
$$
\Delta P_{ij} = \| \vec{p}_i – \vec{P}’_j \| = \sqrt{(p_{xi} – P’_{xj})^2 + (p_{yi} – P’_{yj})^2 + (p_{zi} – P’_{zj})^2}
$$
where $0 < i, j \leq n-1$.
Step 3: Define Edge Weights for the Bipartite Graph. Since the KM algorithm finds a matching that maximizes the sum of edge weights, but we wish to minimize total displacement, we define the weight as the reciprocal of the displacement (optionally normalized).
$$
w_{ij} = \frac{1}{\Delta P_{ij}}
$$
A summary table of these calculations for a small example is shown below:
| Current Follower $i$ | Target Slot $j$ | Displacement $\Delta P_{ij}$ (m) | Edge Weight $w_{ij}$ (1/m) |
|---|---|---|---|
| F1 | S1 | 150.5 | 0.00664 |
| F1 | S2 | 89.2 | 0.01121 |
| F2 | S1 | 210.3 | 0.00475 |
| F2 | S2 | 45.7 | 0.02188 |
Step 4: Initialize Vertex Labels (Feasible Labels). Initialize labels for vertices in subsets $A$ (current positions) and $B$ (target slots). Let $u_i$ be the label for vertex $i$ in $A$, and $v_j$ for vertex $j$ in $B$. A common initialization is:
$$
v_j = 0 \quad \text{for all } j \in B
$$
$$
u_i = \max_{j \in B} (w_{ij}) \quad \text{for all } i \in A
$$
This initialization ensures the feasibility condition: $u_i + v_j \ge w_{ij}$ for all edges $(i, j)$.
Step 5 & 6: Find Maximum Matching via KM Algorithm. The core iterative process of the KM algorithm is executed:
- For each follower $i$ in $A$, attempt to find an augmenting path in the equality subgraph $G_l$ (the graph containing only edges where $u_i + v_j = w_{ij}$) using a method like the Hungarian algorithm.
- If a perfect matching (an augmenting path for all $i$) is not found, adjust the vertex labels. Find the minimum slack value $d$:
$$ d = \min_{i \in A, j \in B, i \text{ visited}, j \text{ not visited}} (u_i + v_j – w_{ij}) $$
Then update labels:
$$ u_i := u_i – d \quad \text{for visited } i \in A $$
$$ v_j := v_j + d \quad \text{for visited } j \in B $$
This creates new edges in the equality subgraph. - Repeat the search for augmenting paths with the updated labels until a perfect matching $M^*$ is found. This matching assigns each current follower $i$ to a unique target slot $j$, minimizing the sum of displacements.
Step 7: Output the Optimal Assignment. The algorithm outputs the optimal assignment mapping $\phi: i \rightarrow j$, meaning follower UAV $i$ is assigned to move to target slot position $\vec{P}’_j$.
Thrust Calculation for Trajectory Control
Once the target position $\vec{P}’_{\phi(i)}$ for each follower $i$ is determined via the KM assignment, a control law is applied to generate the required thrust. We employ a straightforward physics-based model derived from Newton’s second law.
Step 1: Compute Required Displacement Vector. For follower $i$, calculate the displacement vector $\vec{d}_i$ from its current position $\vec{p}_i$ to its assigned target position.
$$
\vec{d}_i = \vec{P}’_{\phi(i)} – \vec{p}_i
$$
Step 2: Compute Desired Velocity Vector. Given the time interval $\Delta t$ to achieve the displacement, the desired velocity vector $\vec{v}_{i,des}$ is:
$$
\vec{v}_{i,des} = \frac{\vec{d}_i}{\Delta t}
$$
Step 3: Compute Required Acceleration Vector. Based on the current velocity $\vec{v}_i$ and the desired velocity $\vec{v}_{i,des}$, compute the necessary acceleration $\vec{a}_i$, respecting the UAV’s maximum acceleration capability $a_{max}$.
$$
\vec{a}_i = \min\left( \frac{\| \vec{v}_{i,des} – \vec{v}_i \|}{\Delta t},\ a_{max} \right) \cdot \frac{\vec{v}_{i,des} – \vec{v}_i}{\| \vec{v}_{i,des} – \vec{v}_i \|}
$$
This formulation ensures the acceleration vector points in the direction of the required velocity change and is capped at the physical limit $a_{max}$.
Step 4: Compute Command Thrust Vector. Finally, applying Newton’s second law, the required thrust force $\vec{F}_i$ for follower UAV $i$ with mass $m_i$ is:
$$
\vec{F}_i = m_i \cdot \vec{a}_i
$$
This thrust vector, along with attitude control, is used to drive the UAV toward its assigned position in the drone formation. The control loop for a single follower can be summarized by the following block diagram/equation chain:
$$
\vec{p}_i \xrightarrow[\text{KM}]{\text{Assignment}} \vec{P}’_{\phi(i)} \rightarrow \vec{d}_i \rightarrow \vec{v}_{i,des} \rightarrow \vec{a}_i \rightarrow \vec{F}_i
$$
Simulation Experiments and Validation
The speed at which a drone formation converges to a specified geometry and its ability to maintain that geometry are two critical metrics for evaluating intelligent formation control algorithms. To test these metrics for our proposed method, we designed the following simulation experiments.
Experiment 1: Formation Generation and Maintenance
We consider a drone formation composed of 120 homogeneous UAVs. The initial state simulates a dispersal from a carrier vehicle: 119 followers are initialized with positions following a Gaussian distribution centered on the leader’s location. The leader then proceeds toward a designated target point, while the followers are required to form and maintain a pre-defined “V” formation (wedge formation) as they follow the leader. The detailed simulation parameters are listed in the table below.
| Parameter Name | Value |
|---|---|
| Leader Initial Position | [0, 0, 5000] m |
| Follower Initial Position Noise | 200 * $\mathcal{N}$(0,1) m |
| Initial Velocity (All UAVs) | 200 m/s |
| Initial Yaw, Pitch | 90°, 0° |
| Target Position | [4000, 6000, 0] m |
| Target Velocity | 100 m/s |
| Target Yaw, Pitch | 45°, 0° |
| Number of UAVs | 120 |
| V-formation Angle | 60° |
| Formation Layers | 3 |
| Inter-layer Spacing | 50 m |
| Intra-layer UAV Spacing | 100 m |
The simulation results are illustrated in the trajectory plots. The trajectories show the UAV swarm initializing near the starting area. The leader moves toward the target, and the 119 followers successfully organize into the specified V-shaped drone formation and maintain it throughout the flight to the target region. The movement is smooth, and the formation’s topological structure remains consistent, demonstrating good stability and coordination.
To quantify the performance, we examine the position tracking for a sample follower (UAV #1). Its initial position error relative to its assigned slot in the V-formation was nearly 1000 meters. Under the control of our algorithm, the errors in the x, y, and z axes were reduced to negligible levels within approximately 7, 3, and 2 seconds, respectively. Subsequently, during the following flight, only minimal tracking errors persisted. This confirms that our proposed drone formation control method exhibits rapid convergence during formation generation and excellent maintenance capabilities once the formation is established.
Experiment 2: Formation Reconfiguration
To validate the adaptability and effectiveness of the control method during shape transitions, a second experiment was conducted. The initial drone formation is a circular pattern. At the simulation time $t = 20$ seconds, a command is issued to reconfigure into a linear (line-ahead) formation. The formation parameters before and after the switch are detailed below.
| Parameter Name | Value (Circular Formation) | Value (Linear Formation) |
|---|---|---|
| Number of UAVs | 120 | 120 |
| Formation Layers | 3 | 3 |
| Inter-layer Spacing | 50 m | 50 m |
| Intra-layer UAV Spacing | 200 m | 100 m |
| Reconfiguration Trigger Time | N/A | 20 s |
The trajectory plot for this experiment clearly shows the initial circular drone formation. At $t=20s$, the formation begins its transition. The KM algorithm instantly computes the optimal reassignment of all followers to new positions in the linear formation. The followers swiftly move to their new assignments, while the leader continues its path. The transition is executed smoothly and efficiently, with the swarm successfully achieving and maintaining the new linear formation geometry on its way to the target. This experiment underscores the method’s capability for rapid and optimal drone formation reconfiguration.
Conclusion
This study has effectively modeled the physical structure of a drone formation using graph theory principles. Building upon this foundation, we proposed a novel formation control method centered on the Kuhn-Munkres algorithm. This approach elegantly transforms the problems of formation generation, maintenance, and reconfiguration into a mathematical graph matching problem. The core strength lies in using the KM algorithm to provide a globally optimal position assignment for follower UAVs during transitions, minimizing total movement. This assignment is seamlessly integrated with a physics-based thrust calculation derived from Newton’s second law to achieve precise trajectory control.
Simulation experiments involving a 120-UAV swarm demonstrated the method’s effectiveness. The results validated key performance metrics: rapid convergence to a desired V-formation from a disordered state, stable maintenance of the formation during flight, and efficient, optimal reconfiguration from a circular to a linear pattern. The method exhibits both the quick response associated with centralized-like optimization and the scalability inherent in solving a well-defined assignment problem. Future work will focus on integrating this core formation control method with higher-level mission planning, real-time situational awareness and data fusion, and dynamic path planning algorithms. Such integration will provide a comprehensive research foundation for unlocking the full potential of autonomous drone formation capabilities in complex operational environments.