Publication - Improved Max-Sum Algorithm For DCOP with n-ary Constraints

Authors: Kim, Yoonheui; Lesser, Victor
Title: Improved Max-Sum Algorithm For DCOP with n-ary Constraints
Abstract: Many distributed constraint optimization (DCOP) algorithms include nodes´ local maximization operation that searches for the optimal variable assignment in a limited context. When the variable domain is discrete, this operation is exponential in the number of associated variables and thus computationally challenging. McAuley´s recent work on efficient inference implements this maximization operator such that in most cases only a small set of values is examined without loss of accuracy. We increase the applicability of such approach to DCOP in the three following ways. First, we extend it to non-pairwise graphs with better computational expected complexity. Second, we remove the requirement for offline sorting, which often is not realistic in many DCOP domains, while keeping the same complexity. Third, we provide a correlation measure to determine dynamically the appropriate cases to apply the technique since its efficiency is sensitive to characteristics of the data sets. We combine this technique with the Max-Sum algorithm and verify empirically that our approach provides significant time savings over the standard Max-Sum algorithm.
Keywords: Coordination, Distributed AI, Distributed Problem Solving, Multi-Agent Systems
Publication: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, pp. 191 - 198
Editor: Ito, Jonker, Gini, and Shehory
Location: St. Paul, MN
Publisher: IFAAMAS
Date: 2013
Sources: PDF: /Documents/kim_aamas2013.pdf
Reference: Kim, Yoonheui; Lesser, Victor. Improved Max-Sum Algorithm For DCOP with n-ary Constraints. Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems, Ito, Jonker, Gini, and Shehory, ed., IFAAMAS, pp. 191-198. 2013.
bibtex: 
@inproceedings{Kim-521,
  author    = "Yoonheui Kim and Victor Lesser",
  title     = "{Improved Max-Sum Algorithm For DCOP with n-ary
               Constraints}",
  booktitle = "Proceedings of the 12th International Conference
               on Autonomous Agents and Multiagent Systems",
  editor    = "Jonker Ito and Shehory Gini",
  publisher = "IFAAMAS",
  pages     = "191-198",
  year      = "2013",
  address   = "St. Paul, MN",
  url       = "http://mas.cs.umass.edu/paper/521",
}