Li, Teng (Cranfield University), Shin, Hyo-Sang (Cranfield University), Tsourdos, Antonios (Cranfield University)

Efficient Decentralized Task Allocation for UAV Swarms in Multi-Target Surveillance Missions

Scheduled for presentation during the Regular Session "Swarms I" (WeA2), Wednesday, June 12, 2019, 10:20−10:40, Heritage A

2020 International Conference on Unmanned Aircraft Systems (ICUAS), June 11-14, 2019, Athens, Greece

This information is tentative and subject to change. Compiled on April 26, 2024

Abstract

This paper deals with the large-scale task allocation problem for Unmanned Aerial Vehicle (UAV) swarms in surveillance missions. The task allocation problem is proven to be NP-hard which means that finding the optimal solution requires exponential time. This paper presents a practically efficient decentralized task allocation algorithm for UAV swarms based on lazy sample greedy. The proposed algorithm can provide a solution with an expected optimality ratio of at least p for monotone submodular objective functions and of p(1 − p) for non-monotone submodular objective functions. The individual computational complexity for each UAV is O(pr^2), where p ∈ (0,0.5] is the sampling probability, r is the number of tasks. The performance of the proposed algorithm is testified through digital simulations of a multi-target surveillance mission. Simulation results indicate that the proposed algorithm achieves a comparable solution quality to state-of-the-art algorithms with dramatically less running time. Moreover, a trade-off between the solution quality and the running time is obtained by adjusting the sampling probability.