Distributed Matching-By-Clone Hungarian-Based Algorithm for Task Allocation of Multi-Agent Systems

In this article, we present a novel approach, namely distributed matching-by-clone hungarian-based algorithm (DM- CHBA), to multiagent task-allocation problems, in which the num- ber of agents is smaller than the number of tasks. The proposed DMCHBA assumes that agents employ an implicit coordination mechanism and consists of two iterative phases, i.e., the commu- nication phase and the assignment phase. In the communication phase, agents communicate with their connected neighbors and exchange their local knowledge base until they converge on the global knowledge base. In the assignment phase, each agent builds a squared cost matrix by cloning agents and adding pseudotasks when necessary, and applying the Hungarian method for task allocation. A local planning algorithm is then applied to identify the order of task execution for an agent. The proposed DM- CHBA is proven to produce conflict-free assignments among agents in finite time. We compare the performance of DMCHBA with the consensus-based bundle algorithm, the distributed recursive Hungarian-based algorithms, and the cluster-based Hungarian algorithm (CBHA) in Monte-Carlo simulations with different num- bers of agents and tasks. The numerical results reveal the superior convergence and optimality of DMCHBA over all other selected algorithms.