（交通信息工程及控制专业论文）多Agent的协同与通信技术研究.pdf

南京航空航天大学硕士学位论文 摘要 本文首先分析了多a g e n t 协同技术的发展现状和趋势，对多a g e n t 协同中的启发 式任务分配算法、基于排队论和基于t r i b a s e 模型的任务分配算法进行了介绍，并对 在a g e n t 通信领域占主导地位的两种通信语言k q m l 和f i p a a c l 以及黑板方式 和点对点方式等常见的a g e n t 通信连接方式进行了探讨。在对任务分配和多a g e n t 通信管理等问题进行较为深入的讨论的基础上，本文分析了几个典型的多a g e n t 系统 结构，并将多a g e n t 协同技术引入企业信息管理领域，提出了基于冗余服务管理的多 a g e n t 协同模型_ r s m a c m 。r s m a c m 模型结合服务队列理论以及冗余服务管理 技术，采用x m l 语言进行通信消息的表达，对负载均衡、通信效率和可靠性、复杂 语义通信及其灵活性等方面进行了研究和实践。文章最后结合南京禄口国际机场生产 运营管理信息系统项目，阐述了r s m a c m 模型的应用与实现，并对实际的运行效果 进行了分析评价。 关键诃：协同，a g e n t ，多a g e n t 系统，任务分配，通信 多a g e n t 妁协同与通信技术研究 a b s t r a c t t h i s p a p e r f i r s t a n a l y s e s t h e d e v e l o p m e n t s t a t u sa n d t e n d e n c y o fm u l t i a g e n t c o o p e r a t i o nt e c h n o l o g y , a n d i n t r o d u c e sah e u r i s t i ct a s kd i s t r i b u t i o n a l g o r i t h m ，t h e a l g o r i t h m s b a s e do n q u e u i n gt h e o r y a n dt h e a l g o r i t h m b a s e do nt r i b a s em o d e li n m u l t i - a g e n tc o o p e r a t i o n t h e nt h i sp a p e rd i s c u s s e sk q m l a n df i p a - a c la st w o l e a d i n g a g e n tc o m m u n i c a t i o nl a n g u a g e sa n da n a l y s e su s u a lc o n n e c t i n gm e t h o d si nc o m m u n i c a t i o n a m o n gt h ea g e n t ss u c h a sb l a c k b o a r da n dp o i n t t o p o i n tm e t h o d t h e nb a s e do nt h e d i s c u s s i o no ft a s kd i s t r i b u t i o na n dc o m m u n i c a t i o na m o n gt h ea g e n t s ，t h i sp a p e ra n a l y s e s a r c h i t e c t u r eo fs o m et y p i c a lm u l t i - a g e n ts y s t e m s ，t h e ni n t r o d u c e sm u k i - a g e n tc o o p e r a t i o n t e c h n o l o g yi n t ot h ef i e l do fe n t e r p r i s ei n f o r m a t i o nm a n a g e m e n t ，a n db r i n g sf o r w a r dt h e r e d u n d a n ts e r v i c em a n a g e m e n tb a s e dm u l t i a g e n tc o o p e r a t i o nm o d e l ( r s m a c m ) t h e m o d e lr s m a c m i n t e g r a t e sq u e u i n gt h e o r ya n dr e d u n d a n t s e r v i c em a n a g e m e n t t e c h n o l o g y a n du t i l i z e sx m l l a n g u a g et oe x p r e s sm e s s a g e s ，a n da c c o r d i n gt ow h i c h ，t h i sp a p e r i m p l e m e n t s a n dr e s e a r c h e s0 nl o a d b a l a n c e ，e f f i c i e n c y a n d r e l i a b i l i t y i n a g e n t c o m m u n i c a t i o n ，c o m p l e xs e m a n t i cc o m m u n i c a t i o na n di t sf l e x i b i l i t y f i n a i l y b a s e do n n a n j i n gl u k o ui n t e r n a t i o n a la i r p o r t sm a n a g e m e n ti n f o r m a t i o ns y s t e m ( l k m i s ) ，t h e p a p e r d i s c u s s e st h ea p p l i c a t i o na n d i m p l e m e n t a t i o no f r s m a c m ，a n dg i v e s t h ee v a l u a t i o n o f t h es y s t e m s p e r f o r m a n c e k e y w o r d s ：c o o p e r a t i o n ，a g e n t ，m u l t i - a g e n ts y s t e m ，t a s kd i s t r i b u t i o n ， c o m m u n i c a t i o n 南京航空航天大学硕十学位论文 第一章绪论 多a g e n t 理论是由分布式人工智能( d a i ，d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n c e ) 的一 个分支d p s ( 分布式问题求解：d i s t r i b u t e dp r o b l e ms o l v i n g ) 引发出的。由于d p s 对 a g e n t 的假设过多，无法体现d p s 试图建造的社会系统的特征 1 】，因此人们提出了多 a g e n t 系统( m a s ：m u l t i - a g e n ts y s t e m ) 的概念。随着多a g e n t 理论的发展，自然地， 多a g e n t 协同问题成为该领域的研究重点之一。 1 1 多a g e n t 协同理论 在多a g e n t 系统( m a s ：m u l t i a g e n ts y s t e m ) 中，各成员a g e n t 之间通过交互 和协商，采取联合行动合作完成一系列目标和任务。多a g e n t 协同( c o o p e r a t i o n ) 的 本质，是使多个a g e n t 能够通过合作以更加有效地解决某个问题是协调行为中的一 种，其中心在于“合作”。 从广义上讲，多a g e n t 协同主要涉及八个方面的内容【2 j ： ( 1 ) 个体a g e n t 的推理，主要研究如何增强个体a g e n t 的推理能力，以达到提 高多a g e n t 之间一致性的目的。 ( 2 ) 任务分配，是协同中的一个研究重点，包括任务的分解、子任务的承担等 方面。 ( 3 ) 多a g e n t 规划，是一个构造a g e n t 行为的过程，其目的是为追求多a g e n t 的问题求解一致性。 ( 4 ) 目标和行为的一致性问题。 ( 5 ) 冲突处理及资源管理，冲突处理主要研究在多a g e n t 协同过程中产生的冲 突，以及如何发现冲突并消除冲突的问题。资源管理为了给成员a g e n t 合理地分配资 源，使每个成员在达成自身目标的同时也不影响系统目标和其它a g e n t 目标的实现。 ( 6 ) 建立其它a g e n t 的模型。 ( 7 ) 多a g e n t 之间的通信管理，这并非一般意义上的网络通信问题，而是为了 保证实现a g e n t 成员问智能化协同工作的通信管理。 ( 8 ) 适应与学习，是为了保证a g e n t 能对环境的变化做出相应反应，并以某种 方式反作用于环境，为a g e n t 间在环境改变的情况下进行合作提供知识基础【2 2 1 。 在这八个方面的研究内容中，任务分配是中心，它保证了总任务的完成和系统目 标的实现。而保证任务分配顺利进行的最基本条件就是成员a g e n t 之间要能有效地沟 通。 由上述分析可以看出，使多a g e n t 协同技术在实践中真正得到应用，有两方面问 多a g e n t 的协同与通信技术研究 题是最先需要解决的：任务分配和多a g e n t 通信管理。 1 2 多a g e n t 协同技术的发展现状及趋势 多a g e n t 协同技术的研究大致经历了两个阶段 3 2 1 ：第一阶段为二十世纪七十年代 到八十年代，第二阶段为二十世纪九十年代以后。前一阶段的研究基于对a g e n t 的协 商假设，即m a s 中的成员都是协商型a g e n t ( d e l i b e r a t i v e t y p ea g e n t s ) ，这一阶段的 研究从宏观上把握m a s 中各成员a g e n t 的社会特性和行为，以a g e n t 问的交互作用 ( i n t e r a c t i o n ) 、通信( c o m m u n i c a t i o n ) 、任务分解和分配( t a s kd e c o m p o s i t i o na n d d i s t r i b u t i o n ) 以及冲突的协商解决等为代表性的研究内容。 进入第二阶段后，出现了许多新的a g e n t 类型，为多a g e n t 协同技术的研究带来 了突破，一些引入新型a g e n t 的协同机制开始应用于各种m a s 中。在这一时期， c a r n e g i em e l l o n 大学设计并实现了几个典型的开放式m a s ，为多a g e n t 协同技术的 研究提供了模型基础。这几个m a s 包括v i s i t o rh o s t i n gs y s t e m 【2 3 】、p l e i a d e s 2 4 】和 r e t s i n a ( r e u s a b l et a s k b a s e ds y s t e mo f i n t e l l i g e n tn e t w o r k e da g e n t s ) m # t “等。目 前大部分m a s 的协同模型都参考了这几个系统。v i s i t o rh o s t i n gs y s t e m 较好地实现 了a g e n t 的智能性，主要功能是通过a g e n t 的协同工作模拟人类制定访客计划安排。 p l e i a d e s 在v i s i t o rh o s t i n gs y s t e m 的基础上建立一个基于合作型a g e n t ( c o l l a b o r a t i v ea g e n t ) 的分布式构架( d i s t r i b u t e da r c h i t e c t u r e ) ，整个系统采用任务a g e n t ( t a ) 和信息a g e n t ( i a ) 建立两层结构，通过个体a g e n t 内部的协同模块以及a g e n t 问的协商实现系统协同。r e t s i n a 和p l e i a d e s 类似，由个体a g e n t 内部功能强大 的协同部件配合系统服务来完成协同。这几个典型系统均采用分布式协同策略，没有 专门负责协同的中央机构。对于大型开放式m a s 而言，由于系统规模较大，难以掌 握全局知识，是无法设置一个专门负责全局控制的中央机构的；而中小型m a s 的系 统规模有限，采用一个中央机构进行全局管理是可行的，而且如果设置这样一个中央 机构，还可以大大削弱个体a g e n t 协同部件的功能，在一定的系统规模范围内，带来 更高的协同效率。由此可见，上述的几个典型系统所采用的分布式协同策略较为适合 大型开放式m a s ，但对于中小型m a s 而言并不是较为有效的选择。此后，为解决中 小型m a s 协同效率的问题，出现了具有中央管理服务机构的协同模型，但由于协同 控制中心的负荷以及系统通信数量都较大，不能较好地满足实际需要。 目前，越来越多的研究者开始将多a g e n t 协同技术应用于企业信息管理领域，利 用a g e n t 之间的合作特性处理复杂的业务逻辑。随着应用研究的深入，人们开始探讨 如何在保证一定系统性能的前提下，合理安排个体a g e n t 与系统管理服务机构( 或中 介机构) 在协同方面的负担问题。这一点是提高多a g e n t 协同效率的关键，反映了今 后一段时问内关于多a g e n t 协同技术应用研究的一个重要方向。 南京航空航天大学硕士学位论文 1 3 课题研究背景及内容 南京禄口国际机场生产运营管理信息系统( 简称l k m i s ) ，历经三年时间，已建 成了以运输生产信息流、人力资源信息流、决策管理信息流和财务信息流为基础的信 息管理系统，主要包括生产运营支持和业务管理支持两大子系统。整个系统涉及生产 指挥调度、货运管理、财务管理、人事管理、内部和外部网站管理、医疗卫生管理、 物资计划管理以及机关管理办公自动化等模块。 在l k m i s 的一期二期工程中以c s 及b i s 结构进行系统开发，实现了机场的管 理信息化和生产自动化，达到了预定的功能需求和性能标准。随着南京禄口机场的生 产规模扩大、管理机制改革以及部门机构重组，对l k m i s 提出了新的要求：第一， 系统能以较小的代价增加大量的新模块和新用户；第二，要求l k m i s 具有更多的协 同工作能力，满足信息流整合以及功能模块之间合作的需要：第三，针对原有的c s 结构程序，解决由大量客户端访问服务器端数据库所造成的瓶颈问题；第四，系统要 易于维护。为满足新的需求，项目组在第三期工程中引入多a g e n t 协同技术，并对原 有的部分功能模块进行改造，使其成为a g e n t ，借助于a g e n t 之闯的合作特性实现了 模块间的协同工作以及信息流的整合，使系统更加易于维护和扩展，并解决了客户端 对数据库访问的效率问题。 本课题具体的研究内容如下： ( 1 ) 以多a g e n t 协同技术为重点，讨论协同过程中的任务分配与执行等问题。 ( 2 ) 研究在a g e n t 协同过程中的多a g e n t 通信管理问题。 ( 3 ) 研究并提出基于冗余服务管理的多a g e n t 协同模型( r s m a c m ) ，以多a g e n t 协同处理任务请求的机制和多a g e n t 通信管理两方面为主，阐述该模型的理论基础和 相关实现技术，并应用于南京禄口国际机场生产运营管理信息系统的第三期工程中。 多a g e n t 的协同与通信技术研究 第二章多a g e n t 协同技术 总体来说，多a g e n t 的协同机制可以分为两类：集中式协同机制和分布式协同机 制。采用集中式协同机制，则在m a s 中有一个或若干个专门负责协同管理而不处理 具体应用逻辑的系统a g e n t ，其它处理应用逻辑的a g e n t 的协同功能非常弱；分布式 协同机制则主要依靠个体a g e n t 内部的协同部件和a g e n t 间的协商完成协同，系统中 没有专门的协同管理a g e n t ，只会有一些起辅助作用的中介服务机构，而处理应用逻 辑的a g e n t 内部的协同部件具有较强大的功能。这两类机制没有严格的孰优孰劣之 分，究竟采取何种协同机制，与m a s 的开放性和系统规模有密切的关系。一般而言， 前者更适合于中小型m a s ，而后者更适合于大型的开放式m a s 。 2 1m a s 的结构与协同 对协同机制的分类源于m a s 的组织结构分类，根据是否存在管理和服务机构， m a s 的组织结构可分为分布式、集中式和混合式1 2 , 3 1 三种，具体结构见图2 1 1 2 1 ，其中 集中式与分布式的区别就在于有没有一个中心管理者负责成员a g e n t 的集中控制。 曲集中式 c ) 混合式2 b 1 混合式1 d 1 分布式 图2 1m a s 结构表示管理服务机构，o 表示成员a g e n t 集中式结构的m a s ，将关系密切、有共同意愿的a g e n t 集合成一组，在保证每 个成员一定自治性的前提下，用一个管理服务机构来负责这一组内的协同控制。多个 a g e n t 组还可以组成一个高一级的a g e n t 组，并有一个高层管理a g e n t 来负责低层管 理服务机构的协同，可以有若干个这样的层次。管理服务机构与成员a g e n t 问具有一 南京航空航天大学硕士学位论文 定的管理与被管理关系。 在分布式m a s 中不存在管理服务机构，而是采用中介服务机构来为a g e n t 成员 间的协同提供辅助和服务作用，它与成员a g e n t 间不存在管理与被管理关系。混合式 结构则兼有分布式和集中式的特征，既有管理服务机构，也有中介服务机构。m a s 的组织结构对协同机制的决定作用就体现在这两种机构的功能上，它们在协同中的作 用是不同的。 管理服务机构负责对所有或部分a g e n t 成员的行为、协作、任务分配以及共享资 源等进行统一的调配和管理，建立学习系统和a g e n t 成员的模型，实现成员行为和系 统安全性监测及控制等【4 l 。它与成员a g e n t 之间存在着一定的管理与被管理关系，但 这种管理活动并不采用简单的命令方式，而是以协商的方式进行，保证了成员a g e n t 自治性的实现。一个可行的管理服务机构除具有系统整体目标、当前环境等知识外， 至少还应知道如下几个信息： 管辖范围内所有的a g e n t 的位置。 这些a g e n t 提供何种服务，有什么样的能力。 这些a g e n t 的状态。 管辖范围内的共享资源信息，包括种类、数量以及使用情况等等。 设管理服务机构为m ，所有处理应用逻辑的a g e n t 组成集合a g e n t = a g e n t - ， a g e n t 2 ，a g e n t 3 ，a g e n t 。 。在协同过程中，a g e n t i ( i 啊1 , 2 ，n ) 如果能独立完成一 项任务，就不再向m 提出协商请求，否则就向m 提出合作请求；m 接到请求后如果 发现该任务可由另一个或几个a g e n t 完成，则可以向这些a g e n t 提出合作要求，或者 也可以将这些a g e n t 的信息告知a g e n t i ，由它们自行协商；收到合作要求信息的a g e n t 有权决定是否接受该合作请求，并给m 以反馈，如此数次反复直至达成协议；对于 复杂任务，则由m 分解该任务，再计算出有能力完成各子任务的a g e n t 集合，经过协 商直至达成协议。 中介服务机构用以发布、保存和维护各a g e n t 成员的能力、位置和状态等信息， 并进行合作对象和服务请求的匹配工作，它与系统内a g e n t 成员的关系是服务与被服 务关系。中介服务机构与管理服务机构最大的不同在于，中介服务机构仅仅为a g e n t 成员提供中介服务，并不像管理服务机构那样拥有多个a g e n t 成员和系统当前环境的 丰富知识，也不对系统的共享资源进行管理，更缺乏总体的协同组织能力。这样的区 别是由系统规模决定的：中介服务机构一般存在于大型的开放的m a s 中，不可能像 管理服务机构那样拥有系统内所有的全局知识。常见的中介服务机构有多种，以一种 模仿市场交易过程的协同机制为例，中介服务机构的协同过程可参考图2 2 2 8 1 。 多a g e n t 的协同与通信技术研究 图2 2 中介服务机构b r o k e r 的协同机制 当某个a g e n t 需要寻找合作伙伴时，则请求中介机构b r o k e r 寻求合作对象：b r o k e r 根据所掌握的全局知识，将合作请求发送给相应的a g e n t ( 可能有多个) ；愿意合作 的a g e n t ( s e l l e r ) 收到请求后向b r o k e r 发送表示同意合作的信息( b i d s ) ；b r o k e r 再 把这些同意合作的信息发给合作请求者( b u y e r ) ；最后，合作请求者的确认信息经过 b r o k e r 被传达给同意合作的a g e n t 。这样的协商过程完毕后，合作各方就可根据协商 结果进行合作了。 2 2 多a g e n t 系统的任务分配 a g e n t 接到用户的任务请求后，会根据知识领域决定是直接执行该任务、委托其 它a g e n t 执行此任务还是将任务分解后再由多个a g e n t 合作完成。这个任务分配过程 的目的就是要使系统在完成某个任务时的执行和通信开销尽量小，在保证a g e n t 之间 不发生冲突的前提下，同时达到局部和全局目标。许多学者都对此做出了有益的研究， 下文对目前已有的几种任务分配机制进行介绍，其中启发式任务分配算法对集中式协 同机制和分布式协同机制都适用，排队论调度算法适合于集中协同机制，t r i b a s e 模 型适合于分布式协同机制。 2 2 1 启发式任务分配算法1 5 i 启发式任务分配算法把任务的分解与子任务的分配过程合并为一个线性规划问 题，为复杂任务的分配提供了一个可行的方法。其主体思想是把任务分配过程中应满 足的条件形式化为一组约束条件，再将系统执行和通信开销定义为一个系统开销函 数，最后用线性规划方法求系统开销函数在一组约束条件下的最小值，在这个最小值 之下得到的任务执行计划就是最终的任务分配结果。 定义任务分解问题为 ，k 为知识集，所谓知识这里定义为任务的 初始条件、目标及中间结果；a 是操作集，一个操作t 。根据其输入信息i n p u t ( t 0 得出 相应输出结果o u t p u t ( t i ) ，给定任务将通过a 中的操作完成；e 是执行者集合( 即任 务a g e n t 集合) 。k 、a 和e 给出了系统的环境定义，而i 和g 定义了要完成的任务， 6 南京航空航天大学硕士学位论文 i 是要完成的任务的已知条件( i c k ) ，g 是完成任务后所要得到的结果( g c k ) ，即 任务的目标。 得到任务分配方案可行解的约束条件为：只有给定一个操作所必需的输入信息力 才执行该操作：任务执行想要得到的结果都能达到。这两个条件可以转换为5 个约束： ( 1 ) 每个操作要么不被执行，要么被某个a g e n t 执行一次，不可能被重复执行。 ( 2 ) 所有操作的输出信息组成的集合必须包括任务目标集中的每一个信息。 ( 3 ) 对于每一个被执行的操作而言，其所有输入信息都应该存在。 ( 4 ) 任务被分解为一个操作集后，各操作的执行顺序必须可行。这一点对子任 务间具有相互约束关系的情况而言非常重要。 ( 5 ) 在一个任务分配方案中，只有当一个操作为另一个操作提供输入信息时， 它们之间才进行通信。 在以上条件约束下，任务分配的最优解在目标函数取最小值时获得，目标函数为： z f e x e c f u n ( a 州e ) + c o m m f u n ( e ，易) ( 1 ) l i t i 公式( 1 ) 中e x e c f u n ( a , ，五，) 为a g e n t j 执行操作i 的执行开销，c o m m f u n ( e ，e j ) 为两个a g e n t 问的通信开销。 启发式算法把任务分配问题分成两个子问题求解：第一个是将任务分解为一组操 作，即确定一组满足约束条件( 2 ) 、( 3 ) 和( 4 ) 的操作。第二个是在保证系统执行 开销和通信开销最小的前提下，把第一个问题中得到的一组操作分配给a g e n t 执行。 定义系统环境；设系统共有n 个操作、m 个任务a g e n t ( 处理业务逻辑的a g e n t ) 以及k 种知识。求解第一个子问题的步骤如下： ( 1 ) 从n 个操作中选出所有可以把任务初始信息作为其输入信息的操作，组成 操作集b e g i n n e r s ，b e g i n n e r s 中包含了多少个操作，就说明对给定任务进行分解有多 少个可能的路径。 ( 2 ) 如果b e g i n n e r s 为空集，则说明任务的初始信息不足以成为任何一个操作的 输入信息，问题不可解，退出算法。 否则从b e g i n n e r s 中任选一个操作t o ，将t o 从b e g i n n e r s 中去除，定义以o u t p u t ( t 0 ) 和初始信息组成的并集为当前已知条件，令a c t i o n s = t o ) 。直至可以获得任务目标g 中的所有信息或者a 中的所有操作均已被选择之前，循环执行如下动作：从所有不 属于a c t i o n s 的操作中选出可以把当前已知条件作为输入信息的所有操作( 即所有在 当前已知条件下可以执行的操作) ，再将这些操作的输出信息与当前己知条件合并， 成为新的当前已知条件，同时把这些操作放入a c t i o n s 集合中。 这一步是为了确定以t o 为起始操作来分解任务是否可行，能否得到一个包含任 务分解可行解的操作集。操作t o 与循环中被选择的所有操作组成一个集合a c t i o n s 。 ( 3 ) 如果已获得任务目标g 中的所有信息，则从a c t i o n s 中找出一组操作，组 多a g e n t 的协同与通信技术研究 成一个输出信息覆盖任务目标集g 的操作集，算法结束；否则说明a 中的所有操作 均已被选择之后还未能获得任务目标g 中的所有信息，即以t o 为起点操作是不可行 的，重新开始执行第( 2 ) 。 经过如上几步得到一组可行的操作集后，开始求解第二个子问题，即在满足约束 条件( 1 ) 和( 5 ) 的情况下求目标函数的最小值，并把此时的分配方案作为任务分配 的最优解，最优解由一组数据对组成 ， ， 。在实际求解中，由 于此问题的约束条件数目与操作间传递的数据量的平方成正比，要真正获得最优解的 代价将会随着操作间传递的数据量的增大而大幅增长，此时用常规的整数规划方法求 解已经不合适了。这时可以采用线性规划松弛法 2 9 1 来求解，一般可以得到一个近似最 优解。 在基于多a g e n t 的分布式开放计算环境中。启发式任务分配算法可以较好地处理 复杂任务，并获得优越的系统性能。但是对一个中小型封闭式m a s 而言，这样的算 法代价是非常大的。特别是对那些大多数用户请求都可以由一个a g e n t 完成的系统， 采用启发式算法反而会大大增加系统开销。所以，启发式任务分配算法在很少需要对 任务进行分解的系统中并不具有优势。 2 2 2 基于排队论的调度算法 在多a g e n t 系统中，如果用户提交的任务请求经常只需一个a g e n t 就可以完成， 不需要先进行任务的分解，就可以用排队论的方法进行任务分配。这样既可以有效地 选择任务的执行者，也可以使系统复杂度降低、易于实现。 排队论调度算法适合于集中协同机制，其主要思想是：每个a g e n t 都允许任务排 队，称之为服务队列，a g e n t 根据先来先服务( f c f s ) 的原则依次执行自己队列中的 任务。系统根据和a g e n t 服务队列相关的参数，在提供同种服务的多个a g e n t 间选择 一个队列参数最优的a g e n t 作为某个任务的执行者，并将该任务放到被选定a g e n t 的服务队列末尾。 排队论调度算法是一类算法，所选的队列参数不同，算法也不一样，比较有代表 性的有以下三种： 第一种，最小队列算法。 该算法对文献 1 6 1 中m i n q 算法进行了改进，定义最大允许队列长度与当前队列 长度的差值为剩余服务能力，该算法将最小队列的衡量标准从 1 6 1 中的最大剩余服务 能力改为最小当前队列长度。因为队列中的一项任务能否较早地得到执行并不取决于 剩余服务能力，而取决于当前队列的长度：例如，a g e n ta 最大允许队列长度为1 ， 当前队列长度为0 ，a g e n tb 最大允许队列长度为3 ，当前队列长度为1 ，按文献1 1 6 】 的算法则选b 执行任务，但在队列中各任务执行时间相差不大的情况下，选择a 反 南京航空航天大学硕士学位论文 而能使任务更快得到执行。 设系统提供n 种服务，其中第i 种服务记为s i ，提供s i 服务的a g e n t 共k i 个，令 提供第i 种服务的第j 个a g e n t 为a 0 ( i _ 1 ，n 且j = l ，k i ) ，a i j 在所有提供s i 服务 的a g e n t 问的序号就是j ，其最大允许队列长度为q m a x i j ，当前队列长度为q c u r r i j ， 这里q m a x ，和q c u r r i i 都不包括正在执行中的任务。最小队列算法如下： ( 1 ) 根据用户提交的任务的初始条件、各种服务所需要的输入信息以及与任务 相关的知识领域，找到任务所需要的服务s i ： ( 2 ) 获取提供s i 服务的各a g e n t 的当前队列长度：q c u r r i l ，q c u r r i 2 ， q c u r r i k i ； ( 3 ) 如果对k 。个a g e n t 都有q m a x 0 = q c u r r 0 成立，则拒绝用户任务请求并转 到( 5 ) ，否则继续； ( 4 ) 在q c u r r o q m a x i j 的a g e n t 中选出q c u r r 0 最小的一组a g e n t ，并从中 选出序号最小的一个作为任务的执行者，把任务提交给它； ( 5 ) 结束。 第二种，最小等待时间算法i l “。 实际过程中，可能会出现这样的情况：一个a g e n t 的服务速度很快，虽然它的服 务队列很长，但却可以在很短时间内执行完所有的任务；而另外一个a g e n t 虽然队列 很短，但却需要更长的时间才能将队列中的任务处理完。如果用最小队列算法，新任 务会选择后者，结果反而会等待更长的时间。对于各a g e n t 处理能力相似，各任务的 预计执行时间也相差不大的系统而言，这个问题可以忽略，但如果系统内a g e n t 处理 能力相差很大，或者任务的预计执行时间相差很大时，就应该采用最小等待时间算法。 该算法不以队列长度为选择任务执行者的标准，而是考虑如何使待执行任务的等待时 间最短。 根据第一种算法的假设a 。i 队列中共有q c u r r i l 个任务在等待服务，设各任务的 预计执行时间为t l ，t 2 ，t q c u r r 那么，下一个提交给a i l 的任务的等待时间 为：w t i j = t l 十t 2 + + t q c u r r i i ，这里为了简化，没有将正在执行的任务的剩余执行时 间算在内。算法如下： ( 1 ) 根据用户提交的任务的初始条件、各种服务所需要的输入信息以及与任务 相关的知识领域，找到任务所需要的服务s i , ( 2 ) 获取提供s i 服务的各a g e n t 的当前队列长度：q c u r r i i ，q c u r r i 2 ， q c u r r i k i ； ( 3 ) 计算被分配的任务选择a j i ( 净1 ，nj 罩j = l ，k i ) 所需要等待的时间：、t i l ， w t l 2 ，w t ( 4 ) 如果对k i 个a g e n t 都有q m a x i j = q c u r r j j 成立，则拒绝用户任务请求并转 9 多a g e n t 的协同与通信技术研究 到( 6 ) ，否则继续； ( 5 ) 在q c u r r j j q m a x i j 的a g e n t 中选出w t 0 揖t d 、的一组a g e n t ，并从中选出 序号最小的一个作为任务的执行者，把任务提交给它： ( 6 ) 结束。 第三种，历史信息算法【l 。 最小队列算法和最小等待时间算法都没有考虑历史信息，而历史信息算法则将历 史信息考虑在内，以决定任务的执行者。该算法以a g e n t 的利用率、各a g e n t 的当前 队列长度等为决定因素，计算出各a g e n t 的权重值m u ，并选取m u 最小的a g e n t 集合 中序号最小的一个为任务执行者。先给出两个定义： d e f 啪利月率= 器( 观察时间跏t n o w 砜o w 】) ( 2 ) 。e f a 。队列长度的权重为m ”= 口u 口+ 箍 ( 3 ) 其中口0 ，卢1 并且d + = 1 口、是系统参数，d 越大表明在选择任务执行者时，考虑a un n n n ! 够- - 点，卢越大表明考虑a i 的当前队列长度更多一点。 历史信息算法如下： ( 1 ) 根据用户提交的任务的初始条件、各种服务所需要的输入信息以及与任务 相关的知识领域，找到任务所需要的服务s i ： ( 2 ) 获取提供s j 服务的各a g e n t 的当前队列长度：q c u r r i l ，q c u r r i 2 ， q c u r r i k i ； ( 3 ) 获取a l ，a i i ( 在观察时间段t n o w - t , t 。 内的工作时间，用公式( 2 ) 计 算它们的利用率u i l ，u i 2 ，u i k i l ( 4 ) 用公式( 3 ) 计算a i l ，a i 2 ，a i k i 的权重m u ，m i 2 ，m i k i ； ( 5 ) 如果对k j 个a g e n t 都有q m a x o = q c u r r i j 成立，则拒绝用户任务请求并转 到( 7 ) ，否则继续； ( 6 ) 在q c u r r u q m a x i j 的a g e n t 中选出权重m u 最小的一组a g e n t ，并从中选 出序号最小的一个作为任务的执行者，把任务提交给它； ( 7 ) 结束。 三种算法相比，最小队列算法需要的系统信息和系统开销最小，但在各a g e n t 处理能力差异较大时，不能为新任务选择一个等待时间最小的a g e n t ；最小等待时间 算法需要较多的系统信息，在a g e n t 处理能力相差较大和任务预计处理时间相差较大 0 南京航空航天大学硕士学位论文 时，可以使各任务尽快得到执行，但在a g e n t 处理能力相近时，其结果与最小队列算 法相比并没有什么优势；历史信息算法充分考虑了任务分配的均衡性，使提供同一种 服务的a g e n t 的任务量和工作时间都差不多，但需要较大的系统开销。因此，当提供 相同服务的a g e n t 处理能力相近时，则采用最小队列算法是最好的；若a g e n t 处理能 力相近，需要每一个a g e n t 工作时间都差不多且允许系统有较大的开销时，则采用历 史信息法；若提供相同服务的a g e n t 的处理能力相差较大，则采用最小等待时间算法。 2 2 3t r i b a s e 模型f 3 0 j t r i b a s e 模型从单个a g e n t 内部结构的角度来研究多a g e n t 协同机制，适合于分布 式协同机制的任务分配。该模型对t w i n b a s e 模型 3 3 1 进行了改迸，主要思想源于 j e n n i n g s 等人提出的a c q u a i m a n c em o d e l 3 ”。它基于这样一个理论：单个a g e n t 在合作 中需要的关于其它a g e n t 的信息，不再存储于一个全局协同管理者中，而是高度分布 地存储于自身内部的w r a p p e r 中。单个a g e n t 一般由两部分组成，一部分是应用逻辑 部件，该部件实现a g e n t 的应用功能，往往是一个已有的应用程序，另一部分是一个 w r a p p e r ，负责实现a g e n t 的社会特性，如竞争、协同等，w r a p p e r 包括了a g e n t 的行 为模型。t w i n b a s e 模型在a g e n t 的w r a p p e r 中建立了和协同相关的两个信息库：合 作者信息库c o o p e r a t o rb a s e 和任务信息库t a s kb a s e 【3 。t r i b a s e 在此基础上将 c o o p e r a t o rb a s e 中有关a g e n t 本身的信息分为两种，半静态信息和动态信息，半静态 信息仍存放在c o o p e r a t o rb a s e 中，动态信息存放在状态库s t a t eb a s e 中。利用t r i b a s e 模型进行任务分配，其核心问题在于如何组建c o o p e r a t o r b a s e 、t a s kb a s e 和s t a t eb a s e 的结构和信息。 a g e n tx 的c o o p e r a t o rb a s e 包括两个部分：c o i l a b o r a t o r ss e c t i o n 和s u b s c r i b e r s s e c t i o n ，存储了a g e n tx 所有合作者的永久性信息，即在其生命周期内不变的信息。 c o l l a b o r a t o r ss e c t i o n 存有这些合作者的地址、消息格式和责任。s u b s c r i b e r ss e c t i o n 记 录了所有对a g e n tx 的状态变化感兴趣的a g e n t s 的地址，这些a g e n t s 是事先向a g e n t x 定购了其状态变化信息的，一旦a g e n tx 有了状态或计划的变动，就会向这些在 s u b s c r i b e r ss e c t i o n 中记录的a g e n t s 公告变动信息。 a g e n tx 的s t a t eb a s e 存放了台作者的非永久信息，包括a g e n ts e c t i o n 和t a s k s e c t i o n 。a g e n ts e c t i o n 存放了所有与a g e n tx 有合作关系的a g e n t s 的实时状态，包括 它们的负载和可信度，一个a g e n t 占用一个元组。某个元组的可信度可以用该元组数 据保持不变的时间以及( 或) 数据变动的频率表示。数据t a s ks e c t i o n 存放了a g e n t x 要执行的任务的信息，这些任务有些是x 自己的任务，有些是其它a g e n t 请求合作解 决的任务。 a g e n tx 的t a s kb a s e 包括了任务可能的分解方案，共分为p r o b l e ms e c t i o n 和p l a n 多a g e n t 的协同与通信技术研究 s e c t i o n 。p r o b l e ms e c t i o n 存放对a g e n tx 的任务t a s k 的可能分解方案。p l a ns e c t i o n 主 要是给出在当前状态下如何执行p r o b l e ms e c t i o n 中任务的建议。 上述的t r i b a s e 模型包含的三个库，c o o p e r a t o r b a s e 、s t a t eb a s e 和t a s kb a s e 之间 的关系，可以用图2 3 来表示： 图2 _ 3 t r i b a s e 模型 在不考虑子任务执行顺序的前提下，基于t r i b a s e 的任务分配过程如下所述： 当a g e n tx 接到一个任务s u p e r t a s k 之时，x 可以有两种选择：第一是使用存在于 t a s kb a s e 的p l a ns e c t i o n 中已有的一个执行计划；第二是重新生成一个新计划。如果 采用第二种方法，则分配步骤是： ( 1 ) x 从t a s k b a s e 的p r o b l e ms e c t i o n 中找到有关s u p e r t a s k 的知识。 ( 2 ) 查找c o o p e r a t o r b a s e ，为操作集 t i 中的每一个操作找到可能的执行者。最 后每一萃中组合 ， ， ( k 为操作的个数) 形成一个任务分