A task-oriented heuristic for repairing infeasible solutions to overlapping coalition structure generation

Guofu Zhang, Zhaopin Su*, Miqing Li, Meibin Qi, Jianguo Jiang, Xin Yao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)
170 Downloads (Pure)

Abstract

Overlapping coalition formation (OCF), which provides a natural framework for modeling scenarios where each agent can join and allocate their resources to several completely different coalitions at the same time, has become a very active topic in multiagent systems. For OCF in resource-constrained and subadditive task oriented domains, an agent may not possess sufficient resources to meet the needs of multiple coalitions simultaneously. As a result, there may exist many potential resource conflicts among the rival overlapping coalitions. To tackle such situations, we first present a natural variation of the traditional OCF model and analyze the size of the solution space and the computational complexity of the overlapping coalition structure generation (OCSG) problem. Next, we develop a generic task-oriented heuristic (TOH) for individual repairs that can be used in binary meta-heuristic algorithms to generate overlapping coalitions in a parallel manner. Moreover, we show how the proposed TOH repairs a 2-D individual to resolve resource conflicts and discuss several basic properties. Finally, to evaluate the effectiveness of TOH, we compare it with the existing agent-oriented heuristic for the OCSG problem. The empirical results demonstrate that TOH is of high efficiency and effectiveness in harsh environments with fierce competition over scarce resources.
Original languageEnglish
Pages (from-to)785-801
Number of pages17
JournalIEEE Transactions on Systems, Man and Cybernetics: Systems
Volume50
Issue number3
Early online date26 Jun 2017
DOIs
Publication statusPublished - Mar 2020

Bibliographical note

Funding:
This work was supported in part by the National Natural Science Foundation of China under Grant 61573125, Grant 61329302, and Grant 61371155, in part by the Engineering and Physical Sciences Research Council under Grant EP/K001523/1, and in part by the Anhui Provincial Natural Science Foundation under Grant 1608085MF131, Grant 1508085MF132, and Grant 1508085QF129.

Keywords

  • Overlapping coalition formation
  • Subadditive tasks
  • Constrained resources
  • Two-dimensional binary individual
  • Heuristic

Fingerprint

Dive into the research topics of 'A task-oriented heuristic for repairing infeasible solutions to overlapping coalition structure generation'. Together they form a unique fingerprint.

Cite this