The efficacy of modern multi-drone operations hinges not merely on the aggregate capability of individual platforms but on the sophisticated, orchestrated behavior of the entire drone formation. A critical enabler for such collaborative autonomy is the task of cooperative target assignment, which involves intelligently allocating the members of a drone formation to a cluster of targets to maximize overall mission effectiveness. This problem is inherently complex, characterized by combinatorial explosion, dynamic constraints, and competing objectives. Among the paramount challenges are the need for computational efficiency to adapt to fast-changing battlespaces and the necessity to enforce temporal coordination among attacks to achieve synergistic effects, such as suppression or sequential strikes. This article presents a fast cooperative target assignment method for a drone formation that explicitly incorporates timing constraints, leveraging the principles of Satisficing Decision Theory (SDT) to balance solution quality with the speed of computation.
The visual precision required for a drone light show, as seen in the image above, mirrors the need for strict spatial and temporal coordination in a combat drone formation. Just as each drone must be at an exact location at a precise moment to contribute to the overall image, each member of a tactical drone formation must engage its target within a specific time window and sequence to ensure mission success.
1. Problem Formulation for Drone Formation Target Assignment
We consider a cooperative engagement scenario where a drone formation \(F\) consisting of \(N\) unmanned aerial vehicles (UAVs) is tasked with engaging a target cluster \(C\) containing \(M\) distinct targets. The drone formation \(F\) and target cluster \(C\) are defined as:
$$ F = \{U_1, U_2, …, U_N\} $$
$$ C = \{T_1, T_2, …, T_M\} $$
The core decision is to determine which drone attacks which target. We define a binary decision variable \(x_{i,j}\):
$$ x_{i,j} = \begin{cases}
1, & \text{if drone } U_i \text{ is assigned to attack target } T_j\\
0, & \text{otherwise}
\end{cases}
\quad \forall i \in \{1,…,N\}, \forall j \in \{1,…,M\} $$
The canonical target assignment problem for a drone formation can be framed as an optimization problem with the following typical constraints:
$$
\begin{aligned}
& \max && J(x_{1,1}, …, x_{N,M}) \\
& \text{s.t.} && \sum_{j=1}^{M} x_{i,j} \leq 1, \quad \forall i \quad \text{(One drone, one target)} \\
& && \sum_{i=1}^{N} x_{i,j} \geq 1, \quad \forall j \quad \text{(Each target must be attacked)}
\end{aligned}
$$
The objective function \(J\) traditionally aggregates measures of expected engagement benefit (e.g., probability of kill, target value) and cost (e.g., fuel, risk exposure). However, this standard model lacks the expressiveness to encode critical temporal dependencies between attacks, which are essential for true drone formation synergy.
2. The Satisficing Decision Theory Framework for Rapid Assignment
To address the real-time requirement, we adopt the Satisficing Decision Theory (SDT) framework. Instead of searching the entire combinatorial space for a global optimum, SDT first reduces the search space by having each agent (drone) identify a “good enough” or satisficing set of options based on its local perspective.
For each drone \(U_i\) and target \(T_j\), we define two functions:
- Selectability Function (\(p_{s,i}(T_j)\)): Measures the benefit/desirability of \(U_i\) engaging \(T_j\).
- Rejectability Function (\(p_{r,i}(T_j)\)): Measures the cost/undesirability of \(U_i\) engaging \(T_j\).
These are modeled as:
$$ p_{s,i}(T_j) = J_{benefit,i}(T_j) = p_{i,j} \cdot \rho_j $$
$$ p_{r,i}(T_j) = J_{cost,i}(T_j) = (w_1 \cdot r_{i,j} + w_2 \cdot d_{i,j}) \cdot \nu_i $$
where \(p_{i,j}\) is the kill probability, \(\rho_j\) is the target value, \(r_{i,j}\) is the risk, \(d_{i,j}\) is the normalized fuel cost/distance, \(\nu_i\) is the drone value, and \(w_1, w_2\) are weighting coefficients.
The individual satisficing set for drone \(U_i\) at a given caution level \(q_i\) is then defined as:
$$ SS_{q,i} = \{ T_j \in C \mid p_{s,i}(T_j) \geq q_i \cdot p_{r,i}(T_j) \} $$
The parameter \(q_i\) acts as a tuning knob for decision conservatism. A higher \(q_i\) means the drone is more cautious, requiring significantly higher selectability than rejectability for a target to be considered satisfactory.
The joint satisficing search space \(\Omega_{sat}\) is the Cartesian product of all individual satisficing sets, containing only those assignment combinations where each drone is assigned a target from its own satisficing set:
$$ \Omega_{sat} \subseteq SS_{q,1} \times SS_{q,2} \times … \times SS_{q,N} $$
This space is vastly smaller than the full combinatorial space \(N^M\), enabling rapid search. The global optimal assignment is then sought within this restricted but high-quality space \(\Omega_{sat}\).
3. Modeling and Enforcing Timing Constraints
The novel contribution lies in integrating timing constraints into this SDT-based fast assignment framework. We introduce two key concepts.
3.1 Definitions: Time Window and Attack Sequence
Definition 1 (Mission Time Window): The command center dictates a best-execution time interval \([t_k^{min}, t_k^{max}]\) for the entire cooperative task \(k\) (the target cluster \(C\)).
Definition 2 (Target Attack Timing Relation): Specific temporal relationships exist between targets within \(C\). For any two targets \(T_a\) and \(T_b\):
- Precedence (\(T_a \rightarrow T_b\)): \(T_a\) must be attacked before \(T_b\). \(T_a\) is the predecessor, \(T_b\) is the successor. A minimum time gap \(\delta t_{a,b} > 0\) may be required.
- Simultaneity (\(T_a \parallel T_b\)): \(T_a\) and \(T_b\) must be attacked at the same time, implying \(\delta t_{a,b} = 0\).
A sequence of such relations defines the attack schedule for the drone formation.
3.2 Feasibility Condition for Timing Constraints
Assume drone \(U_p\) is assigned to target \(T_a\) and drone \(U_s\) is assigned to its successor target \(T_b\) (\(T_a \rightarrow T_b\)). Each drone has an estimated time of arrival (ETA) window at its target based on its initial position, speed, and approximate path. This gives a feasible execution window for the attack.
- For \(\{U_p, T_a\}\): Feasible window is \([ET A_p^{min}, ET A_p^{max}]\).
- For \(\{U_s, T_b\}\): Feasible window is \([ET A_s^{min}, ET A_s^{max}]\).
Due to the precedence constraint, if \(T_a\) is attacked at time \(t_a\), then \(T_b\) cannot be attacked before \(t_a + \delta t_{a,b}\). Therefore, the constrained execution window for \(T_b\) relative to \(T_a\)’s window is:
$$ [ET A_p^{min} + \delta t_{a,b}, \quad ET A_p^{max} + \delta t_{a,b}] $$
For the assignment to be temporally feasible, the feasible window for \(\{U_s, T_b\}\) must overlap with this constrained window. The temporal feasibility condition for a pair of assignments is that the length of their overlap interval is positive:
$$ \text{Length}\big(\; [ET A_s^{min}, ET A_s^{max}] \cap [ET A_p^{min} + \delta t_{a,b}, ET A_p^{max} + \delta t_{a,b}] \; \big) > 0 $$
This concept extends to the entire chain of assignments in the drone formation. Let \(\text{Interval}(\mathbf{X})\) represent the intersection of all time windows for assignment set \(\mathbf{X}\), after applying all sequential timing constraints. The hard timing constraint for a complete candidate assignment is:
$$ \text{Length}(\text{Interval}(\mathbf{X}_{candidate})) > 0 \tag{TC1} $$
Assignments violating (TC1) are discarded.
3.3 Temporal Performance Metrics for Optimization
Merely satisfying (TC1) is insufficient. To choose the best among feasible schedules, we introduce two temporal performance metrics for the objective function \(J\).
1. Temporal Robustness Index (\(J_{TR}\)): The length of the feasible time intersection interval. A larger interval provides more scheduling flexibility and robustness against uncertainties.
$$ J_{TR} = \text{Length}(\text{Interval}(\mathbf{X})) $$
2. Sequential Initiation Time (\(J_{SIT}\)): The earliest possible start time for the entire attack sequence, relative to the mission window. An earlier start is generally preferable.
$$ J_{SIT} = \inf(\text{Interval}(\mathbf{X})) – \delta t_{first} $$
where \(\delta t_{first}\) is the offset of the first target in the sequence.
These metrics are normalized by the mission time window duration:
$$ \hat{J}_{TR} = \frac{J_{TR}}{t_k^{max} – t_k^{min}}, \quad \hat{J}_{SIT} = \frac{J_{SIT} – t_k^{min}}{t_k^{max} – t_k^{min}} $$
4. The Integrated Fast Assignment Algorithm with Timing Constraints
The complete algorithm for a drone formation is as follows:
Step 1: Individual Satisficing Set Generation. Each drone \(U_i\) calculates \(p_{s,i}\) and \(p_{r,i}\) for all targets and, given \(q_i\), constructs its satisficing set \(SS_{q,i}\).
Step 2: Joint Satisficing Search Space Construction. Generate the set \(\Omega_{sat}\) of all possible assignment combinations from the Cartesian product of individual \(SS_{q,i}\).
Step 3: Feasibility Filtering. For each candidate assignment in \(\Omega_{sat}\):
- Check basic constraints (one target per drone, all targets covered).
- Calculate ETA windows for all drone-target pairs.
- Apply timing constraints to compute \(\text{Interval}(\mathbf{X})\).
- Discard the candidate if \(\text{Length}(\text{Interval}(\mathbf{X})) \leq 0\).
Step 4: Optimal Assignment Selection. From the filtered set of temporally feasible assignments, select the one that maximizes the comprehensive objective function:
$$ \max J = \omega_1 \cdot \hat{J}_{Benefit} – \omega_2 \cdot \hat{J}_{Cost} + \omega_3 \cdot \hat{J}_{TR} – \omega_4 \cdot \hat{J}_{SIT} $$
where \(\hat{J}_{Benefit}\) and \(\hat{J}_{Cost}\) are the normalized total benefit and cost for the drone formation, and \(\omega_1\) to \(\omega_4\) are weighting factors.
The search within \(\Omega_{sat}\) can be done via efficient enumeration or heuristic search due to the significantly reduced space, ensuring rapid convergence.
5. Simulation Analysis and Results
A simulation scenario was constructed with a drone formation of \(N=6\) UAVs and a target cluster of \(M=5\) targets with a specified attack sequence: \(T_1 \rightarrow T_2 \rightarrow T_3 \rightarrow T_4 \rightarrow T_5\), with inter-target time delays \(\Delta t = [30, -10, 30, -40]\) seconds. The mission time window was \([300, 900]\) seconds. Key simulation parameters are summarized below.
| Parameter | Value / Description |
|---|---|
| Number of Drones (\(N\)) | 6 |
| Number of Targets (\(M\)) | 5 |
| Target Values (\(\rho_j\)) | [0.9, 0.7, 0.5, 0.3, 0.2] |
| Drone Values (\(\nu_i\)) | [1.0, 0.8, 0.6, 0.6, 0.4, 0.2] |
| Weights (\(w_1, w_2\)) | 0.1, 0.1 |
| Weights (\(\omega_1, \omega_2, \omega_3, \omega_4\)) | 0.1, 0.1, 0.4, 0.4 |
| Mission Time Window | [300s, 900s] |
The caution parameter \(q\) was varied to study its effect. The individual satisficing sets for different \(q\) levels are shown below. A target is marked ‘1’ if it is in the drone’s satisficing set.
| Drone (U_i) / Target (T_j) | T1 | T2 | T3 | T4 | T5 |
|---|---|---|---|---|---|
| q = 0.5 | All drones had all 5 targets in their satisficing set. | ||||
| U1 (q=0.5) | 1 | 1 | 1 | 1 | 0 |
| U2 (q=0.5) | 1 | 1 | 1 | 1 | 1 |
| … U6 | 1 | 1 | 1 | 1 | 1 |
| q = 1.0 | |||||
| U1 (q=1.0) | 1 | 0 | 0 | 0 | 0 |
| U2 (q=1.0) | 1 | 1 | 0 | 0 | 0 |
| U3 (q=1.0) | 1 | 1 | 1 | 1 | 0 |
| U4 (q=1.0) | 1 | 1 | 1 | 1 | 0 |
| U5 (q=1.0) | 1 | 1 | 1 | 1 | 0 |
| U6 (q=1.0) | 1 | 1 | 1 | 1 | 1 |
| q = 1.5 | |||||
| U1 (q=1.5) | 0 | 0 | 0 | 0 | 0 |
| U2 (q=1.5) | 1 | 0 | 0 | 0 | 0 |
| U3 (q=1.5) | 1 | 1 | 0 | 0 | 0 |
| U4 (q=1.5) | 1 | 1 | 1 | 1 | 0 |
| U5 (q=1.5) | 1 | 1 | 1 | 1 | 0 |
| U6 (q=1.5) | 1 | 1 | 1 | 1 | 1 |
The impact of the caution level \(q\) on algorithmic performance is critical. The following metrics were compared against a brute-force exhaustive search (which does not use satisficing sets).
| Caution Level (q) | Search Space Size | Computation Time (ms) | Formation Effectiveness (% of Optimal) | Temporal Robustness \(J_{TR}\) (s) |
|---|---|---|---|---|
| 0.5 (Low Caution) | Very Large | ~1200 | ~99% | 490 |
| 1.0 (Medium Caution) | ~15,625 | ~280 | ~96% | 490 |
| 1.5 (High Caution) | ~1,296 | < 50 | ~92% | 490 |
| 2.0 (Very High Caution) | ~256 | < 10 | ~88% | 120* |
| Brute-Force (Baseline) | \(6^5 = 7776\) | ~450 | 100% | 490 |
| *At q=2.0, the highly restricted satisficing sets reduced temporal flexibility, leading to a lower \(J_{TR}\). | ||||
The results demonstrate a clear trade-off managed by the SDT framework:
- Computational Speed: As \(q\) increases, the satisficing sets shrink, drastically reducing the search space \(\Omega_{sat}\) and computation time. The high-caution (\(q=1.5\)) SDT method was over 9x faster than brute-force search.
- Solution Quality: While higher \(q\) leads to a slight decrease in the overall formation effectiveness score (a reduction of up to 12%), the solutions remain at a high quality level (above 88% of optimal). This “satisficing” trade-off is acceptable for real-time applications.
- Timing Constraint Achievement: The algorithm successfully found assignments satisfying the complex sequence of timing constraints. The Temporal Robustness \(J_{TR}\) was maximized within the feasible set. When timing gaps were increased dramatically (e.g., \(\Delta t = [360, -240, 180, -420]\)), the feasible \(J_{TR}\) decreased to 120 seconds, and the algorithm correctly identified a different optimal assignment that accommodated this tighter temporal coupling.
The comprehensive objective function \(J\) for the optimal assignment at \(q=1.0\) can be broken down as:
$$
\begin{aligned}
J_{optimal} &= \omega_1 \hat{J}_{Benefit} – \omega_2 \hat{J}_{Cost} + \omega_3 \hat{J}_{TR} – \omega_4 \hat{J}_{SIT} \\
&= 0.1(0.85) – 0.1(0.22) + 0.4(0.817) – 0.4(0.15) \\
&= 0.085 – 0.022 + 0.3268 – 0.06 \\
&= 0.3298
\end{aligned}
$$
where the normalized \(J_{TR} = 490/600 \approx 0.817\).
6. Conclusion
This article has presented a fast and effective method for cooperative target assignment within a drone formation that rigorously accounts for critical timing constraints. By embedding the temporal feasibility condition and performance metrics within the Satisficing Decision Theory framework, the method achieves two primary objectives essential for networked drone formation operations: computational tractability for real-time re-planning and temporal coordination for synchronized, sequential attacks. The integration of the temporal robustness index and sequential initiation time into the global optimization criterion ensures that the selected assignment is not only feasible but also provides desirable scheduling flexibility and efficiency.
Simulation results validate that the approach can rapidly generate high-quality assignments under varying levels of decision caution, effectively managing the trade-off between speed and optimality. The method ensures that the complex interplay of individual drone capabilities, target values, and intricate attack sequences is resolved in a cohesive manner, truly enabling synergistic behavior for the entire drone formation. Future work will focus on integrating this assignment module with online cooperative path planning to generate dynamically feasible trajectories that realize the scheduled attack times, closing the loop on autonomous drone formation mission execution.