Coalition Structure Generation with the Graphics Processing Unit
University of Warsaw
13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS’14), 2014
@article{pawlowski2014coalition,
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},
year={2014}
}
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.
May 3, 2014 by hgpu
