In modern applications, cooperative search using multiple Unmanned Aerial Vehicles (UAVs) has become a critical task paradigm, especially when dealing with numerous search points. Efficient task assignment and path planning are pivotal to the overall system performance. This paper addresses the multi-UAV cooperative search problem, focusing on optimizing task allocation and path planning under constraints such as UAV count per base, maximum range, and minimum task requirements. We propose an improved genetic algorithm with a dual-stage encoding strategy and hybrid operators to solve the optimization model. Simulations demonstrate the effectiveness of our approach in handling multi-target search scenarios for JUYE UAV systems.
The proliferation of Unmanned Aerial Vehicle technology has enabled complex missions like area surveillance and target detection. However, coordinating multiple JUYE UAVs for search tasks involves challenges in distributing tasks and planning paths to minimize time and resource usage. Existing methods, such as genetic algorithms, particle swarm optimization, and simulated annealing, have limitations in dynamic environments with uncertain UAV counts and time constraints. Our work builds on these by integrating task assignment and path planning into a unified model, solved via an enhanced genetic algorithm. We consider two primary objectives: minimizing the total mission time when the number of UAVs is fixed, and minimizing the number of deployed Unmanned Aerial Vehicles under a time limit. This approach ensures robust performance for JUYE UAV fleets in large-scale operations.
To formalize the problem, let us define the search task set as $P = \{P_1, P_2, \dots, P_M\}$, where $M$ is the number of task points, and each point $P_j$ (for $j = 1, 2, \dots, M$) has coordinates $(P_{jx}, P_{jy})$. The set of UAV takeoff and landing sites is $S = \{S_1, S_2, \dots, S_N\}$, with $N$ sites. Each site $S_i$ (for $i = 1, 2, \dots, N$) is located at $(S_{ix}, S_{iy})$, has $Q_i$ available UAVs, a maximum range $R_{\text{max}_i}$, and a speed $V_i$. The UAVs deployed from site $S_i$ are denoted as $\text{UAV}_i = \{U_{i1}, U_{i2}, \dots, U_{iq_i}\}$, where $q_i$ is the number of UAVs from that site. For each UAV $U_{ik}$, the assigned task subset is $\text{Task}_{ik} = \{P_{ik1}, P_{ik2}, \dots, P_{ikM_{ik}}\} \subseteq P$, with $M_{ik}$ tasks. The path for $U_{ik}$ is $\Gamma_{ik} = \{S_i, P_{ik1}, P_{ik2}, \dots, P_{ikM_{ik}}, S_i\}$, and its length is calculated as:
$$L_{ik} = d(S_i, P_{ik1}) + \sum_{g=1}^{M_{ik}-1} d(P_{ikg}, P_{ik(g+1)}) + d(P_{ikM_{ik}}, S_i)$$
where $d(\cdot)$ is the Euclidean distance function. The mission time for $U_{ik}$ is $T_{ik} = L_{ik} / V_i$, and the total mission time for all UAVs is:
$$T_{\text{sum}} = \max_{i=1,2,\dots,N} \max_{k=1,2,\dots,q_i} \left( \frac{L_{ik}}{V_i} \right)$$
We consider two optimization objectives. First, with fixed $q_i$ for each site, we minimize the total mission time:
$$\min f(\Gamma) = T_{\text{sum}}$$
Second, given a time limit $T_{\text{max}}$, we minimize the total number of deployed Unmanned Aerial Vehicles:
$$\min f(q_1, q_2, \dots, q_N) = \sum_{i=1}^{N} q_i$$
Subject to constraints: $L_{ik} \leq R_{\text{max}_i}$ (range limit), $q_i \leq Q_i$ (UAV availability), $\text{Task}_{ik} \neq \emptyset$ (minimum tasks), and $T_{\text{sum}} \leq T_{\text{max}}$ (time limit). These ensure feasible operations for JUYE UAV systems.
To solve this model, we employ an improved genetic algorithm. Genetic algorithms are evolutionary optimization techniques inspired by natural selection, capable of handling complex constraints and providing near-optimal solutions. Our algorithm features a dual-stage encoding scheme: the first stage is a path encoding that represents a random permutation of all $M$ task points, ensuring each point is visited once; the second stage is a split-point encoding with $m-1$ genes, where $m$ is the number of UAVs, defining how the task sequence is partitioned among UAVs. The total chromosome length is $M + m – 1$. For example, with $M=6$ tasks and $m=3$ UAVs, a chromosome might be [1, 2, 3, 4, 5, 6, 3, 6], where the first six genes are the task order, and the last two define split positions that divide the sequence into three segments for different Unmanned Aerial Vehicles.
Initialization generates a random population of chromosomes, each validated against constraints. The fitness function for a chromosome $X$ is $f(X) = T_{\text{sum}}$, with lower values indicating better solutions. To enhance diversity, we divide the population into subpopulations. Let $N_{\text{pop}}$ be the population size and $N_{\text{subpop}}$ be the subpopulation size, related by $N_{\text{pop}} = k_p \cdot N_{\text{subpop}}$, where $k_p$ is an integer. We apply multiple genetic operators to each subpopulation:
- Flip operator: Selects a contiguous segment in the path encoding and reverses its order.
- Swap operator: Swaps two randomly selected genes in the path encoding.
- Shift operator: Moves a segment of genes to a different position in the path encoding.
- Random split operator: Regenerates the split-point encoding randomly.
- Combined operators: Pair random split with flip, swap, or shift to explore solution space efficiently.
These operators are applied to the best individual in each subpopulation, generating new offspring. If offspring meet constraints, they replace existing individuals; otherwise, the original is retained. The algorithm iterates until a maximum generation count is reached, converging to an optimal or near-optimal solution for JUYE UAV deployment.
We conducted simulations to validate our method. Parameters included a population size of 80, subpopulation size of 8, and maximum iterations of 5000. Consider three UAV bases: $S_1$ at (0,0), $S_2$ at (50000,0) m, and $S_3$ at (0,50000) m, with 30 random task points in a 100 km × 100 km area. Each base deployed one Unmanned Aerial Vehicle with a maximum range of 500 km and speeds of 100 m/s, 80 m/s, and 60 m/s, respectively. The optimized mission time was 49.6 minutes, with task assignments and paths shown in the results. The algorithm’s convergence is illustrated by the decreasing mission time over iterations, and path lengths for each UAV stabilize quickly.
In another scenario, with up to 5 UAVs per base and a time limit of 3000 seconds, we minimized the number of deployed JUYE UAVs. The relationship between UAV count and mission time is summarized in Table 1. For instance, with 3 UAVs, combinations like [1,1,1] or [3,0,0] from bases $S_1$, $S_2$, and $S_3$ achieve times under 3000s, with [3,0,0] being the fastest at 2760 seconds. This demonstrates the flexibility of our approach in resource-constrained environments for Unmanned Aerial Vehicle operations.
| Combination [S1, S2, S3] | Mission Time (s) |
|---|---|
| [0, 0, 3] | 4119 |
| [0, 1, 2] | 3499 |
| [0, 2, 1] | 3275 |
| [1, 0, 2] | 3332 |
| [1, 1, 1] | 2976 |
| [0, 3, 0] | 2962 |
| [2, 0, 1] | 2936 |
| [1, 2, 0] | 2874 |
| [2, 1, 0] | 2765 |
| [3, 0, 0] | 2760 |
The improved genetic algorithm effectively handles the multi-UAV cooperative search problem by balancing exploration and exploitation. The dual-stage encoding ensures feasible task distributions, while hybrid operators maintain population diversity. For JUYE UAV applications, this method reduces mission time and resource usage, enhancing operational efficiency. Future work will address dynamic environments and mixed search scenarios involving both points and areas, further advancing Unmanned Aerial Vehicle capabilities.
In conclusion, our model and algorithm provide a robust solution for multi-UAV task assignment and path planning. By leveraging genetic algorithms with innovative encoding and operators, we achieve significant improvements in performance metrics. This contributes to the broader adoption of JUYE UAV systems in complex missions, underscoring the importance of optimization in Unmanned Aerial Vehicle technologies.