Publication - Effective Variants of the Max-Sum Algorithm for Radar Coordination and Scheduling

Authors: Kim, Yoonheui; Krainin, Michael; Lesser, Victor
Title: Effective Variants of the Max-Sum Algorithm for Radar Coordination and Scheduling
Abstract: Abstract—Solving a coordination problem in a decentralized environment requires a large amount of resources and thus exploiting the innate system structure and external information as much as possible is necessary for such a problem to be solved in a computationally effective manner. This work proposes new techniques for saving communication and computational resources when solving distributed constraint optimization problems using the Max-Sum algorithm in an environment where system hardware resources are clustered. These techniques facilitate effective problem solving through the use of a pre-computed policy and two phase propagation on Max-Sum algorithm, one inside the clustered resources and one among clustered resources. This approach shows equivalent quality to the standard Max- Sum algorithm while reducing communication requirements on average by 50% and computation resources by 5 to 30% depending on the specific problem instance. These experiments were performed in a realistic setting involving the scheduling of a network of as many as 192 radars in 48 clusters.
Publication: Proceedings of 2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 357 - 364
Location: Lyon, France
Date: October 2011
Sources: PDF: /Documents/kim_iat11.pdf
Notes: Longer version available as technical report here: http://mas.cs.umass.edu/paper/502
Reference: Kim, Yoonheui; Krainin, Michael; Lesser, Victor. Effective Variants of the Max-Sum Algorithm for Radar Coordination and Scheduling. Proceedings of 2011 IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 357-364. October 2011. Longer version available as technical report here: http://mas.cs.umass.edu/paper/502
bibtex: 
@inproceedings{Kim-507,
  author    = "Yoonheui Kim and Michael Krainin and Victor Lesser",
  title     = "{Effective Variants of the Max-Sum Algorithm for
               Radar Coordination and Scheduling}",
  booktitle = "Proceedings of 2011 IEEE/WIC/ACM International
               Conference on Intelligent Agent Technology",
  pages     = "357-364",
  month     = "October",
  year      = "2011",
  address   = "Lyon, France",
  url       = "http://mas.cs.umass.edu/paper/507",
}