TY - GEN
T1 - Coalition Structure Generation with the graphics processing unit
AU - Pawłowski, Krzysztof
AU - Kurach, Karol
AU - Svensson, Kim
AU - Ramchurn, Sarvapali
AU - Michalak, Tomasz P.
AU - Rahwan, Talal
N1 - Publisher Copyright:
Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - Coalition Structure Generation
KW - Dynamic programming
KW - GPU
UR - http://www.scopus.com/inward/record.url?scp=84911386758&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84911386758&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84911386758
T3 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
SP - 293
EP - 300
BT - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
T2 - 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014
Y2 - 5 May 2014 through 9 May 2014
ER -