Regular Papers

International Journal of Control, Automation, and Systems 2024; 22(4): 1212-1224

https://doi.org/10.1007/s12555-022-1182-5

© The International Journal of Control, Automation, and Systems

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

Lexing Wang, Tenghai Qiu*, Zhiqiang Pu, Jianqiang Yi, Jinying Zhu, and Wanmai Yuan

Chinese Academy of Sciences

Abstract

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.

Keywords Coalition formation, hedonic games, heterogeneous agents, Nash stable, task allocation.

Article

Regular Papers

International Journal of Control, Automation, and Systems 2024; 22(4): 1212-1224

Published online April 1, 2024 https://doi.org/10.1007/s12555-022-1182-5

Copyright © The International Journal of Control, Automation, and Systems.

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

Lexing Wang, Tenghai Qiu*, Zhiqiang Pu, Jianqiang Yi, Jinying Zhu, and Wanmai Yuan

Chinese Academy of Sciences

Abstract

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.

Keywords: Coalition formation, hedonic games, heterogeneous agents, Nash stable, task allocation.

IJCAS
April 2024

Vol. 22, No. 4, pp. 1105~1460

Stats or Metrics

Share this article on

  • line

IJCAS

eISSN 2005-4092
pISSN 1598-6446