微信服务号

微信订阅号

2025-4-3- 17
Home > Archive>Volume 22, Issue 4, 2011 >625-639. DOI:10.3724/SP.J.1001.2011.03765
PDF HTML XML Export Cite reminder
Algorithm for Distributed Constraint Optimization Problems with Low Constraint Density
Author:
Affiliation:

  • Article
    • | |
  • Metrics
    • |
  • Reference [29]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    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.

    Reference
    [1] Modi PJ, Shen WM, Tambe M, Yokoo M. Adopt: Asynchronous distributed constraint optimization with quality guarantees.Artificial Intelligence, 2005,161(1-2):149-180. [doi: 10.1016/j.artint.2004.09.003]
    [2] Dechter R. Constraint Processing. San Fransisco: Morgan Kaufmann Publishers, 2003.
    [3] Meisels A. Distributed Search By Constrained Agents. Heidelberg: Springer-Verlag, 2007.
    [4] Petcu A. A class of algorithms for distributed constraint optimization [Ph.D. Thesis]. Lausanne: Ecole Polytechnique Federale deLausanne, 2007.
    [5] Nguyen XT, Kowalczyk R, Phan MT. Modelling and solving QoS composition problem using fuzzy DisCSP. In: Proc. of the IEEEInt’l Conf. on Web Services. 2006. 55-62. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4032012 [doi: 10.1109/ICWS.2006.93]
    [6] Newman MEJ. The structure and function of complex networks. SIAM Review, 2003,45(2):167-256.
    [7] Chechetka A, Sycara K. No-Commitment branch and bound search for distributed constraint optimization. In: Proc. of the Int’lJoint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2006). 2006. 1427-1429. http://portal.acm.org/citation.cfm?id=1160900 [doi: 10.1145/1160633.1160900]
    [8] Petcu A, Faltings B. A scalable method for multiagent constraint optimization. In: Proc. of the Int’l Joint Conf. on ArtificialIntelligence (IJCAI 2005). 2005. 266. http://portal.acm.org/citation.cfm?id=1642336
    [9] He LJ, Zhang W. An agent organization structure for solving DCOP based on the partitions of constraint graph. Journal ofComputer Research and Development, 2007,44(3):434-438 (in Chinese with English abstract). [doi: 10.1360/crad20070310]
    [10] Pearce JP, Maheswaran RT, Tambe M. Dcop games for multi-agent coordination. In: Proc. of the Int’l Workshop on DistributedConstraint Reasoning. 2005. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.59.1370
    [11] Buckley F, Lewinter M. A Friendly Introduction to Graph Theory. Prentice Hall, 2002.
    [12] Maheswaran RT, Tambe M, Bowring E, Pearce JP, Varakantham P. Taking DCOP to the real world: Efficient complete solutionsfor distributed multi-event scheduling. In: Proc. of the Int’l Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS2004). 2004. 310-317. http://portal.acm.org/citation.cfm?id=1018762 [doi: 10.1109/AAMAS.2004.257]
    [13] Sultanik E, Modi PJ, Regli WC. On modeling multiagent task scheduling as a distributed constraint optimization problem. In: Proc.of the Int’l Joint Conf. on Artificial Intelligence (IJCAI 2007). 2007. 1531-1536. http://portal.acm.org/citation.cfm?id=1625523
    [14] Zhang W, Xing Z, Wang G, Wittenburg L. An analysis and application of distributed constraint satisfaction and optimizationalgorithms in sensor networks. In: Proc. of the Int’l Joint Conf. on Autonomous Agents and Multiagent Systems (AAMAS 2003).2003. 185-192. http://portal.acm.org/citation.cfm?id=860605 [doi: 10.1145/860575.860605]
    [15] Hirayama K, Yokoo M. Distributed partial constraint satisfaction problem. In: Proc. of the Int’l Conf. on Principles and Practice ofConstraint Programming. 1997. http://www.springerlink.com/index/w0g12371455j61x5.pdf [doi: 10.1007/BFb0017442]
    [16] Davin J, Modi PJ. Impact of problem centralization in distributed constraint optimization algorithms. In: Proc. of the Int’l JointConf. on Autonomous Agents and Multiagent Systems (AAMAS 2005). 2005. 1057-1063. http://portal.acm.org/citation.cfm?id=1082633 [doi: 10.1145/1082473.1082633]
    [17] Petcu A, Faltings B. MB-DPOP: A new memory-bounded algorithm for distributed optimization. In: Proc. of the Int’l Joint Conf.on Artificial Intelligence (IJCAI 2007). 2007. http://www.aaai.org/Library/IJCAI/2007/ijcai07-234.php
    [18] Petcu A, Faltings B. ODPOP: An algorithm for open/distributed constraint optimization. In: Proc. of the National Conf. onArtificial Intelligence (AAAI 2006). 2006. http://www.aaai.org/Library/AAAI/2006/aaai06-112.php
    [19] Larrosa J, Schiex T. Solving weighted CSP by maintaining arc consistency. Artificial Intelligence, 2004,159(1):1-26. [doi:10.1016/j.artint.2004.05.004]
    [20] Junges R, Bazzan A. Evaluating the performance of DCOP algorithms in a real world, dynamic problem. In: Proc. of the Int’l JointConf. on Autonomous Agents and Multiagent Systems (AAMAS 2008). 2008. 599-606. http://portal.acm.org/citation.cfm?id=1402308
    [21] Gershman A, Zivan R, Grinshpou T, Meisels A. Measuring distributed constraint optimization algorithms. In: Proc. of the Int’lWorkshop on Distributed Constraint Reasoning. 2008. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.165.8032
    [22] Bejar R, Domshlak C, Fernández C, Gomes C, Krishnamachari B, Selman B, Valls M. Sensor networks and distributed CSP:Communication, computation and complexity. Artificial Intelligence, 2005,161(1-2):117-148. [doi: 10.1016/j.artint.2004.10.001]
    [23] USC distributed constraint optimization problem (DCOP) repository. 2009. http://teamcore.usc.edu/dcop/
    [24] Galinier P, Hao JK. Tabu search for maximal constraint satisfaction problems. In: Proc. of the Int’l Conf. on Principles and Practiceof Constraint Programming. 1997. http://www.springerlink.com/content/d147151702x758w3/ [doi: 10.1007/BFb0017440]
    [25] Gershman A, Meisels A, Zivan R. Asynchronous forward-bounding for distributed constraints optimization. In: Proc. of theEuropean Conf. on Artificial Intelligence (ECAI 2006). 2006. http://portal.acm.org/citation.cfm?id=1567044
    [26] Ezzahir R, Bessiere C, Benelallam I. Dynamic backtracking for distributed constraint optimization. In: Proc. of the European Conf.on Artificial Intelligence (ECAI 2008). 2008. http://portal.acm.org/citation.cfm?id=1567527
    [27] Wang XF, Li X, Chen GR. Complex Network Theory and its Application. Beijing: Tsinghua University Press, 2006 (in Chinese).
    [28] Bar S, Gonen M, Wool A. An incremental super-linear preferential Internet topology model. In: Proc. of the Annual Passive &Active Measurement Workshop (PAM). 2004. http://www.springerlink.com/content/8pwttx4wkxwr7lvl/ [doi: 10.1007/978-3-540-24668-8_6]
    [29] Faltings B, Macho-Gonzalez S. Open constraint programming. Artificial Intelligence, 2005,161(1-2):181-208. [doi: 10.1016/j.artint.2004.10.001]
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

丁博,王怀民,史殿习,唐扬斌.低约束密度分布式约束优化问题的求解算法.软件学报,2011,22(4):625-639

Copy
Share
Article Metrics
  • Abstract:4992
  • PDF: 7464
  • HTML: 0
  • Cited by: 0
History
  • Received:June 16,2009
  • Revised:October 10,2009
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2032291Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063