Publication - Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems

 Authors: Mailler,Roger; and Lesser,Victor Title: Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems Abstract: Distributed Constraint Satisfaction (DCSP) has long been considered an important area of research for multi-agent systems. This is partly due to the fact that many real-world problems can be represented as constraint satisfaction and partly because real-world problems often present themselves in a distributed form. In this paper, we present a complete, distributed algorithm called {\em asynchronous partial overlay (APO)} for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO performs better than other known, complete DCSP 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), Vol: 1, pp. 446 - 453 Location: New York Publisher: IEEE Computer Society Date: 2004 Sources: PS: /Documents/mailler/mailler-571.psPDF: /Documents/mailler/mailler-571.pdf Reference: Mailler,Roger; and Lesser,Victor. Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems. Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2004), Volume 1, IEEE Computer Society, pp. 446-453. 2004. bibtex: @inproceedings{Mailler-354, author = "Roger Mailler and Victor Lesser", title = "{Using Cooperative Mediation to Solve Distributed Constraint Satisfaction Problems}", booktitle = "Proceedings of Third International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2004)", volume = "1", publisher = "IEEE Computer Society", pages = "446-453", year = "2004", address = "New York", url = "http://mas.cs.umass.edu/paper/354", }