A Decentralized Multi-Agent Algorithm for the Set Partitioning Problem

Gerrit Anders, Florian Siefert, Jan-Philipp Steghöfer, and Wolfgang Reif

A decentralized algorithm for solving set partitioning problems (SPP) has numerous applications in multi-agent systems. Apart from its relevance for problems of operations research, the SPP is equivalent to clustering of agents as well as the generation of coalition structures. SPADA, the algorithm proposed in this paper, does not use central metrics, relies exclusively on local agent knowledge, and respects agent autonomy. By trying to increase its own benefit, each subset of agents, representing a coalition or cluster, contributes to establishing a suitable partitioning. Agents are at liberty to decide if they want to join or leave a subset. All operations that change the composition of these subsets or the acquaintances of agents can be mapped onto a graph that represents these relations. The algorithm is evaluated in a scenario of decentralized energy management where it is used as a self-organization mechanism. The evaluations show that the quality of the partitioning is within 10% of the solutions found by a particle swarm optimizer with global knowledge.
published 03.09.2012 Proceedings of the 15th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA-2012)

Publisher: Springer Berlin Heidelberg



For questions regarding the publication, please contact!