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

Predrag T. Tošić, Gul A. Agha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 highly desirable tasks 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.

Original languageEnglish (US)
Title of host publicationMassively Multi-Agent Systems I - First International Workshop, MMAS 2004, Revised Selected and Invited Papers
PublisherSpringer-Verlag Berlin Heidelberg
Pages104-120
Number of pages17
ISBN (Print)3540269746, 9783540269748
DOIs
StatePublished - Jan 1 2005
Event1st International Workshop on Massively Multi-Agent Systems, MMAS 2004 - Kyoto, Japan
Duration: Dec 10 2004Dec 11 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3446 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Workshop on Massively Multi-Agent Systems, MMAS 2004
CountryJapan
CityKyoto
Period12/10/0412/11/04

Keywords

  • Agent coalitions
  • Distributed algorithms
  • Distributed group formation
  • Large-scale multi-agent systems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Maximal clique based distributed coalition formation for task allocation in large-scale multi-agent systems'. Together they form a unique fingerprint.

Cite this