Learning-Augmented Deterministic Task Allocation and Routing for Heterogeneous Multi-UAV Systems

This paper presents a learning-augmented deterministic method for heterogeneous multi-UAV task allocation and routing in static, fully observed environments. UAV-specific asymmetric path-length matrices represent the output of an offline path planner, allowing online planning to focus on assignment and route construction. The deterministic core evaluates insertions, checks energy feasibility, prioritizes tasks with few feasible UAVs, repairs blocked states, and improves completed routes. A shallow multilayer perceptron ranks feasible candidates by predicting future regret, defined as the difference between the makespan after deterministic completion and the immediate post-insertion makespan. The objective minimizes makespan first and uses aggregate route length only when makespan values are equal within the prescribed numerical tolerance. The model was trained on 12 synthetic instances and evaluated on 20 separate instances, each containing 20 tasks and four heterogeneous UAVs under uniform, clustered, and mixed layouts. It was compared with two greedy insertion heuristics, the corresponding deterministic ablation (CT-D), and a linear-regret variant. The proposed method achieved a mean makespan of 106.24 versus 107.46 for CT-D, a descriptive reduction of approximately 1.1%. Compared with CT-D, aggregate route length increased by approximately 1.5%, while mean runtime increased from 0.059 to 0.233 s. Performance improved on clustered and mixed layouts but declined slightly on uniform layouts.