Publication - DJAO: A Communication-Constrained DCOP algorithm that combines features of ADOPT and Action-GDL

Authors: Kim, Yoonheui; Lesser, Victor
Title: DJAO: A Communication-Constrained DCOP algorithm that combines features of ADOPT and Action-GDL
Abstract: In this paper we propose a novel DCOP algorithm, called DJAO, that is able to efficiently find a solution with low communication overhead; this algorithm can be used for optimal and bounded approximate solutions by appropriately setting the error bounds. Our approach builds on distributed junction trees used in Action-GDL to represent independence relations among variables. We construct an AND/OR search space based on these junction trees. This new type of search space results in higher degrees for each OR node, consequently yielding a more efficient search graph in the distributed settings. DJAO uses a branch-and-bound search algorithm to distributedly find solutions within this search graph. We introduce heuristics to compute the upper and lower bound estimates that the search starts with, which is integral to our approach for reducing communication overhead. We empirically evaluate our approach in various settings.
Publication: 28th AAAI Conference on Artificial Intelligence (AAAI-14)
Location: Quebec City, Canada
Publisher: AAAI Press
Date: July 2014
Sources: PDF: /Documents/ykim_aaai14.pdf
Notes: 8 pages. (To appear.)
Reference: Kim, Yoonheui; Lesser, Victor. DJAO: A Communication-Constrained DCOP algorithm that combines features of ADOPT and Action-GDL. 28th AAAI Conference on Artificial Intelligence (AAAI-14), AAAI Press. July 2014. 8 pages. (To appear.)
bibtex: 
@inproceedings{Kim-530,
  author    = "Yoonheui Kim and Victor Lesser",
  title     = "{DJAO: A Communication-Constrained DCOP algorithm
               that combines features of ADOPT and Action-GDL}",
  booktitle = "28th AAAI Conference on Artificial Intelligence
               (AAAI-14)",
  publisher = "AAAI Press",
  month     = "July",
  year      = "2014",
  address   = "Quebec City, Canada",
  url       = "http://mas.cs.umass.edu/paper/530",
}