A novel distributed scheduling algorithm for maximizing total task allocations of multi-UAV systems

This paper addresses the task allocation problem by maximizing the number of successfully allocated tasks through two decentralized algorithms: a novel performance impact algorithm with new scoring (PINS) and a local exchange performance impact algorithm (LEPI). PINS employs a scoring strategy that expands task inclusion capability in the task inclusion phase while ensuring tasks, once assigned, remain allocated. LEPI extends PINS by incorporating task reassignment to optimize allocations further. Evaluated in a deadline-limited and fuel-constrained simulated rescue scenario, both algorithms outperform existing methods and provably converge to conflict-free assignments within a finite number of iterations. Extensive simulations illustrate LEPI’s superiority, improving the number of allocated tasks by up to 3.82% over the benchmarks; however, LEPI’s substantially higher computational complexity limits its large-scale applicability. Conversely, PINS achieves up to 2.32% performance gains with computational complexity comparable to the Performance Impact (PI) algorithm.