Header

UZH-Logo

Maintenance Infos

Exploring Hybrid Iterative Approximate Best-Response Algorithms for Solving DCOPs


Verman, Mihaela; Stutz, P; Hafen, Robin; Bernstein, Abraham (2016). Exploring Hybrid Iterative Approximate Best-Response Algorithms for Solving DCOPs. In: International Workshop on Optimisation in Multi-agent Systems, Singapore, 10 May 2016 - 10 May 2016.

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. The Iterative Approximate Best-Response Algorithms can be decomposed in three types of components and mixing different components allows to create hybrid algorithms. We implement a mix-and-match framework for these algorithms, 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 configurable as well as extensible. It allows us to easily recombine the components, create and exhaustively evaluate possible hybrid algorithms.

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. The Iterative Approximate Best-Response Algorithms can be decomposed in three types of components and mixing different components allows to create hybrid algorithms. We implement a mix-and-match framework for these algorithms, 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 configurable as well as extensible. It allows us to easily recombine the components, create and exhaustively evaluate possible hybrid algorithms.

Statistics

Downloads

9 downloads since deposited on 06 Jul 2016
7 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:10 May 2016
Deposited On:06 Jul 2016 13:02
Last Modified:06 Jul 2016 18:30
Publisher:s.n.
Free access at:Official URL. An embargo period may apply.
Official URL:http://www.cs.nmsu.edu/~wyeoh/OPTMAS2016/docs/OPTMAS_2016_paper_6.pdf
Other Identification Number:merlin-id:13269

Download

Preview Icon on Download
Preview
Filetype: PDF
Size: 299kB

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