基于G-Net的多Agent系统建模及其在敏捷生产调度中的应用.doc

基于G-Net的多Agent系统建模及其在敏捷生产调度中的应用摘要: 阐述一种基于G-net和会话Schema相结合的MAS建模方法，并且将其应用于敏捷生产调度系统。首先，参照标准G-net的定义，建立了符合BDI逻辑框架的Agent模型GBA，给出了GBA组件的基本结构及定义；其次，论述了基于GBA的MAS模型结构、协调机制和会话策略；最后以一个典型的敏捷生产调度建模为例，通过功能分解的方法，将Agent赋予不同角色进行交互。本方法能够满足智能制造中复杂过程建模灵活性的需求, 并使系统具有良好的扩展性和可重用性。关键词: Agent；G-net；Schema；MAS；敏捷调度Agent-Oriented G-Net Model and Its Application in Agile Production SchedulingAbstract: In this paper, a G-net and conversation schema combined approach to designing intelligent agents for multi-agent systems (MAS) and the application in agile production scheduling modeling is proposed. Firstly, we customize the basic G-net model to define a so-called “G-net BDI Agent”, by providing the agent architecture and the detailed design. Secondly, the basic system structure, collaboration mechanism and the conversation policy is presented. Finally, a function-based decomposition method for different agent roles defining was suggested to illustrate our modeling technique for Agile Production Scheduling systems. This approach meets expansible, reusable requirement of intelligent manufacturing system, and with good flexibility.Key words: Agent；G-net；Schema；MAS；Agile Scheduling1 引言由于实时多Agent 系统（Multi-Agent System, MAS）固有的复杂性，如何构造Agent，使Agent模型具有充分的可靠性、可维护性和可扩展性，是将MAS推向实用化的关键之一。G-net是一种基于面向对象方法的有色Petri网建模理论1，适用于复杂软件系统的逻辑分析和功能设计。近年来, 有研究者将G-net建模方法应用于构造BDI Agent模型234，但是这些模型并没有给出比较详细的BDI运行机制，并且Agent之间的通信是通过外部接口的直接信息交换来进行，或者是通过一种“访问登记等待反馈”规则机制的中间件（Middleware）来做媒介。当系统应用于并发事件较多、实时性要求较高的生产调度系统时，系统的状态变量有可能会大幅增加，Agent之间的协作过程与MAS的稳定性有可能变得难以控制。本文综合考虑了生产调度系统的应用特点和G-net建模方法的优点，并借鉴基于Schema的会话策略5，提出一种基于G-net和Schema会话模型相结合的MAS建模方法，将其应用于敏捷生产调度系统的设计。这种方法的主要特点是:l 符合BDI逻辑框架的Agent设计，可以把复杂的任务执行和协作过程进行分解，转变为一系列的单一对象、单目标的处理过程，降低了系统构造和维护的复杂性；l 可以有效控制整个系统的行为, 使系统在追求全局性能的同时，实现Agent 个体局部性能的最大化，进而获得满意的运行效果；l 可在需要的时候将知识库、规则库、分析模块和运算策略集成到相应的规则中，以得到所需的满意性能；l Agent 组件及其规则具有“即插即用”的特性，提高系统建模的方便性、适应性和重构性。2面向Agent的G-net模型2.1标准G-net模型G-net是一种面向对象的有色Petri网模型67，一种G-net表示一个对象类，多个G-net可以组成一个完整的G-nets系统。G-net 用G = ( GSP , IS) 表示。G-nets系统通过各个对象的GSP 进行交互，通过IS 实现对象内部方法的调用。图1描述了一个G-net实体的结构框架和运行机制。对GSP和IS作如下定义：（1）GSP 是三元组(Oid，MS，AS )，代表对象的内部属性和外部信息接口。其中Oid是G-net 的唯一标识，MS 是接口中定义的方法，AS 是对象属性。（2）IS 代表对象的内部结构，也是GSP 接口中定义的方法的实现集合。IS 中的方法是三元组(P，T，A)，P 是入口库所EP、方法调用库所MIP 和返回库所RP 的集合。每一个方法仅有一个EP 和一个RP用于表示方法入口和结果返回出口，但可以有多个MIP。这里MIP 定义为实现对象功能的各种方法的调用，它是一个二元组(O.Nid，mtd)，这里O可以是G-net 本身或其他G-net , O.Nid是O的唯一标识，mtd 属于O.MS , 每一个MIP (O.Nid，mtd) 表示对O的mtd方法调用。T是IS内部变迁的集合；A是IS内部全体有向弧的集合，其定义为：（PRP）T）（T（PEP）。2.2 基于G-net的BDI Agent模型一个典型的BDI Agent通常包含4个主要的数据结构8: 1.信念集，用于表示Agent对环境的认识，其中的信息可能不完全或不正确；2.期望和目标(goal)集，对应于分配给Agent要执行的任务；3.意图集，表示Agent已决定和承诺完成的期望，Agent将持续它对一个意图的承诺，直到它相信该意图已满足，或由于某些原因该意图不再可完成；4.规划库，包括一组预定义规划或方法，表示Agent为完成各种意图所遵循的过程性知识或程序。总之，它们分别表示了Agent的陈述性、选择性、决策性和过程性状态。下面对G-net 表示的实时对象模型进行扩展，得到如图2所示的符合BDI逻辑框架的Agent模型 GBA（G-net BDI Agent）。GBA模型由信息接口库所GSP( G) 和内部结构IS构成，其中IS由目标模块GL、计划模块PL、调度模块SC、知识库模块KB以及控制模块PN 组成。这里GSP包含了Agent的属性，并且是与其它Agent的唯一交互接口，Agent交互信息的输入和输出都是通过它完成的。另外，由于MAS仅考虑Agent 感兴趣以及能够感知到的外部元素，所以GSP还构成了外部环境（Envirement）的组成元素，由所有Agent的GSP组成的集合可以反映整个外部世界模型。目标模块GL是对目标的抽象，表示Agent需要实现的目标集合。计划模块PL是计划集合的抽象，每一个计划与一个目标或子目标相对应，而目标或子目标可以由多个计划完成，一般选择最好的几个计划作为实现目标的候选计划。调度模块SC以候选计划为输入，根据Agent中各个任务的时限，确定本地调度方案，并且实现Agent的各种功能。知识库模块KB是信念(Belief) 的抽象，描述Agent对所处环境的判断和内部精神状态。对上述的GBA模型（G-net BDI Agent model）作出定义如下：定义1：一个GBA是二元组GBA（GSP， IS）。GSP 是三元组GSP （Aid，MS，AS），代表GBA的内部属性和外部信息接口，其中Aid是GBA的唯一标识，MS 是GSP中定义的方法，AS 是GBA的属性。IS是五元组IS （GL，PL，KB，SC，PN）,代表GBA的内部结构，其中GL是目标模块，PL是计划模块，KB是知识库模块，SC是调度模块，PN是控制器模块。定义2：一个PN控制器模块是从属于GBA的CPN子网。PN为六元组PN（IGS，IGL，IPL，IKB，ISC，DMU）。其中，IGS，IGL，IPL，IKB，ISC，DMU分别是PN模块与GSP，GL，PL，KB，SC等模块的接口；而DMU是决策单元的集合，包括三种抽象变迁：感知、决策和更新状态。定义3：GL模块、PL模块、KB模块、SC模块都是从属于GBA的CPN子网，均为四元组GL/PL/KB/SC（P，T，A，DB）。其中，P 是入口库所EP、方法调用库所MIP 和返回库所RP 的集合，每一个方法仅有一个EP 和一个RP用于表示方法入口和结果返回出口，但可以有多个MIP。T是模块内部变迁的集合；A是模块内部全体有向弧的集合，其定义为：（PRP）T）（T（PEP）；DB是用于支持方法实现的数据库所，包括：静态数据、动态数据、事实库、规则库和算法库等等。2.3 控制器模块PN在GBA的各组成部分中，GL，PL，KB，SC分别包含了Agent的各种目标集（Goals）、计划集（Plans）、信仰集（Beliefs）和意图集（Intentions）。控制器PN是用于协调GBA内部GL，PL，KB，SC等模块运行的核心单元，其模板结构如图3所示：在PN模块中包含一个自治单元（Autonomous unit），表示Agent的自治性和内部动机。自治单元内有一个代表“感知”的抽象变迁。当计划模块PL的条件得到满足或者感觉到GSP中有新的事件发生，感知将被触发，自治单元将根据Agent目前的精神状态（目标，计划和知识）决定是否应该启动会话机制或者只是对精神状态进行更新。会话可以包括Agent内部各模块之间的会话和与其它Agent的会话。在GBA模型中有5 种托肯，它们分别是表示通信消息托肯mTkn，目标托肯gTkn，计划托肯pTkn，调度托肯sTkn 和知识托肯kTkn。定义这些托肯为二元组（tag，body），其中tag 属于message，goal，plan，schedule，knowledge，body 是要传送信息的具体内容。当tag 分别取goal，plan，schedule，knowledge时，GSP 接口库所中的托肯将发送给内部结构IS 中的目标模块、计划模块、知识模块或调度模块。ABS模型中的5种托肯一起通过内部结构IS和抽象库所接口GSP反映实时Agent 在所处环境下的工作状态和相互关系。由于敏捷生产调度的应用要求，由GBA构成的MAS必须具有较高的通信效率和响应性能，所以有必要专门设计一种GBA用于Agent之间的信息交换，即下文所描述的通信AgentCM。当普通GBA中的托肯tag取message时，GSP 接口库所中的托肯将发送给通信AgentCM，进行基于Schema模型的会话。3通信AgentCM3.1 基于Schema的Agent通信模型通常，多数MAS 采用合同网协议（Contract net protocol）11方法或其它类似的各种拍卖（Auction）、谈判（Negotiation）等方法来处理Agent 之间的协调与合作问题。合同网方法着眼于环境的不确定性和Agent 决策的敏捷性，但往往过多地强调任务的分配，而忽视了通信的效率。或者强调Agent 间自由竞争可能导致某些任务不能分配，造成系统死锁，影响系统的稳定工作。为此，本文建议采用一种基于通信Agent 和Schema规则会话机制的敏捷调度方法。采用基于Schema的Agent通信模型，具有能够比较容易地表示Agent之间的通信模式和验证这种模型正确性的特点。由于每个GBA的外部接口GSP中已经包含了对Agent属性的描述，用Schema建立消息托肯mTkn，可以比较容易地获知各个GBA的状态信息，并且可以直接将这些状态信息用于Schema的建模。通信schema是一种包含了会话策略的CPN模板，可以让多个Agent在共同的会话主题（Topic）下实现信息交换。下面是对会话主题及Schema的定义：定义4：一个会话主题TP是三元组TP（TP_ID，GBA，ARGUMENTS）。其中，TP_ID是TP的标识，AGENTS是参与主题的Agent清单，ARGUMENTS是围绕主题的对话。定义5：一个会话Schema是四元组Schema（Agents，Acts，States，Arcs，TPs）。其中，Agents = Agt1, Agt2, , Agtm，表示参与会话的Agent集合；ActsAct1，Act2， ，Actn，构成用于Agent互动的消息托肯mTkn；StatesSta1，Sta2， ，Stal，表示各Agent的状态变化；Arcs（Acts States）（StatesActs），表示States与Acts之间的变迁关系；TPsTp1，Tp2， ，Tpk，表示Agent实现某种协作的主题集。简单Schema可以通过组合和嵌套组成复合型Schema。例1：一种要求获取信息的会话SchemaREQUEST(A, B)（图4）。Agents：（A，B）；Acts：（request，continue，repair，req_ack，req_repair，acknowledge，cancel）；States：（submitted，failed，succeeded）；Arcs：/relations between Acts and States; TPs：（content）.3.2 通讯Agent-CM通信AgentCM是一种采用Schema会话策略的特殊GBA，其定义如下：定义6：一个CM是二元组CM（GSPC， IS）。GSPC 是二元组GSPC（CP，AS），代表CM的内部属性和外部信息接口，其中CP是GSPC中定义的会话策略，AS 是CM的属性。IS是五元组IS （MPU，ASP，GYP，SCL，PNC）,代表CM的内部结构，其中MPU是通信接口处理单元，ASP是会话Schema实体池，GYP是GBA注册类库，SCL是Schema类库，PNC是会话控制器模块，其结构与普通GBA的控制单元PN类似。图5描述了CM（Communication Manager）的内部结构。CM中的Schema类库SCL由一个Schema线程类集合（构造Schema实例的模板）组成。会话实体池中的处理引擎可以通过调用GSP注册表实现GBA类到GBA实例的过程，并且响应GSP中要求的会话策略CP，执行Schema类的实例化过程。CM中的ASP保存所有活动的Schema。一旦CM从GBA的GSP那儿收到一条初始化一次通信的消息，则触发Schema匹配过程。如果ASP的处理引擎探测到ASP的大小还没有达到它的域值（threshold），CM从SCL中选择适当的Schema类，然后创建它的实例并把它加到ASP中。该Schema一直保存在ASP中，直到它到达结束状态为止，然后从ASP中把它去除。对于大型的系统设计，也可以采用多个CM来平衡ASP的负荷。CM还包含了通信处理单元MPU，用于信号接受和发送的路径处理。Schema会话的处理流程采用“识别匹配运行”的规则机制，其流程如图6。4由GBA组成的敏捷生产调度系统制造企业的敏捷生产调度问题一直是研究的热点。多Agent生产调度系统（Multi-Agent Schedule System，MASS）的建模方法主要有两种：基于任务的分解或基于区域的分解。GBA的结构能够使每个Agent 通过协作互动完成一项或多项特定的任务, 如顺序规划、调度算法、执行某加工任务等，所以比较适合采用基于功能的分解方法，建立MASS模型时可以按照生产调度过程中的物理或逻辑单元的功能和协作关系进行建模。图7以一个家电组装企业的生产调度为例，描述了典型的MASS协作模型。由于MASS是由处于生产环境中的多个Agent组成的系统，MASS的建模需要考虑Agent之间的关系、交互和通讯结构的描述，使Agent能够在满足所有本地和全局约束的条件下以协调的方式实现系统的总体目标或任务。在GBA模型中，GSP包含了Agent的属性，并且是与其它Agent交互的唯一接口。另外，由于系统仅考虑Agent 感兴趣以及能够感知到的外部元素，所以可以由所有GBA的GSP集合组成MASS的环境模型。图8反映了MASS协作模型中各种GBA、环境以及通讯Agent（即图中的CMCommunication Manager）三者之间的交互关系。由于敏捷调度具有复杂性和动态性特点，如果在实有生产能力与需求能力之间发生冲突时，往往需要采取一些人为干预的管理手段。例如提前和拆分工单、修改评判规则、增加或减少在用设备的数量，或者将部分任务分包出去等方法。这样调度人员与MASS之间必须能够进行会话, 实现必要的人工干预和操作设置。这时，可以将调度员本身视为一个完整的GBA，在系统中增加调度员接口GSP，并且在CM的会话策略库中扩充调度员Schema，可以比较容易地实现图形界面的建模以及MASS与人工决策的互动功能。5 结束语本文提出一种基于G-net和会话Schema相结合的MAS建模方法，建立了符合BDI逻辑结构的GBA模型，阐述了基于Schema方式的会话策略，并且说明了如何将这种方法应用于敏捷生产调度系统的建模。由于提出的Agent 组件及系统总体架构具有“即插即用”的特性，调度规则和运算策略可以方便地重构和重用, 使得系统具有良好的扩展性和适应性，有助于实现复杂MAS的设计和开发。参考文献： 1 A Perkusich, J de Figueiredo. G-Nets: A Petri Net Based Approach for Logical and Timing Analysis of Complex Software SystemsJ. Journal of Systems and Software, 1997, 39(1): 3959,.2 H Xu, S M Shatz. Extending G-Nets to Support Inheritance Modeling in Concurrent Object-Oriented DesignA. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC) C, Nashville, Tennessee, USA, October 2000, pp. 3128-3133.3 H Xu, S M Shatz. An Agent-based Petri Net Model with Application to Seller/Buyer Design in Electronic Commerce A. Proc. of the 5th International Symposium on Autonomous Decentralized Systems (ISADS) C, Dallas, Texas, USA, March 2001, pp.11-18.4 A Khetarpal, S Tu. Applying an Object-Based Petri Net to the modeling of Communication Primitives for Distributed Software A. Proc. of the Conf. on High Performance ComputingC, 1998.5 F H Lin, D H Norrie. Schema-based Conversation Modeling for Agent-oriented Manufacturing System J. Computers in Industry, 2001(46):259-274.6 Y Deng, S Chang, A Perkusich, J de Figueredo. Integrating Software Engineering Methods and Petri Nets for the Specification and Analysis of Complex Information SystemsA. Proc. of the 14th International Conference on Application and Theory of Petri NetsC, Chicago, USA, June 1993, pp. 206-223.7 Y Deng, S Chang. A G-Net Model for Knowledge Representation and ReasoningJ. IEEE Trans. Knowledge and Data Eng, 1990, 2(3):295-310.8 A S Rao, M P George.