Consensus-based bundle algorithm with local replanning for heterogeneous multi-UAV system in the time-sensitive and dynamic environment

Consensus-based bundle algorithm (CBBA) is a decentralized task allocation algorithm that can produce feasible and conflict-free task assignment solution for multi-UAV system in the search and rescue scenarios. Further considering the new emerging tasks, this paper studies how to realize task reasssignment in the time-sensitive and dynamic environment. Effective task replanning algorithm aims to maximize the score value of task replanning solution when ensuring the timely allocation of the new task. Thus, an extension of CBBA called CBBA with local replanning (CBBA-LR) is proposed to produce reliable task replanning solution with quick response to the new task. Firstly, the capable matrix is adopted in CBBA-LR to denote the capable relationship between UAVs and tasks. Only capable UAVs for the new task are included in the task replanning. Then, the performing time list is introduced to the bid lists. For each UAV, CBBA-LR selects the assigned tasks whose performing times overlap the time window of the new task as the potential reset tasks. The setting of potential reset tasks effectively reduces the number of tasks included in the replanning process. After that, each UAV selects the nearest task to the new task from the potential reset task set as the reset task. Hence, CBBA-LR resets the most likely insert position of the new task from each UAV's path. Finally, CBBA runs based on the reset task schedules to get the task replanning solution. Numerical simulations demonstrate the solution quality and convergence time of CBBA-LR from four perspectives: different time windows of the new task, different locations of the new task, continuous appearance of new tasks and different scales of search and rescue scenarios. The simulation results verify the feasibility and superiority of CBBA-LR compared with other replanning strategies.