第3章部分可观测环境下迁移 工作流服务导航方法 3.概述 1 在面向目标的迁移工作流方法中,每个工作位置上的 服务主体可以作为导航主体对迁移实例提供导航服务。 因为导航主体都只能为迁移实例提供自己基于局部工作 流视图的帮助,相对于全局目标来说,它仅是一个部分可 观测的环境,所以,单位置导航使得迁移实例可能得不到 实现正确决策的充要信息,以至于造成迁移实例迷航或工 作流中断。部分可观测环境中迁移实例的求解路径不偏 离全局目标成为当前的技术难点之一。 在部分可观测的迁移工作流环境下,迁移工作流系统 需要一种“主动”的机制保障迁移实例移动决策逼近全局 目标。本章在第2章的研究基础上,通过导航主体在自己 的业务熟人域内实现对迁移实例的导航,使迁移实例的每 步移动决策都能逼近全局目标,又使产生的新工作位置具 有可替代性。面向目标的迁移工作流服务导航方法,将显 ·57· 面向目标的迁移工作流主动服务方法 式的全局性业务过程定义和工作流调度隐式地分布于由 工作流参与者形成的业务熟人网络上。由于每个工作位 置都是一个帮助迁移实例求解业务过程的知识源,因此, 本质上也是一种基于分布式知识的工作流问题求解系统。 基于分布式知识系统求解工作流问题,符合多agent系统 特征,不仅可以有效降低对工作流设计者知识完备性的要 求,而且可以增加工作流管理的柔性。 本章首先定义了部分可观测的迁移工作流环境,并建 立了部分可观测环境下的服务导航模型;然后定义了通用 的基于本体论(Ontology)的环境描述规范,用于解决部分 可观测环境中不易描述的问题,使得导航主体可理解工作 流环境的动态变化,并触发目标相关性评价;最后介绍了 一个目标驱动的服务导航算法,促使导航主体为迁移实例 提供满足寻航目标的服务,是实现面向目标的迁移工作流 主动服务的有效方法。 3.部分可观测的迁移工作流环境 2 随着协同政务、协同商务、协同制造、协同诊疗、协同 应急指挥等业务应用的不断深入,多机构、跨地域的大规 模业务协作过程越来越多。囿于部门或机构分工及业务 自治等原因,在多机构之间建立统一的工作流模型及中心 化的工作流管理系统是困难的。虽然WfMC 规范建议可 ·58· 第3章部分可观测环境下迁移工作流服务导航方法 以通过不同工作流引擎之间的互操作,实现跨机构工作流 管理系统之间的应用集成,但因为系统集成涉及任务分担 模式、结果共享方式、数据转换格式、访问权限及访问路径 设置等诸多因素,所以工作流设计者不仅要知晓完整的业 务流程,而且要熟悉所有参与机构承担的业务及其应用接 口功能。机构越多,业务协同范围越大,全局性知识就越 复杂,就越难以掌握和完备,业务过程定义也就越难以完 善。因此,工作流设计者的知识难以完备、业务过程定义 的完善性难以保证等问题,一直是制约工作流技术在跨机 构大规模协同业务中推广应用的瓶颈。 在社会合作系统中,并非所有的工作流程都要在事前 完整定义的前提下才能进行。例如,在行政许可联合审批 工作流程中,申请者可能只知道与其申请相关的某个部 门,不知或知之甚少需要联合审批的其他部门,以及其中 的审批过程,申请者能做的就是直接去其知道的部门申请 审批,表达自己的申请目标并听取该部门关于就地可以审 批什么事项、下一步应该去何部门、审批什么事项的建议。 其他审批部门还可以为申请人提供建议,所有审批部门的 合理建议为申请者动态地定义了一个行政许可审批业务 流程。 又如,在购物工作流程中,购物者可能只知道与其采 购目标相关的某个商店或企业,对该商店或企业能否满足 他的全部采购需求知之甚少,也不知道还有哪些商店或企 ·59· 面向目标的迁移工作流主动服务方法 业可以为其提供采购服务,购物者能做的就是直接去其熟 悉的商店或企业进行采购,表达自己的采购目标并听取该 商店或企业关于就地可以采购什么物品、下一步应该去何 商店或企业、采购什么物品的建议。其他的商店或企业还 可以为申请人提供建议,所有商店或企业的合理建议为购 物者动态地定义了一个购物业务流程。 上述的业务流程具有移动计算特征,可以采用移动 agent计算模式进行管理。例如,许可申请人可以创建一 个迁移实例,令其携带自己的审批文件和基础资料游走于 各审批部门设置在网络上的许可审批受理结点之间,进行 逐项事务审批。又如,购物人可以创建一个迁移实例,令 其携带自己的购物清单和商务资料游走于各商店或企业 设置在网络上的商务门户之间,进行比价采购。移动 agent计算为工作流管理提供了对非中心化、松散耦合特 性的支持,迁移工作流是其中的一个重要研究方向。现有 的“让迁移实例清楚地知道做什么和需要什么”的设计思 想,不仅要求事前建立工作流联盟,以便于为迁移实例规 划工作位置或支持迁移实例服务发现;而且要求为移动迁 移实例编写完整定义的业务过程说明,因此,同样会使工 作流管理系统陷入机构越多,协同范围越大,设计难度就 越高,也就越可能发生工作流例外的困境。 上面的分析表明:基于导航主体的工作位置推介和 移动主体的迁移决策建立一种迁移工作流方法,允许工作 ·60 · 第3章部分可观测环境下迁移工作流服务导航方法 流在业务过程动态定义中执行,它将不再需要事前对业务 过程进行完整的定义,也不需要事前建立完整的工作流联 盟,因而不仅可以大大降低工作流计者的负担,而且会大 大提高工作流的柔性,特别适用于那些多机构、大规模、全 局业务过程定义困难并且具备移动计算特征的协同业务 应用。 定义3- 1 服务导航是指当前工作位置向迁移实例推 荐下一个合适的工作位置。 定义3- 2 部分可观测的迁移工作流环境pomwe是 一个三元组(sg,wv,bad), 其中,sg是迁移实例的寻航目 标,wv 是导航主体的业务熟人域;bad是导航主体的工作 流视图。 本节提供一种基于本体论(Ontology)的环境描述规 范,称为工作流环境描述规范(WorkflowEnvironment DescriptionCriterion,WEDC )。图3-1显示了WEDC 的 基本结构。 在部分可观测环境中,业务熟人所在的工作位置能够 提供的业务目标与寻航目标的关联度评价取决于导航主 体对业务熟人的能力及相关细节的观测。对于导航主体 而言,与寻航目标和导航结果相关的数据、信息以及工作 流的当前状态属于局部信息。导航主体形成自己的业务 熟人关系并触发导航行为,依赖对这些信息的观测与分 析,另外也受到工作流全局目标的约束。WEDC 通过机器 ·61· 面向目标的迁移工作流主动服务方法 ·62 · !!"#!$%&'"#$%& 第3章部分可观测环境下迁移工作流服务导航方法 可理解的方式,采用面向对象的方法描述观测结果。导 航主体对于环境中可观测的每个实体都是环境实体的子 类。WEDC定义了4个直接继承于环境实体的子实体: 寻航目标(navigationrequirement)、业务熟人(busines acquaintance)、工作流视图(workflowview)和目标关联度 评价(objectrelationappraisement)。 - 3 ifunctio 定义3寻航目标sg是一个三元组(d,{n}, {ufnto其中,d表示寻航目标的标识;{uctin} nucin}), ifno 表示寻航目标的功能属性集合;{unfunction}表示寻航目 标的非功能属性集合。 寻航目标表明了迁移实例的需求以及期望获得的服 务或资源,目的在于请求当前工作位置中的导航主体的导 航建议。 工作流视图是对工作流流程的抽象,用来支持工作流 的部分可见性。 定义3- 4 工作流视图wv是一个二元组(activity, date),其中,activity表示活动的集合;date是由基本过程 和活动得到的数据集合。 WEDC为导航主体定义了3个子类的业务熟人:BA_ Pa用于表示业务目标与之为泛化关系的熟人;BA_Ch指 代业务目标与之为特殊化的熟人;BA_Br指代业务目标与 之为平级的熟人。 目标关联评价是指根据寻航的需求,导航主体通过业 ·63· 务熟人的业务目标的支持度、能力自信度以及目标关联度 三个方面对导航方案进行评价,作为服务导航的依据。 结合图2-9自助旅游服务系统的例子,给出WEDC定 义的一个简单应用。以下自助旅游服务导航主体所收到 的一个寻航请求:4月30日到5月3日从北京出发,到济 南旅游,费用不超过3000元。给出该导航主体所观测到 环境实体的WEDC描述。 n1024 self-help travel plan april 30th to may 3 i plan from beijing to jinan tourism. departures destination date costs costs<=3000 元 …… ·64· 面向目标的迁移工作流主动服务方法 self-help travel services system provide self-help travel services ticket hotel insurance … …< /restrictions> ba1001
workstation ip
ticket father-child departure time return time fares ·65· 第3章 部分可观测环境下迁移工作流服务导航方法 ba1002
workstation ip
hotel father-child check-in time check-out time accommodation costs …< /business acquaintances> n1024 support self-confidence relation …< /navigation response> ·66· 面向目标的迁移工作流主动服务方法 第3章部分可观测环境下迁移工作流服务导航方法 3.部分可观测环境下的主动服务导航 3 人工智能领域中一项重要而长期的目标就是构造一 个具有在复杂环境中能自动完成指定任务能力的agent。 人工智能规划正是可以达成这个目标的重要方法之一。 它所研究的问题就是aent如何按照从环境中反馈回来 的信息采取相应的行动 g 。在这个规划框架下,agent与其 所处的环境是两个独立但又可以相互交互的部分。环境 可以描述为一个状态的集合,在某一时刻,agent可以通过 执行某一动作而改变环境的状态。同时,环境的反馈提供 了agent关于这种变化的信息。 决策论规划模型的核心就是所谓的马尔可夫决策过 程(MarkovDecisionProces,MDP),当一个规划问题用 MDP来建模的时候,问题的解就称为策略(policy)———行 动到状态的映射,即根据环境状态的反馈信息指出下一步 的行动。在MDP中,反馈信息实际上就是环境的状态。 agent所得到的是关于环境的精确信息,换言之,MDP是 完全可观测(completelyobservable)的。 而部分可观测的马尔可夫决策过程(PartialyObservableMarkovDecisionProceses,POMDP)则是 MDP的推广。与MDP一样,它假定行动的结果是非确定 性的,但与MDP不同的是,它认为agent从环境得回的反 ·67· 面向目标的迁移工作流主动服务方法 馈信息是不精确的,即只是部分可观测(partialy observable)的。在部分观察的情况下,不再可以直接根据 世界的状态选择行动,因此最多也就是根据观察知识来进 行行为决策。部分POMDP 为解决带有这种不确定性的 规划问题提供了数学框架。众所周知,即使是对于简单的 有限水平的POMDP 问题,找到一个最优解也是PSPACE(PolynomialSpace)难题,POMDP问题甚至比NP 完全问题还要难以解决。POMDP 自从被提出以来,在人 工智能和控制研究领域受到广泛关注,并且许多精确算法 随之被提出。 在面向目标的迁移工作流系统中,工作位置中管理、 执行服务导航的主体称为导航主体,它负责处理迁移实例 的寻航请求,然后实时地向迁移实例推荐下一个工作位 置,它所做的推介即称为导航策略。很自然地,导航系统 可以被描述为一个状态机,导航的状态由一些状态变量构 成,表示导航主体观察到的迁移实例的需求、推荐的结果 以及导航的历史等,状态转移则由导航主体的导航策略来 驱动。 面向目标的迁移工作流服务导航系统必须能在没有 全局业务流程知识、全面了解其他工作位置能够提供的服 务,以及不能准确理解迁移实例需求模型的情况下进行导 航。在用MDP模型来描述导航系统时,导航主体要知道 准确的系统状态,所以系统状态必须以导航主体的观察及 ·68 · 第3章部分可观测环境下迁移工作流服务导航方法 历史为基础,这就大大增加了建模的难度,而不确定性更 会导致系统状态很难准确定义。如何在导航主体得不到 准确的状态信息时寻找最优导航策略?部分可观测马尔 可夫决策过程为此提供了一个理论框架,导航策略可被 看作从某个观察到许多导航动作的概率分布的映射,同 时还需要记住前面的动作和观察来帮助区分不同的 状态。 3.部分可观测环境下的服务导航模型 3.1 在面向目标的迁移工作流系统中,导航主体负责预测 迁移实例下一步的迁移决策,实时地向迁移实例推介业务 熟人网的一个或多个服务主体。导航主体必须利用随机 环境中部分观察到的信息、历史动作序列和立即报酬值来 采用一种策略进行决策,为迁移实例进行导航。 定义3- 5 部分可观测环境的导航模型定义为六元组 z,t,m= s(s: ,a 表示工作流的状态集合 ,r,o), 其中: ,s={s1,sn s2,…,}; a={a2,…, a:导航主体的导航行动的集合,a1,an}; z:导航主体的观测集合,即迁移实例得到导航信息 后反馈的有限集合以及熟人网络的变化; t:s*a→s:状态转移函数,当导航主体在某一状态 s 执行导航后,根据观察得到迁移实例和业务熟人网络的反 馈,实现下一个状态s一般用t(a,s来 '概率分布, s,z,') ·69· 面向目标的迁移工作流主动服务方法 表示; r:s*a→r:导航主体所获得的报酬函数,是当前状 态下采用导航动作时所获得的报酬值,表示为r(a); s, o:s*a→PR(:表示导航主体采取导航行动 a 转 o) 移到状态s'时,观测函数 o 确定其在可能观测上的概率分 布,一般用O(a,表示。 s' ,o) 在面向目标的迁移工作流系统中,导航主体不能得到 完全的工作流状态信息,所以使用信念状态表示导航主体 所知道的工作流状态信息。 定义3- 6 信念状态表示的是导航主体对当前状态的 一种信念,是所有状态上的一个概率分布,使用b:1] S→[0, 来表示:b(表示处于状态s的概率,满足Σs) = 1。 s) b( s∈ S 在每个时间点,导航主体都要更新自己的信念状态。 根据Bayes原理,新信念状态为 b(s')sa,s,z,')s)/Po|a, =O( ' ,o)ΣT(a,sb(r(b) s∈ S 其中,Poa,为归一因子。 (3-1) r(|b) 评价函数为 b,=s)s,( ρ(a)Σb(R(a) 32) s∈ S 有了信念状态,导航主体的下一个信念状态和期望评 价只与当前的信念状态和导航行为有关,与历史导航动作 ·70· 第3章部分可观测环境下迁移工作流服务导航方法 和观察无关,满足马尔可夫属性。图3-2给出了导航主体 的部分可观测环境的导航模型,求解模型的方法转换为基 于信念状态的马尔可夫决策过程。 图3-2 部分可观测环境的导航模型 用值迭代求解信念MDP,可以采用近似算法Fib,在 当前时间点,部分可观测环境下的导航主体只能观测而不 知道确切的状态信息,但是从下个时间点开始,导航主体 将知道确切的状态信息,这样可以按照每个观察和每个状 态信息来挑选最佳向量α,如式(3-3)所示,而不是根据每 个观测和所有组合来挑选,其中γ为折扣因子,目的是让 期望值收敛。 a αi+1(=s,maxΣ s,z,') s)R(a)+γΣ T(a,s o∈ Z s'∈ S ·71· 面向目标的迁移工作流主动服务方法 a' O( ' ,o) i (') 33) sa,αs( 3.基于业务熟人网络的导航索生成 3.2 定义3- 7 导航索是指为迁移实例提供的一条迁移工 作流执行路径,由满足迁移实例寻航目标的多个工作位置 组成。 根据目标关联评价结果,导航主体可建立相应的导航 索。在规划导航索时,导航主体计算其业务熟人关系范围 内各工作位置的业务目标与寻航目标的关联度,故称为基 于业务熟人网络的导航索生成机制。 导航主体对寻航目标sg=(p1,p2,…,pn )和业务目 标bg=(p1,p2,…,pm )(pi 为目标中所定义的属性)进 行观测,计算目标支持度s。 定义3- 8 目标支持度s: s=same(sg,bg)/dif(sg,bg)-1 (3-4) 其中,same(sg,bg)表示两类目标中相同的属性个数; dif(sg,bg)表示属性中相异的属性个数。 设定一个阈值s,对于目标关联支持度大于 s 的均可 视为导航主体的业务熟人的业务目标对寻航目标具有一 定的支持性,由此得到一个与寻航目标相关的推荐集合, 结合导航主体对推介的业务熟人的能力自信度,进行目标 关联度的计算公式如下: 2 r2=Σ(n) Σ(m) (sij-scij)(3-5) i=1j=1 scij ·72 · 其中,n 表示寻航目标属性个数;m 表示业务目标属性个 数;sij是导航主体实际观测到的业务目标对寻航目标的支 持度;scij是导航主体关于其业务熟人能力自信度的计算, 在本书参考文献[47]中有详细的论述。该公式能够根据 目标支持相关信息,从当前的业务熟人网络得到较为准确 的与寻航目标有关联关系的特定业务熟人。 下面给出目标驱动的服务导航算法odsn,该算法实现 了导航主体的业务熟人网络内的导航。 算法3-1 目标驱动的服务导航(odsn)。 初始化阶段: do cbad(bg) //算法2-2 生成业务熟人网络; in 业务熟人网络 按熟人能力自信度降序排序; 设支持度阈值s 和关联度阈值r; 运行阶段: 导航索初始为null; {设置导航的期望状态为unsat; do {业务熟人网络内选取自信度最高的业务熟人; 若多个业务熟人自信度相同则随机选取一个; 计算s(sg,bg) //式(3-4) if (s(sg,bg)< s) //检测支持度是否小于阈值 业务熟人移入fail_list; ·73· 第3章 部分可观测环境下迁移工作流服务导航方法 //失败列表中的业务熟人在当前服务导航中 将不再被推介 else {设置导航的期望状态为sat; 计算目标关联度r(sg,bg) ; //式(3-5) } if(r(sg,bg) < r) //检测关联度是否小于阈值 {更新能力自信度; 将满足条件的业务熟人插入的导航索中; } }while(导航的期望状态= = unsat or 熟人网络! = 失 败列表); if(导航的期望状态= = sat) return(导航索); else return(null); } 算法分为两个阶段:初始化阶段和运行阶段。初始 化阶段待选业务熟人按能力自信度降序排序。初始阶段 仅在系统部署的时候运行一次。运行阶段在每次接收到 寻航请求时调用,以选择关联度最高的业务熟人参与导航 索。该算法在最坏情况下的时间复杂度为O (n×m )(n 为候选业务熟人的数量;m 为寻航目标中的属性个数),最 坏情况是指没有满足需求业务熟人参与导航索。 ·74· 面向目标的迁移工作流主动服务方法 第3章部分可观测环境下迁移工作流服务导航方法 3.验证与分析 4 为了验证本章所提出的目标驱动的服务导航算法能 够有效保证面向目标迁移工作流主动服务的可靠性,实验 以第2章建立的自助旅游服务系统为应用背景。本节设 计了两个实验,对比参考文献[100]中的服务导航算法和 目标驱动的服务导航算法odsn在部分可观测环境下迁移 工作流执行的效果,主要以工作流服务导航成功率为性能 指标进行验证。 在自助旅游服务系统中,旅游者寻航目标产生的同时 从迁移工作流中“变化”相同数量的工作流视图子目标,变 化的数量占总工作流视图数量的10% 。工作流视图因主 观因素或者客观原因不可完全观测,从图3-3可以看出在 工作流子目标产生与消失比较频繁的情况下,本章提出的 目标驱动的导航算法odsn具有较大优势,执行成功率比 一般导航算法服务导航成功率高很多。 由图3-4所示,目标驱动的导航算法odsn刚开始运行 时,由于业务熟人网络还未建立完善,基于业务熟人网络 的服务导航的成功率并无优势,但是随着时间的推进,业 务熟人网络逐步完善,服务导航的成功率也随之上升,而 未考虑业务熟人关系的导航无此特性。 ·75· 面向目标的迁移工作流主动服务方法 图3-3 部分可观测环境下服务导航的成功率比较 图3-4 随时间变化的服务导航成功率比较 ·76·