Header

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.

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.

Statistics

Altmetrics

Downloads

46 downloads since deposited on 01 Sep 2016
33 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:27 Aug 2017 22:49
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

Download

Download PDF  'Cuilt: a Scalable, Mix-and-Match Framework for Local Iterative Approximate Best-Response Algorithms'.
Preview
Content: Published Version
Filetype: PDF
Size: 196kB
View at publisher