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

17 downloads since deposited on 06 Jul 2016
5 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:02 Feb 2018 10:08
Publisher:s.n.
OA Status:Green
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

Download PDF  'Exploring Hybrid Iterative Approximate Best-Response Algorithms for Solving DCOPs'.
Preview
Filetype: PDF
Size: 299kB