E-CBBA: A Consensus Auction Approach for Multi-UAV Task Allocation Under Time Window and Task Priority Constraints

Abstract

This paper proposes a collaborative task allocation model for heterogeneous multi-UAV systems in missions with chain-structured task priorities and strict time constraints. The model considers key constraints, including UAV flight speed, task capability differences, execution limits, and ordered task dependencies, enabling accurate representation of coordinated chain task execution. Traditional approaches struggle to ensure both real time performance and feasibility when the number of tasks and UAVs grows. To address this challenge, we develop an Extended Consensus-Based Bundle Algorithm (E-CBBA). The algorithm extends the traditional CBBA framework by introducing a maximum gain task screening strategy, a feasible position set for path insertion, and a global task execution time matrix for distributed consensus and conflict resolution. These mechanisms ensure that each UAV evaluates and inserts tasks only under feasible priority, timing, and kinematic conditions. We prove the convergence and approximate optimality of E-CBBA. Extensive simulations show that E-CBBA achieves higher objective values and task completion rates than traditional CBBA and GA-based methods, while maintaining fast convergence, scalability to multiple sequential task types, robustness under moderate communication degradation, and feasibility in ROS 2 and Gazebo simulations. Note to Practitioners—Multiple unmanned aerial vehicles (UAVs) are increasingly deployed in real combat and emergency response missions, where tasks are often subject to strict time constraints and precedence relationships. As the number of tasks and UAVs grows, existing task allocation methods tend to suffer from excessive decision latency and frequent task conflicts, which severely degrade coordination efficiency. To address these challenges, we propose an extended consensus-based bundle algorithm (E-CBBA) that enables UAVs to rapidly identify feasible tasks and achieve coordinated task allocations while explicitly respecting task ordering and temporal constraints. The proposed algorithm extends the conventional CBBA framework by incorporating task dependency modeling and time feasibility checking, allowing scalable and conflict-free coordination in complex mission scenarios. Simulations demonstrate that the method significantly improves task completion rates and decision speed, and remains effective as the number of tasks and UAVs increases. Future work will incorporate online learning to enhance robustness. The algorithm can also be extended to multi-robot coordination scenarios such as emergency rescue, logistics delivery, and inspection missions.