Coalition Structure Generation with the graphics processing unit

Krzysztof Pawłowski, Karol Kurach, Kim Svensson, Sarvapali Ramchurn, Tomasz P. Michalak, Talal Rahwan

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

Abstract

Coalition Structure Generation-the problem of finding the optimal division of agents into coalitions-has received considerable attention in recent AI literature. The fastest exact algorithm to solve this problem is IDP-IP [17], which is a hybrid of two previous algorithms, namely IDP and IP. Given this, it is desirable to speed up IDP as this will, in turn, improve upon the state-of-the-art. In this paper, we present IDPG-the first coalition structure generation algorithm based on the Graphics Processing Unit (GPU). This follows a promising, new algorithm design paradigm that can provide significant speedups. We show that IDPG is faster than IDP by two orders of magnitude.

Original languageEnglish (US)
Title of host publication13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages293-300
Number of pages8
ISBN (Electronic)9781634391313
StatePublished - 2014
Event13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 - Paris, France
Duration: May 5 2014May 9 2014

Publication series

Name13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Volume1

Other

Other13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
CountryFrance
CityParis
Period5/5/145/9/14

Keywords

  • Coalition Structure Generation
  • Dynamic programming
  • GPU

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Coalition Structure Generation with the graphics processing unit'. Together they form a unique fingerprint.

  • Cite this

    Pawłowski, K., Kurach, K., Svensson, K., Ramchurn, S., Michalak, T. P., & Rahwan, T. (2014). Coalition Structure Generation with the graphics processing unit. In 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014 (pp. 293-300). (13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014; Vol. 1). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).