English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/133296
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Coalition Structure Generation Problems: optimization and parallelization of the IDP algorithm

AuthorsCruz-Mencia, Francisco ; Cerquides, Jesús ; Espinosa, Antonio; Moure, Juan C.; Ramchurn, Sarvapali; Rodríguez-Aguilar, Juan Antonio
KeywordsCoalition Structure Generation
Multi-agent systems
Issue Date6-May-2013
CitationOPTMAS 2013 6th International Workshop on Optimisation in Multi-Agent Systems (in conjunction with AAMAS 2013 6th-7th May 2013)
AbstractThe Coalition Structure Generation (CSG) problem is wellknown in the area of Multi-Agent Systems. Its goal is to establish coalitions between agents while maximizing the global welfare. Between the existing dierent algorithms designed to solve the CSG problem, DP and IDP are the ones with smaller temporal complexity. After analyzing the operation of the DP and IDP algorithms, we identify which are the most frequent operations and propose an optimized method. Then, we analyze the memory access pattern and nd that its irregular behavior represents a potential performance bottleneck. In addition, we study and implement a method for dividing the work in dierent threads. We show that selecting the best algorithmic options can improve performance by 10x or more. Furthermore, the execution in a dual-socket, six-core processor computer may increase performance by an additional 5x-6x. With this, we are able to solve a CSG problem of 27 agents using our multi-core computer in 1.2 hours.
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
OPTMAS2013.pdf955,62 kBAdobe PDFThumbnail
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.