基于政策的层次系统协作模型

来源 :软件 | 被引量 : 0次 | 上传用户:luoxiaozhang
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  摘要:为了解决大型层次系统中多Agent间的协作问题,提出了一种基于政策的协作模型。首先分析层次系统中Agent间协作的特点,然后给出相关概念定义,构建Agent政策框架及政策分享机制,最后提出协作模型算法。实践表明,该模型能够在大型、分布式环境中实现资源和服务的协同,使Agent的行为决策更加规范可控,因此具有高度的灵活性及扩展性,对于解决层次MAS协作问题具有一定的参考价值。
  关键词:政策;多Agent系统;协作模型
  中图分类号:TP391文献标识码:Adoi: 10.3969/j.issn.1003-6970.2011.03.014
  
  Policy-driven cooperation model in hierarchical multi-agent system
  LI Chang1, FENG Xiao-jie2
  (1.Combined-Operations Staff Room, Artillery Command Academy of PLA, Xuanhua 075100, China;
  2.PLA General Staff Communications Training Base, Xuanhua 075100, China)
  【Abstract】 To solve the problem of cooperating among large hierarchical multi-agent system, a Policy-Driven cooperation model is proposed. First, we analyze the cooperation peculiarity in the hierarchical MAS. Then we define the correlative domain, construct the policy-driven Agent framework and identify the policy-share mechanisms. Finally we give an algorithm based policy-driven. Through a field fight case and the result, it is demonstrated the improved cooperation model can be used to solve the task assigned problem of MAS. The result show that the model maintained a certain degree of autonomy and at the same time enhanced the controllability at the organizational level.
  【Key words】policy; Multi-Agent system; Cooperation model
  0引言
  随着MAS(Multi-Agent System)技术的日益成熟,越来越多大型、开放、复杂的领域利用MAS技术构建仿真系统,并取得了许多重要成果[1,2]。在MAS中,Agent间有效的协作不仅能提高单个Agent的功效,也能提高系统的整体性能,增强多Agent系统解决问题的能力,加强系统的柔性[3]。Agent间的协作关系包括点对点型、中央控制型、超类子类型以及层次型[4]。其中,由于层次型协作关系更适合于描述类似于人类社会的组织结构而备受研究者的青睐,成为目前研究的热点问题。
  目前的协作机制研究,主要基于合同网[5,6]。虽然包括基于合同网在内的协作机制为Agent之间的协作奠定了基础,但对个体Agent而言,现有的BDI逻辑不能简洁的促使其采取与系统整体期望相一致的行为,也不能使相互陌生的Agent动态地组成协同系统。
  针对以上问题,本文采用政策作为整个层次MAS协作的行为准则,提出基于政策的多Agent协作模型,从而使层次MAS协作具有较高的灵活性和扩展性。
  1层次系统中Agent协作特点
  层次系统协作关系如图1所示。
  图1层次系统Agent协作关系图
  Agent协作的过程是对任务进行分解并由多个Agent分别完成的过程。对任务的分解,可以表示为图1所示的树型结构图。图中,T0为上级Agent接受的任务,该Agent将T0分解为T1和T2。T2交给某一个下级Agent完成,同时将T1继续分解。所以T0=T1+T2,T1=T3+T4…。该树的所有叶子结点代表分配给所有下级Agent的子任务,它们组成总任务。
  层次系统中Agent的协作与商务领域中研究的基于市场机制的竞争、投标、合同的协作方式截然不同。在层次系统中,协作关系极少存在投标、中标等问题,更多的是任务、命令、指示等。在Agent间的相互关系上,不是竞争、欺骗等关系,而是指挥、控制等关系[7]。与一般意义上的Agent协作不同,层次系统中Agent协作具有以下特点:
  (1) 层次系统中,各个职能Agent虽然表现出一定的自治性,但是其对外更多的表现为受控性,即各个职能Agent必须无条件的接受上级Agent的指挥控制。同时上级Agent对下级Agent表现出绝对的权威性。
  (2) 协作的时机主要有以下几种情况:针对某一任务,单个Agent由于自身资源所限无法完成,需要其他Agent支援配合;能完成某任务,但其执行任务的某个动作,依赖于其他Agent的前序动作;存在命令,由上级Agent根据效用思维进行推理认为,其下级某些Agent联合执行任务效用最好,即以消息的形式下达命令。
  2问题定义
  政策、MAS以及Agent行为被视为相互独立的部分,它们之间通过一定的组合及映射关系,最终实现Agent行为的输出。而且通过行为之间的组合,可以反映多个政策的要求。为了说明基于政策的Agent间协作过程,给出相关定义如下。
  定义1政策是系统对在某种状态下所作行为选择的一种陈述性描述,即规定了主体在什么状态或条件下,发生了什么事件时该做些什么动作[8]。通常政策是指导系统行为的方法,它规定了MAS的目标、动作及效用。
  定义政策P为一个四元组P=,其中,Strigger是触发政策执行的状态集,A是政策执行的动作集,Sgoal是政策执行后的状态集,U是衡量执行效果的效用函数。
  定义2Agent是处在某个环境中的计算机系统,系统有能力在这个环境中自主行动以实现其设计目标[9]。它具有自主性、反应性、预动性、社会性、协作性、移动性等特征。
  定义Agent为一个五元组,即Ag =,其中,Att表示Agent的属性,包括内在属性和外在属性;P为Agent必须遵循的政策;Ser为Agent所具有的服务;FKB表示知识库;BDI表示Agent的心理模型。
  定义3MAS协作模型为一个五元组M=<Ag,G,P,T,S>,其中Ag={A1,A2,…,An}是参与协作的Agent集,G表示在特定情况下的协作目标,P表示协作政策,T表示协作成员集,Ag∈T,S表示协作配置。
  处于时刻T、状态S的MAS通常被描述为状态和值的序列。政策指导系统执行一个动作,从而使系统达到一个新的状态S’。因此,政策可以被视为是一个状态转换函数[10]。
  定义4行为表示为一个三元组B=|OP,state,cost|。其中,OP是指该行为的操作,反映该行为要提供的功能;state={accepted | refused | failed | complete}表示该行为的状态;cost为执行代表,表明执行该行为所消耗的资源总量。
  由定义可知,一个政策P可产生引导Agent的一个行为B,假如当前存在两个政策P1、P2作用于同一客体上,标志为P1的政策产生行为B1,标志为P2的政策产生行为B2。可以通过B1、B2的组合combinedB(B1,B2)来同时反映政策P1、P2的要求。对于一个政策导向过程来说,关键在于根据政策来实现Agent与行为之间的绑定。
  政策驱动的实质是实现集合m∈PA×BA×AA中一个状态到另外一个状态的改变。其中,PA代表政策域;BA代表行为域;AA代表Agent域[11]。
  3基于政策的多Agent协作机制
  多Agent协作是指多个Agent通过协调各自的行为,围绕共同的目标而相互作用的合作过程[12]。在协同过程中,利用政策作为Agent协同的导向和调控的主要手段,在政策的规范和驱动下,Agent执行规定的协同动作,推动协同的进程,并且维持协同进程的正常进行。
  3.1政策驱动的Agent结构模型
  图2展示了在MAS中Agent与其它Agent的交互情况。
  每一个Agent都有两种属性,分别是外部属性和内部属
  性[13]。内部属性是Agent的固有属性,包括每一个Agent的地位、功能及与其他Agent交互的政策等。
  图2层次系统Agent协作关系图
  外部属性包括外部相关信息、在特定环境中其他Agent所呈现出的特殊属性等。当Agent加入到新的MAS中时,它必须通过其内在属性通知系统构造服务它的存在。由内在属性,系统构造服务构造出所加入进来的Agent的外在属性。
  政策按照不同的作用域分为两种——全局政策和个体政策。全局政策是系统内部各Agent之间必须遵守的规则的形式化,体现了系统的全局利益。个体政策是单个Agent自己必须遵守的,体现个体偏好或行为约束。
  与不同政策对应的是不同的服务,政策启动相应服务。常用的服务有系统配置服务、发现服务、定位服务、失败检测服务、命名服务以及认证服务等。
  接口用于与系统中的其他Agent或服务通信。
  3.2政策共享机制
  在MAS中,政策可以在Agent间分散部署并共享[14]。Agent可以动态的共享这些政策。这可以使Agent减小其体积。如果没有政策共享,那么在最初执行任务时,每一个Agent中的政策集都必须包含所有政策,这无形中增加了Agent的政策集规模并影响Agent的执行效率。而Agent共享政策,可以使每一个尤其是下级Agent中的政策集规模变小,Agent初始运行时只需要其自身必需的政策。在需要协作时,由上级Agent通过服务接口传输新增的政策。政策共享如图3所示。
  图3Agent间政策共享
  初始运行时,每一级Agent中的政策集中只包含与其初始任务相关的政策。当需要协作时,上级Agent除了向下级Agent明确任务目标以外,还需要制定新增的政策,从而指导下级Agent的协作。
  4政策导向的Agent协作算法
  本算法的应用背景是战场作战仿真,使用上级Agent代表在作战仿真系统中各级具有指挥权限的指挥Agent,下级Agent代表完成具体作战任务的作战单元Agent,指挥Agent负责任务的分配及谋划作战单元Agent间的协作。本算法针对的主要是Agent在静态条件下的协作机制,即某一时间段内,Agent可以完成的几项子任务,不考虑完成任务的执行时间,也没有考虑多任务的时间重叠等问题[15]。
  Step1 指挥Agent向建制内作战单元Agent下达命令T={t1, t2, …, tn},作战单元Agent将自身所能完成该任务T的能力上报给指挥Agent;
  Step2 作战单元Agent接受到作战任务后,在个体政策的指导下,对各项任务进行排序,构建自身的任务集合;
  Step3 作战单元Agent从任务集合中顺序获取当前处理的任务,当任务集为空时,说明任务已经完成,成功退出;
  Step4 当作战单元无法完成任务或指挥Agent要求必须协作时,转入下一步;
  Step5 指挥Agent根据协作申请下达协作指示,同时检测有无全局政策:
  (1)有。应用全局政策;
  (2)无。转入下一步;
  Step6 检测有无个体政策:
  (1)有。应用个体政策,并进行政策冲突消解;
  (2)无。转入下一步;
  Step7 指挥Agent分配协作政策,刷新下级Agent政策集,启动下级Agent与政策相关的服务;
  Step8 下级Agent建立并执行协作行为,产生协作动作;
  Step9 下级Agent当前任务完成,转入Step3,进行下一任务的规划。
  这种MAS协作模型将以政策驱动及政策分布共享的优势相结合,作战任务的协作方案由上级Agent制定,减轻了作战单元Agent的初始设计复杂度及运行时的计算量。在协同过程中,Agent的行为受多级政策的共同影响,采用政策集优先级和最近生效时间优先原则[16],过滤无效政策,最终形成无冲突协作行为。
  5结束语
  随着对MAS技术的研究深入,层次MAS中Agent间的协作问题越来越多的呈现出复杂性的特点。本文基于政策驱动的理论对协作问题进行了深入研究。以作战仿真系统为背景,给出了协作模型及相关算法。实践表明,该模型符合作战指挥领域的基本特点,可以很好地解决大型作战仿真系统中Agent间的协作问题。下一步,将继续研究实时交互的稳定性及多任务时间重叠等问题。
  参考文献
  [1] 赵晓哲, 王超. 基于MAS的编队协同作战仿真系统建模研究[J]. 系统仿真学报. 2009, 21(8):2381-2385.
  [2] 潘长鹏, 张海峰, 陈洁. 基于Agent的分布式海上编队防空作战仿真体系[J]. 火力与指挥控制. 2007, 32(9):92-94.
  [3] 琚春华, 钱阳峰. 基于角色的多Agent层次型协作管理模型与商务应用[J]. 计算机工程与设计. 2007, 28(8):1927-1930.
  [4] Maoguang Wang, Zhongzhi Shi, Shifei Ding: Hierarchical Policy for Agent Grid Collaboration[C]. GCC 2007:236-241.
  [5] 王向东, 魏蓉, 王文杰. 基于扩展合同网的多Agent协作研究[J]. 微电子学与计算机. 2008, 25(4):108-111.
  [6] 马建红, 王万森, 季秋. 基于改进的合同网的多专家Agent协作的研究[J]. 计算机应用. 2004, 24(11):47-49.
  [7] 王玉柱, 傅凝, 牛荣健. 联合战役决心方案自动生成系统中多Agent协作方法[J]. 计算机应用. 2005, 25(4):944-946.
  [8] 胡军, 李长云. 基于政策的多主体协作维护机制[J]. 计算机工程与应用. 2007, 43(6):27-31.
  [9] 杨蓓, 黄厚宽. 基于MAS的协作学习机制研究[J]. 计算机研究与发展. 2006, 43(Suppl):132-136.
  [10] Maoguang Wang, Zhongzhi Shi, Shifei Ding: Hierarchical Policy for Agent Grid Collaboration[C]. GCC 2007:236-241
  [11] 胡军, 李正通. 政策导向型多Agent协同系统研究[J]. 计算机应用研究. 2010, 27(8):3009-3015.
  [12] 史忠植. 智能主体及其应用[M]. 北京:科学出版社, 2000:30-6
  [13] Anand Tripathi, Devdatta Kulkarni, Tanvir Ahmed: Policy-driven configuration and management of agent based distributed systems. ACM SIGSOFT Software Engineering Notes (SIGSOFT) [C]. 2005,30(4):1-7
  [14] Sarmad Sadik, Arshad Ali, Hafiz Farooq Ahmad, Hiroki Suguri: Policy Based Approach to Enhance Task Execution Performance of Mobile Agents[C]. PDPTA 2006:542-547.
  [15] 杨克巍, 李兴兵, 李孟军. 基于集合覆盖理论的Agent协作问题研究[J]. 系统工程学报. 2009, 24(6):759-763.
  [16] 胡军, 李志昂. 面向虚拟组织的政策导向型自治、可控Agent模型[J]. 湖南大学学报: 自然科学版. 2010, 37(6):71-76.
  注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
其他文献
摘 要: 小学阶段由于受到年龄、语言环境的影响和课时的限制,小学英语教学效果不理想。究其原因,无非是学生对英语基础知识掌握不牢,学习方法单一,教师指导不到位。在小学英语课堂教学中,要从基础抓起,重视音标、单词教学,采取游戏教学法,培养小学生英语学习兴趣,从而提高小学英语教学实效性。  关键词: 小学英语 基础性教学 教学思考  小学阶段受到年龄、语言环境的影响和课时的限制,小学英语教师教学要
结合高等职业院校人才培养工作评估方案中数据采集的要求,将模型驱动框架技术在实际的数据采集平台开发过程中的应用进行分析与探讨,实践证明,该改系统在实际应用中具有良好的可
[摘要]制鞋是轻工业的重要组成部分,对国家经济发展具有重要的支撑作用。随着经济发展全球化趋势不断加强,以及国内市场日渐饱和,面向国际是我国制鞋企业的全新发展方向。基于此,文章就针对我国制鞋企业国际营销出现的一些问题作出分析,然后针对性地提出了国际营销的具体策略,以期能够对制鞋企业提供参考,促进其国际竞争力。  [关键词]制鞋企业;国际营销;自主品牌  随着我国的国际影响力和经济实力不断提升,我国的
脑梗死以其发病率、致残率、病死率高及神经损伤的难治性等因素,备受神经科医生关注,并已成为严重的社会-医学-经济问题。脑梗死属中医的“中风”范畴,考诸历代文献,记载甚多,数千
急性肾功能衰竭(ARF)是急性高血压性脑出血术后的常见并发症,其转归直接影响着患者预后。笔者所在科室于2008年1月~2010年10月手术治疗高血压性脑出血患者32例,其中11例术后合并AR
高职院校是以培养用人单位所需人才的教育场所,实践教学评价关系到高职院校人才培养的质量,职业教育自身培养目标的实现和整个教学环节的质量。近十几年来,我国对高职院校实
学风建设是大学生教育管理的根基所在,设计类专业学生思维活跃、个性张扬,不易接受枯燥刻板的教育。面对设计类专业的情况和学生特点,南京理工大学设计艺术与传媒学院通过专
摘 要:本文对网页去噪的定义和分类、经典方法以及实验方法等进行了研究,在重定义启发式规则的基础上,针对文本类网页,设计新的算法,并用代码进行实现,在对比结果中验证,该算法能很好的解决文本类网页噪音问题。  关键字:网页去噪;DOM树;风格树;启发式规则  中图分类号:TP393.092 文献标识码:A DOI:10.3969/j.issn.1003-6970.2013.08.029  本文著录格式