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", } |