Publication - Cooperative Negotiation for Soft Real-Time Distributed Resource Allocation

Authors: Mailler, Roger; Lesser, Victor; and Horling, Bryan
Title: Cooperative Negotiation for Soft Real-Time Distributed Resource Allocation
Abstract: In this paper we present a cooperative negotiation protocol that solves a distributed resource allocation problem while conforming to soft real-time constraints in a dynamic environment. Two central principles are used in this protocol that allow it to operate in constantly changing conditions. First, we frame the allocation problem as an optimization problem, similar to a Partial Constraint Satisfaction Problem (PCSP), and use relaxation techniques to derive conflict (constraint violation) free solutions. Second, by using overlapping mediated negotiations to conduct the search, we are able to prune large parts of the search space by using a form of arc-consistency. This allows the protocol to both quickly identify situations where the problem is over-constrained and to identify the appropriate fix to the over-constrained problem. From the global perspective, the protocol has a hill climbing behavior and because it was designed to work in dynamic environments, is an approximate one. We describe the domain which inspired the creation of this protocol, as well as discuss experimental results.
Keywords: ANTs, Cooperative Negotiation, Distributed Search, Multi-Agent Systems, Negotiation, Real Time
Publication: Proceedings of Second International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2003), pp. 576 - 583
Location: Melbourne
Publisher: ACM Press
Date: July 2003
Sources: PS: /Documents/mailler/p455-mailler.ps
PDF: /Documents/mailler/p455-mailler.pdf
Notes: Also available as UMass Computer Science Technical Report 2002-49.
Reference: Mailler, Roger; Lesser, Victor; and Horling, Bryan. Cooperative Negotiation for Soft Real-Time Distributed Resource Allocation. Proceedings of Second International Joint Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2003), ACM Press, pp. 576-583. July 2003. Also available as UMass Computer Science Technical Report 2002-49.
bibtex: 
@inproceedings{mailler:SPAM03,
  author    = "Roger Mailler and Victor Lesser and Bryan Horling",
  title     = "{Cooperative Negotiation for Soft Real-Time
               Distributed Resource Allocation}",
  booktitle = "Proceedings of Second International Joint
               Conference on Autonomous Agents and MultiAgent
               Systems (AAMAS 2003)",
  publisher = "ACM Press",
  pages     = "576-583",
  month     = "July",
  year      = "2003",
  address   = "Melbourne",
  url       = "http://mas.cs.umass.edu/paper/241",
}