（系统工程专业论文）基于多智能体的生产调度方法与应用.pdf

摘要 多智能体技术是目前人工智能领域的研究热点，它对解决具有空间分布特点 的复杂问题有着独特的优势，是一种具有重要研究意义和应用价值的方法。生产 调度是控制与管理一体化的接合部，向上要给企业经营战略决策层提供决策依 据，向下要安排生产加工任务，指导监督控制层的运作。由于调度问题大多数都 是具有n p 难度的组合优化问题，寻找具有多项式复杂性的优化方法几乎是不可 能的。将多智能体技术和生产调度相结合，利用多智能体系统的分布求解特性， 将复杂任务分解成相对简单的单元模块，通过协商和合作共同完成任务，从而降 低单一调度系统设计的复杂性。 本文系统地阐述了多智能体理论及其在生产调度中的应用，通过多智能体技 术，把计划分配与任务调度有机的结合起来，实现整个系统的计算机集成。具体 研究工作包括以下几个方面： 首先，系统地分析了多智能体系统中智能体之间的通信以及多个智能体之间 的协作问题，为基于多智能体技术的调度系统的提出建立理论基础。 其次，对传统的车间调度系统进行了深入分析，在传统调度系统的基础上， 建立了一套基于多个智能体系统的车间调度系统模型，系统的智能化通过招标一 一投标过程来体现，系统的动态性、多且标优化性、全局最优化性，通过一套奖 罚制度和综合评价标准来具体实现，本文对其数学模型做出了详细介绍。奖罚制 度和综合评价标准，能够很好的满足现代制造系统的要求，很好的解决复杂车间 的调度问题，对于实现车间调度智能化起到了重要作用。 再次，在车间调度多智能体模型的基础上，提出了适合动态调度的多智能体 模型，并针对机器不确定和任务不确定这两种情况进行了研究。通过把蚁群算法 与强化学习相结合，提出了一种基于自适应a g e n t 的车问调度方法。当生产环境 发生变化时，蚂蚁会根据历史奖励和立即奖励情况进行决策，实现任务在机器资 源上的分配。 最后，将多智能体技术应用到芯片制造生产线动态调度上，给出了基于智能 体的动态调度模型，以及智能体决策中使用的调度算法。通过实例，给出了方法 的使用过程。 智能体作为一种思想，代表了现代人工智能的发展方向。随着计算机技术、 通信技术、自动化技术、制造技术和现代管理技术的提高，生产调度必将向着网 络化、智能化、规模化、实用化的方向发展。 关键词：多智能体，动态调度，强化学习，蚁群算法 a b s t r a c t m u l t i - a g e n ts y s t e m i so n eo ft h ei m p o r t a n tr e s e a r c hf i e l d so fa r t i f i c i a l i n t e l l i g e n c e i th a sp a r t i c u l a rp r e d o m i n a n c ef o rs o l v i n gc o m p l e xd i s t r i b u t e dp r o b l e m s ， w h i c hi sa ni m p o r t a n tm e t h o df u l lo fa p p l y i n gv a l u e p r o d u c t i o ns c h e d u l i n gi st h e j o i n to fc o n t r o la n dm a n a g e m e n t o nt h eo n eh a n d , i tw i l ls u p p l yd e c i s i o n sf o rt h e e n t e r p r i s e ；o nt h eo t h e rh a n d ，i tw i l la r r a n g ep r o d u c t i o nt a s k sa n ds u p e r v i s et h e c o n t r o ll a y e r b e c a u s et h em o s ts c h e d u l i n gp r o b l e mi sn ph a r d ，i ti si m p o s s i b l et of i n d o u tc o m m o na l g o r i t h mw i t hp o l y n o m i a lc o m p l e x i t y w ec o m b i n et h em u l t i a g e n t t e c h n i q u ea n dp r o d u c t i o ns c h e d u l i n ga n dd e c o m p o s ec o m p l e xt a s kt ou n i t sb yt h e d i s t r i b u t e dc h a r a c t e r i s t i co fm u l t i - a g e n ts y s t e m w er e d u c et h ec o m p l e x i t yo fs y s t e m d e s i g n i n gt h r o u g ha g e n t s c o o p e r a t i o n i nt h i st h e s i s ，t h em u l t i a g e n tt e c h n o l o g ya n di t sa p p l i c a t i o ni nt h ep r o d u c t i o n s c h e d u l i n gw e r ei n t r o d u c e d t h ep l a n sd i s t r i b u t i n ga n da s s i g n m e n t ss c h e d u l i n gw e r e i n t e g r a t e di n t ot h ew h o l es y s t e mb ym u l t i a g e n tt e c h n o l o g y t h em a i nr e s e a r c hw o r k i sd e s c r i b e da sf o l l o w i n g ： f i r s t l y ，w ed i s c u s st h eb a s i cc o n c e p t ，c h a r a c t e r i s t i ca n dc l a s s i f i c a t i o no fa na g e n t ； a n a l y z et h ec o m m u n i c a t i o na n dc o o p e r a t i o na m o n ga g e n t s i t w i l lp r e p a r ef o r s c h e d u l i n gs y s t e mb a s e do nm u l t i - a g e n ts y s t e m s e c o n d l y , w ea n a l y s e st h et r a d i t i o n a lj o b s h o ps c h e d u l i n gs y s t e md e e p l y , a n d c r e a t e sam o d e lo fj o b s h o ps c h e d u l i n gs y s t e mb a s e do nm u l t i a g e n ts y s t e m t h e i n t e l l i g e n tc h a r a c t e ri se m b o d i e db yi n v i t i n gt op u b l i cb i d d i n g ；t h ed y n a m i c , m u l t i a i m sa n dg l o b a lo p t i m i s mc h a r a c t e ri sr e a l i z e db yas e to fr e w a r d p u n i s hp r i n c i p l ea n d s y n t h e s i si n d e x ，o fw h i c hm a t h e m a t i c a lm o d e l i si n t r o d u c e di nt h e s i s t h e r e w a r d p u n i s hp r i n c i p l e a n ds y n t h e s i si n d e xc a nm e e tt h en e e d so fm o d e m m a n u f a c t u r es y s t e m ，s o l v et h ec o m p l e xj o b s h o ps c h e d u l i n gp r o b l e m sa n dr e a c to n t h ei n t e l l i g e n t i z a t i o no f j o b - s h o ps c h e d u l i n g ，w h i c hb a s e do nm u l t i - a g e n ts y s t e m t h i r d l y , w es u p p o s ead y n a m i cs c h e d u l i n gm o d e lb a s e do nw o r k s h o pm a s s c h e d u l i n gm o d e la n dm a k es i m u l a t i o n so fm a c h i n eu n c e r t a i n t ya n dt a s ku n c e r t a i n t y c o m b i n i n ga n tc o l o n ya l g o r i t h ma n dr e i n f o r c e m e n tl e a r n i n g ，a n e wj o b s h o p s c h e d u l i n ga l g o r i t h mb a s e do na na d a p t i v ea g e n tw a sp r o p o s e d w h e nt h ep r o d u c t i o n e n v i r o n m e n tc h a n g e d ，t h ea r t i f i c i a la n tc a nm a k ed e c i s i o nb yt h ep a s ta n dt h e i m m e d i a t ee n c o u r a g e m e n t t h e nt h ed i s t r i b u t i o no ft h ea s s i g n m e n t so nt h em a c h i n e s i l w a s c o m p l e t e d i nt h ee n d ，w ea p p l ym u l t i a g e n tt e c h n i q u et ot h ec h i pm a n u f a c t u r i n gp r o d u c t i o n d y n a m i cs c h e d u l i n g w ec r e a t eam o d e lo fd y n a m i cs c h e d u l i n gs y s t e mb a s e do n m u l t i - a g e n ts y s t e ma n ds c h e d u l i n ga r i t h m e t i ci nt h ep r o c e s so ft h ed e c i s i o no nt h e a g e n t s hg i v e st h ep r o c e s so ft h es c h e d u l i n ga r i t h m e t i cf r o mt h ee x a m p l e t h ea g e n ti sat h o u g h t ，r e p r e s e n t i n gt h ed e v e l o p m e n td i r e c t i o no ft h em o d e r n a r t i f i c i a l i n t e l l i g e n c e w i t h t h ei m p r o v e m e n to ft h ec a l c u l a t o r t e c h n i q u e ，t h e c o r r e s p o n d e n c et e c h n i q u e ，t h ea u t o m a t i o nt e c h n i q u e ，m a n u f a c t u r i n gt h et e c h n i q u e a n dm o d e mm a n a g e m e n t ，t h ep r o d u c t i o ns c h e d u l i n gw i l ld e v e l o pa l o n gt h en e t w o r k , i n t e l l i g e n c e ，r e g u l a r i z a t i o na n dp r a c t i c a l i t y k e yw o r d s ：m u l t i a g e n t ，d y n a m i cs c h e d u l i n g , r e i n f o r c e m e n tl e a r n i n g , a n tc o l o n y a l g o r i t h m 1 1 1 武汉理工大学硕士学位论文 1 1 研究背景及意义 第1 章绪论 调度的一般概念是在给定的时间内对系统内的有限资源进行合理安排，使之 以尽可能优良的性能完成预定的任务。对于生产系统而言，生产调度要根据系统 的生产目标和环境状态，在尽可能满足约束条件( 如交货期、工艺要求和路线、 资源现状) 的前提下，按照工艺规程和计划，通过下达生产计划及调度指令对系 统内的可用资源进行实时任务分配，以达到缩短产品的制造周期、减少在制品、 降低库存、提高生产资源的利用率以及提高制造系统生产率等目的。生产调度问 题的研究不仅具有重要的理论意义，而且具有重要的实际应用价值。在全球制造 的新形势下，生产调度研究面临着许多新问题，迫切需要有新的调度方法和调度 机制来解决。 生产调度问题一般可以描述为：针对某项可以分解的工作，在一定的约束条 件下，如何安排其组成部分所占用的资源、加工时间及先后顺序，以获得产品制 造时间或者成本等最优。 影响调度问题的因素很多，正常情况下有：产品的投产期，交货期( 完成期) ， 生产能力，加工顺序，加工设备和原料的可用性，批量大小，加工路径，成本限 制等，这些都是所谓的约束条件。有些约束条件是必须要满足的，如交货期，生 产能力等，而有些达到一定的满意度即可，如生产成本等。这些约束在进行调度 时可以作为确定性因素考虑。而对于设备故障，原料供应变化，生产任务变化等 非正常情况，都是事先不能预见的，在进行调度时大多作为不确定性因素考虑。 生产调度中涉及的工厂资源包括：原料、设备、人力、资金、能源等。资源 的详细分配受到产品的生产工艺的限制。 生产调度的性能指标可以是成本最低、库存费用最少、生产周期最短、生产 切换最少、设备利用率最高、三废最少等。实际生产调度的性能指标大致可以归 结为三类： ( 1 ) 最大能力指标：包括最大生产率、最短的生产周期等，它们都可以归结 为在固定或者无限的产品需求下，最大化生产能力以提高经济效益。在假定存在 连续固定需求的前提下，工厂通过库存满足产品的需求，调度问题的主要目标为 提高生产设备的利用率、缩短产品的生产周期，使工厂生产能力最大，这类生产 调度问题可以称为最大能力调度问题。 ( 2 ) 成本指标：包括最大利润、最小运行费用、最小投资、最大收益等。其 武汉理工大学硕士学位论文 中收益指产品销售收入，运行费用包括库存成本、生产成本和缺货损失。 ( 3 ) 客户满意度指标：包括最短的延迟、最小提前或者延期惩罚等。在传统 的调度中，一般以平均流通时间最小、制造周期最短、满足交货期为调度目标， 而在实际生产中，由于提前完成的产品必须保存到交货期，而延期产品必须交付 违约金，因此，在实际调度中经常考虑提i ； 或者延期惩罚。 调度问题的研究从二十世纪五十年代起就受到应用数学、运筹学、自动化和 人工智能等领域科学家的重视，科学家们利用运筹学中的线性规划、整数规划、 目标规划、动态规划及决策分析方法，研究并解决了一系列有代表意义的调度和 优化问题。 人们普遍把c o n w a y ，m a x w c u 和m i l l e r 三人有关调度的研究工作作为调度 理论研究的正式开始，他们3 人也被人们称为调度理论的奠基人。按照他们的定 义，所谓调度是指“如何分配一系列资源去完成一系列任务”。在生产系统中， 调度被定义为“如何分配一系列机器，使它们在一定的时间内完成一系列的任务 订单”于是，生产调度表现为一个排序问题。为区别起见，他们把工件在一台 机器上的排产定义为“排序”，而将对于多个不同机器上工件的排序问题命名为 “调度”。调度的结果是调度时序表。它是一个“任务一时间”表，是一个“关 于每一个项目以及为完成这些项目所采取的必须操作的执行序列随时间分配的 计划”。这样，生产调度问题被描述为一个“在一定的初始条件和约束条件下寻 求使某一性能指标最优”的数学问题，即一个最优化计算或最优控制问题。研究 证明，这是一类难以解决的n p 完全问题。 然而，传统的调度技术和模型无论所使用具体的计算技术是属于数学优化方 法的、还是运筹学的、抑或是人工智能方法，调度的研究工作始终是从应用数学 的分析与研究角度展开的。由于这种调度模型和概念是对实际生产调度问题的抽 象，在实际制造系统开放的、动态的环境下，生产调度问题呈现极强的动态性， 例如机器的损坏、加工计划的改变以及紧急订单的处理等，这就使得传统的调度 技术和模型很难直接运用于解决实际的生产调度问题。 2 0 世纪7 0 年代后期，经典调度理论取得了重要进展，并且作为一门应用数 学学科已经基本成熟，但是实际调度问题与经典调度问题还有相当的距离。严重 阻碍经典调度理论研究取得重大进展和突破的关键还是调度问题的n p 性质，实 际调度问题往往都是非常复杂的，没有确定的物理和自然规律可循，因此是非常 难解的，并且大多是没有精确解的。从2 0 世纪8 0 年代初开始，人们就一直在尝 试并致力于解决实际调度问题，调度研究由理论研究转向应用研究阶段。在这样 的历史背景下，应用人工智能、计算智能和实时智能研究成果，解决实际调度问 题的智能调度方法就走上了历史的舞台。 武汉理工大学硕士学位论文 由于智能体( a g e n t ) 具有较高的智能性、灵活性和良好的合作能力，为系 统各组成实体提供了并发与合作的平台，因此多智能体系统( m u l t i a g e n ts y s t e m m a s ) 在许多复杂系统管理与控制的应用研究和实践中得到了成功的发展。计 算机网络尤其是i n t e m e t 的广泛应用，不仅可以为制造企业建立有效的通讯机制， 实现资源重用与共享，更重要的是创造了具有分布和异构特征的协同工作环境。 基于多智能体的调度方法既融合了多种现代的理论和技术成果，如先进制 造、分布式人工智能、计算机技术等，又能够适应当前制造系统对于柔性、敏捷 性和重构能力的需要。以分布式动态智能调度方法和分布式控制结构为重要支撑 技术的，由多个动态合作的智能自治的制造实体组成的分布式制造系统能够解决 传统制造系统结构过于单一、对环境缺乏适应性等问题，并且会成为未来制造系 统的发展方向。随着分布式人工智能特别是多智能体系统技术研究的不断深入和 在制造系统中的逐渐应用，人们认识到智能体技术可以为实现分布式制造系统提 供方法和工具。 1 2 生产调度问题的研究现状 在经典调度理论中，调度问题仅仅被看作组合优化问题，致使其在实际生产 中的应用受到了较大的局限。2 0 世纪8 0 年代，人工智能的蓬勃发展为生产调度 注入了新鲜的血液，进化算法、禁忌搜索算法、人工神经网络、模拟退火算法等 得到了广泛的研究，并取得了丰硕的成果，应该说，这方面的经典调度理论己经 比较成熟了，但是在实际应用中的效果并不理想，其原因可以归纳为模型过于简 化、方法过于单一、适用范围狭窄等。分布式人工智能的发展促使生产调度系统 从传统的集中式转向分布式，其中m a s 技术在调度研究领域的应用研究中日益 活跃起来，并且开始成为一个重要的研究方向。在调度系统中应用多智能体技术， 主要是针对不确定的和不断变化的制造系统环境下比较复杂的调度问题，尤其是 那些短期的、敏捷性要求较高的动态调度。相对于传统的调度方法和系统，智能 体具有较好的分布性、实时性、健壮性和适应性。 近年来，随着对分布式人工智能和先进制造系统的进一步研究，表明拥有较 高的智能性、灵活性和良好的合作能力的智能体之间彼此协作的分布式制造系统 可以快速地响应环境变化。多智能体放松了对集中式、规划和顺序控制的限制， 提供了分散控制、应急和并行处理，提供更快速的问题求解。这样，制造系统便 可以通过分布在车间里的资源和个体智能体之间的联合来实现系统的集成。近些 年来，各国纷纷将智能体理论和多智能体技术应用于制造车间调度问题的研究 上，已经取得了一定的研究成果，建立了各种各样基于智能体的调度原型或仿真 系统。 3 武汉理工大学硕士学位论文 国外的研究机构已展开了对基于智能体调度系统的研究，日本、美国，和欧 洲在分布式人工智能及其应用研究处于世界前列。h a d a v i 提出的分布式实时调 度的多智能体系统结构；b a k e 研究了包括调度在内的工厂控制算法在分布分层 结构的多智能体制造环境中的实施问题：s h a w 提出用智能体方法进行制造调度 和控制，指出制造单元可以通过投标机制，将作业以子合同的形式转包给其它制 造单元；c h e n 采用智能体技术进行制造调度与供应链协调研究；b u t l e r 提出了 用于分布式动态调度的多智能体体系结构，将调度分为两个层次，第一层通过智 能体的协商机制，以一种分布式的方法制造单元分配给作业，第二层对共享制造 资源进行动态分配；这些系统都引入了a g e n t 概念对制造车间生产过程加以分 析，但并没有一个切实可行的基于多a g e n t 的调度原型系统。 n o r r i e 列举了近3 0 个国际上已经开展或正在进行的运用a g e n t 技术进行制 造规划、调度及控制的研究项目。从这些研究项目可以看出，运用a g e n t 技术进 行制造规划与调度等问题的研究，其常见的做法是用a g e n t 来表示制造中的各种 物理资源或逻辑资源，如机床、物料运输设备、机器人、订单、b o m 等，并根 据制造过程的组织形式，通过网络及a g e n t 通讯协议将它们连接成一个多a g e n t 系统，然后，采用多a g e n t 系统理论和方法对a g e n t 的协作、协商、调度、控制、 冲突消解、智能显现等行为进行研究。 在1 9 9 4 年的一项国际合作研究项目“智能制造系统研究计划”提出的六个 研究方向当中，合弄制造系统是比较有影响的一种思想，它偏重于利用人工智能 技术研究新的未来灵活制造模式，具有合作性、自治性和智能性。在具体实现方 式上与分布式人工智能中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 m s 调度原型系统，实现 了制造单元的柔性智能化与基于网络的制造系统柔性智能化集成。此外，沈阳自 动化所在多智能控制器研究与设计中，把a g e n t 及多a g e n t 模式应用于多机械手、 多机器人的协调与协作设计中，开发了基于多a g e n t 的多机器人协调调度系统， 已取得了阶段性成果。我国“八五”期间也有一些高校和研究机构如清华大学、 上海交通大学、西安交通大学、北京机械工业自动化研究所等进行此类问题的研 究，并己开发出相应的计算机宿主生产调度与管理系统，逐步从理论研究阶段走 向应用阶段。这表明国内越来越多的研究人员开始进驻a g e n t 技术和应用制造系 4 武汉理- 大学硕士学位论文 统调度问题的研究。 回顾以往的研究历程，我们发现在早期的研究中，生产调度往往被抽象描述 为一个有性能指标、有约束条件、寻一求最优解的数学问题。但由于其实质上是 一个n p 难题，即随着问题规模增大，寻求最优解的计算量呈指数增长，使得一 些常规得优化方法难以奏效。因此，激发了很多研究者致力于“优化调度”的研 究，试图解决调度算法的求解速度和求解质量等问题。 随着研究的深入和制造系统的发展，特别是柔性制造系统、计算机集成制造 系统的应用，实际生产系统的复杂性和动态性增加，促使人们进一步研究能够处 理生产环境的不确定性和意外时问的生产调度技术，使得调度目标变成“柔性调 度”。 近年来，随着全球市场的形成，造成市场竞争加剧，加之社会的进步和科学 技术的飞速发展，要求调度系统应具有快速适应变化和技术更新的速度，并能适 应制造企业快速重组、动态联盟的需要，因此，当前的调度目标逐渐转变成“敏 捷调度”。 可见，面对现代制造的复杂要求，如果依然遵循传统的调度研究方法和思路， 单纯通过研究某些算法的改进和扩展等努力来解决，是达不到预期的效果的，需 要从系统的角度出发，采用新的思路研究理想的调度系统模型、合理的调度系统 结构以及能够集成经典的调度方法的先进调度策略和方法。这是生产调度系统适 应未来制造需要的必然发展趋势，也是制造控制理论和技术发展的必然趋势。 1 3 本文的研究目的、研究内容和章节安排 1 3 1 研究目的 针对传统的调度系统不能满足复杂的、动态的实际工作环境的现状以及当今 对制造系统的快速反应性的需求，对基于多智能体的生产调度理论进行了研究。 企业接收订单后如何进行计划的分解、分配以及如何充分利用企业内部资源进行 合理的调度等都是本文要涉及的问题。 企业从订单的录入到最终产品的产出是一个极其复杂的过程，如果单纯地用 应用数学的方法来建模实现资源的优化，其求解过程是属于一个n p 问题。故我 们用多智能体技术来模拟我们人类的思维和协作机制，以实现资源的优化调度， 最终实现生产的自动化和企业效益的最大化。 1 3 2 研究内容 本文是基于多智能体技术的生产调度问题研究，利用多智能体的自治性和协 作关系来实现企业资源的优化调度，根据计划实现最终的优化目标。具体来说， 5 武汉理_ e 大学硕士学位论文 主要包括以下几个方面： ( 1 ) 多智能体在车间调度中的应用。建立了基于多智能体的车间调度系统模 型和车间调度系统模型中的招标投标模型。 ( 2 ) 对蚁群算法进行研究，利用蚁群算法的并行性和鲁棒性来实现车间的优 化调度。同时，在蚊群算法研究的基础上，把蚊群算法与强化学习相结合，建立 了基于自适应智能体的强化学习模型，实现车问的在线学习和调度 ( 3 ) 基于智能体的芯片制造生产线动态调度方法研究。建立了基于智能体的 动态调度模型，然后给出了工件智能体与设备智能体间协商使用的协商协议，以 及智能体决策中使用的调度算法。 1 3 3 章节安排 本文的章节安排为： 第1 章绪论。本章首先阐述了本文的研究背景及意义，进而分析了生产调 度问题的研究现状，最后引出了本文的研究目标与研究内容，并给出本文的章节 安排 第2 章智能体与多智能体系统。本章首先介绍了智能体理论，接下来介绍 了多智能体系统的体系结构和多智能体间的交互与合作，最后介绍了多智能调度 系统，引进了实体型智能体。 第3 章基于多智能体的车闯调度方法研究。本章首先引入了车间调度问题 模型，在此基础上，提出了基于多智能体的车间调度系统模型，建立了基于多智 能体技术车间调度问题的招标投标调度模型。接着分析了基于多智能体的作 业车间动态调度方法研究，提出了适合动态调度的多智能体模型，并针对机器不 确定和工件集不确定这两种情况进行了分别介绍。 第4 章基于自适应智能体的车间实时调度方法研究。本章通过把蚁群算法 与强化学习相结合，建立了自适应a g e n t 的车间调度模型实现在线学习。 第5 章基于智能体的芯片制造生产线动态调度方法研究。本章首先给出了 基于智能体的动态调度模型，然后给出了工件智能体与设备智能体之间协商使用 的协商协议，以及智能体决策中使用的调度算法，最后通过实例，给出了方法的 使用过程。 第g 章总结与展望。本章对本文的研究工作进行了总结，并对进一步的研 究作了展望。 武汉理工大学硕士学位论文 第2 章智能体与多智能体系统 2 1 智能体理论 2 1 1 智能体的定义及特点 智能体( a g e n t ) 概念来自于分布式人工智能领域，它是分布式人工智能的 一个基本术语，是人工智能的一个原语。a g e n t 在计算机领域的研究和应用起源 于2 0 世纪7 0 年代美国麻省理工学院研究人员开展的一系列关于分布式人工智能 的研究。由于a g e n t 的研究还没有完全成熟，因此学术界并没有统一的定义。 在a g e n t 的众多定义中，比较通用的是w o o l d r i d g e 和j e n n i n g s 在1 9 9 5 年提 出的定义：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 所有可能具有的特点： ( 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 也能够主动地进行基于自身目标和信念的活动，以改变周围环境。 ( 4 ) 推理性：软件a g e n t 可根据己有的知识和经验，以理性、可再生的方式 进行推理。软件a g e n t 的智能由三个主要部件来完成，即内部知识库、自适应能 力以及基于知识库的推理能力。 ( 5 ) 学习和适应能力：主体可以根据过去的经验积累知识，也可以修改其行 为以适应新的环境。 ( 6 ) 规划能力：根据目标、环境等的要求，a g e n t 应该至少对自己的短期行 为做出规划。虽然程序设计人员可以提供一些常见情况的处理策略，但这些策略 武汉理工大学硕士学位论文 不可能覆盖a g e n t 将遇到的所有情况。所以，a g e n t 需要具有生成规划的能力。 ( 7 ) 时问连续性；传统程序在用户需要时激活，不需要时或者运算结束后停 止，a g e n t 与之不同，它应该至少在“相当长”的时间内连续运行。 2 1 2 智能体的结构分类 主体结构需要解决的问题是主体由哪些模块组成，他们之闻如何交互信息， 主体感知到的信息如何影响它的行为和内部状态，以及如何将这些模块用软件或 硬件的方式组合起来形成一个有机的整体，主体可以看成一个黑箱，通过传感器 感知环境，通过效应器作用环境。 a g e n t 的分类方法很多，根据协作方式，智能体可以分为协作智能体和非协 作智能体，根据控制方式可以分为中央控制和分布控制。 a g e n t 系统是个高度开放的智能系统，其结构如何将直接影响到系统的智能 和性能。人工智能的任务就是设计a g e n t 程序，即实现a g e n t 从感知到动作的映 射函数。 这种智能体程序需要在某种称为结构的计算设备上运行。这种结构可以是一 台普通的计算机，或者可能包含执行某种任务的特定硬件，还可能包括在计算机 和智能体程序间提供某种程度隔离的软件，以便在更高层次上进行编程，一般意 义上，体系结构使得传感器的感知对程序可用，运行程序并把该程序的作用选择 反馈给执行器。可见，智能体，体系结构和程序之间具有如下关系： 智能体= 体系结构+ 程序 根据问题求解能力来分类主体，可以分为以下三种结构： ( 1 ) 慎思主体 慎思主体也称作认知主体，是一个显式的符号模型，包括环境和智能行为的 逻辑推理能力它保持了经典人工智能的传统，是一种基于知识的系统。环境模 型一般是预先实现的，形成主要部件知识库。采用这种结构的主体要面对以下两 个基本问题： 转换问题：如何在一定的时间内将现实世界翻译成一个准确的、合适的 符号描述： 表示推理问题：如何用符号表示复杂的现实世界中的实体和过程，以及 如何让主体在一定的时间内根据这些信息进行推理做出决策。 慎思主体是具有内部状态的主动软件，它与具体的领域知识不同，具有知识 表示、问题求解表示、环境表示、具体通信协议等。根据主体思维方式的不同， 慎思主体可以分为抽象思维主体、形象思维主体。抽象思维主体是基于抽象概念 的，通过符号信息处理进行思维。形象思维主体是通过形象材料进行整体直觉思 维，与神经机制的连接论相适应，慎思主体结构如图2 - 1 所示。 武汉理工大学硕士学位论文 。_ 。- 。 智能体 ： 图2 - 1 慎思主体结构 ( 2 ) 反应主体 反应智能体只能简单地对外部刺激产生响应，没有任何内部状态。每个智能 体既是客户又是服务器，根据程序提出请求或做出回应在这种类型的主体中，没 有世界模型和规划，仅有一些简单的行为模式，这些行为模式以“刺激响应” 方式对环境的变化做出反应，反应主体结构如图2 2 。 反应主体的奇特之处不在于它的体系结构，而在于它能以一种简单的方式与 其他主体交互，通过这种交互能呈现出全局复杂的活动模式，从而解决人型复杂 的问题。 己有的试验表明：在现实世界中，反应主体在执行某些任务时优于传统方法。 然而，反应主体的问题求解方式不十分通用，特别是无法处理某些需要通过推理 或从记忆中获得知识，而不能通过感知得到知识的任务。而且，反应主体适应能 力一般比较差，常常没有任何学习能力 图2 2 反应主体结构 ( 3 ) 混合结构 前面我们讨论了主体的慎思结构和反应结构，它们反应了传统人工智能和基 9 武汉理工大学硕士学位论文 于行为的人工智能的特点。无论是纯粹的慎思结构还是纯粹的反应结构都不是构 造主体的最佳方式。人们提出混合结构的主体系统，试图以此来融合经典和非经 典的人工智能。 最显然的方式就是在一个主体中包含两个( 或多个) 子系统：一个是慎思予系 统，含有用符号标号表示的世界模型，并用主流人工智能中提出的方法生成规划 和决策；另一个是反应子系统，用来不经过复杂的推理就对环境中出现的事件进 行反应。通常，反应子系统的优先级比慎思子系统高，以便它对环境中出现的重 要事件进行快速的反应，混合主体结构如图2 3 。 凡生活在一个现实和虚拟世界中的主体，会遇到各种不同的情况。主体除了 要对紧急情况做出反应，还要规划中短期行为。混合型结构综合了前两种结构的 优点在实际中最常用。 卜般 图2 - 3 混合主体结构 大多数主体不仅要与环境交互作用，更主要的是处理和解释接收的信息，达 到自己的目的。图2 - 4 给出了智能主体的工作过程。主体接收到的信息首先要以 适当的方式进行融合，并能为主体知识库所接受。一旦主体接收外部信息，信息 处理过程成为主体的核心，因为它反映主体的真正功能。信息处理的目的是解释 可用的数据，形成具体规划。因为每个主体都有具体的目标，内部目标的影响必 须作为影响的部分考虑。如果影响弄清楚了就要采取行动，使之到达或接近目标。 形成规划时主体可以规定知识，包括对新情况反映的具体处理步骤。但是，这不 是本质的东西，因为主体执行可以不要规划。当要求对环境对象交互时，动作模 块将使用合适的交互模块。控制执行也是动作模块的任务。 1 0 武汉理工大学硕士学位论文 图2 4 智能主体的工作过程 2 1 3 智能体的模型 图2 5 是一个智能体的基本模型，可分为对外协作单元、知识库和问题求解 单元3 个主要部分。对外协作单元负责与其它a g e n t 和外部环境的交互与协同， 获取任务，并根据任务的复杂程度和自身的资源、状态和能力寻求协调与合作， 同时也向其它a g e n t 提供所需要的力所能及的服务，实现资源、知识、信息和功 能的共享；知识库包含了一个a g e n t 为完成其任务所必需的知识和数据，主要包 括领域知识和数据、协作知识和数据以及行为模型等；问题求解单元则根据所获 得的任务，根据自身资源、状态及行为，其它a g e n t 及环境信息，所代理实体的 状态，利用知识库所提供的相关知识和必要的数据，进行局部任务规划、推理和 决策，产生相应控制信息和数据，控制自身和实体的操作与进行，并监视自己和 实体的运行状态。 图2 5 中各模块功能如下： ( 1 ) 网络接1 ：3 ：完成网络数据格式和a g e n t 内部数据格式间的相互转化和传 输，以及网络信息的接收和发送。 ( 2 ) 通信管理模块：负责网络通信事务的管理，包括数据报文的生成，网络 信息的识别、解释和处理工作。 ( 3 ) 协作管理模块：根据所获网络信息决定任务的接收与否。如接受任务， 则将其放入任务池中；如不接受，那么就根据协作知识库中的知识和数据进行推 理，查找得到可能完成或能与之合作完成该任务的a g e n t ，并通过通讯管理模块 向这些a g e n t 发送消息，以将该任务迁移给它们或合作完成。 爿 交互 k 、 ( 信息融合： i 、 ( 信息处理： ， _ f i 交互 武汉理工大学硕士学位论文 ( 4 ) 协议：为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 的协议一起构成多智能体系统的协 调机制。 ( 5 ) 实体接口：是a g e n t 与其所代理的实体间控制和数据信息相互交换、传 输的桥梁。 ( 6 ) 状态监视模块：一方面，跟踪、记录a g e n t 行为活动情况，以供自身任 务规划、推理、决策、控制、执行和学习所用，也备其它a g e n t 查询；另一方面， 监视该a g e n t 所代理实体的当前运行状态，并将结果报告给规划模块作为任务规 划的重要依据，同时也报告给协作管理模块作为接受任务的参考数据。 控制执行模块：将决策结果转换成控制信息，产生相应的数据，一方面 控制自己的行为活动，另一方面通过实体接口控制实体的运行。 ( 8 ) 任务池和能力登记器：任务池容纳协作管理模块接受来的任务；能力登 记器记录该a g e n t 自身和它所代理实体的属性和功能，为人机交互和其它a g e n t 了解其情况提供依据。 ( 9 ) 规划、推理和决策模块：根据当前实体运行状态、对外部环境的判断以 及自身当前的行为、状态、资源、知识和能力，为完成全局总目标，利用任务规 划模型、行为模型、相关知识和数据，进行规划、推理和决策，决定任务的执行 过程和其它行为活动，实现问题求解。如果由于自身的资源或能力不及，或者实 体出现故障时，可以通过谈判与协商由协作管理模块将任务迁移给其它a g e n t ， 或者寻求其他有能力的a g e n t 合作完成。任务迁移和合作使得各a g e n t 合理分担 负载，系统资源得以充分利用，保证任务及时顺利完成，提高系统的吞吐量、并 行度和可靠性。 ( 1 0 ) 学习模块：根据实体和a g e n t 的自身状态、行为和外部环境信息及其 它a g e n t 的状态、行为，通过执行学习算法，或者向其它a g e n t 学习，实时动态 地调整、修改、补充和完善知识库中的领域知识和数据、协作知识和数据以及行 为模型等。 武汉理工大学硕士学位论文 2 2 多智能体系统 图2 5 智能体的基本模型 通信网络 多智能体系统( m u l t i - a g e n ts y s t e m ，m a s ) 指的是一些自主的a g e n t 通过协作 共同完成某些任务的计算系统；它可以将耦合度较深的问题解耦成简单的任务， 使系统便于升级和控制；可以接受动态和不确定的知识，具有一定的智能性、适 应性；十分适合分布式架构。采用多个a g e n t 进行协作，可以通过任务分解和任 务协调来提高整个系统的性能，也可以克服单个a g e n t 知识不完全、处理的信息 不确定等缺点。对于m a s 的需求主要源于分布计算的复杂性。目前m a s 技术 己经在广泛的领域内得到了应用，特别是开放系统和复杂系统，以解决一些其它 技术不能解决或不容易解决的问题。 系统中的a g e n t 需要按照一定的结构组织起来，以相互通信和协作，这就需 要为m a s 选择合适的体系结构。体系结构是任何控制系统的骨架，通过对现有 文献的分析可以得出，m a s 的体系结构主要分为以下几种