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

Authors:	Kim, Yoonheui; Krainin, Michael; and Lesser, Victor
Title:	Effective Variants of Max-Sum Algorithm to Radar Coordination and Scheduling
Abstract:	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. 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. 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.
Keywords:	Distributed Problem Solving
Publication:	UMass Computer Science Technical Report 2011-007
Date:	February 2011
Sources:	PDF: techical_kim_2011_007.pdf
Reference:	Kim, Yoonheui; Krainin, Michael; and Lesser, Victor. Effective Variants of Max-Sum Algorithm to Radar Coordination and Scheduling. UMass Computer Science Technical Report 2011-007. February 2011.
`bibtex`:	@article{Kim-502, author = "Yoonheui Kim and Michael Krainin and Victor Lesser", title = "{Effective Variants of Max-Sum Algorithm to Radar Coordination and Scheduling}", journal = "UMass Computer Science Technical Report 2011-007", month = "February", year = "2011", url = "http://mas.cs.umass.edu/paper/502", }