A Distributed Task Rescheduling Method for UAV Swarms Using Local Task Reordering and Deadlock-Free Task Exchange

Abstract

Distributed task scheduling is an ongoing concern in the field of multi-vehicles, especially in recent years; UAV swarm performing complex tasks endows it with new characteristics, such as self-organization, scalability, reconfigurability, etc. This requires the swarm to have distributed rescheduling capability to dynamically include as many unassigned tasks or new tasks as possible, while satisfying tight time constraints. As one of the most advanced rescheduling methods, the Performance Impact (PI)-MaxAss algorithm provides an important reference for this paper. However, its task exchange-based strategy faces the deadlock problem, and the task rescheduling method should not be limited to this. To this end, a new distributed rescheduling method is proposed for UAV swarms, which combines the local task reordering strategy and the improved task exchange strategy. On the one hand, based on the analysis of the fact that the scheduler is unreasonable for individuals, this paper proposes a local task reordering strategy denoted as PI-Reorder, which simply adds the reordering strategy to the recursive inclusion phase of the PI-MinAvg algorithm, so that unassigned tasks or new tasks can be included without relying on the task exchange. On the other hand, from the phenomenon that two or more vehicles occasionally get caught in an infinite cycle of exchanging the same tasks, the deadlock problem of PI-MaxAss is analyzed, which is then solved by introducing a deadlock-free task exchange strategy, where some defined counters are used to detect and isolate the deadlocks. Then, a rescue scenario is used to demonstrate the performance of the proposed methods, PI-Hybrid compared with PI-MaxAss. Monte Carlo simulation results show that, compared with PI-MaxAss, this method can not only increase the number of allocations to varying degrees, but also reduce the average waiting time, while ensuring deadlock avoidance. The methods can be used not only for the secondary optimization of the existing task exchange scheduling algorithms to escape local optima, but also for task reconfiguration of swarm tasks after adding or removing tasks.

Keywords

• performance impact method
• multi-agent scheduling
• task rescheduling
• distributed method
• deadlock problem
• search and rescue