Distributed Task Allocation and Trajectory Planning for Heterogeneous UAV Swarms in Multi-Constraint Environments
TL;DR
The Sequentially Extended Consensus-Based Bundle Algorithm (SECBBA), a deadlock-free distributed scheduling framework, is proposed, extending through the integration of a deadlock detection and resolution mechanism based on directed graph Depth-First Search, thereby guaranteeing conflict-free task allocation.
Abstract
Owing to the stringent spatio-temporal coupling and kinematic constraints, the task allocation problem for heterogeneous unmanned aerial vehicle (UAV) swarms is generally regarded as an NP-hard problem. To address this, this paper proposes the Sequentially Extended Consensus-Based Bundle Algorithm (SECBBA), a deadlock-free distributed scheduling framework. First, a multi-task allocation model is established by incorporating constraints associated with payload resources, task scheduling, and threat zone. Subsequently, the conventional Consensus-Based Bundle Algorithm (CBBA) is extended through the integration of a deadlock detection and resolution mechanism based on directed graph Depth-First Search (DFS), thereby guaranteeing conflict-free task allocation. Furthermore, a sequential hierarchical strategy is introduced to transform global temporal dependencies into tractable soft time-window constraints. Finally, to ensure physical feasibility, Dubins curves are tightly coupled with the allocation process, enabling nonholonomic path planning for fixed-wing UAVs. Simulation results demonstrate that SECBBA reduces global task costs by 13.3%, 22.7%, and 39.4% compared to the Consensus-Based Bundle Algorithm with Temporal Consistency Constraints (CBBA-TCC), Improved Genetic Algorithm (IGA) and Q-Learning baselines, respectively. It consistently maintains performance advantage of 9.8%, 23.2% and 19.0% under variable weights with high computational efficiency, significantly enhancing swarm timeliness in complex, coupled multi-task scenarios.