（计算机软件与理论专业论文）基于多agent的语义web服务自动组合方法的研究.pdf

西华大学硕士研究生学位论文 基于多a g e n t 的语义、b 服务 自动组合方法的研究 计算机软件与理论专业 研究生高志升指导教师刘兴伟 把现有的w e b 服务按照一定的语义和逻辑自动组合起来，以得到增 值的服务是当前w e b 服务领域研究的一个热点。目前w e b 服务组合面l 临 的主要问题是系统的可伸缩性、消息传输效率以及w e b 服务的自动发现， 同时对于复杂问题的组合存在效率低的问题。因此本文结合现有w e b 服 务组合的研究成果，利用语义w e b 、a i 规划、情景演算等先进技术对基 于a i 的语义w e b 服务自动组合方法进行了研究。 本论文主要的研究内容和特色如下： ( 1 ) 提出了一种基于多a g e n t 的语义w e b 服务自动组合模型 ( m a c s ) 。该模型建立在分布式u d d i 基础上，每个u d d i 按照定义的 领域本体进行分组，并且只接受一个特殊领域的w e b 服务的注册与查询 请求。本模型利用子a g e n t 对一个受限领域w e b 服务注册中心中已存在 的w e b 服务进行描述以作为其能力。同时设置个中心a g e n t ，该中心节 点接收子a g e n t 的能力描述注册，最后利用这些能力描述实现w e b 服务 的自动组合。这样组合中的复杂问题的解决就分成两部分实现：首先中心 节点将复杂问题划分成子a g e n t 能解决的子问题，然后将这些子问题发到 对应的带有u d d i 的子a g e n t ( s a w u ) 进行二次规划组合。 ( 2 ) 对现有的w e b 服务描述模型o w l - s 进行完善和扩展，形成描 述子a g e n t 能力的模型- - o w l - s 4 s a w u ( o w l - sf o rs a w u ) 。首先对w e b 本体语言o w l 进行扩展，形成领域约束描述语言一r u l e d r ，用其来描述 第1 页 西华火学硕士研究生学位论文 w e b 服务组台中存在的领域约束规则。然后在o w l - s 的基础上增加领域 约束规则和其所属的节点信息，扩展为o w l s 4 s a w u 。o w l s 4 s a w u 既可以作为中心a g e n t 组合的抽象服务，同时也能用于子a g e n t 以自动完 成w e b 服务的组合。 ( 3 ) 实现了中心a g e n t 和子a g e n t 端的w e b 服务组合规划算法以及 基于多a g e n t 的语义w e b 服务自动组合原型系统。a g e n t 以o w l - s 4 s a w u 为o p e r a t o r s 进行h t n 规划，子a g e n t 端以o w l 。s 4 s a w u 为模板情景 演算为形式工具，g o i n g 为程序语言进行w e b 服务组合。 ( 4 ) 最后通过实验验证了服务组合规划算法。实验的基础网络平台 使用了s u n 的j x t a 。 关键词：语义w e b 服务：a i 规划：服务组合：a g e n t 第1 i 页 西华大学硕士研究生学位论文 a n m u l t i a g e n tb a s e da p p r o a c hf o ra u t o m a t e d s e m a n t i cw e bs e r v i c e sc o m p o s i t i o n s p e c i a l i t yc o m p u t e rs o f t w a r ea n dt h e o r y m a s t e rc a n d i d a t eg a oz h i s h e n g s u p e r v i s o rl i ux i n g w e i c o m p o s i n gt h ee x i s t i n gw e bs e r v i c e sa c c o r d i n gt oc o r r e s p o n d i n gs e m a n t i c a n dl o g i ct og e tv a l u e a d d e ds e r v i c e si st h ef o c u so fw e bs e r v i c er e s e a r c h d o m a i n c u r r e n t l ym a i n l yp r o b l e m so ft h ew e bs e r v i c ec o m p o s i t i o na r et h e s c a l a b i l i t yo ft h es y s t e m ，t h ee f f i c i e n c yo ft r a n s p o r t i n gm e s s a g ea n dt h e d i f f i c u l t y o fd i s c o v e r i n gt h ea u t o n o m i cs e r v i c e f u r t h e r m o r e ，i th a sl o w e r e f f i c i e n c yf o rt h ec o m p l e xt a s k sc o m p o s i t i o n s ot h i sp a p e ra p p l i e dt h ec u r r e n t r e s e a r c ho fw e bs e r v i c ec o m p o s i t i o n ，a n dt h et e c h n o l o g i e so fs e m a n t i cw e b ， a ip l a n n i n g ，s i t u a t i o nc a l c u l u se t ct or e s e a r c h o fa u t o m a t i cc o m p o s i t i o n s e m a n t i cw e bs e r v i c e t h em a i nr e s e a r c hc o n t e n t sa n dr e s e a r c hc h a r a c t e ri nt h i s p a p e ra r ea s f o l l o w s ： 1 ac o m p o s i t i o ns e m a n t i cw e bs e r v i c em o d e lb a s e do nm u t i a g e n t ( m a c s ) i sp r o p o s e d t h em o d e li sf o u n d e do nt h ee n v i r o n m e n to fd i s t r i b u t e du d d i e v e r yu d d i i sg r o u p e db yd o m a i no n t o l o g y ，a n de a c hu d d io n l ya c c e p t st h e w e bs e r v i c er e g i s t r a t i o na n dq u e r yq u e s tf r o mas p e c i a ld o m a i n t h em o d e l d e s c r i b e st h ew e bs e r v i c e sw h i c ha l r e a d ye x i s ti nt h er e s t r i c t e dd o m a i nu d d i a n dt a k e st h e ma si t s a b i l i t y b e s i d e st h i s ，i ts e t su pah a ( h e a d e ra g e n t ) ， w h i c ha c c e p t st h es u b a g e n t s r e g i s t r a t i o nr e q u e s ta b o u ti t sa b i l i t y , a n da tl a s t c o m p o s e sw e bs e r v i c et or e s o l v ec o m p l e xt a s kb yu s i n go ft h e s ea b i l i t i e s t h u st h es o l v i n go fc o m p l e xt a s ki n c o m p o s i t i o nc a nb ed i v i d e di n t o t w o s t a g e s a tt h ef i r s ts t a g e ，t h eh ad e c o m p o s et h ec o m p l e xt a s ki n t os u b t a s k s ， a n ds e c o n d l ys e n ds u b - t a s k st oc o r r e s p o n d i n gs a w u ( s u b a g e n tw i t hu d d i ) f o rt h es e c o n dt i m ep l a n n i n g 第1 i i 页 西华大学硕士研究生学位论文 2 b ye v o l v i n gt h ee x i s t i n gw e bs e r v i c ed e s c r i p t i o nm o d e lo w l - s ，am o d e l f o rd e s c r i b i n gt h ea b i l i t yo fs u b - a g e n to w l - s 4 s a w u ( o w l - sf o rs a w u ) i s f o r m e d f i r s t l y ，e v o l v i n gt h eo w l w i t hw e bo n t o l o g yl a n g u a g et od e s i g na r e s t r i c t e dd o m a i nd e s c r i p t i o nl a n g u a g er u l e d r ，w h i c hc a nb eu s e dt od e s c r i b e t h ed o m a i nr e s t r i c t e dr u l e st h a te x i s ti nt h ec o m p o s i t i o nw e bs e r v i c e t h e n p r o p o s i n gan e ws e m a n t i cw e bs e r v i c em o d e lc a l l e do w l s 4 s a w ub y e n r i c h i n go w l - sw i t hd o m a i nr e s t r i c t e dr u l e sa n dt h en o d ei dw h i c ht h e o w l - s 4 s a w ub e l o n g st o o w l - s 4 s a w uc a nb eu s e da st h ea b s t r a c t s e r v i c ef o rh aa sw e l la ss u p p l y i n gt h es a w ut of i n i s hc o m p o s i t i o nw e b s e r v i c ea u t o m a t i c a l l y 3 t h ew e bs e r v i c ec o m p o s i t i o n p l a n n i n ga l g o r i t h m so ft h eh aa n d s u b a g e n ta r ei m p l e m e n t e di nap r o t o t y p es y s t e mo fm a c s h ad oh t n p l a n n i n gb yu s i n go w l - s 4 s a w ua so p e r a t o r s s u b a g e n tc o m p o s e sw e b s e r v i c e sb yt a k i n gt h eo w l o s 4 s a w ua s t e m p l a t e ，s i t u a t i o n c a l c u l u sa s f o r m a lt o o l sa n dt h eg o l o ga sp r o g r a m m i n g l a n g u a g e 4 a tl a s tw eh a v ev e r i f i e dt h es e r v i c ec o m p o s i t i o na l g o r i t h mb y e x p e r i m e n t t h ee x p e r i m e n t sf u n d a m e n t a ln e tp l a t f o r mi sj x t a k e yw o r d s ：s e m a n t i cw e bs e r v i c e ，a ip l a n n i n g ，s e r v i c ec o m p o s i t i o n ，a g e n t 第1 v 页 西华大学硕二e 研究生学位论文 1 绪论 w e b 服务以其自包含、自描述、交互性等特点将w e b 应用从信息 交互领域扩展到了服务交互领域，已成为当前电子商务的主要解决方 案，越来越多的服务商开始运用w e b 向用户提供服务。随着网上w e b 服务的同益增多，怎样通过组合这些已经存在的w e b 服务从而获得增 值的新服务就成为一个热点问题。事实上，网上绝大部分数据和服务对 计算机来说是“不可理解的”，妨碍计算机“理解”和自动处理这些数 据和服务的最大障碍在于目前的数据和服务缺乏语义。而语义w e b 是 其最新解决方案，是当前w e b 的延伸和扩展，它赋予w e b 中的所有信 息以定义良好的语义，最终目的是让计算机能够自动理解和处理w e b 数据。 1 1 语义w e b 服务 1 1 1 w e b 服务 w e b 服务是一种新型的w e b 应用程序，w 3 cw e bs e r v i c e a r c h i t e c t u r e 小组为w e b 服务暂行的定义是：“w e b 服务是由u r i 标识 的软件应用程序，其接口和绑定可以通过x m l 构件进行定义、描述和 发现，w e b 服务支持通过基于因特网的协议使用基于x m l 的消息与其 他软件应用程序直接交互 1 2 。”w 曲服务可以应用于程序集成、b 2 b 的集成及软件和数据的重用等。 w e b 服务的体系结构是基于三个角色( 服务提供者、服务代理、服 务请求者) 和三个操作( 发布、发现、绑定) 构建的。服务提供者通过 在服务代理处注册来发布其服务，服务请求者通过服务代理查找服务登 记记录来发现所需服务，并绑定调用服务，如图1 1 所示。 w e b 服务核心组件是基于w s d l ( w e bs e r v i c ed e s c r i p t i o n l a n g u a g e ) 、u d d i ( u n i v e r s a ld e s c r i p t i o n d i s e o v e r ya n di n t e g r a t i o l q ) 和s o a p ( s i m p l eo b j e c ta c c e s sp r o t o c 0 1 ) 等标准规范的x m l 。w e b 月& 务是用标准的、规范的、基于x m l 的w s d l 语言描述的，浚描述包括了 与服务交互所需要的接口、传输仂、议和位置等信息。u d d i 为企业和应 用程序在i n t e r n e t 上快速、动态的查找服务提供了一个交互式的平台 第1 页 西华人学硕士研究生学位论文 3 。s o a p 是一种基于x m l 的不依赖于传输协议的表示层协议，用于应 用程序以对象形式方便地交换数据。 圃 7r 发布发现 f i g1 1w e bs e r v i c ep u b l i ca n df i n d i n g 图1 1w e b n 务注册和查询 1 1 2 语义w e b 语义w e b 是发明因特网超文本系统的麻省理工学院万维网协会主席 蒂姆伯纳斯李为新一代互联网命的名。语义w e b 不仅仅提供人类能 够理解的文字和图像信息，而且能够理解人类的语言，可以使人与电脑 之间的交流变得像人与人之间交流一样轻松。语义网的实现是基于x m l 语言和资源描述框架( r d f ) 来完成的。因此，我们认为语义网是未来 智能w e b 服务、下一代知识管理方法、电子商务协作等高级网络应用和 服务的基本解决方案 4 。 本体论( o n t o l o g y ) 被广泛地认为是实现语义w e b 的基本技术。通常， w e b 上的本体包括分类和一套推理规则。分类是定义对象的类别及其之 问的关系。推理规则是计算机“理解”信息的方法。通常情况下，这些 信息都是以一种机器可读的方式来表示的。这样本体就为应用系统的通 信提供了稳定的统一的参考模型。使用本体能增强网络的功能，能使应 用、服务智能地进行互操作，提高网上搜索的准确性等等。因此怎样将 语义w e b 技术和w e b 服务技术结合起来，并通过w e b 服务的语义封装为 人们提供所谓的语义w e b 服务，是一个非常值得研究的问题。 1 13 语义w e b 服务 w e b 服务标准( u d d i ，w s d l ，s o a p 等) 的描述能力有限，其大大限 制了对w e b 服务的语义操作。另一方面，语义w e b 用“d a m l + 0 1 1 o w t ” 第2 页 奎 洲一龟 两华大学硕士研究生学位论文 语义地表达信息，服务和代理都可以直接访问它们。因此，结合语义 w e b 技术的w e b 服务，称为语义w e b 服务将是一种更为智能的服务，是 f i g1 2w e bd e v e l o pt r e n d * 图1 2 w e b 发展趋势 w e b 服务未来的发展趋势，如图1 2 所示 5 。 语义w e b 服务采用基于o w l ( w e b 本体语言) 的服务描述本体( o w l s ) 作为w e b 服务的标记模型，其为提供机器可以解释的、精确的、关于 w e b 服务属性和能力的描述而提供了一系列标记符。这有效地克服了在 传统方式下，对w e b 服务的查找、访问和组合是用户自己来完成，且这 利查找和访问是基于关键词的，靠用户自己来理解解释服务的语义的缺 陷。在语义w e b 环境下，用户可以通过一个智能a g e n t 来自动发现、自 动执行其所需的w e b 服务，甚至a g e n t 可以自动选择和提供交互服务来 为用户完成复杂任务。 在o w l s 中，描述服务的基本信息主要有三类本体： s e r v ic e p r o f i l e ，s e r v i c e m o d e l 和 s e r v i c e g r o u n d i n g 。其中 s e r v ic e p r o f i l e 描述了服务的属性信息，包括服务所提供的功能、服务 的输入、输出、执行的前提条件、执行后产生的结果等。其描述了服务 能做什么，用于对服务的自动搜索。s e r v j c e m o d e l 描述了服务在执行 时将会发生什么，服务是如何工作的，并在s e r v i c e g r o u n d i n g 配合下 完成服务的执行。s e r v i c e g r o u n d i n g 将过程模型的描述和w g d l 中的通 讯协议及消息描述联系起来，它描述了访问一个服务的细节。o w l s 和 当前的w e b 服务标准u d d i 、w g d l 等结合可以较好地支持w e b 服务的语 第3 页 茎 西华大学硕士研究生学位论文 义发现和语义组合。如图1 3 所示 6 ，2 。 其中o w l sp r o c e s s 描述了服务的过程，可以用于原子服务的组合， 但由于o w l 在规则方面表达能力的局限性，o w l s 模型没有用户选择服 务所表现出来的偏好以及特定领域的领域约束的描述，这就意味着计算 u d d i服务发现 i 矍堑垄塑1 0 w l - sp r o c e s s 0 w l - sp r o c e s s 0 w l - sp r o f i l e & u d d i o w l 广sg r o u n d i n g & w s d l k q m l a c l s o a p h t t p ，f t p j 互 服务交互 服务发布 服务描述 通讯协议 基于x m l 的消息l 网络协议 f i g1 3a r c h i t e c t u r eo fs e m a n t i cw e bs e r v i c e 幽1 3 语义w e b 服务的体系结构 机在遇到不确定情况时需要用户的干预，同时产生的服务组合序列可能 与实际的领域事实相矛盾。 1 2w e b 服务组合 w e b 服务组合是指从互联网中选取相对简单、可用的w e b 服务并将 它们组合成新服务的技术 7 。组合后的新服务被称为组合服务，用予 组合服务的子服务称为原子服务。通过组合现有的w e b 服务可以创造出 新的服务功能和增值的新服务，同时其也非常适合于当今的商务应用集 成和企业应用集成，因此w e b 服务组合技术在工业界和学术界都得到了 空前的关注。w e b 服务组合方法主要可以分为两类：一种是以基于x m l 第4 页 西华大学硕士研究生学位论文 的工作流描述语言和工作流技术为基础的组合方式，它们基本上是一种 静态组合、动态绑定的方式，组合的自动化和动态适应性程度不高。另 一种是基于a j 规划的自动w e b 服务组合方式。本节将对这两种w e b 服 务组合技术进行简单综述。 1 2 1 基于流程的w e b 服务组合 基于流程的w e b 服务组合有两种方式：o r e h e s t r a t i o n 和 c h o r e o g r a p h y 。使用o r c h e s t r a t i o n ，需要一个总控过程来控制所涉及 到的w e b 服务，并协调w e b 服务不同操作的执行。所涉及到的w e b 服务 并不知道( 也不必知道) 它们是组合过程的一部分。只有中央的总控过 程知道它们如何组合和协调。相比之下，c h o r e o g r a p h y 并不依赖中央 的总控协调过程。相反，每个涉及其中的w e b 服务都知道何时执行自己 的操作，和谁交互。c h o r e o g r a p h y 方式集中在消息的交换。所有的 c h o r e o g r a p h y 参与者都需要知道业务流程，要执行的操作，要交互的 消息以及交换消息的时机。从组合w e b 服务来执行业务流程的角度来 看，o r c h e s t r a t i o n 比c h o r e o g r a p h y 更灵活： 我们知道谁负责执行整个业务流程。 即使w e b 服务并不知道它们是业务流程的一部分，但我们仍然可 以把它们组合起来。 当错误发生时，我们可以提供一个备选的方案。 目前像i b m 、m i c r o s o f t 和s u n 等主要的软件公司已经建立了各种 w e b 服务组合标准，并且更加先进和精炼的标准正在制定中。主要有 b p e l 4 w s ，x l a n g ，w s f l ，b p m l ，w s c i 和w s c d l ，如图1 4 所示 8 。 其中b p e i 4 w s 构建在x m l 和w e b 服务的基础上。它是一个以x m i 为 基础的语言，支持w e b 服务技术的协议群，包括s o a p ，w s d l ，u d d i ， w s r e i a b l e m e s s a g e ，w s a d d r e s s i n g ， w s c o o r d i n a t i o n和 w s t r a n s a c t i o n 。b p e l 4 w s 是早期两个工作流语言( w s f l 和x l a n g ) 的 综合。w s f l 由i b m 设计，基于有向图的概念。x l a n g 由微软设计，是一 种块结构语言+ 。b p e l 4 w s 综合了w s f l 和b p e l 4 w s 的特点，为描述业务 流程提供了丰富的语义词汇。b p e l 流程定义了参与流程的w e b 服务执 第5 页 西华大学硕士研究生学位论文 幽1 4e v o l v e m e n to f w es e r v i c es t a n d a n d 幽1 4 w e 服务标准进展 行的确切次序。它可以按顺序执行，也可以并发执行。使用b p e l ，我 们可以表达条件行为，例如，是否执行一个w e b 服务取决于前一个执行 结果；也可以创建循环、声明变量、 h a n d l e r 等等。综合使用这些结构， 业务流程。 复制和为变量赋值，定义错误处理 我们可以用算法的方式定义复杂的 b p m l 是由b u s i n e s sp r o c e s sm a n a g e m e n ti n i t i a t i v e ( b p m l o r g ) 提出的另外一个标准，其最初是为了标准化管理e b u s i h e s s 流程而提 出来的。但是b p m l 可以应用于企业应用集成和w e b 服务组合等多种场 合。b p m i 。是专门为可执行商务流程定制的规格浣明，因此其支持具有 发送、接收和调用w e b 服务功能的控制流程、数据流程和事件流程，并 且支持条件选择、顺序、循环和同步并发控制结构。 w s c 是s u n 、s a p 、b e a 和t n t a l i o 几家公司于2 0 0 2 年7 月提出来 的。它是第一个基于x m l 语言的，通过描述服务提供者和服务使用者的 消息交换而为它们的全面协作而提供了统一标准。w s c i 也是建立在 w s d i 基础上的，并用其来定义包含在w s c i 行为中的w e b 服务操作，而 行为用于定义一个基本的请求和响应消息。同时w s c i 可以通过请求调 用外部服务，也支持事务和异常的处理。 第6 页 西华大学硕士研究生学位论文 w s c d l 是为w e b 服务参与者之间进行协同操作、长期运行、通过 p 2 p 进行协作而制定的x m l 描述规范。它描述了包含在商业协作中的所 有w e b 服务参与者之间可见的行为消息交换的全局视图。w s c d l 仅仅 是商业避程的抽象描述，它通过具体的平台和编程语言去实现w e b 服务 的合作。 它们之问的简单比较可以概括为：w s c d l 为消息交换的交互的可 见行为描述提供了足够的机制，b p m l 易于描述过程的执行，而b p e l 4 w $ 在两个方面都有不错的表现。同时b p m l 拥有更多的语义信息去支持企 业应用集成，而w s c d l 能更好地描述b 2 b 的相互协作。b p e l 4 w s 获得 了广泛的支持，许多重要的软件开发商都在它们的软件中提供了对 b p e l 4 w s 的支持。 1 2 2 基于a i 规划的w e b 服务组合技术 在语义标注w e b 服务的环境里，用户为了完成某个任务可以借助于 智能a g e n t 。这些a g e n t 可以自动识别，如果需要还可以动态组合w e b 服务以完成用户的目标，所有这些工作都可以在没有用户参与的情况下 完成 9 。但是动态自动组合w e b 服务是十分困难的问题，至今还没有 找到一个最佳的解决方案。什么技术能够更好地自动组合w e b 服务还不 是十分清晰，目前存在的一个比较好的技术是a i 规划。已经有一大批 探讨怎样应用a i 规划技术进行w e b 服务组合以达到目标的工作和论文， 下面将对a i 规划和a i 规划用于w e b 服务的主要工作进行简单综述。 1 2 2 1a i 规划 r u s s e l ，s a n dn o r v i g 1 0 将规划定义为：规划可以解释为一种问题解 决方式，一个a g e n t 运用其关于可用的动作信念( b e l i e f s ) 加上它们的 推理在一组抽象的可能的规划上找到问题的解。一般地，一个规划问题 包括下面三部分 1 0 1 1 1 ： 用某种形式化语言。描述的可被执行的行动 一个行动是根据前提和效果来指定的，前提在该行动执行前必须成 立，效果则是在其执行后发生。例如，一个表示飞机从一个地方飞到另 个地方的行动： 第7 页 西华大学硕士研究生学位论文 a c t i o n ( f l y ( p ，f r o m ，t o ) ，p r e c o n d ：a t ( p ，f r o m ) 八p l a n e ( p ) 八 a i r p o r t ( f r o m ) 八a i r p o r t ( t o ) ，e f f e c t ：一a t ( p ，f r o m ) 八a t ( p ，t o ) ) 这里p r e c o n d 表示前提，e f f e c t 表示效果。通常一个行动由3 部分组 成：一是行动名和行动参数，用来标识行动，如：f l y ( p ，f r o m ，t o ) ： 第二是前提，是一个无函数正文字的合取式，规定在行动能够被执行前， 一个状态中那些文字必须为真。前提中的任何变量也必须在行动参数表 中；第三是效果，是无函数文字的合取式，描述了当行动执行时状态是 如何变化的。效果中的正文字p 表示由行动产生的状态中被断言为真， 而否定文字1 1 ) 则被断言为假，效果中的变量也必须出现在行动参数表 中。 形式化的初始状态 初始状态是必要的，因为规划过程总是在个给定初始状态下执行 最终获得变到目标状态的一个操作序列。规划器将世界分解成逻辑条 件，并且把一个状态表示为正文字的合取。如：a t ( p l a n e ，n e l b o u r n e ) a a t ( p l a n e ：，s y d n e y ) ，表示包裹传递问题中的个状态。在实际的应用 中，存在不完全的信息、错误信息和模糊信息等问题，因此对状态的完 整无歧义的描述是非常重要的，目前已开发出一系列的规划形式化方 法，如：s t r i p s ( s t a n f o r dr e s e a r c hi n s t i t u t ep r o b l e ms o l v e r ) ， 针对s t r i p s 的不足而开发的行动描述语言( a d l ) ，规划域定义语言 ( p d d l ) 和其扩展( n p d d l ) 等。 形式化描述的目标。 经典的a i 规划方法中，目标表示为期望的目标状态所拥有的属性， 通常是正文字的合取和析耿及有关的变量。规划器需要判断从一个初始 状态执行最后到达目标状态的解决方案是否满足预定目标。如： g o a t ( o n ( a ，b ) 八0 ( b ，c ) ) ，表示当b 在a 上而c 在a 上则目标为真。 1 2 2 2 主要a i 规划 ( 1 ) 状态空间搜索规划。一个状态空问由一个有限的状态集s ， 一个有限的动作集a ，一个描述动作从一个状态到另一个状态的转移函 数f 和一个度量行动a 在状态s 下发生的代价函数c ( a ，s ) 构成基于状 第8 页 西华大学硕士研究生学位论文 态空间的规划器就是通过搜索可以达到目标状态的可用行动实例来完 成舰划问题。对于状态空间的搜索主要有前向状态空间搜索、后向状态 空间搜索和状态空问的启发式搜索三种。主要的状态空间规划系统有 h s p ，a + ，f f 等 1 3 ，1 0 ( 2 ) 图规划方法。一个规划图包含一个阶段序列，与规划中的时 间步相对应，阶段o 表示初始状态。每个阶段包括一组文字和一组行动。 粗略地讲，文字是所有那些在那个时间步上可能为真的文字，真值情况 取决于前一时间步执行的行动。行动是所有那些在那个时间步其前提可 能得到满足的行动，取决于哪些文字确实成立。规划图已被证明对于求 解难的规划问题时是高效的工具。基于图的规划系统代表有美国卡乃基 一梅隆大学( c a r n e g i em e l l o nu n i v e r s i t y ) 的图规划系统g r a p h p l a n ( b l u m 和f u r s t ) 、德国的i p p 、英国的s t a n 、美国盛顿大学( u n i v e r s i t y o fw a s h i n g t o n ) 的s g p ( d a n i e ls w e l d 等) 1 4 ( 3 ) 基于可满足的规划方法。可满足性规划的根本思想是将规划问 题表示为一个推理问题，然后利用强大的成熟的推理算法解决问题。可 满足性规划主要有三种：第一种是命题满足规划，如：g s a t ，w a l k s a t ，l g p 系统等 1 0 ：第二种是描述逻辑可满足性规划；第三种是基于p e t r i - n e t 的可达性分析的规划方法，其原理是将原子w e b 服务按照所有可能的组 合构成一个p e t r i n e t ，然后应用p e t r i n e t 的标准算法一可达性分析一 判断规划的目标状态是否可达，这种技术还可以应用于判断一个规划表 示是否是良好无歧义的 1 5 。 ( 4 ) 基于逻辑编程的规划方法。一个逻辑程序由一组形如a b l ，b n 的h o r n 子句组成。h o r n 子句是至多只有一个正文字的文字 析取式。例如，子句a v ，b l v v b n 逻辑编程和规划的关系以及规 划问题与逻辑程序在学术界得到了广泛的研究。如，s w o r d ，g o l o g 和 s m o d e l s 1 0 等。 ( 5 ) 逐步细化的分层规划方法。以s h o p 2 1 6 为代表的层次规划 方法思想是：首先勾画出一个完整但又比较粗略的规划解，然后逐步细 化、逐步明确，直到足以具体完成整个规划的每一步操作，层次规划方 第9 页 西华大学硕士研究生学位论文 法实际上是把不同性质的问题放在不同层次上加以考虑。 ( 6 ) 基于模型检测的规划方法。模型检测( m o d e lc h e c k i n g ) 是当前 计算机研究领域上的一个热点，它将一个系统模型跟逻辑需要进行比 较，从而发现不一致性。传统上，这个思想用于硬件电路上的验证和网 络协议的验证。近期，这个思想用在智能规划中，取得了令人瞩目的成 就，产生了一系列功能较强的规划系统：m b p 、m i p s 、t a l p l a n n e r 、t l p l a n 和u m o p 1 7 。 以上是常用的a i 规划算法，以下对一些经典的规划系统从w e b 服 务组合所需的对领域复杂性的描述、对复杂目标的支持、处理不确定性 信息的能力和对感知行为的支持等几个方面进行简单对比，见表 1 1 1 0 。 表1 1w e b 服务组合需求与a i 规划 t a b l 1w e bs e r v i c ec o m p o s i t i o nr e q u i r ea n da ip l a n n i n g 规划 ! 领域扩展目标 感知动态目标不确定行为 复杂性 f f m e t r i c ( s l m e p d d l2 1l e v e ln on o n on o b a s e d ) 1 ，l e v e l 2 s o p r g r a p h p l a np d d l 伽l n on on o n o b a s e d l b l a c k b o x ( s a p d d u s t r i p sw i t h n on on on o t ， g r a p h p l a n r e s t r i c t i o i t s b a s e d ) l g p ( s a tb a s e d ) p 1 3 d l2 1i e v e l sn on o n on o 1 ，2 , 3 p l a n n e r1 3 0 m a i nc o m p l e x i t ye x t e n d e d s e n s i n g d v n a m i c n o n d e t e r m g o a l s o b j e c t s s h o p 2 ( h t n 具有舰格时间的y e s y e sy e s b a s e d ) p d d u a d l c o n g 0 1 0 9 ( h i 曲 情景演算 y e sy e s y e s l e v e lp r o ge x e c ) m i p s ( p l a n n i n ga s 具自否定、前置条件 s u p p o r t s n 0 n on o m o dc h e c k 、的p d d u s t r i p s c t l m b p ( p l a n n i g a sp d d k 2 1 + e x t e n s i o n y e sy e sn o ? y e s ， m o dc h e c k ) 第1 0 页 西华大学硕士研究生学位论文 t l p l a n ( t e m p r o a l a d l + m e t r i c sy e sn on on o ) t a l p l a n n e r ( t e mp d d l 2 1 ( o r t a l ) l 扎y e s n o ( u n d e r 讥 p o r a l ) 从表中可知，经典的规划方法如f f ，s g p 等除了能较好描述复杂领 域外对其他的w e b 服务组合的支持明显不足。相反一些基于控制知识的 规划系统如s h o p 2 ，t l p i a n 等则对w e b 服务组合提供了比较全面的支持。 下面将对一些著名的基于a i 规划的w e b 服务组合方案给予简单探讨。 1 2 2 3 基于a i 规划的w e b 服务组合相关研究 s e l f - s e r v 1 2 将组合服务操作的逻辑过程表示为一个状态表，其 描述了调用服务操作组件的流程。一个状态表根据事件条件行为规则由 基本状态、组件或转移组成，一个基本状态负责执行一个基本的或组合 服务。复合状态是通过“o r ”或“a n d ”连接的多个状态表。 g o o g 通过构建可根据用户喜好而更改的通用模板而一直被用作服 务组合，以产生一个组合的规划。这种模板不是自动被创建但构成规划 的组成部分。 s h o p 2 是马里兰大学开发的一个h t n 规划器，用于处理操作和方法， 它们代表了原子和组合服务。s h o p 2 操作描述了完成一个基本任务需要 做些什么工作，s h o p 2 方法描述怎样将一个组合任务分解成部分有序的 子任务。此项工作包括使用转换算法将一个d a m l s 过程模型转换成 s h o p 2 文件。这些文件可用于产生s h o p 2 规划，被转换成d a m l s 并被 d a m i 一s 执行者执行。 1 2 2 4 基于a i 规划的语义w e b 服务组合中存在的问题 语义w e b 服务自动组合还处于研究的初级阶段，还不能像b p e l 那 样直接用于w e b 服务自动组合。主要是还存在以下一些尚没有完全解决 的问题：( 1 ) 行为的表示方法，当前的规划方法还不能很好地表示w e b 服务组合中包含循环和不确定性选择的复杂结构。( 2 ) 服务的描述问题， 好的w e b 服务描述能够使计算机能够更好地无歧义地识别w e b 服务。 o w l 。s 目前还存在语义描述不全，规则表示偏弱的问题。( 3 ) w e b 服务 第1 i 页 西华大学硕七研究生学位论文 的自动发现，怎样在海量的w e b 服务中找出组合所需的w e b 服务也是一 个值得研究的问题。( 4 ) w e b 服务描述标准和发布代理结构混杂，需要 寻求合适的方案去解决这些异构系统中w e b 服务的调用和发现问题。 ( 5 ) 现有的方案主要是一个独立的规划组合器，这对于解决复杂问题 存在查找w e b 服务难，效率低的问题。( 6 ) 怎样确保异构分布环境中 w e b 服务的安全和事务。 1 3 本文的主要研究内容 基于a i 规划的w e b 服务自动组合是一件非常复杂的工作，本文结 合现有的成功规划方法对w e b 服务的自动组合进行了初步的研究。主 要包括以下四个方面： ( 1 ) 提出一个基于多a g e n t 的w e b 服务组合框架m a c s 。在本文 第二部分，分析了w e b 服务组合的w e b 服务环境，然后给出了在该环 境上的基于多a g e n t 的语义w e b 服务自动组合框架