In recent years, the rapid advancement of unmanned aerial vehicle (UAV) drone technology has led to its widespread application in complex urban scenarios such as disaster relief, logistics delivery, and environmental monitoring. These missions often require coordinated execution by UAV drones with diverse functionalities. Traditional task allocation methods for multi-heterogeneous UAV drones typically follow a sequential “allocate-then-plan” approach, which often fails to account for real-world obstacles and path costs, resulting in suboptimal overall costs and imbalanced workloads. To address these issues, I propose a static task allocation algorithm for multi-heterogeneous UAV drones based on improved genetic operators. This algorithm integrates path planning into the task allocation process, enabling协同 optimization and overcoming the limitations of traditional methods. The core innovations include enhanced genetic operators, a functionally coupled chromosome encoding strategy, adaptive crossover and mutation mechanisms, and the embedding of a path planning module. These improvements enhance the accuracy of cost function calculations, leading to better global optimality and robustness in allocation results.
The task allocation problem for multi-heterogeneous UAV drones involves assigning a set of tasks to a fleet of UAV drones with varying capabilities, considering constraints such as obstacle avoidance, range limits, and task requirements. The goal is to minimize the total path cost while ensuring balanced workloads among the UAV drones. This problem is inherently complex due to the combinatorial nature of allocation and the need for feasible flight paths. My approach formulates it as a mathematical model and solves it using a dual-layer improved genetic algorithm (GA). The outer layer handles task allocation, while the inner layer optimizes path planning for each UAV drone, incorporating a sparse A* algorithm with variable step sizes for obstacle avoidance. This integration ensures that path costs are accurately evaluated during allocation, leading to more realistic and efficient solutions.
To elaborate, the static task allocation problem is defined using four key variables: the environment \(E\), the UAV drone set \(U = \{U_1, U_2, \dots, U_{N_u}\}\), the task set \(T = \{T_1, T_2, \dots, T_{N_t}\}\), and the constraint set \(C\). Here, \(N_u\) is the total number of UAV drones, and \(N_t\) is the total number of targets. Each target may have multiple tasks, such as search and transport tasks. The heterogeneity of UAV drones is categorized into three types: search UAV drones, transport UAV drones, and comprehensive UAV drones. Search UAV drones can only perform search tasks, transport UAV drones only transport tasks, and comprehensive UAV drones can handle both. Constraints include functional matching, maximum task limits per UAV drone, and maximum flight range. For example, each UAV drone \(U_i\) can execute at most \(L_i^{\text{task}}\) tasks, and the total flight distance for each UAV drone must not exceed a maximum range \(\text{len}_{\text{max}}\).
The task set includes various targets with random combinations of search and transport tasks. For each target \(T_j\), its task attributes are represented as \(\text{Task}_j = \{\text{Task}_j^s, \text{Task}_j^t\}\), where \(\text{Task}_j^s \in \{0,1\}\) indicates the need for a search task, and \(\text{Task}_j^t \in \{0,1\}\) for a transport task. The total number of tasks across all targets is given by:
$$ N_{\text{Task}} = \sum_{j=1}^{N_t} m_j $$
where \(m_j \in \{1,2\}\) denotes the number of tasks at target \(T_j\). Constraints ensure that all tasks are allocated, each task is performed by exactly one capable UAV drone, and no task is repeated. Additionally, the environment contains obstacle regions \(E_{\text{obs}}\), and UAV drone flight paths must avoid these obstacles.
The objective function aims to minimize both the total path cost and the imbalance in path costs among UAV drones. An allocation matrix \(X = [x_{ij}] \in \mathbb{R}^{N_u \times 2N_t}\) is defined, where \(x_{ij} \in \{0,1\}\). If \(j\) is odd, \(x_{i\left(\frac{j+1}{2}\right)} = 1\) means UAV drone \(i\) performs the search task of target \(\frac{j+1}{2}\); if \(j\) is even, \(x_{i\left(\frac{j}{2}\right)} = 1\) means UAV drone \(i\) performs the transport task of target \(\frac{j}{2}\). Let \(X_i\) be the \(i\)-th row of \(X\), representing the tasks assigned to UAV drone \(i\). For each UAV drone, the optimal task sequence \(p_i\) and its corresponding flight path are determined using a variable-step sparse A* algorithm, yielding the path cost \(C(X_i, p_i)\). The total path cost is:
$$ C_{\text{sum}} = \sum_{i=1}^{N_u} C(X_i, p_i) $$
The balance degree of path costs among UAV drones is defined as:
$$ B_l = \frac{C_{\text{max}} – C_{\text{min}}}{C_{\text{max}}} \times 100\% $$
where \(C_{\text{max}} = \max(C(X_1, p_1), C(X_2, p_2), \dots, C(X_l, p_l))\) and \(C_{\text{min}} = \min(C(X_1, p_1), C(X_2, p_2), \dots, C(X_l, p_l))\). The overall objective function combines these metrics:
$$ \min J = C_{\text{sum}} \cdot (1 + \omega \cdot B_l) $$
Here, \(\omega\) is a weight factor that controls the emphasis on balance. The constraints are summarized as follows:
| Constraint | Description | Mathematical Form |
|---|---|---|
| 1 | Maximum tasks per UAV drone | \(\sum_{j=1}^{2N_t} x_{ij} \leq L_i^{\text{task}}, \forall i = 1,2,\dots,N_u\) |
| 2 | Each task assigned to at most one UAV drone | \(\sum_{i=1}^{N_u} x_{ij} \leq 1, \forall j = 1,2,\dots,2N_t\) |
| 3 | All tasks allocated | \(\sum_{i=1}^{N_u} \sum_{j=1}^{2N_t} x_{ij} = N_{\text{Task}}\) |
| 4 | Flight range limit per UAV drone | \(C(X_i, p_i) \leq \text{len}_{\text{max}}, \forall i = 1,2,\dots,N_u\) |
| 5 | Obstacle avoidance | \(\sum_{i=1}^{N_u} \text{Tra}_i \cap E_{\text{obs}} = \emptyset\) |
To solve this model, I designed a dual-layer improved genetic algorithm. The outer GA optimizes task allocation, while the inner GA, embedded with path planning, computes the path cost for each allocation solution. The overall framework is illustrated below, showing the interaction between allocation and path planning layers. This integrated approach allows for accurate cost evaluation and better global optimization.
The chromosome encoding strategy is crucial for handling heterogeneity. I propose a multi-agent chromosome encoding that couples UAV drone functionalities with task requirements. Each chromosome represents a feasible allocation solution and consists of four features: target, task, UAV drone, and UAV drone functionality. The total number of genes in a chromosome equals \(N_{\text{Task}}\). For example, consider a scenario with 4 targets and 3 UAV drones. Targets 1 and 2 have both search and transport tasks, target 3 has only a transport task, and target 4 has only a search task. A sample chromosome might encode that UAV drone 1 handles transport tasks for targets 2 and 3, UAV drone 2 handles search tasks for targets 1 and 4, and UAV drone 3 handles the transport task for target 1 and the search task for target 4. This encoding is flexible and can be viewed as two sub-chromosome groups: one based on UAV drones and another based on targets. These groups are interchangeable, facilitating genetic operations.
Population initialization is performed by randomly generating chromosomes that respect task-UAV drone functional matching. Since initial chromosomes are in target-based sub-chromosome group form, they are later converted to UAV drone-based groups for fitness evaluation. The fitness of each chromosome depends on the optimal path costs for all UAV drones. Specifically, for each UAV drone, the inner GA finds the shortest path cost for its assigned task sequence using the variable-step sparse A* algorithm to avoid obstacles. The fitness is then computed using the objective function \(J\). This process ensures that path planning is tightly coupled with allocation, improving accuracy.
The genetic operators are enhanced to improve convergence and solution quality. The selection operator employs a stratified differential strategy. The population is divided into three layers based on fitness: top 30% (elite), middle 40%, and bottom 30%. Elite individuals are directly preserved. The middle layer uses dynamic tournament selection, where the tournament size \(k\) adapts based on the change in average fitness \(\Delta f\):
$$ k = k_{\text{min}} + (k_{\text{max}} – k_{\text{min}}) \cdot \frac{\Delta f}{\Delta f_{\text{max}}} $$
This maintains diversity when progress is slow and increases selection pressure when improvements are significant. The bottom layer uses roulette wheel selection with probabilities inversely proportional to fitness:
$$ p_i = \frac{f_i}{\sum_{i=1}^{N_a} f_i} $$
where \(N_a\) is the number of individuals in the bottom layer.
For crossover, chromosomes are first converted to target-based sub-chromosome groups. A position-based multi-point crossover is applied, swapping genes at multiple positions between parent chromosomes. After crossover, the offspring are converted back to UAV drone-based groups and checked for constraint satisfaction (e.g., maximum task limits). This ensures that crossover produces valid allocations. Similarly, mutation operates on the UAV drone elements of genes. For a selected gene, the UAV drone is changed to another capable UAV drone while preserving the task and target. The mutated chromosome is also validated against constraints.
To further enhance adaptability, I introduce a dual adaptive adjustment strategy for the number and probability of genetic operations. Based on the population’s evolutionary state, the number of genes involved in crossover \(N_c\) and mutation \(N_m\) are adjusted using Sigmoid functions:
$$ N_c = \begin{cases}
N_{c1} \cdot \left(1 – \frac{1}{1 + e^{-\alpha \Delta f_i}}\right), & \Delta f_i \geq 0 \\
N_{c2} \cdot \frac{1}{1 + e^{-\alpha \Delta f_i}}, & \Delta f_i < 0
\end{cases} $$
$$ N_m = \begin{cases}
N_{m1} \cdot \left(1 – \frac{1}{1 + e^{-\alpha \Delta f_i}}\right), & \Delta f_i \geq 0 \\
N_{m2} \cdot \frac{1}{1 + e^{-\alpha \Delta f_i}}, & \Delta f_i < 0
\end{cases} $$
Here, \(N_{c1}\), \(N_{c2}\), \(N_{m1}\), \(N_{m2}\) are limits for high and low fitness populations, and \(\alpha\) is the Sigmoid slope. Similarly, crossover probability \(p_c\) and mutation probability \(p_m\) are adaptively tuned:
$$ p_c = \begin{cases}
p_{c1} – \frac{(p_{c1} – p_{c2}) \times (f_i – f_{\text{avg}})}{f_{\text{max}} – f_{\text{avg}}}, & f_i \geq f_{\text{avg}} \\
p_{c1}, & f_i < f_{\text{avg}}
\end{cases} $$
$$ p_m = \begin{cases}
p_{m1} – \frac{(p_{m1} – p_{m2}) \times (f_i – f_{\text{avg}})}{f_{\text{max}} – f_{\text{avg}}}, & f_i \geq f_{\text{avg}} \\
p_{m1}, & f_i < f_{\text{avg}}
\end{cases} $$
where \(p_{c1}\), \(p_{c2}\), \(p_{m1}\), \(p_{m2}\) are maximum and minimum probabilities, and \(f_{\text{avg}}\), \(f_{\text{max}}\) are average and maximum fitness values. These adjustments help balance exploration and exploitation throughout the evolution.
To validate the algorithm, I conducted simulations in a MATLAB environment. The scenario involves a 100 m × 100 m × 50 m 3D space with obstacles representing urban buildings. Six heterogeneous UAV drones and 11 multi-task targets are randomly deployed. The UAV drone details are as follows:
| UAV Drone ID | Type | Position (m) | Max Tasks |
|---|---|---|---|
| U1 | Search | (10, 2, 18) | 4 |
| U2 | Transport | (25, 2, 18) | 4 |
| U3 | Comprehensive | (40, 2, 18) | 4 |
| U4 | Transport | (55, 2, 18) | 4 |
| U5 | Search | (70, 2, 18) | 4 |
| U6 | Comprehensive | (85, 2, 18) | 4 |
The target tasks include search and transport tasks at various locations, with a total of 18 tasks. Four building obstacles are placed at centers (33,40,14), (35,75,15), (70,41,20), and (90,44,15) with respective dimensions. The algorithm parameters are set as: population size 100, maximum crossover probability 0.9, minimum crossover probability 0.5, maximum mutation probability 0.1, minimum mutation probability 0.001, and iterations 200. The weight \(\omega\) in the objective function is set to 0.5 to balance total cost and equity.
I compared the improved GA with a traditional GA. The traditional GA uses standard operators without adaptive mechanisms or integrated path planning. The convergence curves show that the traditional GA stagnates at a local optimum of 879.5721 after 64 iterations, while the improved GA reaches a global optimum of 811.6239 at iteration 84. The improved GA exhibits faster convergence and better solution quality, thanks to the enhanced operators and adaptive strategies. The optimal allocation solution from the improved GA is summarized below:
| UAV Drone ID | Task Sequence | Total Path Cost (m) |
|---|---|---|
| U1 | T11 (search) → T16 (search) → T18 (search) | 94.1807 |
| U2 | T21 (transport) → T24 (transport) → T26 (transport) | 73.7981 |
| U3 | T111 (search) → T211 (transport) | 97.9781 |
| U4 | T22 (transport) → T29 (transport) → T210 (transport) | 94.4987 |
| U5 | T12 (search) → T15 (search) → T19 (search) | 86.6725 |
| U6 | T23 (transport) → T17 (search) → T110 (search) | 91.8887 |
All UAV drones satisfy the maximum task limit and range constraints. The paths avoid obstacles, and the overall cost is minimized with balanced workloads. The visualization of the allocation shows distinct flight paths for each UAV drone type: green for search UAV drones, blue for transport UAV drones, and red for comprehensive UAV drones. Solid lines indicate simultaneous search and transport tasks, dashed lines for search tasks, and dot-dashed lines for transport tasks. This demonstrates the algorithm’s effectiveness in handling heterogeneous tasks and complex environments.
The improved genetic algorithm demonstrates significant advantages over traditional methods. By integrating path planning into task allocation, it avoids the pitfalls of inaccurate cost estimation. The functionally coupled chromosome encoding ensures that UAV drone capabilities match task requirements. Adaptive genetic operators maintain population diversity and accelerate convergence. The dual-layer structure allows for precise cost calculations, leading to better global optima. In the simulation, the improved GA reduced the total cost by approximately 7.7% compared to the traditional GA, while also improving balance among UAV drones. These results validate the algorithm’s superiority in terms of convergence speed, solution quality, and robustness for multi-heterogeneous UAV drone task allocation.
In conclusion, this work addresses the critical challenge of task allocation for multi-heterogeneous UAV drones in urban disaster relief scenarios. The proposed algorithm, based on improved genetic operators, effectively combines allocation and path planning into a cohesive framework. Future research could extend this approach to dynamic environments where tasks or UAV drone states change in real-time. Additionally, incorporating more complex constraints, such as energy consumption or communication limits, could further enhance practicality. Overall, this algorithm provides a robust foundation for optimizing UAV drone operations in complex missions, ensuring efficient and balanced task execution.