Solving distributed constraint optimization problems using cooperative mediation

By R. Mailler, Victor R. Lesser. Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, 2004. AAMAS 2004., 2004

396 citations recorded by the source corpus.

Distributed Constraint Optimization Problems (DCDP) have, for a long time, been considered an important research area for multi-agent systems because a vast number of real-world situations can be modeled by them. The goal of many of the researchers interested in DCOP has been to find ways to solve them efficiently using fully distributed algorithms which are often based on existing centralized techniques. In this paper, we present an optimal, distributed algorithm called optimal asynchronous partial overlay (OptAPO) for solving DCOPs that is based on a partial centralization technique called cooperative mediation. The key ideas used by this algorithm are that agents, when acting as a mediator, centralize relevant portions of the DCDP, that these centralized subproblems overlap, and that agents increase the size of their subproblems as the problem solving unfolds. We present empirical evidence that shows that OptAPO performs better than other known, optimal DCOP techniques.

Subfields: Computer Networks and Communications, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/60889e111c8de7da2c5b37f7d9748ec03e08cdf4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Bounded approximate decentralised coordination via the max-sum algorithm (2009, methodology): “These DCOP techniques can be broadly divided into two classes: complete algorithms (i.e., algorithms that always find a solution that optimises the global objective function), such as ADOPT [5], OptAPO [6], DPOP [7], NCBB [8] and AFB [9]; and approximate algorithms such as the Distributed Stochastic”
A survey of multi-agent organizational paradigms (2004, methodology): “This resource allocation scheme employs a second, weaker form of federation through its use of mediators [59].”
Decentralised coordination of low-power embedded devices using the max-sum algorithm (2008, methodology): “The graph colouring problem is a canonical DCOP problem [4, 8], and is one that has previously been used to benchmark coordination algorithms for sensor networks [1, 15].”
Solving Transition Independent Decentralized Markov Decision Processes (2004, background): “Mailler and Lesser (2004), and Modi, Shen, Tambe, and Yokoo (2003) present state-of-the-art algorithms for solving DCOPs.”