（系统工程专业论文）GDSS中多Agent任务分解和调度算法研究.pdf

东南大学硕士学位论文 y 5 6 1 1 2 摘要 g d s s 中多a g e n t 任务分解和调度算法研究 摘要 随着社会和经济的迅猛发展，个人决策支持系统( p e r s o n a ld e c i s i o ns u p p o r t s y s t e m ，p d s s ) 已明显无法满足人们对于关系到长远发展重大问题的决策需要， 尤其是在较大型的企业组织中，各种决策特别是高层战略决策对公司的发展 产生重大影响，设计和构建一种新决策支持系统一群决策支持系统己成当务之 需。近几年来，随着群决策支持系统的支撑技术一计算机支持协同工作( c o m p u t e r s u p p o r t e dc o o p e r a t i v ew o r k ，c s c w ) 和a g e n t 技术的日趋成熟，群决策支持系 统( g r o u p d e c i s i o ns u p p o r ts y s t e m ，g d s s ) 也初见端倪。本文主要研究a g e n t 技 术在g d s s 中的应用。重点研究了如下内容： 1 、对a g e n t 技术整体作简要介绍。其中包括单体a g e n t 和多a g e n t 系统 ( m u l t i a g e n t ss y s t e m s ，m a s ) 技术以及近年来a g e n t 技术方面的相关研究。在 单体a g e n t 中，主要从a g e n t 的定义、特征、结构、形式化表达等方面加以介绍， 而对于m a s 则从定义、结构模式等方面加以阐述。在阐述m a s 结构模式时， 从三种结构视图来说明。 2 、对g d s s 体系结构进行设计。在决策支持系统( d e c i s i o ns u p p o r ts y s t e m ， d s s ) 及智能决策支持系统的基础之上，没有对g d s s 整体进行设计，而是对支 持其群体通讯的c s c w 通讯平台和群体任务处理的任务系统加以设计，并在此 过程中辅以图、程序等进行说明。在对c s c w 通讯平台进行设计时，主要从框 架、结构、详细设计等角度来论述，而对任务处理系统，则主要从任务处理流程 式、设计思路、详细设计等方面来阐述。 3 、本文就任务系统设计中一些关键性技术作深入的探讨。其中包括用户任 务形式化、任务分解、任务调度和子任务执行结果集成等一系列算法。在任务调 度算法中，又依据实际的应用，提出了两个任务调度算法，即实时任务集中式调 度算法和实时任务分布式调度算法。 虽然本文的研究还有一些不足之处，但可以肯定的是，将c s c w 群体协同 工作的思想和a g e n t 技术纳入到d s s 中，这种独特的研究方法对g d s s 的建立 和发展具有重要的理论意义和指导价值。而文中一些重要算法对分布式任务处理 系统特别是分布式实时任务处理系统具有重要意义。 关键词：群决策支持系统；计算机支持协同工作：多a g e n t 系统；任务分解；任 务调度 东南大学硕士学位论文 a b s t r a c t r e s e a r c ho n a l g o r i t h m so f t a s k d e c o m p o s i t i o n a n dt a s k d i s p a t c hi ng d s s a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to f s o c i e t ya n de c o n o m v p e r s o n a ld e c i s i o ns u p p o r t s y s t e m c a l l t s a r i s f yp e o p l e s n e e di n l o n gt e r ma n d v i t a ld e c i s i o n s a n yl o n g e r , e s p e c i a l l yi ns o m el a r g es c a l eo r g a n i z a t i o n sa n de n t e r p r i s e si nw h i c ha 1 1 k i n d so f d e c i s i o n s - - e s p e c i a l l ys t r a t e g i cd e c i s i o n sm a d eb yh i g hl e v e lo fe n t e r p r i s e sh a v ea n v i t a li m p a c to nt h ed e v e l o p m e n to f e n t e r p r i s e s ，t h a td e s i g na n dc o n s t r u c t i n go f an e w t y p eo f d e c i s i o ns u p p o r ts y s t e m s s ) - - g r o u pd e c i s i o ns u p p o r ts y s t e m ( g d s s ) i s s t a r i n g t h e i r f a c e s h o w e v e r , m a t u r i t yb ys t e p s i nt h et e c h n o l o g yo fc o m p u t e r s u p p o r t e dc o o p e r a t i v ew o r k ( c s c w ) a n da g e n tf u n d a m e n t a lt og d s sg i v e sac l u e t os u c han e w t y p es y s t e m o n t h ep o i n to f a p p l i c a t i o no fa g e n tt e c h n o l o g yi ng d s s ， r e s e a r c hw o r ki nt h et h e s i sf o c u so n ： 1 i n t r o d u c e st h et e c h n o l o g yo f a g e n t a saw h o l e b r i e f l y , i n c l u d i n gs i n g l ea g e n t d e s c r i b e df r o m d e f i n i t i o n ，c h a r a c t e r i s t i e s ，s t r u c t u r e ，f o r m a l i z a t i o ne x p r e s s i o n , m u l t i a g e n t ss y s t e m si l l u s t r a t e df r o md e f i n i t i o n , p a t t e r n so fs t r u c t u r e ，a n dr e s e a r c h e s i nt h et e c h n o l o g y o f a g e n t i nr e c e n ty e a r s 2 d e s i g n sp a r t so f s y s t e ms t r u c t u r eo f g d s s w i t hd i a g r a m sa n d p r o g r a m s b a s e d o nd s sa n d i n t e l l i g e n t d e c i s i o n s u p p o r ts y s t e m ( r o s s ) ，i n c l u d i n g ：c s c w c o m m u n i c a t i o np l a t f o r mi s s u e di nf r a m e w o r k 。s t r u c t u r ea n d p a r t i c u l a rd e s i g n t a s k p r o c e s s i n gs y s t e ma r g u e d i n t a s k - p r o c e s s i n gp r o c e d u r e ，c l u e o fd e s i g na n d p a r t i c u l a rd e s i g n 3 p r o b e ss o m ek e yt e c h n o l o g yc o n c e r n e dt a s k p r o c e s s i n gs y s t e mi nas e r i e so f a l g o r i t h m si n c l u d i n g ：u s e r t a s kf o r m u l a t i o n a l g o r i t h m ，t a s kd e c o m p o s i t i o n a l g o r i t h ma n dt a s kd i s p a t c ha l g o r i t h mw h i c hi n v o l v e sr e a l t i m e c e n t r a lt a s k d i s p a t c ha l g o r i t h ma n dr e a l t i m ed i s t r i b u t e dt a s kd i s p a t c ha l g o r i t h m n o t w i t h s t a n d i n g af e wf a u l t si nt h et h e s i s i ti sc e r t a i nt h a tt h ep e c u l i a r m e t h o d o l o g yo f r e s e a r c hi nd s s a b s o r b i n gt h et h o u g h to fg r o u pc o o p e r a t i v ew o r ko f c s c wa n dt h et e c h n o l o g yo fa g e n tg i v e sag o o dr e f e r e n c et oa n dh a si m p o r t a n t a p p l i c a t i o nv a l u ei nc o n s t r u c t i n ga n dd e v e l o p i n gs u c han e wt y p ed s sa l s o ，s o m e k e ya l g o r i t h m sh a v ei m p o r t a n tr e s e a r c hv a l u ei nd i s t r i b u t e dt a s k - p r o c e s s i n gs y s t e m 、 e s p e c i a l l yi nd i s t r i b u t e dr e a l t i m et a s k p r o c e s s i n gs y s t e m k e yw o r d s ：g d s s ；c s c w ；m u l t i a g e n t ss y s t e m ；t a s kd e c o m p o s i t i o n ；t a s k d i s p a t c h 2 东南大学硕士学位论文第一章 第一章绪论 “管理就是决策”1 1 。随着计算机和决策科学等学科的发展，支持信息化决 策的辅助系统一决策支持系统( d e c i s i o ns u p p o r ts y s t e m ，d s s ) 应运而生。7 0 年代，在人工智能的研究中，各种新的知识表示方法的提出以及智能体概念上的 突破为d s s 进一步发展成为智能决策支持系统 2 石1 ( i n t e l l i g e n td e c i s i o ns u p p o r t s y s t e m ，i d s s ) 提供了可能。现代科技的迅猛发展，这些个人决策支持系统 ( p e r s o n a ld e c i s i o ns u p p o f ts y s t e m ，p d s s ) 己明显无法满足人们对于关系到长 远发展重大问题的决策需要，尤其是在生产规模较大的企业组织中，各种决策一 特别是高层战略决策对公司的盛衰成败产生重大影响，设计和构建一个群决策支 持系统己成为当务之需。计算机支持协同工作7 。2 1 ( c o m p u t e rs u p p o s e d c o o p e r a t i v ew o r k ，c s c w ) 作为研究计算机支持群体协同工作一门学科而出现， 为群决策方案解决提供了结构框架，而在8 0 年代中后期兴起的a g e n t 技术 1 3 - 1 9 1 又为c s c w 整个框架的搭建奠定了智能技术基础【2 “。这样，一个基于a g e n t 技 术典型的c s c w 一群决策支持系统( g r o u pd e c i s i o ns u p p o gs y s t e m ，g d s s ) 1 7 也就呼之欲出。 1 1 本文研究的背景和意义 学科的发展无不过在两个方面的突破，一是学科纵深领域的重大发现，二是 学科之间相互交叉形成新的学科，a g e n t 技术与d s s 相结合则属于后者。作为 c s c w 研究的一个重要分支，g d s s 的产生有重要的理论和应用意义： 1 、决策支持系统为a g e n t 技术找到了新的应用点。a g e n t 技术已经被成功 地应用在智能诊断 2 1 - 2 2 1 、机器人工程1 2 3 - 2 5 】、专家系统【2 6 1 和网络管理等多个学科 之中，而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 是一种 在分布式系统或协作系统中能持续自主地发挥作用的计算实体；本身具有一定的 专业知识，并通过感应外部环境的变化，作出智能反应。a g e n t 技术纳入到决策 支持系统时，用户只需向代表用户的a g e n t 提交任务，最后系统将向用户显示结 东南大学硕士学位论文 第一章 果。这一过程，用户不涉及任务的分解和调度，不涉及用户之间的信息交互，不 涉及知识库系统与任务系统的协作，这全赖a g e n t 使系统变得如此智能化。 3 、任务系统及相关算法是分布式处理系统的重要组成部分。随着网络技术 的发展，分布处理技术越来越受到重视。g d s s 作为- 种分布式的信息处理系统， 在设计中使用的任务系统以及相关算法，对于构建分布任务处理系统具有很强的 指导意义，特别是其中的实时任务调度算法对于构建分布式实时任务系统有重要 的应用价值。 总之，g d s s 作为一种的新型决策支持系统，是融决策技术、c s c w 技术、 计算机技术和人工智能技术于一体而形成的产物，它将c s c w 群体协同工作的 思想、人工智能中的知识工程和a g e n t 技术纳入到d s s 中，以其独特的研究方 法和广泛的发展前景，使之一出现就成为决策支持系统研究的热点和主要的发展 方向，正引起国内外学术界和企业界的极大关注。 1 2 本文研究的主要内容 群决策支持系统是“可使决策者以群体的工作方式解决半结构化和非结构化 的、复杂决策问题的计算机系统”。它纳入了人工智能、通信、计算机和决策等 技术，支持大型复杂性、半结构或非结构化问题的求解：支持群体的所有活动， 其中包括接收和分析信息、作决策、处理和测试假设、群体交流等。在研究中发 现，一些决策问题很复杂，复杂到单个的决策者无法了解它的全部，2 0 世纪8 0 年代由t h o m a s 和b u r n s 等人提出了分布式决策的概念。分布式决策摆脱了集中 式决策模型中结果收敛速度慢等问题，但也产生一些新问题，如任务分解、调度、 子任务执行结果汇总。本文正是采用分布式决策的思路来设计g d s s ，并阐明其 中涉及的一系列诸如任务分解、调度等技术问题。 为了便于后面g d s s 系统设计的说明，本文首先对a g e n t 技术作简要介绍， 其中包括单体a g e n t 和多a g e n t 系统( m u l t i a g e n t ss y s t e m s ，m a s ) 技术及相关 研究简介。在单体a g e n t 中，主要从a g e n t 的定义、特征、结构、形式化表达等 方面加以介绍；对于m a s 则从定义、结构模式等方面加以阐述。在阐述m a s 结构模式时，从三种结构视图来说明。 。 接着，本文推出群决策支持系统设计，主要包括c s c w 通讯平台和任务系 东南大学硕士学位论文第一章 统两个方面的设计，在设计过程中辅以图、程序等进行说明。在对c s c w 通讯 平台进行设计时，从框架、结构、详细设计等角度来论述，而对任务处理系统， 则主要从任务处理流程式、设计思路、详细设计等方面来阐述。 随后，本文就任务系统设计中一些关键性技术作深入的探讨，其中有用户任 务形式化、任务分解、任务调度和子任务执行结果集成等一些列算法。在任务调 度算法中，又依据实际的应用，提出了两个任务调度算法，即实时任务集中式调 度算法和实时任务分布式调度算法。这些算法的提出对于构建一个任务处理系统 具有重要的意义。 最后，对全文作总结，并指出与本文研究相关而且仍需继续研究意义的几个 方面。 东南大学硕士学位论文第二章 第二章a g e n t 技术简介 现在一般面向对象系统中，对象的行为是基于单处理器和集中式计算机设计 而成的“激活一等待”串行静态模式。在这种行为模式下，对象和它的调用者 之间只是一种单线的、被动的主从式关系。这种关系从效率上讲是不充分的。为 实现计算的并行化，在使用对象时必须考虑到对它的执行控制和处理机分配等问 题，也就是说，必须在对象的概念上加上智能线程的概念，将对象扩充成一个自 我生存、自我表现的个体。在解决一个一般的、抽象化的问题时，并发对象的概 念是足够的。但是，当面临一个复杂的、现实的问题时，并发对象就难以真实地 模拟它了。在一个分布式开发的计算环境中，获取全局知识是不可能的，这就要 求每个执行模块必须主动地向外界提供信息，从外界获取信息，并与其他模块相 互合作，共同求得问题的解决。为了满足这些要求，学者们引入了a g e m 的概念。 2 1 单体a g e n t 单体a g e m 是m a s 的组成元素，研究和认识单体a g e n t 对于构建功能强大 的m a s 系统具有重要的意义。 2 1 1a g e n t 定义 一种较为广义的观点认为，a g e m 是计算机硬件或软件系统，其组成元素之 间以及与所在环境之间存在着某种特定的关系。a g e m 具有区别于一般意义上所 指硬件和软件的特征。 a g e m 是一个运行于动态环境的具有较高自治能力的实体( 即自治体可以是 系统、机器等；软件a g e n t 是一个计算机软件程序) ，其根本目标是接收另外一 个实体( 即主体可以是用户、计算机程序、系统或机器等) 的委托并为之提供帮 助和服务，能够在该目标的驱动下主动采取包括社交、学习等手段在内的各种必 要的行为以感知、适应并对动态环境的变化进行适当的反应，它与其服务主体之 间具有较为松散和相对独立的关系【2 7 】。 a g e n t 不是自治和提供帮助两种功能的简单相加，而是二者的有机结合。为 主体提供帮助和服务是a g e m 的目标和本质，自治是其属性和实现其目标所应采 d 东南大学硕士学位论文第二章 取的手段。a g e n t 的所有自治行为均以最有效地为用户提供帮助为目的，a 鬓e n t 技术的本质就是研究如何使一个或多个a g e n t 实体尽可能地无需用户干预、依靠 其自身的能力、采取各种可能的方法和技术完成用户所委托的较为复杂的任务。 因此，一个a g e n t 应该尽可能准确理解用户的真实意图，包括帮助用户方便、准 确地描述和表达任务意图，采取各种由目标驱动的、积极主动的行为，如社交、 学习、推理、合作等【2 8 1 ；感知并适应复杂的和不断变化的动态环境；有效的利 用环境中的各种可能的数据、知识、信息和计算资源，为用户提供迅捷、准确和 满意的帮助。 2 1 2a g e n t 的特征 在计算机领域，a g e n t 被认为是被授权的“个人软件助理( p e r s o n a ls o f t w a r e a s s i s t a n t s ) ”【2 ”，是一种在分布式系统或协作系统中能持续自主地发挥作用的 计算实体，其一般具有以下特点： 1 、独立性 a g e n t 是所在环境中边界明确、可被独立引用的行为实体，支持数据、处理 进程和通信设施的封装。 2 、自主性 a g e n t 是可独立运行的实体，能完成自身的目标，能根据自身所处的环境、 内部状态和知识，以及外部事件来决定和控制自身的行为，具有自主地实现自己 独有功能的能力。 3 、协作性 a g e n t 是独立的但不是孤立的实体，当它不能完全独立地完成某个任务时， 能借助通信机制与其他a g e n t 或用户协作，根据自身需要组织并发送消息给其他 a g e n t ，也能理解和处理其他a g e m 发送的消息。还能通过协商方式解决冲突。 4 、适应性 a g e n t 对环境具有很强的适应能力，能对环境的信息( 如突发事件) 作出响 应，并在运行过程中动态地收集信息，进行功能的动态调整。 一般说来，一个a g e n t 拥有有限的知识源，具有多个目标以及适应环境的 能力。a g e n t 拥有的有限知识是对其所处环境或所要求解问题的描述。a g e n t 所 东南大学硕士学位论文 第二章 采取的一切动作都是面向目标的。a g e m 要达到目标，首先必须能感知环境，然 后利用所拥有的知识形成一系列可执行的动作计划，并选择执行。a g e n t 适应环 境的能力是指其具有推理、决策、计划、控制的能力。 2 1 3a g e n t 基本结构 a g e m 是一个能够与外界自主交互，并拥有一定的知识和推理能力，能够独 立完成一定任务的具有一定社会性的实体。a g e n t 的基本结构包括：环境感知模 块、执行模块、通信模块、信息处理模块、自适应性模块、决策与智能控制模块 及知识库和任务表等( 如图2 - l 所示) ，并提供一种形式化的定义，以便具体实 现。 厂、，开= 、 一感知 刮处理模块| 模块c n 、1 斟“ 环、 。 7 叫喜。 ：拶 通 信 。j 境 罔掣、 模 r i 块 资 、 1 型一h 纛 ， 图2 - 1a g e n t 的基本结构 a g e n t 的基本结构陆2 2 1 如图2 - 1 所示，由环境感知模块、执行模块、通信模 块、信息处理模块、自适应性模块、决策与智能控制模块及知识库和任务表组成。 由环境感知模块、执行模块、通信模块负责与系统环境和其他a g e n t 进行交互， 任务与承诺表为该a g c n t 所要完成的功能和任务。为满足用户对服务质量的需求 和适应环境、操作条件的变化，a g e m 应具有自适应单元，提高服务质量和适应 能力。信息处理模块负责对感知和接受到的信息进行初步的加工、处理和储存， 决策与智能控制模块是赋予a g e m 智能的关键部件。它运用知识库中的知识对信 息处理模块处理得到的外部环境信息和其他a g c e n t 的通信信息进行进一步的分 析、推理，为下一步的通信或在任务表中选择适当的任务执行模块时作出合理决 策。 6 东南大学硕士学位论文 第二章 2 1 4 移动a g e n t 及其特性 移动a g e n t ( m o b i l ea g e n t ) 【”，”1 的概念是随着i n t e m e t 的迅速发展而产生 的。随着因特网上信息资源爆炸式增长以及因特网上的站点和用户数呈几何级数 的速度增长，网络上的资源管理日益复杂，系统管理员难以驾御。此外，因特网 在诸多领域( 如基于分布式计算的应用集成和协同工作的应用领域、基于虚拟现 实的应用领域等) 有着广阔的应用前景，但是，原有的因特网上占主导地位的 w w w 技术应用于这方面开发时，却暴露出严重的局限性。 移动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 的特性外，还具备 以下三个基本特性： l 、移动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 的标志。 3 、移动a g e n t 必须保持在不同的地址空间中连续运行，即保持运行的连续 性，也即是在移动到另一个节点上运行时的状态必须是在上一个节点挂起的那一 时刻的状态。 移动a g e n t 组的成员是允许移动的，其在网络节点之间的自由移动可以视为 7 东南大学硕士学位论文 第二章 该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 1 5a g e n t 形式化表示 1 、“事件”分类 a g e n t 在并发对象的基础上对并发对象中的处理的触发源进行扩展，提出了 “事件”的概念。在一个系统中，对象不仅应当处理外部请求，还应了解自身状 况及外部环境等各种信息，并根据这些信息调整自己，使自身适应系统环境的变 化。 事件分为简单事件和复杂事件。简单事件分为三类。第一类是外部事件，包 括外部的请求以及包含特定信息的通知消息；第二类是时间事件，即某个预期的 时间点的到达，如时钟的唤醒等：第三类是状态事件，包括状态的到达和状态转 换的完成。复合事件是由简单事件通过“a n d ”或o r 连接起来的事件。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 的描述，为了便于形式化定义a g e n t ，还可以将a g e n t 的结构定义为：局部数据、历史经验库、处理过程和处理机，如图2 - 2 所示。下 面分别对它们进行说明。 东南大学硕士学位论文第二章 o n d o a p r i o r i t y 图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 对外的窗口，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 ) 服务型：这一类处理过程用来满足外部的请求，提供特定的服务。它 们的触发条件一般是外部请求或通知。 ( 2 ) 协调型：这一类处理过程用以在与其他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 r r 的形式化定义如下： a g e n t p r i v a t ed a t a l ，d a t a 2 ， k n o w l e d g e - b a s er u l e l ，r u l e 2 ， p r o c e s s o n d o a t p r i o r i t y p r o c e s s o n d o a t p r i o r i t y a c t i o n a e t i o n p r o c e s s o r e n d 其中 标识a g e n t 名；p r i v a t e 域定义a s e n t 的局部数据；p r o c e s s 定义a g e n t 的处理过程；a c t i o n 域定义每个处理过程的具体处理流程；p r o c e s s o r 域则标识处理机的地址；k n o w l e d g e - b a s e 域定义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 对自己的处理过程进行改进、完 善，从而不断发展、不断进化。 3 、a g e n t 行为模式 a g e n t 在起生命周期内的行为模式定义如下： w h i l ea l i v ed o b e g i n 扫描所以处理过程p r o c e s s i i f e x i s t k 是问题中的知识集，包括任务的初始条件、目标和中间结果。a 是操作集， 其中的操作接收相应的输入信息，经过计算，得出相应的结果。给定的任务将通 过这些操作来完成。e 是执行单元集，其中每个执行者具有不同的能力，并能以 一定的开销完成操作集中的操作( 如果开销为无穷大，就意味着这个执行者不能 完成此操作) 。i 为初始条件集，是k 的子集，包含完成任务提出时已拥有的知 识。g 是目标集，也是k 的子集，包含完成任务所必须得到的知识。i 和g 定义 了要完成的任务，k 、a 、e 定义了完成任务所依赖的环境。于是，可定义任务 的可行最优分解为下列条件的实现： l 、有的操作在执行前都得到了其必要的输入信息； 2 、g 中的所有知识都将得到； 3 、所耗费的通信和执行开销最小。 为实现第三个条件，定义一个执行开销函数e x e c f u n 和通信开销函数 c o m m u f u n ： e x e c f u n ：a ，e ，r 东南大学硕士学位论文 第四章 c o m m u f u n ：e ，e r( r 为实数集) 下面用a 。a ，i ，j = l ，2 ，n 代表操作：e ，l = 1 ，2 ，l 代表执行单 元；k ，q = 1 ，2 ，q 代表知识；并定义了二进制向量m ，d 。，z 。，x ，v 。 y w i t 如1 ： d e f m = ii f 操作j 的输入信息中包含q 。 d e f d i e = 1 i f 操作j 的输出信息中包含q 。 d e f z j , = 1 i f 由执行单元k 来完成操作i 。 d e f x 1 = 1i f 在完成任务的过程中执行了操作i 。 d e f v l = 1i f 信息i 是完成任务所必需的。 d e f y “= 1i f 操作j 的输入信息可由操作i 的输出信息提供。 d e f w i , = 1 i f 执行单元i 与执行单元k 通信。 根据以上定义可知： l 、每个操作最多可被执行一次，即： v f ( 乙1 ) ( 4 1 ) k v f ( z * x 。) ( 4 2 ) k 2 、所有操作的输出信息集必须覆盖目标集，即： v f ( x j )( 4 3 ) 3 、每个操作仅当其输入信息存在时才能执行，即： v q v j ( y & 巧) m j q x ，) 4 、所执行的操作序列必须是可行的。为形式化定义这一点 制变量r 。为y 。的传递闭包，即： v f ( r f ) v i v j 呵k ( r a + r f + 1 ) ( 4 4 ) 本文引进二进 、i ( r i = 0 ) 式( 4 5 a ) 定义r “为y 。的传递闭包；式( 4 5 b ) 定义r 的传递性； 定义r 是非递归的。 5 、当需要传递信息时才进行通信，即 ( 4 5 a ) ( 4 5 b ) ( 4 5 c ) 式( 4 5 c ) 东南大学硕士学位论文第四章 v i v j v k v i ( z m + z + s 矽j + 2 ) ( 4 6 ) 6 、完成任务的开销为： 这样，任务分解问题就变成在满足约束条件式( 4 1 ) 式( 4 6 ) 的同时使 式( 4 7 ) 的值最小的问题。 z f e x e c f u n ( a ，易) + w o c o m m u f u n ( e ，) ( 4 7 ) 4 1 2 解决任务分解问题启发式算法 该启发式算法 3 2 l 的基本思想是将任务分解问题转化为两个较为简单的问 题。第一是必须确定一组满足任务的约束条件的操作；第二是将在前一步中确定 的操作分配给执行单元执行，并使得耗费的执行开销和通信开销最小。用线性规 划的术语讲，第一个问题对应于寻找满足约束条件式( 4 3 ) 、式( 4 4 ) 、式( 4 5 ) 的包含操作数最少的一组操作；第二个问题对应于满足约束条件式( 4 1 ) 、式 ( 4 6 ) 的情况下使式( 4 7 ) 的值撮小。为生成一组可行的操作集，给出如下的 启发式算法： 定义t 。( i _ 1 ，2 ，n ) 为操作，i n p ( t ，) 为操作t ，所需要的输入信 息，o u t ( t ，) 为操作t r 的输出信息，i n p 。为初始输入信息，o u t 为完成 任务所获得的输出信息。令b e g i n n e r s = t ，：i n p ( t ) c _ i n e o ，a c t i o n s 1 n 】 为操作集数组。 如果b e g i n n e r s - - - - 中，则不存在可行的操作集，算法结束。否则从b e g i n n e r s 中选择一操作t 。，置b e g i n n e r s = b e g i n n e r s - - t 。，定义输入信息集i n p = i n p o u o u t ( l ) ，i n p = i n p 。，令a c t i o n s 1 = t 。) ，m = l 。 置m = m + i ，a c t i o n s m = ( t ，：i n p ( t ，) c i n p a i n p ( t ，) 旺i n p7 ， 1 n p = i n p ，i n p = i n p uu o u t ( t ，) 。 正e a e l m n s m 如果i n p _ d o u t ，则执行第步：否则，立口果( u a c t i o n s i ) c a ，则执 l s 肘 行第步，否则执行第步。 定义操作集r e s u l t = 巾，临时工作集w a n t e d = o u t 。 重复执行如下动作： 东南大学硕上学位论文 第四章 取出w a n t e d 的第一个元素k 。， 按顺序搜寻a c t i o n s ，找出操作t ，：o u t ( t ，) 三 k ) ， 置w a n t e d = w a n t e d - - f k 口1 ，r e s u i t = r e s u l t u t ，。 直到w a n t e d = 巾。 如果( 上n h j ( ud 【盯( i ) ) ) u 1 n p ( t ，) ，则算法结束，r e s u l t 为所 t i e r g s g l t r e r es u i t 需操作集，否则置w a n t e d = ( i n p u ( uo 们( z ) ) 一u i n p ( t t ) ，执行 f e r e 麒n t j e r c s u l t 第步。 在上述算法中，首先确定此问题是否可解。如果存在某个k 使o u t i n p ，则此问题是可解的，否则此问题不可解。然后，如果问题可解，就用在a c t i o n s 中的操作组成一个输出信息覆盖o u t 的操作集。为了减少中间操作，尽量选择 那些在该数组中靠前的操作。如果所得到的操作集是不可行的，即此操作集中某 些操作缺少相应的输入信息，则用同样的方法来得到其输出缺少信息的操作集， 并将这两个操作集进行合并，得到一个可行的操作集。 可以看出，在上面的算法中，步的循环次数随着操作的数目增加而线 性增长，而步的循环次数也与目标的数目成线性关系。因此，此算法的时间复 杂度与所求解问题的复杂度成线性关系，是很有效率的。此算法的空间复杂度显 然也是随问题的复杂度的增加而线性增加的。 下面用一个例子来具体说明这种方法： 假定某任务包含1 2 种信息k 。，e ，k 。其中k 。，k ，k 。，k ，也为初始 信息，k 。，k 。k 。，k ，。为结果信息，可用操作为a ，a 。，h 。它们的输入信息 和输出信息如表4 - 1 所示。 表4 - 1 输入输出信息表 操作输入信息输出信息 a k 口，k ”k ? ，k 却k fk a ?k k k j ，k j k 5 a ，k 口，k ，k 口k ，k mk 口k 。 a ，k 口，k 2 ，k j ，k ，j k 。 东南大学硕士学位论文第四章 a jk d ，k ”k k f k ， a #k k k 5 k ， a ，k 。，k k ，k k fk 5 a #k 口，k ，k k k 6 a 口k d ，k k 4 ，k i ，k j k 5 a ”k k 8k j 口 a jl ok ，k 4 ，k j k a 世k j ，k p ，k ，k k f 根据上述算法，可得a c t i o n s 1 = a 小a c t i o n s 2 = 凡，