UZH-Logo

Maintenance Infos

Cuilt: a Scalable, Mix-and-Match Framework for Local Iterative Approximate Best-Response Algorithms


Verman, Mihaela; Stutz, P; Hafen, Robin; Bernstein, Abraham (2016). Cuilt: a Scalable, Mix-and-Match Framework for Local Iterative Approximate Best-Response Algorithms. In: 22nd European Conference on Artificial Intelligence, The Hague, The Netherlands, 29 August 2016 - 2 September 2016, 1660-1661.

Abstract

Many real-world tasks can be modeled as constraint optimization problems. To ensure scalability and mapping to distributed scenarios, distributed constraint optimization problems (DCOPs) have been proposed, where each variable is locally controlled by its own agent. Most practical applications prefer approximate local iterative algorithms to reach a locally optimal and sufficiently good solution fast. Most implementations presented in the literature, however, only explored small-sized problems, typically up to 100 agents/variables. We implement CUILT, a scalable mix-and-match framework for Local Iterative Approximate Best-Response Algorithms for DCOPs, using the graph processing framework SIGNAL/COLLECT, where each agent is modeled as a vertex and communication pathways are represented as edges. Choosing this abstraction allows us to exploit the generic graph-oriented distribution/optimization heuristics and makes our proposed framework scalable, configurable, as well as extensible. We found that this approach allows us to scale to problems more than 3 orders of magnitude larger than results commonly published so far, to easily combine algorithms by mixing and matching, and to run the algorithms fast, in a parallel fashion.

Many real-world tasks can be modeled as constraint optimization problems. To ensure scalability and mapping to distributed scenarios, distributed constraint optimization problems (DCOPs) have been proposed, where each variable is locally controlled by its own agent. Most practical applications prefer approximate local iterative algorithms to reach a locally optimal and sufficiently good solution fast. Most implementations presented in the literature, however, only explored small-sized problems, typically up to 100 agents/variables. We implement CUILT, a scalable mix-and-match framework for Local Iterative Approximate Best-Response Algorithms for DCOPs, using the graph processing framework SIGNAL/COLLECT, where each agent is modeled as a vertex and communication pathways are represented as edges. Choosing this abstraction allows us to exploit the generic graph-oriented distribution/optimization heuristics and makes our proposed framework scalable, configurable, as well as extensible. We found that this approach allows us to scale to problems more than 3 orders of magnitude larger than results commonly published so far, to easily combine algorithms by mixing and matching, and to run the algorithms fast, in a parallel fashion.

Altmetrics

Downloads

12 downloads since deposited on 01 Sep 2016
12 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Event End Date:2 September 2016
Deposited On:01 Sep 2016 06:26
Last Modified:13 Nov 2016 06:21
Publisher:IOS Press Ebooks
Free access at:Official URL. An embargo period may apply.
Publisher DOI:https://doi.org/10.3233/978-1-61499-672-9-1660
Official URL:http://ebooks.iospress.com/volumearticle/44969
Other Identification Number:merlin-id:13478
Permanent URL: https://doi.org/10.5167/uzh-125850

Download

[img]
Preview
Content: Published Version
Filetype: PDF
Size: 196kB
View at publisher

TrendTerms

TrendTerms displays relevant terms of the abstract of this publication and related documents on a map. The terms and their relations were extracted from ZORA using word statistics. Their timelines are taken from ZORA as well. The bubble size of a term is proportional to the number of documents where the term occurs. Red, orange, yellow and green colors are used for terms that occur in the current document; red indicates high interlinkedness of a term with other terms, orange, yellow and green decreasing interlinkedness. Blue is used for terms that have a relation with the terms in this document, but occur in other documents.
You can navigate and zoom the map. Mouse-hovering a term displays its timeline, clicking it yields the associated documents.

Author Collaborations