Skip to main content

Coalition Structure Generation with the Graphic Processor Unit

Krzysztof Pawłowski‚ Karol Kurach‚ Tomasz Michalak and Talal Rahwan

Abstract

Coalition Structure Generation—the problem of finding the optimal set of coalitions— has received considerable attention in recent AI literature. The fastest exact algorithm to solve this problem is IDP-IP, due to Rahwan et al. (2012). This algorithm is a hybrid of two previous algorithms, namely IDP and IP. As such, 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 speed ups. We show that IDPG is faster than IDP by two orders of magnitude.

Institution
DCS
Number
RR−13−07
Pages
14
Year
2013