Distributed task allocation algorithm for heterogeneous unmanned aerial vehicle swarm based on coalition formation game

This paper presents a distributed allocation algorithm based on a coalition formation game to solve the complex task allocation problem when heterogeneous resources are carried by large-scale UAV swarm and tasks have heterogeneous requirements. Firstly, in response to the large scale of the cluster and the heterogeneity of resources, the K-medoids clustering method is improved by incorporating consideration of heterogeneous resources to reasonably reduce the scale of the original problem. Therefore, the allocation difficulty is reduced through preprocessing. Considering task requirements, resources carried by UAV, and path costs, a task allocation model is established and the original problem is transformed into a coalition partitioning problem. Then a distributed task allocation algorithm based on a coalition formation game is used to solve it. Finally, the simulation results of assigning 30 tasks with heterogeneous requirements to 100 unmanned aerial vehicles carrying 3 types of heterogeneous resources show that the proposed algorithm can improve the real-time performance of task allocation, reduce resource redundancy, and fully leverage cluster efficiency.