主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第9期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
丁博,王怀民,史殿习,唐扬斌.低约束密度分布式约束优化问题的求解算法.软件学报,2011,22(4):625-639
低约束密度分布式约束优化问题的求解算法
Algorithm for Distributed Constraint Optimization Problems with Low Constraint Density
投稿时间:2009-06-16  修订日期:2009-10-10
DOI:10.3724/SP.J.1001.2011.03765
中文关键词:  分布式约束优化问题  多Agent  算法
英文关键词:distributed constraint optimization problem  multi-agent  algorithm
基金项目:国家自然科学基金(90818028); 国家重点基础研究发展计划(973)(2011CB302600); 国家杰出青年科学基金(60625203)
作者单位E-mail
丁博 国防科学技术大学 计算机学院,湖南 长沙 410073 dingbo@nudt.edu.cn 
王怀民 国防科学技术大学 计算机学院,湖南 长沙 410073国防科学技术大学 计算机学院 并行与分布处理国家重点实验室,湖南 长沙 410073  
史殿习 国防科学技术大学 计算机学院,湖南 长沙 410073  
唐扬斌 国防科学技术大学 计算机学院,湖南 长沙 410073  
摘要点击次数: 3562
全文下载次数: 4195
中文摘要:
      多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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利