Open Systems Laboratory at Illinois

Maximal clique based distributed coalition formation for task allocation in large-scale multi-agent systems

By Predrag T. Tosic and Gul A. Agha. In MMAS, volume 3446 of Lecture Notes in Computer Science, 104–120. Springer, 2004.

Full Text:
Download PDF
Publisher Link:


We present a fully distributed algorithm for coalition formation among autonomous agents. The algorithm is based on two main ideas. One is a distributed computation of maximal cliques (of bounded sizes) in the underlying graph that captures the interconnection communication topology of the agents. Hence, given the current configuration of the agents, the coalitions that are formed are characterized by a high degree of connectivity, and therefore a high fault tolerance with respect to the subsequent node and/or link failures. The second idea is that each agent chooses its most preferable coalition based on how highly the agent values each such coalition in terms of the coalition members’ combined resources or capabilities. Coalitions with sufficient resources for fulfilling are preferable to the coalitions with resources that suffice only for completing less valuable tasks. We envision variants of our distributed algorithm presented herein to prove themselves useful coordination subroutines in many massively multi-agent system applications where the agents may repeatedly need to form temporary groups or coalitions of modest sizes in an efficient, online and fully distributed manner.

Keywords  distributed algorithms - large-scale multi-agent systems - distributed group formation - agent coalitions


    author = "Tosic, Predrag T. and Agha, Gul A.",
    editor = "Ishida, Toru and Gasser, Les and Nakashima, Hideyuki",
    title = "Maximal Clique Based Distributed Coalition Formation for
             Task Allocation in Large-Scale Multi-agent Systems",
    booktitle = "MMAS",
    crossref = "conf/mmas/2004",
    ee = "",
    keywords = "multi-agent systems, coordination algorithms",
    pages = "104-120",
    year = "2004",

    editor = "Ishida, Toru and Gasser, Les and Nakashima, Hideyuki",
    title = "Massively Multi-Agent Systems I, First International
             Workshop, MMAS 2004, Kyoto, Japan, December 10-11, 2004, Revised
             Selected and Invited Papers",
    isbn = "3-540-26974-6",
    publisher = "Springer",
    series = "Lecture Notes in Computer Science",
    volume = "3446",
    year = "2005",