Decentralized task allocation for heterogeneous multi-UAV system with task coupling constraints

Cooperative multiple task assignment problem is an essential issue in the collaboration of multiple unmanned aerial vehicles (UAVs). Consensus-based bundle algorithm (CBBA) is a decentralized task assignment method that only considers homogeneous agents and independent tasks. Thus, we develop an extended CBBA with task coupling constraints (CBBA-TCC) in this paper to solve the multi-task assignment problem with task coupling constraints in the heterogeneous multi-UAV system. CBBA is a two-stage iteration algorithm with inner and outer consensus stages. The inner consensus stage is designed as a modified version of CBBA in this paper. A Can-do list is firstly raised at the beginning of bundle construction phase on each agent to record the tasks that can be performed by this agent without violating the task precedence constraints. Hence, at the inner consensus stage, each agent will only bid on the Can-do list. Then, we adopt a task performing time list for each agent to store the performing times of its assigned tasks. With associate consensus strategy of task performing time list at the conflict resolution phase, the precedence constraint of coupled tasks can be guaranteed. After reaching inner consensus, the outer consensus stage introduces an insert-position feasibility index to determine whether the assigned tasks satisfy the coupling constraints and resolve the constraint violation conflicts. Through the iterations of inner and outer consensus stages, CBBA will reach global consensus and obtain conflict-free task assignment results. Numerical simulations demonstrate the feasibility and reliability of CBBA in various search and rescue scenarios.