基于面向对象有色Petri网的合同网协议建模研究
|
摘要
协作是多Agent系统(Multi-Agent System,简称MAS)研究的核心问题之一,而交互是协作的基础。由Randall Davis和Reid G.Smith借鉴商业活动中合同招标的运作模式,对任务和资源分配提出的经典交互协议——合同网协议已成为多Agent协作的关键技术。由于合同网协议任务的产生、分配以及管理者与承包商角色都是动态产生的,灵活性好,已广泛应用于MAS。但经典的合同网协议存在通信量大等不足,众多的研究者对其进行了扩展研究,但大多是用符号逻辑从形式理论上针对诚实友好合作型的协作问题进行的研究,形式理论虽然严谨,但晦涩难懂,不易实现。同时,在非面对面的、动态的网络环境中,Agent的诚实度不一样,这必然导致交互的过程中存在不安全隐患。因此,有必要对合同网协议的安全性进行建模研究,使其简便易懂,能适应MAS中复杂多变的协作问题。
本文将面向对象技术和有色Petri网相结合,采用面向对象有色Petri网(Object-Oriented Colored Petri Net,简称OOCPN),从合同网协议的宏观和微观两个方面进行了建模,得到安全的动态合同网协议(Secure-Dynamic Contract Net Protocol,简称SDCNP)模型。首先,微观上,结合Anand S.Rao和Michael P.Georgeff提出的Agent的认知型结构——BDI(Belief-Desire-Intention)的思想,在目前研究的基础上,引入信任度和阈值,对交互个体——BDI Agent的结构进行建模,通过信任度和阈值来限制发放标书的范围和控制评价标书的数量,达到减少通信量的目的。并采用Petri网的分析方法对模型进行了分析验证,得出模型具有有界性、安全性、活性和可达性;其次,宏观上,借鉴人类社会系统,对合同网协议的交互过程进行了改进,从“法律”和“道德”两个方面引入安全机制——仲裁惩罚机制和行为评估学习机制,一方面对自私Agent的不诚实行为采用“法律”手段进行仲裁惩罚,另一方面通过对自身行为的评估和学习,充分利用历史行为信息,尽量做出有益的行为决策。通过这两方面的安全保证,减少Agent对承诺的否认,增强了合同网协议的安全性。通过对其进行面向对象有色Petri网的建模,验证了模型的正确性;最后,采用REPAST仿真工具对不同模型进行了仿真模拟,对结果进行比较分析,表明SDCNP具有一定的高效性和安全性。
Collaboration is one of the most important issues in the Multi-Agent System (MAS). But the interaction is the basis for collaboration. The Contract Net Protocol (CPN) is a classical interactive protocol, which has been proposed by Randall Davis and Reid G Smith. It borrows ideas from invitation for bid in commercial activity, and it has been applied to tasks and resources distribution. The CPN has become the key technology in collaboration of MAS. In the CPN, the formation of task, distribution and Manager Agents and Contractor Agents are dynamically generated. It is flexibility, and has been widely used in MAS. But the classical CPN, there are many deficiencies, such as the excess communication and so on. Although now many researchers have proposed many methods to expanding and improving it, most of them studied by the logic symbols and the friendly cooperation. The logic symbols are rather obscure and also uneasy to program. At the same time, in the non-face-to-face, dynamic network environment, each Agent's honesty is not same. This will lead to insecurity in the interactive among the agents. Therefore, in order to adapt the dynamic, complex and volatile environment better, it is nessary to research a safe, simple and understandable model to the CPN.
So in this paper, we proposed SDCNP (Secure-Dynamic Contract Net Protocol) model using OOCPN (Object-Oriented Colored Petri Net), which is combined by Object-Oriented and Colored Petri Net to meet this needs. First, from the micro, with belief, desire and intention of BDI Agent which is proposed by Anand S.Rao and Michael P.Georgeff, also used other researchersbresearch results" Trust and Threshold, we model the internal structure of the interaction of the individual. And then use the analytical method of the Petri Net to analyze the model and make sure the model has the boundedness, security, reachability and liveness. Sencond, from the macroscopy, we improve the interaction process based on CPN. From two aspects, which are ! law5 and ! morality5 to guarantee the secrity of CPN. On the one hand, to punish the dishonest actions; on the other hand, according to learning and evaluating its own action and taking full advantage of its historical information. And then it can choose a beneficial action to execute. Through the two aspects of security assurances, reduced the disavowal to its own action, enhanced the security of the CPN. At last, through the simulation to different models using REPAST, the analysis and comparison indicate that the improved CPN, which is SDCNP, has a certain high efficiency and security.
本文将面向对象技术和有色Petri网相结合,采用面向对象有色Petri网(Object-Oriented Colored Petri Net,简称OOCPN),从合同网协议的宏观和微观两个方面进行了建模,得到安全的动态合同网协议(Secure-Dynamic Contract Net Protocol,简称SDCNP)模型。首先,微观上,结合Anand S.Rao和Michael P.Georgeff提出的Agent的认知型结构——BDI(Belief-Desire-Intention)的思想,在目前研究的基础上,引入信任度和阈值,对交互个体——BDI Agent的结构进行建模,通过信任度和阈值来限制发放标书的范围和控制评价标书的数量,达到减少通信量的目的。并采用Petri网的分析方法对模型进行了分析验证,得出模型具有有界性、安全性、活性和可达性;其次,宏观上,借鉴人类社会系统,对合同网协议的交互过程进行了改进,从“法律”和“道德”两个方面引入安全机制——仲裁惩罚机制和行为评估学习机制,一方面对自私Agent的不诚实行为采用“法律”手段进行仲裁惩罚,另一方面通过对自身行为的评估和学习,充分利用历史行为信息,尽量做出有益的行为决策。通过这两方面的安全保证,减少Agent对承诺的否认,增强了合同网协议的安全性。通过对其进行面向对象有色Petri网的建模,验证了模型的正确性;最后,采用REPAST仿真工具对不同模型进行了仿真模拟,对结果进行比较分析,表明SDCNP具有一定的高效性和安全性。
Collaboration is one of the most important issues in the Multi-Agent System (MAS). But the interaction is the basis for collaboration. The Contract Net Protocol (CPN) is a classical interactive protocol, which has been proposed by Randall Davis and Reid G Smith. It borrows ideas from invitation for bid in commercial activity, and it has been applied to tasks and resources distribution. The CPN has become the key technology in collaboration of MAS. In the CPN, the formation of task, distribution and Manager Agents and Contractor Agents are dynamically generated. It is flexibility, and has been widely used in MAS. But the classical CPN, there are many deficiencies, such as the excess communication and so on. Although now many researchers have proposed many methods to expanding and improving it, most of them studied by the logic symbols and the friendly cooperation. The logic symbols are rather obscure and also uneasy to program. At the same time, in the non-face-to-face, dynamic network environment, each Agent's honesty is not same. This will lead to insecurity in the interactive among the agents. Therefore, in order to adapt the dynamic, complex and volatile environment better, it is nessary to research a safe, simple and understandable model to the CPN.
So in this paper, we proposed SDCNP (Secure-Dynamic Contract Net Protocol) model using OOCPN (Object-Oriented Colored Petri Net), which is combined by Object-Oriented and Colored Petri Net to meet this needs. First, from the micro, with belief, desire and intention of BDI Agent which is proposed by Anand S.Rao and Michael P.Georgeff, also used other researchersbresearch results" Trust and Threshold, we model the internal structure of the interaction of the individual. And then use the analytical method of the Petri Net to analyze the model and make sure the model has the boundedness, security, reachability and liveness. Sencond, from the macroscopy, we improve the interaction process based on CPN. From two aspects, which are ! law5 and ! morality5 to guarantee the secrity of CPN. On the one hand, to punish the dishonest actions; on the other hand, according to learning and evaluating its own action and taking full advantage of its historical information. And then it can choose a beneficial action to execute. Through the two aspects of security assurances, reduced the disavowal to its own action, enhanced the security of the CPN. At last, through the simulation to different models using REPAST, the analysis and comparison indicate that the improved CPN, which is SDCNP, has a certain high efficiency and security.
引文
[1]毛新军.面向主体的软件开发[M].北京:清华大学出版社,2005-6.
[2]石纯一,张伟.基于Agent的计算[M].北京:清华大学出版社,2007-5.
[3]吴哲辉.Petri网导论[M].北京:机械工业出版社,2006-4.
[4]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,2005-3.
[5]王红卫.建模与仿真[M].北京:科学出版社,2003.1.
[6]吴世中,祝世雄,张文政等译.应用密码学:协议、算法与C源程序(第2版).北京:机械工业出版社,2001.
[7]徐趁肖,谭南林,苏树强.Petri网理论在现代制造技术中的应用[J].机械设计与制造工程,1999,28(2):30-32.
[8]贲可荣,张彦铎等.人工智能[M].北京:清华大学出版社,2006-3.
[9][美]Rebecca Wirfs-Brock,Alan McKean 著,倪硕,陈师译.对象设计:角色、责任和协作[M].北京:人民邮电出版社,2006-5.
[10]竞晓军,孙松林,周贤伟.智能信息安全[M].北京:国防工业出版社,2006-5.
[11]Anand S.Rao,Michael P.Georgeff.Modeling Rational Agents within a BDI-Architecture[C].In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning.1991,473-484.
[12]Michael Wooldridge,Nick Jennings.Intelligent Agents:Theory and Practice[J].Knowledge Engineering Review.1995-6,10(2):115-152.
[13]Stuart Russell,Peter Norvig.Artificial Intelligence:A Modern Approach[M].Upper Saddle River:Prentice Hall,1995.
[14]Yang Kun,Liu Da-you.Agents:Properties and Classifications[J].Computer Science.1999,26(9):30-34.
[15]Anand S.Rao,Michael P.Georgeff.BDI Agents:from Theory to Practice[C].In Proceeding of the 1st International Conference on Multi-Agent Systems.(ICM AS-95).San Francisco,USA.ACM Pres.1995,312-319.
[16]Sandholm T.W.An Implementation of the Contract Net Protocol based on Marginal Cost Calculations[C].In Proceedings of the 12th International Workshop on Distributed Artificial Intelligence.July 1993.
[17]Reid G.Smith.The Contract Net Protocol:High-Level Communication and Control in a Distributed Problem Solver[J].IEEE Transactions on Computers.1980-12,29(12):1104-1113.
[18]Randall Davis,Reid G.Smith.Negotiation as a Metaphor for Distributed Problem Solving[J].Artifical Intelligence.1983,20(1):63-109.
[19]李海刚,吴启迪.多Agent系统研究综述[J].同济大学学报.2003-6,31(6):728-732.
[20]刘大有,杨鲲,陈建中.Agent研究现状与发展趋势[J].软件学报.2000,11(3):315-321.
[21]Tuomas Sandholm,Victor Lesser.Issues in Automated Negotiation and Electronic Commence:Extending the Contract net Framework[C].In Proceedings of the First International Conference on Multi-Agent Systems(ICMAS-95).San Fransisco.1995-6.
[22]刘海龙,吴铁军.基于合同网的多Agent任务分配分布式优化算法[J].浙江大学学报(工学版).2001-9,35(5):550-554.
[23]兰少华,吴慧中,顾一禾.基于BDI的Agent合同网实现[J].小型微型计算机系统.2001-12,22(12):1471-1474.
[24]王立春,陈世福.多Agent多问题协商模型[J].软件学报.2002,13(8):1637-1643.
[25]陈国梁,王文杰,贾文臣.自适应BDI主体研究[J].计算机仿真.2004-10,21(10):103-106.
[26]马建红,王万森,季秋.基于改进的合同网的多专家Agent协作的研究[J].计算机应用,2004-11,24(11):47-49.
[27]张海俊,史忠植.动态合同网协议[J].计算机工程,2004-11,22(10):44-57.
[28]万武南,王晓京,宋春雨,刘旸.协同设计环境下的任务分配方法的研究[J].计算机工程.2005-8,31(8):151-152.
[29]万武南,王晓京,宋春雨,刘旸.基于范例推理的合同网模型[J].小型微型计算机系统.2005-9,26(9):1578-1581.
[30]宋海刚,陈学广.FIFP合同网协议的一种改进方案[J].华中科技大学学报(自然科学版)[J].2004-7,32(7):31-33.
[31]万武南,王晓京,刘旸.具有安全性的合同网模型[J].四川大学学报(工程科学版).2005-3,37(2):99-104.
[32]于振华,蔡远利,韩九强.基于面向对象Petri网的多Agent系统交互协议建模[J].计算机集成制造系统.2005-8,11(8):1064-1068.
[33]王怀民,陈火旺.对象作为智能主体[J].电子学报,1995-11,23(11):105-108.
[34]TADAO MURATA.Petri Nets:Properties,Analysis,and Application[J].Proceedings of the IEEE.1989-4,77(4):541-580.
[35]李秀,姜澄宇,王宁生,冷晟.一种面向对象的Petri网[J].南京航空航天大学学 报.1999-4,31(2):192-197.
[36]范玉顺,张军.面向对象Petri网方法及其在软件工程中的应用[J].计算机应用.1998-5,18(5):16-22.
[37]陶晓峰,蒋昌骏,段江涛,一种面向对象Petri网的构造及应用研究[J].机械科学于技术.2003-9,22(5):746-750.
[38]张文波,赵海,苏威积等.基于合同网模型的多代理协作研究[J].电子学报.2006-5,34(5):837-844.
[39]赵新宇,林作铨.合同网协议中的Agent可信度模型[J].计算机科学.2006,33(6):150-167.
[40]叶荣华,高济.一种面向多Agent协作和协商的消息机制[J].计算机工程与设计.2004-6,25(6):1024-1026.
[41]刘俊,曹斌,谭丹丹.基于拍卖机制的改进合同网协商策略[J].计算机应用.2007-2,27(2):494-496.
[42]郭锐锋,于东,刘明烈,徐心和.基于合同网的任务分配方法的研究[J].小型微型计算机系统 1999-10,20(10):740-743.
[43]杨鲲,刘大有,郭欣.一个具有高安全性的移动Agent系统模板结构[J].软件学报.2002,13(1):130-135.
[44]盛秋戬,赵志岜,刘少辉,史忠植.多主体团队交互协议[J].软件学报.2004,15(5):689-696.
[45]农毅,古天龙.一种基于行为评估的信任模型[J].沿海企业与科技.2006-11,108-110.
[46]黎波涛,罗军舟.不可否认协议的Petri网建模与分析[J].计算机研究与发.2005,45(9):1571-1577.
[47]李艳平.不可否认协议及其应用的研究[D].陕西师范大学,2004-4.
[48]李丹,陈利,李功丽,王光伟.基于面向对象Petri网的动态合同网协议通用模型[J].计算机应用.2007,27(8):1970-7972.
[49]李丹,陈利,李功丽.面向对象Petri网的合同网协议模型的一种改进方案[J].计算机应用与软件.已录用.
[50]姜昌华等.REPAST--一个多Agent仿真平台[J].系统仿真学报,2006,18(8):2319-2322.
[51]赵剑冬,林健.基于Agent的REPAST仿真分析与实现[J].计算机仿真.2007-9,24(9):266-284.
[52]郝成民,刘湘伟,郭世杰,晏洪勇.REPAST:基于Agent建模仿真的可扩展平台[J].2007-11,24(11):285-288.
[2]石纯一,张伟.基于Agent的计算[M].北京:清华大学出版社,2007-5.
[3]吴哲辉.Petri网导论[M].北京:机械工业出版社,2006-4.
[4]袁崇义.Petri网原理与应用[M].北京:电子工业出版社,2005-3.
[5]王红卫.建模与仿真[M].北京:科学出版社,2003.1.
[6]吴世中,祝世雄,张文政等译.应用密码学:协议、算法与C源程序(第2版).北京:机械工业出版社,2001.
[7]徐趁肖,谭南林,苏树强.Petri网理论在现代制造技术中的应用[J].机械设计与制造工程,1999,28(2):30-32.
[8]贲可荣,张彦铎等.人工智能[M].北京:清华大学出版社,2006-3.
[9][美]Rebecca Wirfs-Brock,Alan McKean 著,倪硕,陈师译.对象设计:角色、责任和协作[M].北京:人民邮电出版社,2006-5.
[10]竞晓军,孙松林,周贤伟.智能信息安全[M].北京:国防工业出版社,2006-5.
[11]Anand S.Rao,Michael P.Georgeff.Modeling Rational Agents within a BDI-Architecture[C].In Proceedings of the 2nd International Conference on Principles of Knowledge Representation and Reasoning.1991,473-484.
[12]Michael Wooldridge,Nick Jennings.Intelligent Agents:Theory and Practice[J].Knowledge Engineering Review.1995-6,10(2):115-152.
[13]Stuart Russell,Peter Norvig.Artificial Intelligence:A Modern Approach[M].Upper Saddle River:Prentice Hall,1995.
[14]Yang Kun,Liu Da-you.Agents:Properties and Classifications[J].Computer Science.1999,26(9):30-34.
[15]Anand S.Rao,Michael P.Georgeff.BDI Agents:from Theory to Practice[C].In Proceeding of the 1st International Conference on Multi-Agent Systems.(ICM AS-95).San Francisco,USA.ACM Pres.1995,312-319.
[16]Sandholm T.W.An Implementation of the Contract Net Protocol based on Marginal Cost Calculations[C].In Proceedings of the 12th International Workshop on Distributed Artificial Intelligence.July 1993.
[17]Reid G.Smith.The Contract Net Protocol:High-Level Communication and Control in a Distributed Problem Solver[J].IEEE Transactions on Computers.1980-12,29(12):1104-1113.
[18]Randall Davis,Reid G.Smith.Negotiation as a Metaphor for Distributed Problem Solving[J].Artifical Intelligence.1983,20(1):63-109.
[19]李海刚,吴启迪.多Agent系统研究综述[J].同济大学学报.2003-6,31(6):728-732.
[20]刘大有,杨鲲,陈建中.Agent研究现状与发展趋势[J].软件学报.2000,11(3):315-321.
[21]Tuomas Sandholm,Victor Lesser.Issues in Automated Negotiation and Electronic Commence:Extending the Contract net Framework[C].In Proceedings of the First International Conference on Multi-Agent Systems(ICMAS-95).San Fransisco.1995-6.
[22]刘海龙,吴铁军.基于合同网的多Agent任务分配分布式优化算法[J].浙江大学学报(工学版).2001-9,35(5):550-554.
[23]兰少华,吴慧中,顾一禾.基于BDI的Agent合同网实现[J].小型微型计算机系统.2001-12,22(12):1471-1474.
[24]王立春,陈世福.多Agent多问题协商模型[J].软件学报.2002,13(8):1637-1643.
[25]陈国梁,王文杰,贾文臣.自适应BDI主体研究[J].计算机仿真.2004-10,21(10):103-106.
[26]马建红,王万森,季秋.基于改进的合同网的多专家Agent协作的研究[J].计算机应用,2004-11,24(11):47-49.
[27]张海俊,史忠植.动态合同网协议[J].计算机工程,2004-11,22(10):44-57.
[28]万武南,王晓京,宋春雨,刘旸.协同设计环境下的任务分配方法的研究[J].计算机工程.2005-8,31(8):151-152.
[29]万武南,王晓京,宋春雨,刘旸.基于范例推理的合同网模型[J].小型微型计算机系统.2005-9,26(9):1578-1581.
[30]宋海刚,陈学广.FIFP合同网协议的一种改进方案[J].华中科技大学学报(自然科学版)[J].2004-7,32(7):31-33.
[31]万武南,王晓京,刘旸.具有安全性的合同网模型[J].四川大学学报(工程科学版).2005-3,37(2):99-104.
[32]于振华,蔡远利,韩九强.基于面向对象Petri网的多Agent系统交互协议建模[J].计算机集成制造系统.2005-8,11(8):1064-1068.
[33]王怀民,陈火旺.对象作为智能主体[J].电子学报,1995-11,23(11):105-108.
[34]TADAO MURATA.Petri Nets:Properties,Analysis,and Application[J].Proceedings of the IEEE.1989-4,77(4):541-580.
[35]李秀,姜澄宇,王宁生,冷晟.一种面向对象的Petri网[J].南京航空航天大学学 报.1999-4,31(2):192-197.
[36]范玉顺,张军.面向对象Petri网方法及其在软件工程中的应用[J].计算机应用.1998-5,18(5):16-22.
[37]陶晓峰,蒋昌骏,段江涛,一种面向对象Petri网的构造及应用研究[J].机械科学于技术.2003-9,22(5):746-750.
[38]张文波,赵海,苏威积等.基于合同网模型的多代理协作研究[J].电子学报.2006-5,34(5):837-844.
[39]赵新宇,林作铨.合同网协议中的Agent可信度模型[J].计算机科学.2006,33(6):150-167.
[40]叶荣华,高济.一种面向多Agent协作和协商的消息机制[J].计算机工程与设计.2004-6,25(6):1024-1026.
[41]刘俊,曹斌,谭丹丹.基于拍卖机制的改进合同网协商策略[J].计算机应用.2007-2,27(2):494-496.
[42]郭锐锋,于东,刘明烈,徐心和.基于合同网的任务分配方法的研究[J].小型微型计算机系统 1999-10,20(10):740-743.
[43]杨鲲,刘大有,郭欣.一个具有高安全性的移动Agent系统模板结构[J].软件学报.2002,13(1):130-135.
[44]盛秋戬,赵志岜,刘少辉,史忠植.多主体团队交互协议[J].软件学报.2004,15(5):689-696.
[45]农毅,古天龙.一种基于行为评估的信任模型[J].沿海企业与科技.2006-11,108-110.
[46]黎波涛,罗军舟.不可否认协议的Petri网建模与分析[J].计算机研究与发.2005,45(9):1571-1577.
[47]李艳平.不可否认协议及其应用的研究[D].陕西师范大学,2004-4.
[48]李丹,陈利,李功丽,王光伟.基于面向对象Petri网的动态合同网协议通用模型[J].计算机应用.2007,27(8):1970-7972.
[49]李丹,陈利,李功丽.面向对象Petri网的合同网协议模型的一种改进方案[J].计算机应用与软件.已录用.
[50]姜昌华等.REPAST--一个多Agent仿真平台[J].系统仿真学报,2006,18(8):2319-2322.
[51]赵剑冬,林健.基于Agent的REPAST仿真分析与实现[J].计算机仿真.2007-9,24(9):266-284.
[52]郝成民,刘湘伟,郭世杰,晏洪勇.REPAST:基于Agent建模仿真的可扩展平台[J].2007-11,24(11):285-288.