Publication - Solving Distributed Constraint Optimization Problems Using Cooperative Mediation

 Authors: Mailler, Roger; and Lesser, Victor Title: Solving Distributed Constraint Optimization Problems Using Cooperative Mediation Abstract: Distributed Constraint Optimization Problems (DCOP) 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 {\em 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 DCOP, 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. Keywords: Cooperative Negotiation, Distributed Problem Solving, Distributed Search, Multi-Agent Systems, Negotiation Publication: Proceedings of Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), pp. 438 - 445 Publisher: IEEE Computer Society Date: 2004 Sources: PS: /Documents/mailler/mailler-569.psPDF: /Documents/mailler/mailler-569.pdf Reference: Mailler, Roger; and Lesser, Victor. Solving Distributed Constraint Optimization Problems Using Cooperative Mediation. Proceedings of Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004), IEEE Computer Society, pp. 438-445. 2004. bibtex: @inproceedings{Mailler-355, author = "Roger Mailler and Victor Lesser", title = "{Solving Distributed Constraint Optimization Problems Using Cooperative Mediation}", booktitle = "Proceedings of Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2004)", publisher = "IEEE Computer Society", pages = "438-445", year = "2004", url = "http://mas.cs.umass.edu/paper/355", }