当前位置:首页 > 商业/管理/HR > 经营企划 > 基于层次图变换的多Agent组织结构动态重组机制
ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.ac.cnJournalofSoftware,Vol.20,No.1,January2009,pp.41−53:+86-10-62562563©byInstituteofSoftware,theChineseAcademyofSciences.Allrightsreserved.基于层次图变换的多Agent组织结构动态重组机制∗王正光,梁晓辉+,赵沁平(北京航空航天大学计算机科学与工程学院虚拟现实技术与系统国家重点实验室,北京100191)DynamicReorganizationMechanismsinMulti-AgentOrganizationalStructurewithHierarchicalGraphTransformationWANGZheng-Guang,LIANGXiao-Hui+,ZHAOQin-Ping(StateKeyLaboratoryofVirtualRealityTechnologyandSystem,SchoolofComputerScienceandEngineering,BeiHangUniversity,Beijing100191,China)+Correspondingauthor:E-mail:lxh@vrlab.buaa.edu.cnWangZG,LiangXH,ZhaoQP.Dynamicreorganizationmechanismsinmulti-agentorganizationalstructurewithhierarchicalgraphtransformation.JournalofSoftware,2009,20(1):41−53.:Theself-adaptationtotheenvironmentalchangesisoneofthekeyissuesoforganization-basedmulti-agentsystems.Dynamicreorganizationoforganizationalstructuresprovidesaneffectiveapproachformulti-agentsystemstorealizeorganizationalobjectivesflexibly.Basedonthestructuralcharacteristicsofagentorganizations,thispaperpresentsasingle-rootedhierarchicalgraphmodeldescribingsocialstructure,roleenactmentandagentcoordinationoftheorganizationalstructures.Thismodeldecreaseseffectivelythecomplexityofreorganizationforlarge-scaleagentorganizationsbymaintainingtheirstructuralelementsbasedonthesingle-rootedandhierarchicalgraphapproach.ItformalizesthereorganizationprocessofagentorganizationalstructuresbyextendingthealgebraicgraphtransformationwiththeDPO(double-pushout)approach.Inthisformalspecification,thesingle-rootedhierarchicalgraphscharacterizedifferentstatesoforganizationalstructuresandthederivationsequencesoftransformationrulesformulatethetransitionprocessoforganizationalstructures.Finally,theexperimentalresultsonreorganizationsimulationandmatchingalgorithmoforganizationtransformationrulesindicatethatthishierarchicalgraphtransformationapproachdefinesformallythereorganizationprocessofagentorganizations,andsupportsthegraph-baseddesignoforganizationalelementsduringthereorganizationprocessandthereorganizationcomputationoflarge-scaleagentorganizations.Keywords:dynamicreorganizationmechanism;organizationalstructure;multi-agentsystem;hierarchicalgraphtransformation;single-rootedhierarchicalgraph摘要:如何动态适应环境是基于组织计算的多Agent系统的关键研究内容之一.组织结构的动态重组为多Agent系统柔性地实现组织目标提供了有效途径.结合Agent组织结构特点,给出了一种描述组织结构的社会结∗SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA01Z333(国家高技术研究发展计划(863))Received2007-05-18;Accepted2008-03-2742JournalofSoftware软件学报Vol.20,No.1,January2009构、角色指定和Agent协调的单根节点层次图模型.通过单根节点和层次化地维护组织结构内元素的拓扑关系,有效地降低了大规模Agent组织重组问题的复杂性;扩展DPO(double-pushout)代数图变换,形式定义了Agent组织结构的重组过程.单根节点层次图描述了重组过程中给定时刻的组织结构状态,图变换规则序列定义了组织结构的变化过程.Agent组织重组和图匹配算法实验结果表明,该层次图变换方法有效地刻画了多Agent组织动态重组过程,并支持图形化重组过程要素设计和大规模Agent组织的重组计算.关键词:动态重组织机制;组织结构;多Agent系统;层次图变换;单根节点层次图中图法分类号:TP18文献标识码:AAgent组织是基于多Agent计算问题的有效求解机制.在开放的环境中,Agent组织需要更柔性地求解问题.例如,组织内Agent个体的知识、能力随环境的变化动态地更新;Agent之间的关系、组织内角色关系随着任务目标的变化动态调整.为了提高Agent组织的自适应性以及问题求解效率,组织的演化或重组问题就成为基于Agent计算的关键.组织重组反映了Agent组织对外部环境变化和内部状态变化的一种适应策略.外部环境变化体现在组织任务目标的开放性和求解过程的开放性上[1],内部状态变化表现在组织内Agent个体的行为变化和组织结构元素关系的变化上[2].目前,组织重组问题研究分为组织变化的要素、实现组织重组的机制及过程、重组产生的时刻、重组产生的动机和可能性等方面[3].已有的Agent群体演化问题研究途径可以分为两类[4]:一类是自底向上的基于Agent角度方法,Agent之间的协作行为依赖于多个Agent自发行为,Agent群体的重组过程是一种突现的行为;另一类是自上而下的基于组织角度方法,Agent之间的关系依赖于各自承担的角色之间的关系,角色关系在组织设计阶段预先设定并随环境变化重新设计,组织的重组过程具有主动性、可控性等特点.在基于组织的多Agent计算问题中,组织结构定义了组织内Agent个体的任务结构和交互方式.Agent组织结构及其变化是重组问题的重要研究方面.1相关研究近年来,Agent组织重组的相关问题得到了广泛关注.Dignum等人[2,3]提出了重组过程中组织变化的形式及重组问题的5个方面的研究内容,已实现了实验环境VILLA研究重组过程仿真,取得了很好的效果.Hübner等人[5]提出了基于MOISE+的组织模型的重组过程,将组织模型分为结构维度、功能维度和义务维度.功能维度描述了组织任务层次,结构维度定义了组织角色关系,义务维度定义了角色对应给定任务允许的行为及义务,将功能维度和结构维度联系起来.在组织结构中指定管理角色集中方式管理重组过程,承担该角色的Agent可以自主地修改组织状态,并应用于小规模机器人团队TeamBots仿真.从软件工程角度,Deloach等人[6]提出了基于MaSE的多Agent系统分析和设计方法,该方法允许小规模的Agent系统重组计算.在MaSE方法中,组织内Agent没有分组,不支持组织的分层结构,对于大规模组织重组存在组合爆炸问题.Durfee等人[7]强调了任务环境和组织结构影响组织的性能,分析了不同的树结构组织在特定环境下对大规模Agent系统的性能影响,并给出了基于组织自设计的重组过程.徐晋晖等人[8]给出了面向结构的组织结构模型、组织设计原则和非形式定义的组织形成演化过程.张伟等人[9]针对Agent组织的设计过程给出了Pi演算形式描述和基于化学抽象机的形式语义.詹剑锋等人[10]基于软件体系结构描述语言形式定义了Agent个体演化过程中内部组件的交互,从微观角度分析了演化过程中Agent个体内部状态的变化.已有工作一般都没有对Agent组织重组过程进行严格的形式定义和对重组过程效率深入研究.本文在分析多Agent计算问题及组织特征的基础上,针对这些问题从组织结构角度提出了一种描述组织结构的社会结构、角色指定和Agent协调3个维度的单根节点层次图模型,给出了Agent组织重组过程的基于层次图变换的形式定义,包括将层次图模型刻画重组过程的组织结构状态和扩展double-pushout代数图变换规则,形式定义重组过程.给出了重组过程中组织图规则应用的图匹配算法.本文的实验结果表明,该层次图变换方法有效地定义了重组过程,并避免了大规模组织重组带来的图节点组合爆炸问题.相对于Hübner,Dignum和DeLoach等人的工作,该层次图变换方法形式定义了Agent组织的重组过程,并支持图形化重组过程要素设计和大规模Agent组织的重组计算.王正光等:基于层次图变换的多Agent组织结构动态重组机制432Agent组织结构及重组过程语义2.1Agent组织结构的3个维度特征多Agent系统是分布式人工智能的重要研究内容[11].在多Agent系统中,Agent群体通过个体的自主计算及个体间的交互实现系统预定的全局目标.个体的自治与交互是多Agent系统的重要特征.在开放的问题求解环境中,由于任务目标的开放性及求解过程的开放性,Agent系统需要面临环境自适应及矛盾冲突等问题[1].相应地,解决自适应及矛盾冲突等问题需要系统中大量的计算资源,例如,Agent个体之间的通信资源.近年来,基于组织的Agent计算有望成为多Agent系统求解问题的新途径[12,13].为了实现基于组织的多Agent问题求解,组织计算过程可以分为4个阶段:(1)对问题领域进行分析和定义,确定任务目标及任务相关的知识、资源约束;(2)进行组织结构设计,定义组织内角色关系、角色之间交互方式和组织元素的约
本文标题:基于层次图变换的多Agent组织结构动态重组机制
链接地址:https://www.777doc.com/doc-457891 .html