（计算机科学与技术专业论文）基于扩展合同网的多agent任务分配机制的研究.pdf

中文摘要 摘要 任务分配已经成为当今以分布式、开放性、智能化和社会性为特征的复杂系 统运作的一个重要问题。但是，系统内外环境的变化不断，系统内成员能力的动 态变化等，这些都可能给任务分配问题的求解带来困难。多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 任务分配机制应用到钢材采购管理系统中，实现供应商选择问题。 基于扩展合同网的多a g e n t 任务分配涉及到m a s 、组织理论等多个领域，其 进一步的完善和发展也有很多研究工作要做，必将有越来越多的研究者关注这一 课题。 关键词：任务分配；多a g e n t 系统；扩展合同网；协商 英文摘要 a b s t r a c t t a s ka l l o c a t i o nh a sb e c o m ea l li m p o r t a n ti s s u eo ft h ec o m p l e xs y s t e m sw i mt h e d i s t r i b u t e d 、o p e n 、i n t e l l i g e n ta n ds o c i a lc h a r a c t e r i s t i cf o rt h ec o l l e c t i o no fo p e r a t i o n h o w e v e r , c o n t i n u o u sc h a n g e so fi n t e r n a la n de x t e r n a le n v i r o n m e n ta n dd y n a m i c a l c h a n g e so ft h ec a p a c i t yo fm e m b e r sm a yg i v et a s k sa l l o c a t i o ns o l v i n gd i f f i c u l t y m u l t i a g e n ts y s t e m ( m a s ) i st os t u d yh o wt om a k eo n eo rm o r ee n t i t i e sc o m p l e t e c o m p l e xo rt e d i o u st a s k sw i t h o u tg u i d a n c et h r o u g hm u t u a lc o o p e r a t i o n , c o o r d i n a t i o n a n dc o n s u l t a t i o n t h ee m e r g e n c eo fm a sb r i n g san e ww a yt os o l v es u c hi s s u e sa s a b o v e c o n t r a c tn e tp r o t o c o l ( c n p ) i sac l a s s i cc o o r d i n a t i o ns t r a t e g yo fa l l o c a t i o no f r e s o u r c e sa n dt a s k s t h eb a s i ci d e ai st oa l l o c a t et a s k sa n dc o m p l e t et h ec o n t r a c t u a l r e l a t i o n s h i pt h r o u g ht h em a r k e tm e c h a n i s m sl i k e t e n d e r i n g - t e n d e r a w a r d i n g w i 廿l l o w e rc o s t sa n dh i g h e rq u a l i t i e s g e n e r a l l y ，t h et r a d i t i o n a lc o n t r a c tn e tm o d e ld o e sn o tp l a c ea n yl i m i t so n c o m p e t i t o r s ， b u tt h eb r o a d c a s to ft a s ka n n o u n c e m e n tt e n d st oc o n s u m em u c h c o m m u n i c a t i o nl o a dw h e nt h ea g e n t sa r ee x c e s s i v e o nt h eo t h e rh a n d ，a g e n tc a nd e a l w i mu n r e s t r i c t e da c c e s st oa n yb i d ，w h i c hm a k e sal o to fc o m m u n i c a t i o nb e c o m e u n n e c e s s a r yb e h a v i o r i no r d e rt or e d u c et h ec o s t s ，s i m p l i f ya g e n td e c i s i o n - m a k i n g p r o c e s sa n di m p r o v et h ee f f i c i e n c yo fs o l v i n gp r o b l e m ，t h i sp a p e ri n t r o d u c e ss e v e r a l m i n dp a r a m e t e r s ，s u c ha sf a m i l i a r , t r u s ta n da c t i v e ，t or e s t r i c tt h es c o p eo ft e n d e rb y a d o p t i n gt h e ”a c q u a i n t a n c em e c h a n i s m ”，s e t sb u f f e rp o o lf o re a c ha g e n tt ol i m i tt h e n u m b e ro f b i d sa n dp r o p o e st h em o d i f i e dr u l e st oe v a l u a t et h eq u a l i t yo ft a s k s b a s e do n t h ei m p r o v e dc o n t r a c tn e tm e t h o d ，am u l t i a g e n tt a s ka l l o c a t i o ns t r a t e g yb a s e do n e x t e n d e dc o n t r a c tn e ti sp r e s e n t e d ，w h i c he n s u r e sab e t t e rn e g o t i a t i o nq u a l i t y , d e s i g n s a n di m p l e m e n t st h et a s ka l l o c a t i o na l g o r i t h m f i n a l l y , o nt h i sb a s i so fa b o v e ，t h et a s k a l l o c a t i o nm e c h a n i s mo fm u l t i a g e n tb a s e do ne x t e n d e dc o n t r a c tn e ti sa p p l i e dt ot h e s t e e lp r o c u r e m e n tm a n a g e m e n ts y s t e m ，i nt h ef o r mo fa ni n s t a n c e ，t oa c h i e v et h ei s s u e o fs u p p l i e rs e l e c t i o n t a s ka l l o c a t i o no fm u l t i a g e n tb a s e do ne x t e n d e dc o n t r a c tn e th a sb e e nc o v e r i n g m a s 、o r g a n i z a t i o nt h e o r ya n do t h e rf i e l d s t h er e s e a r c ho ff u r t h e ri m p r o v e m e n ta n d 英文摘要 d e v e l o p m e n ti ss t i l lt ob ed o n e ，w h i c hc a u s e sa ni n c r e a s i n gn u m b e ro fr e s e a r c h e r sf o r k e yw o r d s ：t a s ka l l o c a t i o nm e c h a n i s m ；m u l t i - a g e n ts y s t e m ；e x t e n d e dc o n t r a c t n e t ；n e g o t i a t i o n 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文= = 基王芷屋金圆圆的丕g 型堡釜佥整扭剑的婴宜：。除论 文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经 公开发表或未公开发表的成果。本声明的法律责任由本人承担。 2 ，押 学位论文作者签名：盅幽 学位论文版权使用授权书 本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学 位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论 文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫 描等复制手段保存和汇编学位论文。同意将本学位论文收录到中国优秀博硕士 学位论文全文数据库( 中国学术期刊( 光盘版) 电子杂志社) 、中国学位论 文全文数据库( 中国科学技术信息研究所) 等数据库中，并以电子出版物形式 出版发行和提供信息服务。保密的论文在解密后遵守此规定。 本学位论文属于：保密口在年解密后适用本授权书。 不保密日( 请在以上方框内打“ ) 论文作者签名：未矛礅导师签名：表i j 宁 日期：如口9 年7 月fe l 基于扩展合同网的多a g e n t 任务分配机制的研究 第1 章绪论 1 1 研究背景 随着计算机技术、通信技术和网络技术的高速发展，分布式人工智能 ( d i s t r i b u t e da r t i f i o mi m e l l i g 懈，d a i ) 的研究越来越受到人们的广泛关注，并 取得的一些研究成果已经在解决实际问题方面起到一定的作用。多a g e n t 系统 ( m u l t i a g e n ts y s t 锄，m a s ) 就是分布式人工智能发展的结果。计算机技术的迅 猛发展也使得社会各个领域发生着快速剧烈的变化，出现了大量以分布式、开放 性、智能化和社会性为特征的复杂系统。 任务分配是这些复杂系统运作中必须解决的一个重要问题，也是多a g e n t 系 统中的热点问题之一【l - 3 】。其原因是：第一，任务分配的效率直接影响到系统的效 率；第二，任务分配机制的好坏直接关系到系统中各a g e n t 能否最大限度地发挥 自身的能力，避免占用更多的资源；第三，当一个a g e n t 没有能力完成当前任务 时，如何在现有机制的基础上，通过有效的对话、协商使多个a g e n t 合作来完成 任务。 任务分配策略的研究一直是任务分配理论关注的重点，这方面的研究分为再 分配型和新任务型4 1 。再分配型的任务分配目前已有如优化算澍5 1 、动态负载平衡 f 6 】等许多成熟的技术方法。新任务型的任务分配是指需要根据系统中各成员的能 力、潜力和当前的资源负载状况，对随机到达系统的新任务进行分配。一方面， 因为环境的随时变化可能产生新的机遇，使复杂系统中不断有新的任务产生，并 且需要及时分配完成；另一方面，系统内各个成员的能力也是不断的动态变化着， 可能会使分配的任务无法及时完成或者系统的负载不均衡，导致这些任务需要再 次进行分配。所有这些特点都给新任务型的任务分配问题的解决带来了困难。 m a s 的出现为这类复杂系统的研究提供了契机【7 1 。a g e n t 所表现出的自治性、 反应性、预动性和社会性，可以为复杂问题的求解提供新方法。同时，m a s 所特 有的如协作性、并行性、健壮性、易扩展性、分布性等特征，更适合用来描述复 杂系统。因此，m a s 被认为是复杂系统研究的重要理论模型。 第1 章绪论 m a s 从2 0 世纪8 0 年代开始被研究，直到2 0 世纪9 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 来解决问题更好的结果。 合同网协议【8 胴( c o n t r a c tn e tp r o t o c o l ，简称c n p ) 是s m i t hr g 和d a v i sr 在1 9 8 1 年提出的关于任务和资源分配的经典协调策略，最早用于分布式传感器系 统。其基本思想是节点之间通过“招标一投标一中标”这一市场投标机制进行任 务分配，使系统以较低的代价，较高的质量完成委托和承揽构成的合同关系。 本文是结合大连重工起重集团有限公司备料厂的“板材数控套料系统 中的 子系统“钢材采购管理系统 而展开的任务分配问题的研究工作。在a g e n t 技术 和m a s 基本理论的指导下，借鉴现有任务分配理论的研究成果和技术方法以及合 同网机制，提出了基于扩展合同网的多a g e n t 任务分配机制。 1 2 国内外研究现状 目前，国内外已经对合同网有一定的研究。a g e n t 间的合作广泛采用合同网协 议，许多学者针对传统合同网的不同方面和应用领域进行改进，如基于黑板的任 务协同机制【l o 】、动态合同网协议等方案。 1 2 1 国外研究情况 美国的卡内基梅隆大学智能协调与后勤实验室提出的m u l t i a g e n t 供需链协调 框架m a s c o t ( m u l t i a g e n ts u p p l yc h a i nc o o r d i n a t i o nt o o l s ) ，其中每一个协调 a g e n t 都是在i p 3 s ( i n t e g r a t e dp r o c e s sp l a n n i n g p r o d u c t i o ns c h e d u l i n g ) 的a g e n t 体 系结构的基础上扩展而来【l l 】【1 2 1 ，支持以事件驱动的协调过程和混合动态计划。 s a n d h o l m 将竞争a g e n t 引入到传统的合同网中，并在投标和中标过程中通过边际 成本计算来进行决策，建立了基于边际成本计算的投标和评标的形式化决策模型 【1 3 】。但是，其计算过程忽略了任务分配时协商策略的质量和其它因素的影响，而 且招投标的过程采用过于简单的单回合单中标者的方式，无法满足现实中复杂系 统下动态任务分配问题的求解需求。u e n o 在合同网协议中引入讨价还价的策略， 通过使用a g e n t 通信语言使合同者和管理者之间进行交流，告诉管理者自己对于 任务执行的意见【1 4 】但是，这种方法极大地增加了a g e n t 决策的复杂度，而且通 基于扩展合同网的多a g e n t 任务分配机n e f f 研究 信采用的不是广泛使用的k q m l 。s i m 建立了一套a g e n t 和任务的选择策略，采 用合同网作为合作设计中的任务分配的协商模型，并通过有色p e t r i 网仿真试验评 价所构建策略的性斛”】。但这种思想过分强调了问题的领域特征，很难建立有效 的合同网理论。h a n n a 研究了不确定环境下多项任务分配中的投标决策问题，构建 了任务分配的m d p 模型，讨论了a g e n t 投标时对中标概率和执行速度的学习策略 1 6 1 。但该模型只适用于有限资源下的序列任务分配问题。c h e n 在合同网的投标和 中标的决策过程中引入投标阈值，以限制协商过程中的计算及通信开销【1 7 1 。f i s c h e 在合同网中引入临时信任拒绝、模拟交易等机制来优化任务分配【i 引。c o l l i n s 将仲 裁机制融合在协商过程中，以防止投标过程中的欺诈行为【l9 1 。l e e 将承诺期限加入 到合同网中来适应任务环境的动态变化【2 0 】等等。另外，b o u z o u i a 在利用学习机制 来优化合同网任务分配过程方面也做了有益的探讨2 1 1 。 1 2 2 国内研究情况 郭锐锋考虑到投标者的过去、现在和将来的可能状态，提出了基于成本模型 的标值计算模型【2 2 】。但是，并没有给出具体的计算方法。万武南给出了一个任务 熟人集的概念，提出一种改进的合同网模型和基于任务熟人集选择候选结点和协 商策略方法的选择机制【2 3 1 。然而，它过分依赖于同类任务的分配历史，而且对于 熟悉度只增不减，不利于描述动态环境下a g e n t 能力的变化。张海俊结合群体智 能提出了一种适应环境及主体能力动态变化的动态合同网协议【l o 】。王玉善将a g e n t 的心智状态引入到合同网协议，讨论了a g e n t 的性格特征、他信度以及友好程度 等因素对招投标过程的影响，提高了合同网模型的适应性和灵活性【2 4 】。文献【2 5 】 通过引入历史信息作为决策的依据，充分利用a g e n t 的历史经验，提出了基于范 例推理( c a s e - b a s e dr e a s o n i n g ，c b r ) 的合同网【2 习。在对任务进行分配时，首先 进行范例的搜索，若找到则在范例的指导下进行任务分配协商；若找不到则继续 招投标过程。高志军提出了一种基于合同网的改进机制任务列表分配机制， 有效地提高了系统实时处理能力和工作效率【2 6 1 。曾广周等人定义了一种a g e n t 能 力自信度，给出了基于合同网协议和a g e n t 能力自信度的任务分配算法和应用实 例【2 7 】。但其前提条件是假设a g e n t 都是真实的，而且没有包括基于历史信息的可 信度计算。而在文献 2 8 1 0 e ，赵新宇提出了可信度模型，以解决系统中存在自私类 第1 章绪论 型的a g e n t 的任务分配问题【2 3 】。胡晶晶等人则采用了拍卖市场机制实现多a g e n t 的任务分配协商，提出了一种英式多议题协商协议，用于实现最佳多议题任务分 配，提高了资源利用型2 引。莫思敏提出了依据承诺度在简化的熟人模型中寻找合 作a g e n t 的方法【3 0 1 。同时，考虑了时间、代价、质量等因素，但是管理者a g e n t 仅仅依据a g e n t 自身的承诺值来挑选a g e n t ，没有考察其历史行为，也没有考虑到 投标a g e n t 为了利益而做出虚假承诺的情况。 1 3 研究内容和主要工作 1 3 1 研究内容 本文的研究是围绕“板材数控套料系统开发 这一项目的子系统“钢材采购管 理系统 而展开任务分配问题的研究工作。通过对大量相关的硕博论文以及中英 文参考文献的阅读和学习，熟悉并了解现有的a g e n t 技术及多a g e n t 开发方法的基 本理论；根据对现有合同网模型的分析和研究，结合心智参数和缓冲池对合同网 进行改进和扩展，建立了基于熟人机制的合同网模型；分析和学习现有的任务分 配机制，提出基于扩展合同网的多a g e n t 任务分配机制，设计并实现任务分配算 法，将该分配机制应用到采购管理系统中，实现供应商的选择。 1 3 2 主要工作 具体地讲，本文的主要工作如下： ( 1 ) 相关理论的研究 介绍了a g e n t 与m a s 的基本理论，对m a s 和单个a g e n t 进行比较，介绍了 基于m a s 的任务分配理论，特别是任务分配方法，为本文基于扩展合同网的多 a g e n t 任务分配机制的研究工作做了一些理论上的铺垫。 ( 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 完成任务的质量做 评价。 ( 3 ) 提出基于扩展合同网的多a g e n t 任务分配机制 分别建立了基于任务熟人信任度的招标策略，引入缓冲池限制投标数目的投 标策略以及结合层次分析法和综合模糊评价法的中标策略。规范了基于扩展合同 网的任务分配各个阶段的行为规则。在此基础上，设计出基于扩展合同网的任务 分配算法，并进行详细的描述。 ( 4 ) 基于扩展合同网的多a g e n t 任务分配机制的应用 结合大连重工起重集团有限公司备料厂的钢材采购管理系统的具体应用，详 细分析了系统的总体功能需求，设计了管理者a g e n t 和投标者a g e n t 的内部结构， 列出部分相关代码；最后设计并实现了基于a g e n t 的钢材采购管理系统的原型系 统。 1 4 论文组织结构 本文共分为六章，内容概要如下。图1 1 展示了论文的组织结构。 第l 章绪论。介绍了论文的研究背景；关于合同网和任务分配机制的国内外 研究现状；阐述了论文的主要研究内容，并说明论文的组织结构。 第2 章m a s 和任务分配理论。介绍了a g e n t 的概念、特征及其结构；m a s 的概念，特征和体系结构；对m a s 和单个a g e n t 进行比较，得出本文选用m a s 的优势；阐述了基于m a s 的任务分配理论。 第3 章多a g e n t 协作中合同网协议的改进。在分析传统合同网存在的不足的 基础上，从控制招标范围、限制投标数目和a g e n t 心智参数更新三个方面对传统 合同网进行改进，形成扩展的合同网模型。 第4 章基于扩展合同网的多a g e n t 任务分配。形式化的描述基于扩展合同网 的多a g e n t 任务分配问题，对任务分配过程中的协商框架、协商策略( 招标策略， 投标策略，中标策略) 以及任务分配算法进行了分析和设计。 第5 章任务分配机制在采购管理系统中的应用。对采购管理系统进行总体分 析和设计；以实例的形式将采购任务分配过程进行详细描述；设计出管理者a g e n t 和投标者a g e n t 的模块结构图。 第1 章绪论 望。 第6 章结论与展望。总结全文的主要工作，并对下一步可能的工作提出了展 图1 i 论文逻辑结构图 f i g 1 il o g i c a ls t r u c t u r eo ft h ep a p e r 基于扩展合同网的多a g e n t 任务分配机制的研究 第2 章m a s 和任务分配理论 2 1a g e n t 技术概述 2 1 1a g e n t 的概念和特征 a g e n t 这个概念来源于人工智能领域。对于“a g e n t 一词，国内的文献有的 翻译成智能体，主体，代理等，但最常见的仍采用英文“a g e n t 3 1 - 3 3 】。a g e n t 一 词最早出现于m m i n s k y l 9 8 6 年出版的s o c i e t yo fm i n d ) ) 一书中，他在书中将 s o c i e t y 和s o c i e t yb e h a v i o r 的概念引入到计算机系统中【3 4 1 。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 关系以及环境特征出发，来预测、引导和达成系统的总体目 标。 ( 1 ) a g e n t 的弱概念【3 5 1 这是从广义的角度来规定a g e n t 最基本的特征。几乎所有被称为a g e n t 的软件 或硬件系统都具有以下的特征： 自治性( a u t o n o m y ) ：a g e n t 能够在没有外界干预的情况下自动操作，并且能 够控制自身的行为和内部状态。自治性是a g e n t 区别于普通对象的重要标志。 反应性( r e s p o n s i v e ) ：a g e n t 能够感知环境并对环境的变化做出反应。环境 包括客观存在的物理实体，通信网络，其他a g e n t 等等。反应性本来是生物体的 基本属性，强调a g e n t 具有反应性表现出a g e n t 具有某种生命特征。 自发性( p r o a c t i v e ) ：a g e n t 不仅能对环境的变化做出反应，还能够根据自身 的目标采取相应的行动。自发性反映了a g e n t 在决策和实施行为过程中的理性特 征。 社会性( s o c i m ) ：a g e n t 所驻留的环境可能存在其他的a g e n t ，它拥有这些 a g e n t 的有关信息和知识，能通过某种通信语言与它们进行交互，实现灵活多样和 复杂的合作、协商和竞争，以满足系统的设计目标。社会性可使a g e n t 之间形成 第2 章m a s 和任务分配理论 多a g e n t 系统，从而构成相应的a g e n t 组织或社会，进而实现对客观世界的抽象、 分解、组织和优化。 ( 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 总是尽可能完成其它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 的行为具有某种不确定性，即使知道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 的弱概念还是强概念，它们都是对a g e n t 的特性的描述。r u s s e l 和n o r v i g 指出，a g e n t 可以是任何能通过感知环境并通过效应器作用于环境的事 物【3 6 1 。a g e n t 是一种更高粒度的抽象，它除了能够实现属性、事件和方法的封装以 外，还可以被赋予思维决策的能力，表现出更高的自治性和较强的目标性、灵活 的反应性以及与其它a g e n t ( 或对象、人等) 进行交互的社会性等【3 7 1 。采用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 的灵活性有助于对软件系统的集成。一般情况下，将遗留系统封装 成a g e n t 来进行维护，可以使其继续发挥作用，以方便已有系统间的连接及其与 新系统的和谐共存，节省了资源。 2 1 2a 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 ) 慎思型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 的决策推理过程。如 b r a t m a n 从哲学的角度研究个体行为意图，提出a g e n t 可以通过意识态度来描述， 并认为只有达到意识层次上的理性平衡才能有效解决问题【3 引。采用慎思式体系结 构的典型实例是i r m a 系统【3 9 】和g r a t e * 系统。 c o h e n 和l e v e s q u e 在b r a t m a n 意图理论的基础上，对信念、意图作了形式化描 述，并用形式逻辑的方法讨论了a g e n t 意识态度的理性平衡，分析了意图在维持 理性平衡中的作用【4 。 r a o 和g e o r g e f f 进一步完善和发展了意图理论，提出了用信念( b e l i e f ) 、愿 望( d e s i r e ) 和意图( i n t e n t i o n ) 三部件刻画a g e n t 的b d i 模型，并采用三个模态 算子进行刻画，建立了描述a g e n t 意识态度的b d i 逻辑【4 2 1 。 另外，还有一些研究者关注着慎思型a g e n t 。在国外，根据a g e n t 应用领域的 不同，s h o h a m 等人将意识态度分为信息类、动机类、社会类和其他类【4 3 】；w o o l d r i d g e 等人则把它分为信息态度和积极态度，并指出一个理性a g e n t 总是基于信息态度 去采取积极态度，如根据信念去选择目标和形成意图，并建立了基于分支时间的 时序逻纠3 5 1 。在国内，清华大学石纯一教授带领研究队伍，以及华中科技大学费 奇教授带领的组织决策和协调科研团队也在这些方面做了大量的研究工作。比如 研究a g e n t 的意图模型【4 4 1 ，意图表达的语义【4 5 1 、社会理性【4 6 1 、理性a g e n t 的基本 结构【4 7 】，理性a g e n t 的推理决策和理性a g e n t 的应m ( 4 9 1 等。 第2 章m a s 和任务分配理论 慎思型a g e n t 的结构如图2 1 所示。a g e n t 通过传感器接收外界环境的信息， 根据内部状态进行信息融合，产生修改当前状态的描述；然后，在知识库的支持 下制定规划；形成一系列动作，通过效应器对环境产生作用 矧。 图2 1 慎思型a g e n t 的结构 f i g 2 1d e l i b e r a t i v ea r c h i t e c t u r e ( 2 ) 反应型a g e n t 与慎思型相对的是反应型a g e n t 。反应型a g e n t 是一种感知动作模型。这种 类型的a g e n t 中没有实际的模型和规划，仅有一些简单的行为模式，以刺激 反应的方式对环境的变化做出反应。其结构如图2 2 ，由感知器感知环境获取状态 信息，根据条件行动规则直接产生动作行为，然后通过效应器作用于外部环境。 在一些动态环境下，要求a g e n t 能够根据相关情景在满足质量标准的前提下快速 做出反应，此时，这种a g e n t 的优势得到发挥。j o n k e r 用a g e n t 来模拟动物的行为 【5 l 】，这是反应型a g e n t 的具体实例。反应型a g e n t 虽然对外界环境的变化有很高 的响应速度，但其智能程度低，缺乏灵活性。典型的系统还有r o s e n s c h e i n 和 k a e l b l i n g 的s i t u a t e da u t o m a t a 5 2 】【5 3 】、a g r e 和c h a p m a n 的p e n g i 5 4 1 、s t e e l s 的m a r s e x p l o r e r 系统5 5 】和m a e s 的a g e n tn e t w o r k s 5 6 1 。 基f 扩展合同网的多a g e n t 任务分配机制的研究 图2 2 反应型a g e n t 的结构 f i g 2 2r e a c t i v ea r c h i t e c t u r e ( 3 ) 混合型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 3 所示。包括如下两个层次的结构：一 是认知型子系统，含有用符号表示的世界模型，基于a g e n t 的内部心智状态，用 人工智能中的方式处理规划和进行决策；二是反应型子系统，能快速响应和处理 环境中突发事件，不使用任何符号表示和推理系统，通常具有较高的优先级。 混合型结构中最关键的问题是如何将各子系统适当地嵌入到一个控制框架 中，以及如何控制各层的动作，并实现各个层间的信息交互。针对这些问题在2 0 0 1 年n i l s s o n 提出三塔式( t r i p l et o w e r s ) 结构，即感知塔、模型塔和动作塔【5 7 1 。 图2 3 混合型a g e n t 的结构 f i g 2 3h y b r i da r c h i t e c m m 第2 章m a s 和任务分配理论 2 2m a s 理论 2 2 1m a s 的概念和特征 多a g e n t 系统( m u l t i a g e n ts y s t e m ，m a s ) 的概念最初源于d a i 领域，它是 由一些自主的a g e n t 组成，通过协作完成某些任务或达到某些目标的计算系统【5 8 1 。 多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 所不能解决得问题。h e r b e ts i m o n 的有 限性( b o u n d e dr a t i o n a l i t y ) 和m a r v i nm i n s k y 的“s o c i e t yo fm i n d 理论为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 系统的动态特性等等。这些方 面与m a s 的特性直接相关。 多a g e n t 系统除了具有单个a g e n t 的特性以外，还具有以下特性： ( 1 ) 协作性：m a s 中的a g e n t 可以相互协作，解决单个a g e n t 无法解决的问 题： ( 2 ) 并行性：m a s 可以通过a g e n t 间的异步并行活动，提高处理复杂问题求 解的质量和效率； ( 3 ) 健壮性：m a s 不依赖于某个单一的控制器去协调所有的任务，不会象集 中控制那样因为某一控制器的崩溃而导致系统瘫痪； ( 4 ) 易扩展性：m a s 松散耦合的特征，保证了其组件的可重用性和可扩充性； ( 5 ) 分布性：m a s 的数据、资源分散在系统环境的各个a g e n t 中，表达了系 统描述问题的分布性。 一个典型的多a g e n t 系统抽象视刚5 9 1 如图2 4 所示。 基于扩展合同网的多a g e n t 任务分配机制的研究 图2 4 多a g e n t 系统典型视图 f i g 2 4t y p i c a lv i e wo fm u l t i - a g e n ts y s t e m 系 互 2 2 。2m a $ 与单个a g e n t 的比较 m a s 与单个a g e n t 的主要区别为： ( 1 ) 用单独一个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 ) 单个a g e n t 总是能力有限，面对的问题领域和应用范围相对狭窄。多a g e n t 协作，可以弥补相互能力上和知识上的不足，提高问题的求解能力，使系统具有 更好的灵活性，拓宽其应用领域。 ( 3 ) 对单个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 的设计都是从全局角度出发，所以更易实现。 ( 4 ) 多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 技术 开发的系统，不但易于维护，效率高，而且还具有较高的灵活性。 2 2 3m a s 的主要研究内容 目前关于多a g e n t 系统的研究主要集中在如下几个方面【删： ( 1 ) m a s 中a g e n t 的模型：m a s 中a g e n t 必须对其他的a g e n t 进行建模，即 在一定抽象层次上描述其他a g e a t 的知识，以进行a g c a t 的推理和协调。主流思想 第2 章m a s 和任务分配理论 是将a g e n t 视为是具有意图的智能系统，基于思维状态的a g e n t 建模。由原来的借 鉴人类思维建立a g e n t 的b d i 模型，向m u l t i a g e n t 扩展，形成m a s 的b d i 模型， 并分析社会承诺和联合意图等概念。 ( 2 ) a g e n t 通信和交互：a g e n t 的通信与交互涉及到a g e n t 之间的物理连接、通 信的方式、通信意图的互相理解和生成、通信术语的解析、交互协议等。 ( 3 ) 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 协商是指借助通信手段和协商策略，交换各自的目标，直到多个a g e n t 的目 标一致或者最终不能达到一致。 目前，a g e n t 协商策略模型和机制的研究是多a g e n t 系统研究的核心问题。本 论文就是针对最后一个问题，即a g e n t 在合同网模型中相互合作以达到任务的合 理分配。 2 3 基于m a s 的任务分配理论 多a g e n t 系统中存在着许多能够独立求解问题的a g e n t ，但是，复杂系统中的 许多问题并不