Abstract
Exploiting unmanned aerial vehicles (UAVs) to execute tasks is gaining growing popularity recently. To solve the underlying task scheduling problem, the deep reinforcement learning (DRL) based methods demonstrate notable advantage over the conventional heuristics as they rely less on hand-engineered rules. However, their decision space will become prohibitively huge as the problem scales up, thus deteriorating the computation efficiency. To alleviate this issue, we propose a double-level deep reinforcement learning (DL-DRL) approach based on a divide and conquer framework (DCF), where we decompose the task scheduling of multi-UAV into task allocation and route planning. Particularly, we design an encoder-decoder structured policy network in our upper-level DRL model to allocate the tasks to different UAVs, and we exploit another attention based policy network in our lower-level DRL model to construct the route for each UAV, with the objective to maximize the number of executed tasks given the maximum flight distance of the UAV. To effectively train the two models, we design an interactive training strategy (ITS), which includes pre-training, intensive training and alternate training. Experimental results show that our DL-DRL performs favorably against the learning-based and conventional baselines including the OR-Tools, in terms of solution quality and computation efficiency.
Introduction
Coordinating a fleet of Unmanned Aerial Vehicles (UAVs) to complete distributed tasks is a complex combinatorial optimization problem, specifically a variant of the Multiple Traveling Salesman Problem (m-TSP). In this scenario, UAVs have limited battery life, represented as a maximum flight distance, which prevents them from visiting every assigned task.
While traditional exact solvers like Gurobi provide optimal solutions, they suffer from exponential time complexity as the number of tasks grows. Heuristics offer speed but require manual rule-tuning. Deep Reinforcement Learning (DRL) automates these rules but faces the "curse of dimensionality" in large-scale scenarios where the number of possible combinations explodes, making it difficult for a single neural network to learn an efficient policy.
Methodology: The DL-DRL Framework
To address the scalability issue, the proposed Double-Level Deep Reinforcement Learning (DL-DRL) approach utilizes a Divide and Conquer Framework (DCF). This framework decomposes the complex scheduling problem into two hierarchical levels:
- Upper-Level (Task Allocation): A Transformer-style encoder-decoder network determines the global distribution of tasks and assigns specific subsets to individual UAVs.
- Lower-Level (Route Planning): An attention-based network determines the optimal sequence for a single UAV to visit its assigned tasks, aiming to maximize task completion within distance constraints.
A critical component of this architecture is the Interactive Training Strategy (ITS). Since allocation and routing are interdependent, the models are trained in three stages: pre-training the lower-level model on random subsets, intensive training of the upper-level model while the lower-level is fixed, and finally, alternate training where both levels are fine-tuned iteratively to reach a global equilibrium.
Experimental Results
The DL-DRL model was evaluated on synthetic datasets with tasks and depots uniformly distributed in a 2D space. Scenarios included fleet sizes of 4 (U4) and 6 (U6) UAVs, with task counts ranging from 80 to 500.
Key findings include:
- Performance: In a 500-task scenario with 6 UAVs, DL-DRL achieved an average of 297.59 completed tasks, outperforming industry-standard OR-Tools (292.10) and K-means+AM (193.21).
- Efficiency: While Gurobi failed to find optimal solutions for even 80 tasks within 1,800 seconds, DL-DRL generated solutions in approximately 0.11 seconds. For massive 1,000-task problems, it maintained a solution time of 2.3 to 3.3 seconds.
- Generalization: Models trained on 500 tasks demonstrated strong zero-shot generalization when applied to up to 1,000 tasks, suggesting the network learns fundamental spatial logic rather than specific patterns.
Conclusion
The DL-DRL approach effectively mitigates the curse of dimensionality in multi-UAV task scheduling. By decoupling allocation from routing and employing an interactive training strategy, the framework achieves superior solution quality and computational efficiency compared to traditional heuristics and exact solvers. Future work will explore heterogeneous fleets, non-uniform task distributions, and dynamic environmental factors such as obstacles and weather.
Summary updated