A Distributed Double-Loop Optimization Method with Fast Response for UAV Swarm Scheduling

Abstract

An unmanned aerial vehicle (UAV) swarm has broad application prospects, in which scheduling is one of the key technologies determining the completion of tasks. A market-based approach is an effective way to schedule UAVs distributively and quickly, meeting the real-time requirements of swarm scheduling without a centre. In this paper, a double-loop framework is designed to enhance the performance of scheduling, where a new task removal method in the outer loop and a local redundant auction method in the inner loop are proposed to improve the optimization of scheduling and reduce iterations. Furthermore, a deadlock detection mechanism is introduced to avoid endless loops and the scheduling with the lowest local cost will be adopted to exit the cycle. Extensive Monte Carlo experiments show that the iterations required by the proposed method are less than the two representative algorithms consensus-based bundle algorithm (CBBA) and performance impact (PI) algorithm, and the number of allocated tasks is increased. In addition, through the deadlock avoidance mechanism, PI can completely converge as the method in this paper.

Keywords

• UAV swarm
• distributed scheduling
• fast response
• market-based approach
• double-loop optimization