微信服务号

微信订阅号

2025年4月13日 7:02 星期日
首页 > 过刊浏览>2006年第17卷第10期 >2029-2039
PDF HTML阅读 XML下载 导出引用 引用提醒
分布式约束满足问题研究及其进展
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60573077(国家自然科学基金);the Program for New Century Excellent Talents in University of China under Grant No.NCET-05-0549(新世纪优秀人才支持计划)


Research and Development of Distributed Constraint Satisfaction Problems
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [45]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    近年来,随着网络技术的快速发展和广泛应用,人工智能领域中的诸多问题,如时序安排、计划编制、资源分配等,越来越多地以分布形式出现,从而形成一类多主体系统.相应地,求解该类问题的传统约束满足问题也发展为分布式约束满足问题,分布式约束满足已经成为多主体系统求解的一般框架.首先,简要介绍了分布式约束满足问题的基本概念,总结了该问题的基本算法及其改进算法,并对这些算法的效率和性能进行了比较分析.然后,讨论了近年来分布式约束满足问题的若干典型应用;最后,给出了分布式约束满足问题基本形式的扩展和今后的研究方向.分布式约束满足问题最新研究进展表明:今后的工作将着重于面向现实问题求解的理论研究,为实际应用提供坚实的理论基础.

    Abstract:

    With the rapid development and wide application of the Internet technology, many problems of Artificial Intelligence, for example scheduling, planning, resource allocation etc., are formally distributed now, which turn into a kind of multi-agent system problems. Accordingly, the standard constraint satisfaction problems turn into distributed constraint satisfaction problems, which become the general architecture for resolving multi-agent system. This paper first briefly introduces the basic concepts of distributed CSPs, and then summarizes the basic and the improved algorithms. Their efficiency and performance are analyzed and the typical applications of distributed CSPs in recent years are discussed. Finally, this paper presents the extensions of the basic formalization and the research trends in this area. Recent related work indicates that the future work will focus on the theoretical research to present the solid theoretical foundation for the practical problems.

    参考文献
    [1]Montanari U.Networks of constraints:Fundamental properties and applications to picture processing.Information Sciences,1974,7(2):95-132.
    [2]Kumar V.Algorithms for constraint satisfaction problems:A survey.AI Magazine,1992,13(1):32-44.
    [3]Sun JG,Jing SY.Solving non-binary constraint satisfaction problem.Chinese Journal of Computers,2003,26(12):1746-1752 (in Chinese with English abstract).
    [4]Sun JG,Zhang YG.Model generation and constraint programming.In:Lu RQ,ed.The Knowledge Science and Computation Science.Beijing:Tsinghua University Press,2003.197-232 (in Chinese with English abstract).
    [5]Zhang XZ,Liu CN.Synchronization of the inference engine with the constraint solver in a CLP system.Journal of Software,1996,7(7):415-421 (in Chinese with English abstract).
    [6]Liu CN.Constraint logic programming--current status and future.In:Lu RQ,ed.The Knowledge Engineering and Knowledge Science Faced to the 21 st Century.Beijing:Tsinghua University Press,2001.251-279 (in Chinese with English abstract).
    [7]Liu JM,Han J,Tang YY.Multi-Agent oriented constraint satisfaction.Artificial Intelligence,2002,136(1):101-144.
    [8]Han J,Chen EH,Cai QS.Multi-Level strategy for maintaining arc consistency in problem solving and its implementation.Journal of Software,1998,9(8):622-627 (in Chinese with English abstract).
    [9]Chen EH,Zhang ZY,Wang XF.A fast recognition algorithm of CRC constraint networks.Journal of Software,2002,13(5):972-979 (in Chinese with English abstra ct).http://www.jos.org.cn/1000-9825/13/972.htm
    [10]Faltings B,Yokoo M.Introduction:Special issue on distributed constraint satisfaction.Artificial Intelligence,2005,161(1-2):1-5.
    [11]Yokoo M,Durfee EH,Ishida T,Kuwabara K.Distributed constraint satisfaction for formalizing distributed problem solving.In:12th Int'l Conf.on Distributed Computing Systems (ICDCS'92).Los Alamitos:IEEE Computer Society Press,1992.614-621.http://citeseer.ist.psu.edu/yokoo92distributed.html
    [12]Yokoo M,Hirayama K.Algorithms for distributed constraint satisfaction:A review.Autonomous Agents and Multi-Agent Systems,2000,3(2):185-207.
    [13]Trevisan L.Approximating satisfiable satisfiability problems.In:Burkard RE,Woeginger GJ,eds.Proc.of the 5th Annual European Symp.on Algorithms.Berlin:Springer-Verlag,1997.472-485.
    [14]Calisti M,Neagu N.Constraint satisfaction techniques and software agents.In:Proc.of the AIIA 2004 Workshop on Agents and Constraints.Perugia,2004.http://www.whitestein.com/pages/downloads/publications.html
    [15]Collin Z,Dechter R,Katz S.On the feasibility of distributed constraint satisfaction.In:Mylopoulos J,Reiter R,eds.Proc.of the 12th Int'l Joint Conf.on Artificial Intelligence.San Fransisco:Morgan Kaufmann Publishers,1991.318-324.
    [16]Zhang Y,Mackworth A.Parallel and distributed algorithms for finite constraint satisfaction problems.In:Sahni S,ed.Proc.of the 3rd IEEE Symp.on Parallel and Distributed Processing.Los Alamitos:IEEE Computer Society Press,1991.394-397.
    [17]Yokoo M.Asynchronous weak-commitment search for solving distributed constraint satisfaction problems.In:Montanari U,Rossi F,eds.Proc.of the 1st Int'l Conf.on Principles and Practice of Constraint Programming (CP'95).Berlin:Springer-Verlag,1995.88-102.
    [18]Yokoo M,Durfee EH,Ishida T,Kuwabara K.The distributedconstraint satisfaction problem:Formalization and algorithms.IEEE Trans.on Knowledge Data Engineering,1998,10(5):673-685.
    [19]Yokoo M,Hirayama K.Distributed breakout algorithm for solving distributed constraint satisfaction problems.In:Weiβ G,ed.Proc.of the 2nd Int'l Conf.on Multiagent Systems (ICMAS'96).Cambridge:MIT Press,1996.401-408.
    [20]Silaghi MC,Sam-Haroud D,Faltings B.Hybridizing ABT and AWC into a polynomial space,complete protocol with reordering.Technical Report,No.364,Lausanne:Swiss Federal Institute of Technology (EPFL),2001.
    [21]Silaghi MC,Sam-Haroud D,Faltings B.Consistency maintenance for ABT.In:Walsh T,ed.Proc.of the 7th Int'l Conf.on Principles and Practice of Constraint Programming (CP 2001).Berlin:Springer-Verlag,2001.271-285.
    [22]Hamadi Y,Bessière C,Quinqueton J.Backtracking in distributed constraint networks.In:Prade H,ed.Proc.of the 13th European Conf.on Artificial Intelligence (ECAI'98).Chichester:John Wiley and Sons,1998.219-223.
    [23]Bessière C,Maestre A,Brito I,Meseguer P.Asynchronous backtracking without adding links:A new member in the ABT family.Artificial Intelligence,2005,161(1-2):7-24.
    [24]Silaghi M,Faltings B.Asynchronous aggregation and consistency in distributed constraint satisfaction.Artificial Intelligence,2005,161(1-2):25-53.
    [25]Yokoo M,Hirayama K.Distributed constraint satisfaction algorithm for complex local problems.In:Demazeau Y,ed.Proc.of the 3rd Int'l Conf.on Multi-Agent System.Los Alamitos:IEEE Computer Society Press,1998.372-379.
    [26]Morris P.The breakout method for escaping from local minima.In:Fikes R,Lehnert W,eds.Proc.of the 11th National Conf.on Artificial Intelligence.Menlo Park:AAAI Press,1993.40-45.
    [27]Hirayama K,Yokoo M.The distributed breakout algorithms.Artificial Intelligence,2005,161(1-2):89-115.
    [28]Cheeseman P,Kanefsky B,Taylor W.Where the really hard problems are.In:Mylopoulos J,Reiter R,eds.Proc.of the 12th Int'l Joint Conf.on Artificial Intelligence.San Fransisco:Morgan Kaufmann Publishers,1991.331-337.
    [29]Hirayama K,Yokoo M.Distributed partial constraint satisfaction problem.In:Smolka G,ed.Proc.of the 3rd Int'l Conf.on Principles and Practice of Constraint Programming (CP'97).Berlin:Springer-Verlag,1997.222-236.
    [30]Yokoo M.Constraint relaxation in distributed constraint satisfaction problem.In:IEEE,ed.Proc.of the 5th Int'l Conf.on Tools with Artificial Intelligence.Los Alamitos:IEEE Computer Society Press,1993.56-63.
    [31]Faltings B,Macho-Gonzalez S.Open constraint programming.Artificial Intelligence,2005,161(1-2):181-208.
    [32]Yokoo M,Suzuki K,Hirayama K.Secure distributed constraint satisfaction:Reaching agreement without revealing private information.Artificial Intelligence,2005,161(1-2):229-245.
    [33]Wallace RJ,Freuder EC.Constraint-Based reasoning and privacy/efficiency tradeoffs in multi-agent problem solving.Artificial Intelligence,2005,161 (1-2):209-227.
    [34]Huhns MN,Bridgeland DM.Multiagent truth maintenance.IEEE Trans.on Systems,Man and Cybernetics,1991,21(6):1437-1445.
    [35]Zhang W,Wang G,Xing Z,Wittenburg L.Distributed stochastic search and distributed breakout:Properties,comparison and applications to constraint optimization problems in sensor networks.Artificial Intelligence,2005,161(1-2):55-87.
    [36]Modi PJ,Jung H,Tambe M,Shen WM,Kulkarni S.A dynamic distributed constraint satisfaction approach to resource allocation.In:Walsh T,ed.Proc.of the 7th Int'l Conf.on Principles and Practice of Constraint Programming (CP 2001).Berlin:Springer-Verlag,2001.685-700.
    [37]Solotorevsky G,Gudes E.Solving a real-life nurses time tabling and transportation problem using distributed CSP techniques.In:Proc.of the CP'96 Workshop on Constraint Programming Applications.1996.123-131.http://citeseer.ist.psu.edu/65211.html
    [38]Liu JS,Sycara KP,Multiagent coordination in tightly coupled task scheduling.In:Tokoro M,ed.Proc.of the 2nd Int'l Conf.on Multi-Agent Systems.Menlo Park:AAAI Press,1996.181-188.
    [39]Sycara KP,Roth S,Sadeh N,Fox MS.Distributed constrained heuristic search.IEEE Trans.on Systems,Man and Cybernetics,1991,21(6):1446-1461.
    [3]孙吉贵,景沈艳.非二元约束满足问题求解.计算机学报,2003,26(12):1746-1752.
    [4]孙吉贵,张永刚.模型生成与约束求解.见:陆汝钤,主编.知识科学与计算科学.北京:清华大学出版社,2003.197-232.
    [5]张秀珍,刘椿年.CLP系统中推理机与约束求解器的协调技术.软件学报,1996,7(7):415-421.
    [6]刘椿年,约束逻辑程序设计CLP--现状与未来.见:陆汝钤,主编.世纪之交的知识工程与知识科学.北京:清华大学出版社,2001.251-279.
    [8]韩靖,陈恩红,蔡庆生.求解过程中约束一致性维护的多层次策略研究.软件学报,1998,9(8):622-627.
    [9]陈恩红,张振亚,王煦法.相接行凸约束网络的快速识别算法.软件学报,2002,13(5):972-979.http://www.jos.org.cn/1000-9825/13/972.htm
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

王秦辉,陈恩红,王煦法.分布式约束满足问题研究及其进展.软件学报,2006,17(10):2029-2039

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

京公网安备 11040202500063号