A Distributed Hungarian-Based Algorithm for Multi-Robot Task Allocation with Load Balancing

Abstract

In this paper, we propose an extended version of the distributed matching-by-clone Hungarian-based algorithm (DMCHBA) to solve the multi-robot task allocation (MRTA) problem with heterogeneous robot capacities in a distributed setting. Each individual in the multi-robot system can effectively complete the conflict-free task allocation and reach global consensus through mutual communication and local computing. The key extensions to the baseline DMCHBA are: (a) elimination of the need for shared global information of the robot attributes, and (b) a modified cloning mechanism that not only accommodates robots with different capabilities but also ensures the balanced workload distribution. The numerical results confirm the load balancing performance as well as the scalability and flexibility of the proposed algorithm.