Decentralized UAV Swarm Scheduling with Constrained Task Exploration Balance

Abstract

Scheduling is one of the key technologies used in unmanned aerial vehicle (UAV) swarms. Scheduling determines whether a task can be completed and when the task is complete. The distributed method is a fast way to realize swarm scheduling. It has no central node and UAVs can freely join or leave it, thus making it more robust and flexible. However, the two most representative methods, the Consensus-Based Bundle Algorithm (CBBA) and the Performance Impact (PI) algorithm, pursue the minimum cost impact of tasks, which have optimization limitations and are easily cause task conflicts. In this paper, a new concept called “task consideration” is proposed to quantify the impact of tasks on scheduling and the regression of the task itself, balancing the exploration of the UAV for the minimum-impact task and the regression of neighboring tasks to improve the optimization and convergence of scheduling. In addition, the conflict resolution rules are modified to fit the proposed method, and the exploration of tasks is increased by a new removal method to further improve the optimization. Finally, through extensive Monte Carlo experiments, compared with CBBA and PI, the proposed method is shown to perform better in terms of task allocation and total travel time, and with the increase in the number of average UAV tasks, the number of iterations is less and the convergence is faster.

Keywords

• UAV planning
• swarm scheduling
• distributed method
• market-based algorithm
• task consideration