%0 Journal Article
%T Algorithm for Distributed Constraint Optimization Problems with Low Constraint Density<br>低约束密度分布式约束优化问题的求解算法
%A DING Bo
%A WANG Huai-Min
%A SHI Dian-Xi
%A TANG Yang-Bin
%A <br>丁博
%A 王怀民
%A 史殿习
%A 唐扬斌
%J 软件学报
%D 2011
%I 
%X 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.
%K distributed constraint optimization problem
%K multi-agent
%K algorithm<br>分布式约束优化问题
%K 多Agent
%K 算法
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=1544A02D6395C7EF6EDE50AB60440C7F&yid=9377ED8094509821&vid=BC12EA701C895178&iid=E158A972A605785F&sid=42FF82ADD37D41AA&eid=46C2A519EDDA03DD&journal_id=1000-9825&journal_name=软件学报&referenced_num=0&reference_num=29