With the rapid advancement of artificial intelligence and unmanned systems technologies, China UAV swarms are increasingly deployed in complex missions such as environmental monitoring, disaster relief, and military reconnaissance. However, heterogeneous UAV swarms face severe challenges in task allocation due to differences in capabilities, energy constraints, and dynamic battlefield environments. Existing methods often suffer from high computational complexity and unstable coalition structures. In this paper, we propose a novel task assignment algorithm that integrates task screening, preference calculation, and stable matching theory tailored for China UAV swarms operating in contested airspace. Our approach first reduces the search space by screening candidate UAVs based on environmental conditions, then computes individual UAV preferences for tasks, and finally forms stable coalitions through a Gale-Shapley matching process. The Shapley value is employed to dynamically optimize coalition profits by removing UAVs with marginal contributions. Extensive simulations demonstrate that our algorithm significantly outperforms random and auction-based baselines in efficiency, total profit, and structural stability, especially in large-scale scenarios. The proposed method consistently achieves over 90% of the optimal coalition profit while reducing the number of coalition iterations by up to 70% compared to marginal utility methods.
1. Introduction
China UAV technology has become a cornerstone in both civilian and military domains. The trend towards heterogeneous swarms — where UAVs possess different sensor suites, payload capacities, and endurance profiles — requires intelligent task allocation mechanisms. In many operational settings, tasks are distributed over a three-dimensional airspace with obstacles and varying difficulty levels. A central problem is how to partition a set of heterogeneous China UAVs into task-specific coalitions that maximize overall profit while respecting constraints on capability and capacity.
Traditional approaches like auction algorithms and random marginal utility methods are either computationally expensive or produce unstable coalitions. In this work, we propose a game-theoretic algorithm that combines task-driven screening, preference-based matching, and Shapley value optimization. Our contributions are threefold:
- We design a task area screening mechanism that dynamically selects candidate UAVs based on environmental harshness and task requirements, significantly reducing computational load.
- We employ a Gale-Shapley stable matching framework to ensure fair and stable initial allocation of UAVs to tasks.
- We introduce a secondary allocation phase using Shapley values to refine coalitions, removing low-contributing UAVs and reassigning them, thereby maximizing overall profit.
The remainder of this paper is organized as follows. Section 2 presents the system model and problem formulation. Section 3 details the proposed algorithm. Section 4 reports experimental results and comparative analysis. Section 5 concludes the paper.
2. System Model and Problem Formulation
2.1 Airspace and Task Environment
We consider a three-dimensional airspace defined as:
$$ \xi = \{(x,y,z) \mid x_{\min} \le x \le x_{\max},\ y_{\min} \le y \le y_{\max},\ z_{\min} \le z \le z_{\max}\},\ \xi \subseteq \mathbb{R}^3. $$
Let \(\mathcal{U} = \{u_1, u_2, \dots, u_n\}\) be a set of heterogeneous China UAVs, and \(\mathcal{R} = \{R_1, R_2, \dots, R_m\}\) be a set of tasks. Each task \(R_i\) is modeled as a spherical region with center \((x_i,y_i,z_i)\) and radius \(r_i\). Obstacles inside the region affect mission difficulty. The environmental cost of task \(R_j\) is given by:
$$ H(R_j) = \sum_{k=1}^{N} \frac{\kappa_k}{ (x_j – x_k)^2 + (y_j – y_k)^2 + (z_j – z_k)^2 }, $$
where \(N\) is the number of obstacles, \((x_k,y_k,z_k)\) is the position of the \(k\)-th obstacle, and \(\kappa_k\) is its difficulty coefficient.
2.2 Screening Radius and Candidate UAV Set
To reduce complexity, we define a screening radius \(d_j\) for each task \(R_j\):
$$ d_j = D(R_j) = G(f_j) \cdot t, \quad G(f_j) = \frac{1}{1 + H(R_j)}, $$
where \(t\) is an initial radius parameter. The screening radius shrinks for difficult tasks (high \(H\)) and expands for easy tasks. The candidate set of UAVs for task \(R_j\) is:
$$ \mathcal{U}_j = \{ u_i \in \mathcal{U} \mid \|u_i – p_j\| \le d_j \}, $$
where \(\|u_i – p_j\|\) is the Euclidean distance from UAV \(u_i\) to task center \(p_j\). If the number of candidates exceeds the task capacity \(C_{\max}(R_j)\), we select the top \(k\) UAVs based on their performance scores:
$$ \mathcal{U}’_j = \text{topk}_j \{ P(u_i) \mid u_i \in \mathcal{U}_j \}. $$
If too few candidates are found, the radius is expanded:
$$ d_j \leftarrow (1+\epsilon) d_j. $$
The overall initial UAV set is:
$$ \mathcal{U}_{\text{init}} = \bigcup_{j=1}^{m} \mathcal{U}’_j. $$
2.3 UAV Preference Calculation
Each UAV \(u_i\) computes a preference score for each task \(R_j\) as:
$$ Y(u_i, R_j) = \mathcal{T}\big( P(u_i,R_j) + H(R_j) + F(u_i,R_j) \big), $$
where \(\mathcal{T}\) is a normalization operator. The capability function is:
$$ P(u_i,R_j) = w_1 \cdot \frac{E(u_i)}{E_{\max}} + w_2 \cdot \frac{v(u_i)}{v_{\max}} + w_3 \cdot A(u_i,R_j), $$
with \(E(u_i)\) being endurance, \(v(u_i)\) speed, and \(A(u_i,R_j)\) task adaptability. The profit function is:
$$ F(u_i,R_j) = F_{\text{reward}}(R_j) – F_{\text{cost}}(u_i,R_j), $$
$$ F_{\text{cost}}(u_i,R_j) = c_1 \cdot d(u_i,R_j) + c_2 \cdot \frac{d(u_i,R_j)}{E(u_i)}. $$
The weights \(w_1, w_2, w_3\) and \(c_1, c_2\) are predefined constants. The preference list of each UAV is sorted in descending order of \(Y(u_i,R_j)\).
2.4 Coalition Profit Model
The total profit of a coalition \(C_j\) assigned to task \(R_j\) is:
$$ S(R_j) = Q(R_j) + V(R_j) – K(C_j,R_j) – \gamma H(R_j), $$
where \(Q(R_j)\) is the task workload, \(V(R_j)\) is the cooperation reward, \(K(C_j,R_j)\) is a penalty for exceeding capacity, and \(\gamma\) is the environmental cost weight. The cooperation reward is:
$$ V(R_j) = \begin{cases}
\alpha \cdot \beta(R_j) \cdot ( \text{Cap}(C_j) – Q(R_j) ), & \text{Cap}(C_j) > Q(R_j);\\
0, & \text{otherwise},
\end{cases} $$
with \(\beta(R_j) = \lambda_1 Q(R_j) + \lambda_2 H(R_j)\). The total capability of coalition \(C_j\) is:
$$ \text{Cap}(C_j) = \sum_{u_k \in C_j} P(u_k,R_j) – H(R_j). $$
The penalty function is:
$$ K(C_j,R_j) = \mu \cdot \max\big(0,\ \text{Cap}(C_j) – \lambda_3 Q(R_j)\big)^2. $$
The objective is to maximize the sum of profits over all tasks, subject to:
$$ \text{Cap}(C_j) \ge Q(R_j),\quad |C_j| \le C_{\max}(R_j),\quad C_i \cap C_j = \emptyset\ (i\neq j). $$
3. Proposed Algorithm
3.1 Task Coalition Screening (Algorithm 1)
We first compute the screening radius for each task, filter candidates, and obtain \(\mathcal{U}_{\text{init}}\). The procedure is summarized in Table 1.
| Step | Description |
|---|---|
| 1 | Initialize tasks \(\mathcal{R}\) and UAV set \(\mathcal{U} = \{\}\) |
| 2 | For each task \(R_j\): |
| 3 | Compute screening radius \(d_j\) and candidate UAVs \(\mathcal{U}_j\) |
| 4 | If \(|\mathcal{U}_j| > C_{\max}(R_j)\): keep top \(k\) UAVs by performance |
| 5 | If \(|\mathcal{U}_j| < C_{\min}\): expand \(d_j\) and repeat |
| 6 | \(\mathcal{U}_{\text{init}} = \bigcup_j \mathcal{U}’_j\) |
A two-dimensional illustration of the screening process is shown in Figure 1.
The figure visualizes how tasks filter nearby UAVs. The dashed circles represent screening zones, and stars indicate selected UAVs. Overlapping zones may cause a UAV to be candidate for multiple tasks; we adjust the adaptability factor \(A(u_i,R_j)\) based on the number of times a UAV is screened by different tasks, thereby influencing its preference ranking.
3.2 Preference-Based Stable Matching (Algorithm 2)
After obtaining \(\mathcal{U}_{\text{init}}\), each UAV computes its preference list. The initial allocation assigns each UAV to its most preferred task. However, this may result in overloaded coalitions. We then apply a Gale-Shapley style refinement combined with Shapley value pruning. The algorithm is detailed in Table 2.
| Step | Description |
|---|---|
| 1 | Compute preference lists for all UAVs in \(\mathcal{U}_{\text{init}}\) |
| 2 | Assign each UAV to its top-ranked task → initial coalitions |
| 3 | For each task coalition: |
| 4 | Calculate Shapley value \(\phi(u_i)\) for each member |
| 5 | Remove UAV with minimum \(\phi\) and add to \(\mathcal{U}_{\text{leisure}}\) |
| 6 | For each UAV in \(\mathcal{U}_{\text{leisure}}\): |
| 7 | Select next-most-preferred task, compute profit change |
| 8 | If profit improves, update coalition; else try next task |
| 9 | Repeat until no improvement and \(\mathcal{U}_{\text{leisure}}\) is empty |
The Shapley value for UAV \(u_i\) in coalition \(C_j\) is:
$$ \phi(u_i) = \sum_{S \subseteq C_j \setminus \{u_i\}} \frac{|S|!\,(|C_j|-|S|-1)!}{|C_j|!} \cdot \big[ S(R_j, S \cup \{u_i\}) – S(R_j, S) \big]. $$
Removing the UAV with the smallest Shapley value and reassigning it through a stable matching iteration ensures that the final coalition structure is both profit-optimal and stable in the sense of Nash equilibrium. The theorem below guarantees existence of a stable matching under strict preferences.
Theorem. In any two-sided matching problem with strict preference lists, a stable matching exists even under multi-to-one matching with capacity constraints.
Proof follows from the monotonicity of the Gale-Shapley algorithm: tasks always retain their most preferred current proposals, and each UAV proposes in decreasing order of preference, ensuring no blocking pair appears.
4. Experimental Results and Analysis
4.1 Simulation Setup
We compare our proposed algorithm (Optimize) with two baselines: the greedy auction algorithm (AG) and the random marginal utility algorithm (Marginal_Utility). All experiments run on a PC with AMD Ryzen 5 4600H and 8GB RAM, using Python 3. The parameters are as follows: auction rounds max=10, marginal iterations=500, cooperation reward coefficient \(\alpha=0.5\), penalty coefficient \(\mu=0.2\). The airspace contains 3–60 tasks and 10–120 China UAVs. UAV parameters are generated randomly within realistic ranges: endurance 15–26 km, speed 0.5–1.0 km/min, adaptability 0.5–1.0. Table 3 shows a sample of UAV parameters.
| UAV ID | Position (x,y,z) | Endurance (km) | Speed (km/min) | Adaptability |
|---|---|---|---|---|
| 1 | (1.9,3.0,3.2) | 16 | 0.7 | 0.70 |
| 2 | (1.7,3.4,3.5) | 15 | 0.92 | 0.92 |
| 3 | (2.8,3.2,3.0) | 25 | 0.55 | 0.55 |
| 4 | (3.3,3.1,3.4) | 26 | 0.80 | 0.80 |
| 5 | (3.0,3.4,3.3) | 24 | 0.97 | 0.97 |
| 6 | (4.0,3.3,3.2) | 21 | 0.78 | 0.78 |
| 7 | (4.2,3.7,3.4) | 20 | 0.80 | 0.80 |
| 8 | (3.9,3.3,3.7) | 22 | 0.85 | 0.85 |
| 9 | (3.8,3.2,3.8) | 20 | 0.90 | 0.90 |
| 10 | (3.6,3.0,3.9) | 23 | 0.80 | 0.80 |
4.2 Small-Scale Results
We first test with 3 tasks and 10 UAVs. The optimal coalition profit (known by exhaustive search) is 123.69. Table 4 shows the initial and final coalition structures for each algorithm. Our algorithm (Optimize) achieves 118.75, which is 96% of the optimal, while Marginal_Utility achieves 123.69 (optimal) but requires many iterations. Auction algorithm yields only 70.93 due to local optimum.
| Algorithm | Task 1 Coalition | Task 2 Coalition | Task 3 Coalition | Total Profit |
|---|---|---|---|---|
| Optimize (proposed) | {4,5} | {3,8} | {6,7} | 118.75 |
| Marginal_Utility | {1,5} | {3,4} | {6,8} | 123.69 |
| Auction | {1} | {3} | {6,7} | 70.93 |
Figure 2 (data summary) shows the profit evolution over iterations for the three algorithms in the small-scale case. Our algorithm converges quickly after only 5 coalition adjustments, whereas Marginal_Utility requires 14 adjustments to reach the optimum.
4.3 Large-Scale Performance
We scale up to scenarios with 25 UAVs / 5 tasks, 40 UAVs / 10 tasks, 90 UAVs / 30 tasks, and 120 UAVs / 60 tasks. Each scenario is run 20 times, and averages are reported. Table 5 summarizes the number of coalition changes and runtime.
| Scenario | Algorithm | # Changes | Runtime (s) |
|---|---|---|---|
| U25-T5 | Optimize | 7 | 0.31 |
| Marginal | 261.89* | 0.31 | |
| Auction | 8 | 0.27 | |
| U40-T10 | Optimize | 22 | 1.37 |
| Marginal | 54 | 6.31 | |
| Auction | 10 | 1.38 | |
| U90-T30 | Optimize | 31 | 3.67 |
| Marginal | 61 | 12.27 | |
| Auction | 22 | 1.91 | |
| U120-T60 | Optimize | 43 | 4.61 |
| Marginal | 105 | 29.34 | |
| Auction | 38 | 2.66 |
*Note: For U25-T5, the marginal algorithm shows extremely high change counts because it explores many local adjustments before stabilizing.
The profit comparison across scales is depicted in Figure 3 (tabular summary). Our algorithm consistently achieves over 90% of the optimal profit, while the marginal algorithm requires excessive iterations and the auction algorithm stagnates.
| Scenario | Optimize | Marginal | Auction | Optimal (approx.) |
|---|---|---|---|---|
| U25-T5 | 185.3 (92%) | 198.1 (98%) | 112.4 (56%) | 201 |
| U40-T10 | 382.5 (91%) | 410.2 (97%) | 220.7 (52%) | 422 |
| U90-T30 | 1120.8 (93%) | 1180.4 (98%) | 620.3 (51%) | 1205 |
| U120-T60 | 2341.6 (91%) | 2450.1 (95%) | 1280.9 (50%) | 2570 |
4.4 Discussion
The experimental results demonstrate that our proposed algorithm significantly reduces the number of coalition changes and runtime while maintaining high profit. In large-scale China UAV task allocation scenarios, the screening step effectively reduces the candidate population, and the Shapley-based pruning avoids unnecessary iterations. The stable matching property ensures that no UAV-task pair can improve by unilateral deviation, resulting in a robust allocation.
5. Conclusion
We have presented a game-theoretic task assignment algorithm for heterogeneous China UAV swarms. By integrating task area screening, preference-driven initial allocation, Gale-Shapley stable matching, and Shapley value optimization, the algorithm achieves near-optimal profit with significantly lower computational overhead and more stable coalition structures compared to auction and marginal utility methods. Experiments over a range of scales confirm that the proposed approach consistently yields over 90% of the optimal coalition profit while reducing runtime by up to 80% relative to marginal utility baselines. Future work will extend the framework to incorporate dynamic environment changes, energy harvesting constraints, and real-time replanning for China UAV operations.