Publication - A Mediation Based Protocol for Distributed Constraint Satisfaction

Authors: Mailler, Roger; and Lesser, Victor
Title: A Mediation Based Protocol for Distributed Constraint Satisfaction
Abstract: Distributed Constraint Satisfaction Problems (DisCSP) have 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 a constraint satisfaction problem and partly because real-world problems often present themselves in a distributed form. The agent paradigm is particularly well suited to handling problems of this type. Agents are easily distributable and have both encapsulated state as well as autonomous reasoning capabilities. This allows them to work together to solve problems that cannot be completely centralized due to security, dynamics, or complexity. In this paper, we present an algorithm called {\em asynchronous partial overlay (APO)} for solving DisCSPs that is based on a mediated negotiation process. The primary ideas behind this algorithm are that agents, when acting as a local mediator, partially centralize a subproblem of the CSP, that these partially centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the CSP as the problem solving unfolds.
Keywords: Cooperative Negotiation, Distributed AI, Distributed Search, Multi-Agent Systems, Negotiation, Search
Publication: The Fourth International Workshop on Distributed Constraint Reasoning, pp. 49 - 58
Location: Acapulco, Mexico
Date: August 2003
Sources: PS: /Documents/mailler/IJCAI03-mailler.ps
PDF: /Documents/mailler/IJCAI03-mailler.pdf
Reference: Mailler, Roger; and Lesser, Victor. A Mediation Based Protocol for Distributed Constraint Satisfaction. The Fourth International Workshop on Distributed Constraint Reasoning, pp. 49-58. August 2003.
bibtex: 
@article{Mailler-250,
  author    = "Roger Mailler and Victor Lesser",
  title     = "{A Mediation Based Protocol for Distributed
               Constraint Satisfaction}",
  journal   = "The Fourth International Workshop on Distributed
               Constraint Reasoning",
  pages     = "49-58",
  month     = "August",
  year      = "2003",
  address   = "Acapulco, Mexico",
  url       = "http://mas.cs.umass.edu/paper/250",
}