With the rapid advancement of drone technology, Unmanned Aerial Vehicle (UAV) swarms have become indispensable in complex operations like search-and-rescue, military reconnaissance, and logistics. As swarm sizes expand and mission scenarios grow more intricate, designing efficient task allocation algorithms presents significant challenges, particularly when handling temporal constraints where subsequent tasks depend on predecessor completion. This dependency creates cross-queue impacts that compromise allocation efficacy and trigger conflicts. To address this, we propose the Temporal Coupling Analysis-based Task Allocation (TCATA) method, which optimizes distributed decision-making while ensuring temporal feasibility.
Problem Formulation
Consider a UAV swarm $\mathcal{U} = \{u_1, \dots, u_n\}$ executing $m$ sequential tasks $\mathcal{T} = \{t_1, \dots, t_m\}$ for survivors $\mathcal{S} = \{s_1, \dots, s_{m/2}\}$. Each survivor requires a search task (type 1) followed by a rescue task (type 2). Heterogeneous UAVs are classified as search ($UT_i=1$) or rescue ($UT_i=2$) agents with maximum velocity $UV_i$, position $UR_i$, and task capacity $L_i$. Task $t_j$ is defined by its location $TR_j$, type $TT_j$, duration $TD_j$, start time $TE_j$, and predecessor constraint $\tau_j$:
$$ \tau_j = \begin{cases}
0 & \text{if } TT_j = 1 \\
TE_{j^\text{pre}} + TD_{j^\text{pre}} & \text{if } TT_j = 2
\end{cases} $$
The objective minimizes cumulative task start times:
$$ \min J = \sum_{i=1}^n \sum_{t_j \in \mathbf{UA}_i} TE_j $$
Subject to temporal, capability, and capacity constraints:
$$ TE_j + TD_j \leq TE_k \quad \forall \text{ rescue tasks } t_k \text{ following search } t_j $$
$$ UT_i = TT_j \quad \forall u_i, \forall t_j \in \mathbf{UA}_i $$
$$ |\mathbf{UA}_i| \leq L_i \quad \forall u_i $$
Temporal Coupling in Market-Based Allocation
Conventional market mechanisms fail under temporal constraints due to cross-queue effects. A task adjustment’s impact propagates beyond its immediate queue, invalidating precomputed utilities. We quantify this by defining an affected queue set $\mathbf{IA}_{i,j}^l$ for task $t_j$ inserted at position $l$ in $u_i$’s queue:
- New executor $u_i$’s queue $\mathbf{UA}_i$.
- Original executor $u_k$’s queue $\mathbf{UA}_k$ (if $t_j$ was assigned).
- Rescue queues for search tasks after $l$ in $\mathbf{UA}_i$.
- Rescue queues for search tasks after removal point in $\mathbf{UA}_k$ (if applicable).
Adjustment utility $w_{i,j}^l$ is the global cost change:
$$ w_{i,j}^l = \sum_{\mathbf{UA}_p \in \mathbf{IA}_{i,j}^l} \left( \sum_{t_q \in \mathbf{UA}_p} TE_q^{\text{new}} – \sum_{t_q \in \mathbf{UA}_p} TE_q^{\text{orig}} \right) $$
Utilities become invalid if dependent queues change during allocation. Traditional conflict resolution fails as adjustments exhibit inter-dependencies modeled through conflict matrix $\mathbf{R}$:
$$ \mathbf{R}_{a,b} = \begin{cases}
1 & \text{if } \mathbf{IA}_a \cap \mathbf{IA}_b = \emptyset \\
0 & \text{otherwise}
\end{cases} $$
TCATA Algorithm
TCATA operates in three phases per iteration:
1. Local Adjustment Set Construction
Each $u_i$ generates candidate adjustments $p_{i,j}^l = (w_{i,j}^l, t_j, u_i, u_k, l, \mathbf{IA}_{i,j}^l, \mathbf{IT}_{i,j}^l, \mathbf{ET}_{i,j}^l)$ for feasible tasks $t_j \notin \mathbf{UA}_i$. After evaluating all positions $l$, it retains top-$\alpha$ proposals $\mathcal{P}_i$.
2. Communication and Consensus
UAVs exchange $\mathcal{P}_i$ via $D$-hop communication ($D$ = network diameter) to build global adjustment set $\mathcal{P}^\text{global}$. Message compression minimizes bandwidth:
| Parameter | Size (bits) |
|---|---|
| Task ID | $\log_2 m$ |
| Executor IDs | $2 \log_2 n$ |
| Insertion Point | $\log_2 L_{\max}$ |
| Utility | 32 (float) |
3. Global Adjustment via Maximum Weighted Clique (MWC)
Conflict-aware selection is modeled as MWC: Graph $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ has vertices for adjustments, edges for non-conflicting pairs ($\mathbf{R}_{a,b}=1$), and vertex weights $w_{i,j}^l$. A greedy algorithm solves:
- Initialize clique $C = \emptyset$, working set $\Omega = \mathcal{V}$.
- Add highest-weight $v_a \in \Omega$ to $C$.
- Remove vertices not adjacent to $v_a$ from $\Omega$.
- Repeat until $\Omega = \emptyset$.
Selected adjustments update global allocation. Iterations continue until convergence.
Simulation Results
We tested TCATA in large-scale search-and-rescue scenarios with communication delay (30 ms/hop). UAVs and tasks scaled from (40, 100) to (160, 400). Comparative analysis against CBBA-TCC, CNP, and distributed GA used:
| Algorithm | Avg. Task End (s) | Iterations | Runtime (s) |
|---|---|---|---|
| TCATA ($\alpha=2$) | 320.72 | 42.6 | 4.38 |
| CBBA-TCC | 323.96 | 107.0 | 21.84 |
| CNP | 348.27 | 452.0 | 13.59 |
| Distributed GA | 407.76 | 300.0 | 12.80 |
TCATA reduced runtimes by >50% versus CBBA-TCC/CNP while improving temporal objectives. The MWC approach enabled conflict-free batch allocation, cutting iterations by 60.2% vs CBBA-TCC. Parameter $\alpha$ balanced computation and communication:
$$ \text{Runtime} = \underbrace{k_1 \alpha n}_{\text{Computation}} + \underbrace{k_2 D \cdot \text{Iterations}}_{\text{Communication}} $$
Modern drone technology benefits from TCATA’s scalability, solving 160-UAV/400-task problems in under 5 seconds.
Conclusion
TCATA efficiently resolves temporal coupling in UAV swarm task allocation by integrating localized adjustment generation with global conflict-aware selection via MWC. Key innovations include temporal-sensitive utility formulation and distributed batch optimization. Future work will explore graph neural networks for enhanced MWC solving and Markov-based temporal impact forecasting. This approach advances autonomous decision-making for large-scale Unmanned Aerial Vehicle operations in latency-sensitive environments.