Ismail, Sarah (Department of Mechanical and Aerospace Engineering, New Mexico S), Sun, Liang (New Mexico State University)

Decentralized Hungarian-Based Approach for Fast and Scalable Task Allocation

Scheduled for presentation during the "Autonomy - I" (WeA1), Wednesday, June 14, 2017, 11:00−11:20, Salon E

2017 International Conference on Unmanned Aircraft Systems, June 13-16, 2017, Miami Marriott Biscayne Bay, Miami, FL,

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

Abstract

In this paper, a novel decentralized task allocation algorithm based on the Hungarian approach is proposed. The proposed algorithm guarantees an optimal solution as long as the agent network is connected, i.e., the second smallest eigenvalue of the Laplacian matrix of the agent graph is greater than zero. In order to show the motivation of the proposed algorithm, the original centralized auction and Hungarian algorithms are compared in terms of the converging speed versus the number of agents. The result shows the superiority of the Hungarian algorithm in scalability over the auction algorithm. Then, the performance of the proposed decentralized Hungarian-Based algorithm (DHBA) is compared with the consensus-based auction algorithm (CBAA) under different situations, including different number of agents and different network topologies. The simulation results show that DHBA outperforms CBAA in all cases on the basis of the converging speed, the optimality of assignments, and computational time.