Hedonic Coalition Formation for Distributed Task Allocation in Heterogeneous Multi-agent System

Due to the complexity of tasks in the real world, multiple agents with different capabilities tend to cooperate to handle diverse requirements of these tasks by forming coalitions. To solve the problem of finding optimal heterogeneous coalition compositions, this paper proposes a novel distributed hedonic coalition formation game method to solve the task allocation problem for multiple heterogeneous agents. Firstly, to quantify the intention of an agent joining each coalition, a utility function for each agent is designed based on the cost and the reward with regard to the given tasks, where the heterogeneous requirements of tasks are also considered. Then, a preference relation related to the utility function is designed for the self-interested agents autonomously choose to join or leave a coalition. Subsequently, a theorem is presented, and analyses have been conducted to show that the proposed method achieves a Nash-stable solution in the heterogeneous system. Further, to develop a Nash stable partition result, a distributed hedonic coalition formation algorithm containing prioritization and consensus stages is designed for each agent to make decisions. The algorithm is implemented based on local interactions with neighbor agents under a connected communication network. Finally, simulations are conducted to verify the performance of the proposed method. Results show that the proposed method has the feasibility in solving heterogeneous composition and the broader scalability in different scenarios.