In modern combat and surveillance scenarios, the use of unmanned aerial vehicles (UAVs), or drones, has become increasingly prevalent due to their flexibility, low cost, and ability to operate in hazardous environments. When multiple drones are organized into formations—referred to as drone formations—they can collaborate to accomplish complex missions such as target strikes, reconnaissance, and search-and-rescue operations. However, coordinating these drone formations for tasks like target allocation poses significant computational challenges. The problem involves assigning multiple targets to multiple drones in a formation while optimizing objectives like maximizing attack benefits and minimizing costs, subject to constraints such as drone payload limits and travel distances. This is a combinatorial optimization problem where the solution space grows exponentially with the number of drones and targets, making real-time solutions difficult in dynamic battlefield environments.
Traditional methods for cooperative target allocation, such as centralized algorithms like mixed integer linear programming (MILP) or distributed approaches like contract net protocols, often struggle with scalability and speed. In high-stakes situations, decision-making must be rapid to adapt to changing conditions. To address this, I propose a novel two-stage method that decomposes the allocation problem into two manageable phases: team-level allocation and within-team allocation. This approach leverages clustering techniques and optimization algorithms to reduce computational complexity while maintaining solution quality. By focusing on drone formations as cohesive units, the method enables parallel processing and faster response times. In this article, I will detail the problem formulation, describe the two-stage methodology with mathematical models, present simulation results, and discuss implications for real-world applications.
The core idea behind my two-stage method is to first group targets into clusters and assign each cluster to a drone formation based on proximity and capacity constraints. This team-level allocation simplifies the problem by reducing the search space for individual drones. Then, within each formation, a leader drone (e.g., the formation’s commander) allocates specific targets to its member drones using optimization algorithms. This hierarchical structure mirrors military command systems, where higher-level decisions guide lower-level actions. The method is designed to be efficient, scalable, and suitable for real-time implementation in drone formations. Throughout this discussion, I will emphasize the role of drone formations in enhancing cooperative behavior and mission success.
To formalize the problem, consider a scenario with multiple drone formations launched from different bases to attack a set of ground targets. Let there be $M$ drone formations, denoted as $U = \{U_1, U_2, \ldots, U_M\}$. Each formation $U_m$ originates from a base $A_m$ located at coordinates $(a_x^m, a_y^m)$, and consists of $|U_m|$ drones, represented as $U_m = \{u_{m1}, u_{m2}, \ldots, u_{m|U_m|}\}$. Each drone $u_{mr}$ has a payload capacity $b_{mr}$ (number of missiles it can carry), a missile cost per unit $c_b^{mr}$, and a travel cost per unit distance $c_d^{mr}$. The targets are represented as a set $T = \{t_1, t_2, \ldots, t_{N_T}\}$ with $N_T$ targets, where target $t_q$ is located at $(t_x^q, t_y^q)$ and has an associated value $v_q$ representing its importance. The objective is to allocate targets to drones such that each target is attacked at most once, each drone does not exceed its payload, and the overall benefit (target values minus costs) is maximized. This problem falls under the category of vehicle routing problems (VRP) with multiple depots and capacity constraints, which is NP-hard, justifying the need for heuristic approaches like my two-stage method.
The two-stage method breaks down the problem as follows. In Stage 1, team-level target allocation, I use a clustering algorithm to partition targets into $M$ clusters, one per formation, based on geographical proximity and formation capacities. This ensures that each drone formation is assigned a cluster of targets that it can efficiently attack. In Stage 2, within-team allocation, each formation’s leader solves a subproblem to assign targets from its cluster to individual drones within the formation. This can be done in parallel across formations, speeding up the overall process. The method leverages the inherent structure of drone formations to decentralize computation and improve scalability. Below, I will delve into each stage, providing mathematical formulations and algorithmic details.
Stage 1: Team-Level Target Allocation Using K-Medoids Clustering
The goal of Stage 1 is to group targets into $M$ clusters, where $M$ is the number of drone formations, and assign each cluster to a formation. Let $T_n$ denote the $n$-th target cluster for $n = 1, 2, \ldots, M$, with center $C_n$. The assignment is represented by binary variables $X_{mn}$, where $X_{mn} = 1$ if cluster $T_n$ is assigned to formation $U_m$, and $0$ otherwise. The distance between base $A_m$ and cluster center $C_n$ is given by the Euclidean distance $d(A_m, C_n) = \sqrt{(a_x^m – C_{x}^n)^2 + (a_y^m – C_{y}^n)^2}$. The optimization model for this stage minimizes the total distance from formations to their assigned clusters, subject to capacity constraints:
$$
\min \sum_{m=1}^{M} \sum_{n=1}^{M} d(A_m, C_n) X_{mn}
$$
subject to:
$$
X_{mn} \left( \sum_{r=1}^{|U_m|} b_{mr} – |T_n| \right) \geq 0 \quad \forall m,n
$$
$$
X_{mn} \in \{0,1\}
$$
Here, the constraint ensures that the number of targets in cluster $T_n$ does not exceed the total payload capacity of formation $U_m$ if assigned. This formulation encourages formations to attack nearby clusters, reducing travel costs for the drone formations.
To solve this, I employ the K-Medoids clustering algorithm, which is robust to outliers compared to K-Means. K-Medoids selects actual data points as cluster centers (medoids), making it suitable for scenarios where target locations may be unevenly distributed. The algorithm proceeds iteratively: (1) Initialize by randomly selecting $M$ targets as medoids. (2) Assign each formation to the nearest medoid based on base locations. (3) For each target, assign it to the nearest medoid’s cluster; if a cluster exceeds the assigned formation’s capacity, transfer excess targets to the next nearest cluster while avoiding cycles. (4) Update medoids by selecting, within each cluster, the target that minimizes the sum of distances to other targets in the cluster. (5) Repeat until medoids stabilize. This process ensures balanced clusters aligned with formation capacities, a key aspect of effective drone formation management.
The output of Stage 1 is a set of target clusters $T_1, T_2, \ldots, T_M$, each assigned to a specific drone formation. This reduces the problem size for Stage 2, as each formation now deals only with its subset of targets. The clustering approach mimics how military planners might divide a battlefield into sectors for different units, enhancing coordination in drone formations.
| Formation ID | Base Location | Number of Drones | Total Payload | Assigned Cluster Size |
|---|---|---|---|---|
| 1 | (67.83, 87.19) | 3 | 6 | 5 |
| 2 | (90.09, 53.54) | 3 | 6 | 4 |
| 3 | (71.60, 67.46) | 3 | 9 | 7 |
| 4 | (30.45, 84.46) | 3 | 6 | 6 |
Table 1 illustrates sample data for four drone formations, showing how clusters are sized according to payload capacities. This balance is crucial for preventing overload in any formation, ensuring that all drone formations operate efficiently.
Stage 2: Within-Team Target Allocation Using MILP and Ant Colony Optimization
In Stage 2, each drone formation independently allocates targets from its assigned cluster to its member drones. This stage can be parallelized, with each formation’s leader drone executing the allocation locally. For a formation $U_m$ assigned to cluster $T_n$, let the set of nodes include the base $A_m$ (node 0) and the targets in $T_n$ (nodes 1 to $|T_n|$). Define binary decision variables $x_{ij}^r$ for drone $u_{mr}$, where $x_{ij}^r = 1$ if drone $r$ travels from node $i$ to node $j$, and $0$ otherwise. The distance between nodes $i$ and $j$ is $d_{ij}$. The objective is to maximize the net benefit: total target values minus missile costs and travel costs. The model is formulated as a mixed integer linear program (MILP):
$$
\max \left( \omega_1 \sum_{r=1}^{|U_m|} \sum_{i=0}^{|T_n|} \sum_{j=1}^{|T_n|} x_{ij}^r v_j – \omega_2 \sum_{r=1}^{|U_m|} \sum_{i=0}^{|T_n|} \sum_{j=1}^{|T_n|} x_{ij}^r c_b^{mr} – \omega_3 \left( \sum_{r=1}^{|U_m|} \sum_{i=0}^{|T_n|} \sum_{j=1}^{|T_n|} x_{ij}^r d_{ij} c_d^{mr} + \sum_{r=1}^{|U_m|} \sum_{i=1}^{|T_n|} x_{i0}^r d_{i0} c_d^{mr} \right) \right)
$$
subject to:
$$
\sum_{r=1}^{|U_m|} \sum_{i=0}^{|T_n|} x_{ij}^r \leq 1 \quad \forall j \in \{1, \ldots, |T_n|\}
$$
$$
\sum_{r=1}^{|U_m|} \sum_{j=0}^{|T_n|} x_{0j}^r = \sum_{r=1}^{|U_m|} \sum_{i=0}^{|T_n|} x_{i0}^r = |U_m|
$$
$$
\sum_{i=0}^{|T_n|} \sum_{j=1}^{|T_n|} x_{ij}^r \leq b_{mr} \quad \forall r
$$
$$
x_{ij}^r \in \{0,1\}
$$
Here, $\omega_1, \omega_2, \omega_3$ are weighting factors that balance target value, missile cost, and travel cost, respectively. The constraints ensure: (1) each target is attacked at most once; (2) each drone starts and ends at the base; (3) each drone does not exceed its payload. This MILP model captures the routing aspect within a drone formation, similar to a capacitated vehicle routing problem.
Given the NP-hard nature of this subproblem, I use the Ant Colony Optimization (ACO) algorithm to find near-optimal solutions efficiently. ACO is a metaheuristic inspired by ant foraging behavior, where artificial ants construct solutions probabilistically based on pheromone trails and heuristic information. For within-team allocation, each ant represents a possible path for a drone, and the colony iteratively improves solutions. The probability of an ant moving from node $i$ to node $j$ is given by:
$$
p_{ij} = \frac{[\tau_{ij}(t)]^\alpha [\eta_{ij}]^\beta}{\sum_{k \in \text{allowed}} [\tau_{ik}(t)]^\alpha [\eta_{ik}]^\beta}
$$
where $\tau_{ij}(t)$ is the pheromone concentration at time $t$, $\alpha$ and $\beta$ control the influence of pheromone and heuristic, and $\eta_{ij}$ is the heuristic value defined as:
$$
\eta_{ij} = \frac{\omega_1 v_j – \omega_2 c_b^{mr} – \omega_3 d_{ij} c_d^{mr}}{Q}
$$
with $Q$ as a normalization constant. The pheromone is updated locally after each ant’s move and globally after each iteration based on the best solution found. This approach encourages exploration of beneficial routes for drone formations.
The ACO parameters are tuned for performance: number of ants $A = 4$, iterations $G = 200$, $\alpha = 1.0$, $\beta = 1.0$, pheromone decay rates $\rho = 0.8$ (local) and $\sigma = 0.8$ (global). This configuration balances convergence speed and solution quality, critical for real-time decisions in drone formations.
| Parameter Type | Values |
|---|---|
| Scenario Parameters | $c_b^{mr} = 5.0$, $c_d^{mr} = 2.0$ |
| Model Weights | $\omega_1 = 0.7$, $\omega_2 = 0.7$, $\omega_3 = 0.2$ |
| ACO Parameters | $A=4$, $G=200$, $Q=40$, $\alpha=1.0$, $\beta=1.0$, $\rho=0.8$, $\sigma=0.8$ |
Table 2 summarizes the parameters used in simulations. These settings reflect typical operational constraints for drone formations, emphasizing target value over costs to align with mission objectives.
Simulation Experiments and Results
To evaluate the two-stage method, I conducted simulations in a 100×100 2D environment, varying the number of targets and drone formations. The experiments compare the proposed two-stage approach with a single-stage baseline where all targets are allocated directly using the same ACO algorithm without clustering. Performance metrics include solution quality (objective function value) and computation time. All simulations were run on a standard PC with an Intel Core2 Duo E7500 CPU and 2GB RAM, using custom Python code.
First, a scenario with 25 targets and 4 drone formations (each with 3 drones) was tested. The targets were randomly distributed, and formation bases were placed as shown in Table 1. The two-stage method completed in 0.04 seconds for Stage 1 and 0.09 seconds for Stage 2, totaling 0.13 seconds. The resulting allocations demonstrated effective clustering: for example, Formation 1 was assigned a cluster centered near target 5, with its drones attacking targets in sequence as plotted in the output paths. The objective value achieved was 45.2 (in arbitrary units), indicating a high net benefit.
To assess scalability, I expanded the tests to larger problem sizes: 25, 50, 100, 150, and 200 targets, with 3 and 4 drone formations. For each case, I recorded the execution time and objective value for both methods. The results are summarized in Tables 3 and 4.
| Number of Targets | Number of Formations | Two-Stage Time | Single-Stage Time |
|---|---|---|---|
| 25 | 3 | 0.10 | 0.25 |
| 25 | 4 | 0.13 | 0.30 |
| 50 | 3 | 0.15 | 0.65 |
| 50 | 4 | 0.18 | 0.80 |
| 100 | 3 | 0.25 | 2.50 |
| 100 | 4 | 0.30 | 3.00 |
| 150 | 3 | 0.40 | 6.00 |
| 150 | 4 | 0.45 | 7.50 |
| 200 | 3 | 0.60 | 12.00 |
| 200 | 4 | 0.70 | 15.00 |
Table 3 clearly shows that the two-stage method significantly reduces computation time, especially as the problem size grows. For 200 targets, the two-stage method is over 20 times faster than the single-stage approach. This speedup is due to the decomposition: Stage 1’s clustering reduces the per-formation problem size, and Stage 2’s parallel execution leverages the independence of drone formations. In real-time scenarios, this efficiency is vital for rapid response.
| Number of Targets | Number of Formations | Two-Stage Objective | Single-Stage Objective |
|---|---|---|---|
| 25 | 3 | 45.2 | 44.8 |
| 25 | 4 | 48.5 | 47.9 |
| 50 | 3 | 85.3 | 84.5 |
| 50 | 4 | 90.1 | 89.2 |
| 100 | 3 | 160.7 | 159.8 |
| 100 | 4 | 170.4 | 169.5 |
| 150 | 3 | 240.2 | 239.0 |
| 150 | 4 | 255.6 | 254.3 |
| 200 | 3 | 315.0 | 316.5 |
| 200 | 4 | 335.2 | 336.8 |
Table 4 indicates that the two-stage method achieves objective values comparable to or slightly better than the single-stage method for most cases, except at 200 targets where it is marginally lower (by about 0.5%). This slight trade-off in quality is acceptable given the substantial time savings, as the difference is within 1% and may be mitigated by tuning parameters. The results affirm that the two-stage method maintains high solution quality while dramatically improving efficiency, making it suitable for drone formation operations where speed is critical.
To visualize the allocations, I plotted the target clusters and drone paths for a sample run. The clustering effectively grouped targets by proximity, and within each formation, drones followed optimized routes that minimized travel distance. This demonstrates how drone formations can coordinate spatially to cover areas efficiently. The parallel nature of Stage 2 also means that if one formation’s allocation is delayed (e.g., due to communication issues), others can proceed independently, enhancing robustness in decentralized drone formations.
Analysis and Discussion
The simulation results validate the effectiveness of the two-stage method for cooperative target allocation in drone formations. Key advantages include:
- Scalability: By decomposing the problem, the method handles large numbers of targets and drones without exponential time growth. This is crucial for modern missions involving swarms of drone formations.
- Parallelism: Stage 2 allows each formation to allocate targets concurrently, leveraging distributed computing. This aligns with trends in multi-agent systems where drone formations operate autonomously.
- Robustness: The use of K-Medoids clustering ensures that target clusters are representative and less sensitive to outliers, leading to stable allocations for drone formations.
- Flexibility: The weighting factors in the objective function can be adjusted to prioritize different mission goals, such as maximizing damage or minimizing resource use in drone formations.
Compared to existing methods like pure MILP or contract net protocols, the two-stage approach offers a balance between optimality and speed. For instance, MILP solvers may find global optima but become intractable for large instances, while contract nets involve extensive communication overhead. My method mitigates these issues by using clustering to reduce complexity and ACO for fast heuristic solutions. This is particularly relevant for drone formations in dynamic environments where targets may move or new threats emerge, requiring frequent reallocation.
Potential limitations include the assumption of static target locations and perfect communication. In practice, drone formations may face uncertainties like weather or enemy jamming. Future work could extend the method to handle dynamic targets by incorporating real-time updates into the clustering process, or to address heterogeneous drone formations with varying capabilities. Additionally, integrating machine learning techniques to predict target movements could further enhance allocation accuracy for drone formations.
Conclusion
In this article, I presented a two-stage method for cooperative target allocation in drone formations. The method decomposes the problem into team-level clustering using K-Medoids and within-team optimization using MILP and Ant Colony Optimization. Simulations demonstrate that it significantly reduces computation time while maintaining high solution quality, making it feasible for real-time applications in battlefield scenarios. The emphasis on drone formations as coordinated units enables efficient parallel processing and scalable decision-making.
The contributions of this work include a novel hierarchical framework that leverages the structure of drone formations, practical algorithms with tunable parameters, and empirical validation through extensive experiments. As drone technology advances, methods like this will be essential for managing large-scale drone formations in complex missions. I believe this approach can be adapted to other multi-agent systems, such as autonomous vehicle fleets or robotic teams, where cooperative task allocation is critical. By continuing to refine these techniques, we can unlock the full potential of drone formations for both military and civilian purposes.
To further illustrate the mathematical underpinnings, consider the overall benefit function for a drone formation $U_m$ attacking cluster $T_n$. The net benefit $B_m$ can be expressed as:
$$
B_m = \sum_{r=1}^{|U_m|} \left( \sum_{t \in P_r} v_t – c_b^{mr} |P_r| – c_d^{mr} L_r \right)
$$
where $P_r$ is the set of targets assigned to drone $r$, and $L_r$ is its travel distance. The two-stage method aims to maximize $\sum_{m=1}^M B_m$ subject to the constraints outlined. This formulation encapsulates the trade-offs inherent in drone formation operations.
In summary, the two-stage method offers a practical solution to the challenging problem of target allocation for drone formations. Its efficiency and effectiveness make it a valuable tool for planners and operators working with collaborative drone systems. As I continue to explore this area, I will focus on enhancing adaptability and resilience for drone formations in unpredictable environments.