低约束密度分布式约束优化问题的求解算法  

Algorithm for Distributed Constraint Optimization Problems with Low Constraint Density

作　　者：丁博[1] 王怀民[1,2] 史殿习[1] 唐扬斌[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]国防科学技术大学计算机学院并行与分布处理国家重点实验室,湖南长沙410073

出　　处：《软件学报》2011年第4期625-639,共15页Journal of Software

基　　金：国家自然科学基金(90818028);国家重点基础研究发展计划(973)(2011CB302600);国家杰出青年科学基金(60625203)

摘　　要：多Agent协作过程中的许多挑战都可以建模为分布式约束优化问题.针对低约束密度的分布式约束优化问题,提出了一种基于贪婪和回跳思想的求解算法.在该算法中,各Agent基于贪婪原则进行决策,能够利用低约束密度问题中大量赋值组合代价为0这一特点来加快求解速度.同时,Agent间的回跳机制可以在贪婪原则陷入局部最优时保证算法的完全性.相对于已有主流算法,该算法可以在保持多项式级别的消息长度/空间复杂度的前提下,以较少的消息数目求解低约束密度的分布式约束优化问题.给出了算法关键机制的正确性证明,并通过实验验证了算法的上述性能优势.Many challenges in multi-agent coordination can be modeled as Distributed Constraint Optimization Problems（DCOPs）.Aiming at DCOPs with low constraint density,this paper proposes a distributed algorithm based on the idea of greed and backjumping.In this algorithm,each agent makes decisions according to the greedy principle that the most assignment combinations in the problems with low constraint density occur at a zero cost,and the backjumping mechanism among the agents ensures the success of this algorithm,even when this greedy principle leads to a local optimum.In contrast with the existing mainstream DCOP algorithms,this algorithm can solve problems with low constraint density with fewer messages while keeping the polynomial message length and space complexity.The correctness of the key mechanisms in this algorithm has been proved,and those advantages in performance have been verified by experiments.

关 键 词：分布式约束优化问题 多AGENT 算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]