微信服务号

微信订阅号

2025年3月24日 13:52 星期一
首页 > 过刊浏览>2016年第27卷第2期 >264-279. DOI:10.13328/j.cnki.jos.004881
PDF HTML阅读 XML下载 导出引用 引用提醒
分布式约束优化方法研究进展
作者:
基金项目:

国家自然科学基金(61572116, 61572117); 国家科技支撑计划(2014BAI17B00); 宁夏回族自治区自然科学基金(NZ 13265); 中央高校东北大学基本科研专项基金(N120804001, N120204003)


Research Progress in Distributed Constraint Optimization Method
Author:
Fund Project:

National Natural Science Foundation of China (61572116, 61572117); National Key Technology Research and Development Program of China (2014BAI17B00); Natural Science Foundation of Ningxia Hui Autonomous Region (NZ13265); Fundamental Research Funds for the Central Universities of Northeastern University (N120804001, N120204003)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [39]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    多agent系统作为分布式人工智能研究领域的重要分支,已被广泛应用于多个领域中复杂系统的建模.而分布式约束优化作为一种多agent系统求解的关键技术,已成为约束推理研究的热点.首先对其适用性进行分析,并基于对已有算法的研究,总结出采用该方法解决问题的基本流程,在此基础上,从解的质量保证、求解策略等角度对算法进行了完整的分类;其次,根据算法分类结果以及执行机制,对大量经典以及近年来的分布式约束优化算法进行了深入分析,并从通信、求解质量、求解效率等方面对典型算法进行了实验对比;最后,结合分布式约束优化技术的求解优势给出了分布式约束优化问题的实际应用特征,总结了目前存在的一些问题,并对下一步工作进行了展望.

    Abstract:

    Multi agent system, one of important branches of distributed artificial intelligence, has been widely applied to modeling a serious of complex systems in diverse research fields. Significant research effort has sought to solve constraint programming with distributed constraint optimization which is a popular framework for multi agent system. The contributions of this research proceed from previous work in the following ways. First, based on the existing research, the applicability of distributed constraint optimization is analyzed, and general process of distributed constraint optimization algorithms is extracted. Second, a relatively complete classification of algorithms is provided from the perspective of quality assurance and solving strategies. Next, considering execution mechanism, a thorough analysis of a large number of classic algorithms proposed in recent years is carried out. Moreover, the experimental analysis of some typical algorithms with the metrics of communication, solution quality and efficiency is provided. Finally, combining the advantage of distributed constraint optimization technology, the application characteristics of distributed constraint optimization problem are proposed, and future work is discussed.

    参考文献
    [1] Lesser V, Corkill D. Challenges for multi-agent coordination theory based on empirical observations. In: Proc. of the AAMAS. Richland: IFAAMAS, 2014. 1157-1160.
    [2] Marconi M, Helmut P. Multi-User eco-driving training environment based on distributed constraint optimization. In: Proc. of the AAMAS. Richland: IFAAMAS, 2013. 925-932.
    [3] Liu JM, Han J, Tang YY. Multi-Agent oriented constraint satisfaction. Artificial Intelligence, 2002,136(1):101-144. [doi: 10.1016/S0004-3702(01)00174-6]
    [4] Han J, Chen EH, Cai QS. Multi-Level strategy for maintaining arc consistency in problem solving and its implementation. Ruan Jian Xue Bao/Journal of Software, 1998,9(8):622-627 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/9/622. htm
    [5] Chen EH, Zhang ZY, Wang XF. A fast recognition algorithm of CRC constraint networks. Ruan Jian Xue Bao/Journal of Software, 2002,13(5):972-979 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/13/972.htm
    [6] Arnon N, Alon G, Amnon M. Concurrent forward bounding for distributed constraint optimization problems. Artificial Intelligence Archive, 2012,193:186-216. [doi: 10.1016/j.artint.2012.09.002]
    [7] Zivan R, Meisels A. Message delay and discsp search algorithms. Annals of Mathematics and Artificial Intelligence, 2006,46:415-439. [doi: 10.1007/s10472-006-9033-2]
    [8] Silaghi MC. Using secure DisCSP solvers for generalized Vickrey auctions complete and stochastic techniques. In: Proc. of the Kaelbling and Saffiotti. 2005.
    [9] Yokoo M. Distributed Constraint Satisfaction, Foundation of Cooperation in Multi-Agent Systems. Berlin: Springer-Verlag, 2001. [doi: 10.1007/978-3-642-59546-2]
    [10] Pragnesh JM, Shen WM. Adopt: Asynchronous distributed constraint optimization with quality Guarantees. Artificial Intelligence, 2005,161:149-180. [doi: 10.1016/j.artint.2004.09.003]
    [11] Petcu A, Faltings B. DPOP: A scalable method for multi-agent constraint optimization. Artificial Intelligence, 2005,161:266-271.
    [12] Patricia G, Pedro M. Improving BnB-ADOPT+-AC. In: Proc. of the AAMAS. Richland: IFAAMAS, 2012. 273-280.
    [13] Mailler R, Lesser VR. Solving distributed constraint optimization problems using cooperative mediation. In: Proc. of the AAMAS. Washington: IEEE Computer Society, 2004. 438-445. [doi: 10.1109/AAMAS.2004.249]
    [14] Fitzpatrick S, Meertens LGLT. An experimental assessment of a stochastic, anytime, decentralized, soft colourer for sparse graphs. In: Proc. of the SAGA. Springer-Verlag, 2001. 49-64. [doi: 10.1007/3-540-45322-9_3]
    [15] Silaghi MC, Yokoo M. Nogood-Based asynchronous distributed optimization. In: Nakashima. et al., eds. Proc. of the AAMAS. ACM, 2006. 1389-1396. [doi: 10.1145/1160633.1160894]
    [16] Thomas L. Distributed constraint optimization: Privacy guarantees and stochastic uncertainty [Ph.D Thesis]. Lausanne: École Polytechnique Fédérale de Lausanne, 2011.
    [17] Chechetka A, Sycara K. No-Commitment branch and bound search for distributed constraint optimization. In: Proc. of the AAMAS. ACM, 2006. 1427-1429. [doi: 10.1145/1160633.1160900]
    [18] Gershman A, Meisels A, Zivan R. Asynchronous forward-bounding for distributed constraints optimization. In: Proc. of the ECAI. IOS Press, 2006. 133-140.
    [19] Gutierrez P, Meseguer P. BnB-ADOPT+ with several soft arc consistency levels. In: Proc. of the ECAI. IOS Press, 2010. 67-72.
    [20] Petcu A, Faltings B. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In: Proc. of the IJCAI. AAAI Press, 2007. 1452-1457.
    [21] Petcu A, Faltings B. O-DPOP: An algorithm for open/distributed constraint optimization. In: Proc. of the AAAI. AAAI Press, 2006. 703-708.
    [22] Kumar A, Petcu A, Faltings B. H-DPOP: Using hard constraints to prune the search space. In: Proc. of the IJCAI. AAAI Press, 2007. 40-55.
    [23] Pearce JP, Tambe M. Quality guarantees on k-optimal solutions for distributed constraint optimization problems. In: Proc. of the IJCAI. AAAI Press, 2007. 1446-1451.
    [24] Kiekintveld C, Yin Z, Kumar A, Tambe M. Asynchronous algorithms for approximate distributed constraint optimization with quality bounds. In: Proc. of the AAMAS. Richland: IFAAMAS, 2010. 133-140.
    [25] Vinyals M, Shieh E, Cerquides J, Rodriguez-Aguilar JA, Yin ZY, Tambe M, Bowring E. Quality guarantees for region optimal DCOP algorithms. In: Proc. of the AAMAS. Richland: IFAAMAS, 2011. 133-140.
    [26] Okimoto T, Joe J, Iwasaki A, Yokoo M, Faltings B. Pseudo-Tree-Based incomplete algorithm for distributed constraint optimization with quality bounds. In: Proc. of the CP. Springer-Verlag, 2011. 660-674. [doi: 10.1007/978-3-642-23786-7_50]
    [27] Meritxell V, Marc P, Rodriguez-Aguilar JA, Cerquides J. Divide-and-Coordinate: DCOPs by agreement. In: Proc. of the AAMAS. Richland: IFAAMAS, 2010. 149-156.
    [28] Daisuke H, Katsutoshi H. DeQED: An efficient divide-and-coordinate algorithm for DCOP. In: Proc. of the AAMAS. Richland: IFAAMAS, 2013. 556-572.
    [29] Ottens B, Dimitrakakis C, Faltings B. DUCT: An upper con_dence bound approach to distributed constraint optimization problems. In: Proc. of the AAAI. Phoenix: AAAI Press, 2012. 528-534.
    [30] Nguyen DT, Yeoh W, Lau HC. Distributed Gibbs: A memory-bounded sampling-based dcop algorithm. In: Proc. of the AAMAS. Richland: IFAAMAS, 2013. 167-174.
    [31] Rogers A, Farinelli A, Stranders R, Jennings NR. Bounded approximate decentralised coordination via the max-sum algorithm. Artificial Intellegence, 2011,175(2):730-759. [doi: 10.1016/j.artint.2010.11.001]
    [32] Rollon E, Larrosa J. Improved bounded max-sum for distributed constraint optimization. In: Proc. of the Constraint Programming. Springer-Verlag, 2012. 624-632. [doi: 10.1007/978-3-642-33558-7_45]
    [33] Larrosa J, Rollon E. Risk-Neutral bounded max-sum for distributed constraint optimization. In: Proc. of the Annual ACM Symp. on Applied Computing. ACM, 2013. 92-97. [doi: 10.1145/2480362.2480383]
    [34] Boi F, Thomas L, Adrian P. Privacy guarantees through distributed constraint satisfaction. In: Proc. of the IAT. IEEE, 2008. 350-358. [doi: 10.1109/WIIAT.2008.177]
    [35] Zang WX, Wang GD, Zhao X, Lars W. Distributed stochastic search and distributed breakout: properties, comparison and applications to constraint optimization problems in sensor networks. Journal of Articial Intelligence Research, 2005,161(1-2): 55-87. [doi: 10.1016/j.artint.2004.10.004]
    [36] Fioretto F, Campeotto F, Fioretto LDR, Yeoh W, Pontelli E. GD-GIBBS: A GPU-based sampling algorithm for solving distributed constraint optimization problems. In: Proc. of the AAMAS. Richland: IFAAMAS, 2014. 1339-1340.
    [37] Okimoto T, Schwind N, Clement M, Inoue K. Lp-Norm based algorithm for multi-objective distributed constraint optimization. In: Proc. of the AAMAS. Richland: IFAAMAS, 2014. 1427-1428.
    [38] Modi PJ, Jung H, Tambe M, Shen WM, Kulkarni S. A dynamic distributed constraint satisfaction approach to resource allocation. In: Proc. of the CP. Springer-Verlag, 2001. 685-700.
    [39] Parsons S, Rodríguez-Aguilar JA, Klein M. Auctions and bidding: Aguide for computer scientists. In: Proc. of the ACM Computing Surveys. ACM, 2011. [doi: 10.1145/1883612.1883617]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

段沛博,张长胜,张斌.分布式约束优化方法研究进展.软件学报,2016,27(2):264-279

复制
分享
文章指标
  • 点击次数:7083
  • 下载次数: 10246
  • HTML阅读次数: 3038
  • 引用次数: 0
历史
  • 收稿日期:2014-10-14
  • 最后修改日期:2014-12-15
  • 在线发布日期: 2015-11-11
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19728040位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号