Coalition Structure Generation with the Graphics Processing Unit

Krzysztof Pawlowski, Karol Kurach, Kim Svensson, Sarvapali Ramchurn, Tomasz P. Michalak, Talal Rahwan
University of Warsaw
13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’14), 2014


   title={Coalition Structure Generation with the Graphics Processing Unit},

   author={Pawlowski, Krzysztof and Kurach, Karol and Svensson, Kim and Ramchurn, Sarvapali and Michalak, Tomasz P. and Rahwan, Talal},



Download Download (PDF)   View View   Source Source   Source codes Source codes




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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: