基于G-KRA模型框架的工作流建模*
2013-12-03孙善武
王 楠, 孙 利, 孙善武, 李 慧
(1. 吉林财经大学 管理科学与信息工程学院, 长春 130117;2. 吉林财经大学 物流产业经济与智能物流省重点实验室, 长春 130117;3. 吉林大学 通信与工程学院, 长春 130012;4. 吉林大学 符号计算与知识工程教育部重点实验室, 长春 130012; 5. 吉林广播电视大学, 长春 130022)
工作流是整体或部分上的商业过程自动化, 在工作流执行期间, 文档、 信息或任务根据一个过程化的规则集从一个参与者传递到另一个参与者[1]. 对于工作流的执行, 构建一个定义好的工作流模型时十分重要. 在开发工作流管理系统(workflow management system, WfMS)的过程中, 目前已提出了很多探索描述商业过程的形式化方法[2-3], 同时也从不同角度分析了工作流的建模过程[4-5], 并基于各种模型框架构造了工作流模型[6], 但这些方法都没有给出一个一般的、 统一的抽象框架形式化地表示工作流建模过程. 抽象是人类感知、 概念化和推理的普遍行为. 在人工智能领域内的抽象问题目前已有许多研究结果, 如问题求解[7-8]、 问题重构[9]、 机器学习[10]和基于模型的诊断[11]等. 文献[12-15]提出了表示改变的模型, 既包括语法重构也包括抽象过程, 该模型称为KRA模型(knowledge reformulation and abstraction, KRA), 设计帮助问题的概念化阶段及抽象算子的自动应用过程. 文献[16-17]已将KRA模型引入到形式化工作流抽象建模的过程中, 将工作流作为一个“感知-抽象”的迭代学习过程. 与KRA模型相比, 广义KRA模型(genera KRA model, G-KRA)[18]在表示客观世界时更一般和灵活, 它可从不同的抽象粒度表示世界.
本文给出了基于G-KRA模型的工作流建模过程, 根据功能知识引入功能感知的概念, 自动构造工作流抽象对象库WfOa. 构建基本行为感知和WfOa中的基于功能的工作流抽象对象之间的映射关系实现基本行为感知与相应映射的替换过程. 通过这些映射关系, 生成了基于功能的抽象模型, 简化了基本工作流模型的表示并帮助实现对应的分层推理.
1 广义KRA模型
定义1[18]一个基本感知P是一个五元组, 即P=(OBJ,ATT,FUNC,REL,OBS), 其中: OBJ包含W中的对象类型; ATT表示对象属性的类型; FUNC确定一个函数集; REL是对象类型间的关系集合.
图1 G-KRA模型框架Fig.1 G-KRA model framework
定义2[18]令P是一个基本感知,A是一个感知者,Oa是一个数据库且Oa中具有某种抽象类型的对象由A预先定义, 则A的一个抽象感知定义为P*=δa(P,Oa), 其中δa表示抽象感知映射.
定义3[18]给定基本感知P、 抽象对象库Oa和抽象感知映射δa, 则一个广义表示框架R*是一个四元组(P*,D*,L*,T*), 其中:P*=δa(P,Oa)表示一个抽象感知;D*表示数据库;L*表示语言;T*表示理论.
数据库Oa是某些抽象对象构成的相当一般化的集合, 可在某个特定的世界中实现具体化. 在G-KRA模型框架下构造抽象模型的过程如图1所示.
2 工作流建模
本文先基于文献[19]提出几个概念, 然后给出一个过程GeneWfOa表示基于功能的工作流抽象对象库WfOa的生成过程. 构造了基本行为感知和基于功能的工作流抽象对象库WfOa之间的映射关系, 最后用相应的映射替换基本行为感知, 生成了给予功能的工作流抽象模型, 并引入文献[16]中的工作流实例描述提出的概念和建模结果.
定义4[19]一个基本行为感知ActP是一个五元组, 即PriActP=(PriActType,PriAgentsType,PriResourceIN,PriResourceOUT,PriConds), 其中: PriActType表示行为类型; PriAgentsType表示该行为参与者的类型; PriResourceIN是该行为处理的资源类型; PriResourceOUT是通过执行该行为生成的结果资源; PriConds表示行为得以执行的约束条件.
基本行为感知与文献[19]中的行为感知构造过程相同, 通过使用基本知识直观地确定了所感知到的工作流Wf的基本模型. 要注意从某些特定领域中相同工作流获得的信息根据基于本体和约束条件的不同而不同.
定义5[19]假设PriActP1和PriActP2是两个基本行为感知, 则它们之间的关系定义为一个四元组PriActRelP=(PriActP1,PriActP2,PriActRelType,PriActRelConds), 即表示当条件集合PriActRelConds中包含的条件成立时, PriActP1和PriActP2之间拥有类型为PriActRelType的关系. 与行为关系感知类似, 可使用如下表示理解基本行为关系感知PriActRelP的定义:
该表示说明了两个基本行为感知之间的执行顺序, 根据文献[19], PriActP1的输入资源PriResourceIN可定义为PriActRelP的输入资源, 而PriActP2的输出资源PriResourceOUT可定义为PriActRelP的输出资源.
引入两个标识符: START和END, 表示基本工作流感知的起始行为感知和终止行为感知, 详细内容可参考文献[19]. 为了构造抽象工作流行为库, 引入功能感知的概念表示基本行为感知和基本行为关系感知的行为抽象.
定义7[19]一个功能感知是对一个行为感知或一个行为关系感知所完成的动作的抽象描述, 用形式FuncName(ResType1,ResType2)表示, 即功能感知FuncName处理资源ResType1, 同时生成结果资源ResType2.
基于功能的工作流抽象对象库WfOa定义为由不同功能感知构成的集合, 该集合可手动预生成或通过自动推导得出.
G-KRA模型中定义抽象对象时丢弃了对象的一些属性信息, 但本文中定义的基于功能的工作流抽象对象库WfOa中功能感知基于功能知识生成, 并可根据它们所处理的资源类型而自动推导生成. 本文用算法GeneWfOa表示基于功能的工作流抽象对象库WfOa的生成过程. 虽然这样生成的功能感知非常一般, 语义信息很弱, 但却可极大简化模型表示, 并完全保证推理能力不受损失. 也可用更复杂的表示, 根据真实的功能语义信息手工定义功能感知.
Procedure GeneWfOa
Input a specific workflow perception WfP; //假设S表示被感知工作流WfP 处理的可区分类型资源的集合, 每个行为感知只有一个输入资源和一个输出资源
S={ }; //S是通过对WfP 中的行为感知分类自动构造生成的集合
For every activity perception ActPi∈WfP{
If (TYPEIN(ActPi)∉S)S+=TYPEIN(ActPi);
If (TYPEOUT(ActPi)∉S)S+=TYPEOUT(ActPi);
} // TYPEIN(ActPi)和TYPEOUT(ActPi)分别表示ActPi处理的输入/输出资源类型
k=1;
For(i=1;i≤|S|;i++)
For(j=1;j≤|S|;j++)//|S|表示S中不同资源类型的数量
WfOa+=Fk(Si,Sj); //Si,Sj∈S,Fk定义为输入资源为Si, 输出资源为Sj的抽象功能感知
假设WfP中行为感知数量为n, 不同类型的资源数量为m, 则算法GeneWfOa从渐近意义上的复杂性可表示为max{n,m2}×O(1), 生成m2个功能感知.
例1本文以文献[20]中的工作流“Write travel report”为例, 基本工作流模型可如文献[16]中描述的过程生成, 结果如图2所示.
图2 “Write travel report”的基本工作流模型Fig.2 Primary workflow model priWfM of write travel report
图2中的基本行为感知描述如下:
PriAct1=(WriteReport,Employee,TravelResource,Report,{ });
PriAct2=(RequestDetails,Employee,Report,Report,{if needed Details});
PriAct3=(ProvideDetails,Sectary,Report,Detail,{if has details});
PriAct4=(FillInDetails,Employee,Detail,Report,{if has details});
PriAct5=(SubmitReport,Employee,Report,Report,{if not need details});
PriAct6=(CheckAndSign,{Manager,Vice Manager},Report,Report,{if no objections});
PriAct7=(CheckAndSubmitObjections,Manager,Report,Objections,{if has objections});
PriAct8=(ReceiveObjection,Employee,Objections,Objections,{ });
PriAct9=(ReviseReport,Employee,Objections,Report,{if has objections}).
根据算法GeneWfOa, 首先生成图2中工作流的不同资源类型, 即{REPORT,INFO,ADVICE}, 然后根据行为处理的资源类型得到功能感知集合作为基于功能的工作流抽象对象库WfOa:F1(REPORT,INFO),F2(REPORT,ADVICE),F3(INFO,REPORT),F4(INFO,ADVICE),F5(ADVICE,REPORT),F6(ADVICE,INFO),F7(REPORT,REPORT),F8(INFO,INFO),F9(ADVICE,ADVICE).
本文先构造基本行为感知集合与WfOa中的基于功能的工作流抽象对象之间的映射关系, 再用相应的映射关系替换PriWfM中的基本行为感知, 生成基于功能的抽象模型AbsWfM, 该过程用算法GeneAbsWfM描述. 通过基本行为感知集合与WfOa之间的映射关系, 可简化基本工作流模型的表示.
Procedure GeneAbs WfM//假设PriActS是包含在基本工作流模型PriWfM中的基本行为感知集合
For every primary activity perception PriActiin PriActS
if (∃Fk∈WfOaand the types of the input and output resources ofFkmatch with that of PriActi){
MappingS+=Mi(PriActi,Fk);
Replace PriActiin PriWfM withMi;
}
显然, 通过分析算法GeneAbsWfM可将渐近的时间复杂性表示为O(nm2), 其中n和m含义与前面定义相同.
例2根据算法GeneAbsWfM, 可生成例1中构造的基本行为感知集合PriActS与WfOa之间的映射关系, 同时进一步生成图2中工作流“write travel report”基于功能的抽象模型AbsWfM. PriActS与WfOa之间的映射关系如图3所示. 工作流“write travel report”基于功能的抽象模型AbsWfM如图4所示.
图3 PriActS与WfOa之间的映射关系Fig.3 Mapping relations between PriActS and WfOa
图4 基于功能的抽象模型AbsWfMFig.4 Function-based abstraction model AbsWfM
综上可见, 本文提出了基于G-KRA模型的工作流建模过程, 并根据功能知识引入功能感知的概念, 自动生成了工作流抽象对象库WfOa. 虽然生成的功能感知非常一般, 语义信息较弱, 但能极大简化模型表示, 并能完全保证模型的推理能力.
[1] WfMC. Workflow Management Coalition Terminology & Glossary, Document Number WFMC-TC-1011 [R]. Brussels, Belgium: Workflow Management Coalition, 1999.
[2] Salimifard K, Wright M. Petri Net-Based Modeling of Workflow Systems: An Overview [J]. European Journal of Operational Research, 2001, 134(3): 664-676.
[3] Bajaj A, Ram S. SEAM. A State-Entity-Activity-Model for a Well-Defined Workflow Development Methodology [J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(2): 415-431.
[4] Aalst W M P, Van Der, Hee K M, Van. Workflow Management-Models, Methods, and Systems [M]. London: MIT Press, 2002.
[5] Tick J. Workflow Model Representation Concepts [C]//Proceedings of 7th International Symposium of Hungarian Researchers on Computational Intelligence. Budapest, Hungary: IEEE, 2006: 329-337.
[6] Tick J. Workflow Modeling Based on Process Graph [C]//Proceedings of 5th Slovakian-Hungarian Joint Symposium on Applied Machine Intelligence and Informatics. Poprad, Slovakia: IEEE, 2007: 419-426.
[7] Ellman T. Synthesis of Abstraction Hierarchies for Constraint Satisfaction by Clustering Approximatively Equivalent Objects [C]//Proceedings of International Conference on Machine Learning. Washington: MA, 1993: 104-111.
[8] Holte R, Mkadmi T, Zimmer R, et al. Speeding Up Problem-Solving by Abstraction: A Graph-Oriented Approach [J]. Art Intelligence, 1996, 85: 321-361.
[9] Subramanian D. A Theory of Justified Reformulations [C]//Change of Representation and Inductive Bias. Boston: Kluwer Academic Publishers, 1990: 147-167.
[10] Bredeche N, SHI Zhong-zhi, Zucker J D. Perceptual Learning and Abstraction in Machine Earning: An Application to Autonomous Robotics [J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 2006, 36(2): 172-181.
[11] Chittaro L, Ranon R. Hierarchical Model-Based Diagnosis Based on Structural Abstraction [J]. Art Intell, 2004, 155(1/2): 147-182.
[12] Saitta L, Zucker J. Semantic Abstraction for Concept Representation and Learning [C]//Proceedings of SARA. California: Springer, 1998: 103-120.
[13] Saitta L, Zucker J D. A Model of Abstraction in Visual Perception [J]. Applied Artificial Intelligence, 2001, 5(8): 761-776.
[14] Saitta L, Zucker J. Abstraction and Complexity Measures [C]//Proceedings of SARA. Whistler: Springer, 2007: 375-390.
[15] Saitta L, Torasso P, Torta G. Formalizing the Abstraction Process in Model Based Diagnosis [C]//Proceeding of SARA. Whistler: Springer, 2007: 314-328.
[16] WANG Nan, SUN Shan-wu. Workflow Modeling Process: A Novel Perspective [J]. International Journal of Digital Content Technology and Its Applications, 2011, 5(7): 455-468.
[17] SUN Shan-wu, WANG Nan, ZHANG Fu-wei. Ontology-Based Workflow Abstraction Modeling [J]. Journal of Jilin University: Science Edition, 2012, 50(2): 299-304. (孙善武, 王楠, 张福威. 基于本体的工作流抽象模型 [J]. 吉林大学学报: 理学版, 2012, 50(2): 299-304.)
[18] SUN Shan-wu, WANG Nan, OUYANG Dan-tong. General KRA Abstraction Model [J]. Journal of Jilin University: Science Edition, 2009, 47(3): 537-542. (孙善武, 王楠, 欧阳丹彤. 广义KRA抽象模型 [J]. 吉林大学学报: 理学版, 2009, 47(3): 537-542.)
[19] WANG Nan, SUN Shan-wu. Formalizing the Process of Hierarchical Workflow Abstraction Modeling [J]. Journal of Convergence Information Technology, 2011, 6(6): 98-105.
[20] Hallvard Trtteberg. Modeling Work: Workflow and Task Modeling [C]//Proceedings of the Third International Conference on Computer-Aided Design of User Interfaces. Norwell: Kluwer Academic Publishers, 1999: 275-280.