Anytime optimal coalition structure generation

Talal Rahwan, Sarvapali D. Ramchurn, Viet D. Dang, Andrea Giovannucci, Nicholas R. Jennings

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

Abstract

A key problem when forming effective coalitions of autonomous agents is determining the best groupings, or the optimal coalition structure, to select to achieve some goal. To this end, we present a novel, anytime algorithm for this task that is significantly faster than current solutions. Specifically, we empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents), using much less memory (O(2n) instead of 0(3n) for n agents). Moreover, our algorithm is the first to be able to find solutions for more than 17 agents in reasonable time (less than 90 minutes for 27 agents, as opposed to around 2 months for the best previous solution).

Original languageEnglish (US)
Title of host publicationAAAI-07/IAAI-07 Proceedings
Subtitle of host publication22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference
Pages1184-1190
Number of pages7
StatePublished - 2007
EventAAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference - Vancouver, BC, Canada
Duration: Jul 22 2007Jul 26 2007

Publication series

NameProceedings of the National Conference on Artificial Intelligence
Volume2

Other

OtherAAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference
CountryCanada
CityVancouver, BC
Period7/22/077/26/07

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Anytime optimal coalition structure generation'. Together they form a unique fingerprint.

  • Cite this

    Rahwan, T., Ramchurn, S. D., Dang, V. D., Giovannucci, A., & Jennings, N. R. (2007). Anytime optimal coalition structure generation. In AAAI-07/IAAI-07 Proceedings: 22nd AAAI Conference on Artificial Intelligence and the 19th Innovative Applications of Artificial Intelligence Conference (pp. 1184-1190). (Proceedings of the National Conference on Artificial Intelligence; Vol. 2).