王 楠, 孫 利, 孫善武, 李 慧

(1. 吉林財經(jīng)大學(xué) 管理科學(xué)與信息工程學(xué)院, 長春 130117；2. 吉林財經(jīng)大學(xué) 物流產(chǎn)業(yè)經(jīng)濟與智能物流省重點實驗室, 長春 130117；3. 吉林大學(xué) 通信與工程學(xué)院, 長春 130012；4. 吉林大學(xué) 符號計算與知識工程教育部重點實驗室, 長春 130012; 5. 吉林廣播電視大學(xué), 長春 130022)

工作流是整體或部分上的商業(yè)過程自動化, 在工作流執(zhí)行期間, 文檔、 信息或任務(wù)根據(jù)一個過程化的規(guī)則集從一個參與者傳遞到另一個參與者[1]. 對于工作流的執(zhí)行, 構(gòu)建一個定義好的工作流模型時十分重要. 在開發(fā)工作流管理系統(tǒng)(workflow management system, WfMS)的過程中, 目前已提出了很多探索描述商業(yè)過程的形式化方法[2-3], 同時也從不同角度分析了工作流的建模過程[4-5], 并基于各種模型框架構(gòu)造了工作流模型[6], 但這些方法都沒有給出一個一般的、 統(tǒng)一的抽象框架形式化地表示工作流建模過程. 抽象是人類感知、 概念化和推理的普遍行為. 在人工智能領(lǐng)域內(nèi)的抽象問題目前已有許多研究結(jié)果, 如問題求解[7-8]、 問題重構(gòu)[9]、 機器學(xué)習(xí)[10]和基于模型的診斷[11]等. 文獻(xiàn)[12-15]提出了表示改變的模型, 既包括語法重構(gòu)也包括抽象過程, 該模型稱為KRA模型(knowledge reformulation and abstraction, KRA), 設(shè)計幫助問題的概念化階段及抽象算子的自動應(yīng)用過程. 文獻(xiàn)[16-17]已將KRA模型引入到形式化工作流抽象建模的過程中, 將工作流作為一個“感知-抽象”的迭代學(xué)習(xí)過程. 與KRA模型相比, 廣義KRA模型(genera KRA model, G-KRA)[18]在表示客觀世界時更一般和靈活, 它可從不同的抽象粒度表示世界.

本文給出了基于G-KRA模型的工作流建模過程, 根據(jù)功能知識引入功能感知的概念, 自動構(gòu)造工作流抽象對象庫WfOa. 構(gòu)建基本行為感知和WfOa中的基于功能的工作流抽象對象之間的映射關(guān)系實現(xiàn)基本行為感知與相應(yīng)映射的替換過程. 通過這些映射關(guān)系, 生成了基于功能的抽象模型, 簡化了基本工作流模型的表示并幫助實現(xiàn)對應(yīng)的分層推理.

1 廣義KRA模型

定義1[18]一個基本感知P是一個五元組, 即P=(OBJ,ATT,FUNC,REL,OBS), 其中: OBJ包含W中的對象類型; ATT表示對象屬性的類型; FUNC確定一個函數(shù)集; REL是對象類型間的關(guān)系集合.

圖1 G-KRA模型框架Fig.1 G-KRA model framework

定義2[18]令P是一個基本感知,A是一個感知者,Oa是一個數(shù)據(jù)庫且Oa中具有某種抽象類型的對象由A預(yù)先定義, 則A的一個抽象感知定義為P*=δa(P,Oa), 其中δa表示抽象感知映射.

定義3[18]給定基本感知P、 抽象對象庫Oa和抽象感知映射δa, 則一個廣義表示框架R*是一個四元組(P*,D*,L*,T*), 其中:P*=δa(P,Oa)表示一個抽象感知;D*表示數(shù)據(jù)庫;L*表示語言;T*表示理論.

數(shù)據(jù)庫Oa是某些抽象對象構(gòu)成的相當(dāng)一般化的集合, 可在某個特定的世界中實現(xiàn)具體化. 在G-KRA模型框架下構(gòu)造抽象模型的過程如圖1所示.

2 工作流建模

本文先基于文獻(xiàn)[19]提出幾個概念, 然后給出一個過程GeneWfOa表示基于功能的工作流抽象對象庫WfOa的生成過程. 構(gòu)造了基本行為感知和基于功能的工作流抽象對象庫WfOa之間的映射關(guān)系, 最后用相應(yīng)的映射替換基本行為感知, 生成了給予功能的工作流抽象模型, 并引入文獻(xiàn)[16]中的工作流實例描述提出的概念和建模結(jié)果.

定義4[19]一個基本行為感知ActP是一個五元組, 即PriActP=(PriActType,PriAgentsType,PriResourceIN,PriResourceOUT,PriConds), 其中: PriActType表示行為類型; PriAgentsType表示該行為參與者的類型; PriResourceIN是該行為處理的資源類型; PriResourceOUT是通過執(zhí)行該行為生成的結(jié)果資源; PriConds表示行為得以執(zhí)行的約束條件.

基本行為感知與文獻(xiàn)[19]中的行為感知構(gòu)造過程相同, 通過使用基本知識直觀地確定了所感知到的工作流Wf的基本模型. 要注意從某些特定領(lǐng)域中相同工作流獲得的信息根據(jù)基于本體和約束條件的不同而不同.

定義5[19]假設(shè)PriActP1和PriActP2是兩個基本行為感知, 則它們之間的關(guān)系定義為一個四元組PriActRelP=(PriActP1,PriActP2,PriActRelType,PriActRelConds), 即表示當(dāng)條件集合PriActRelConds中包含的條件成立時, PriActP1和PriActP2之間擁有類型為PriActRelType的關(guān)系. 與行為關(guān)系感知類似, 可使用如下表示理解基本行為關(guān)系感知PriActRelP的定義：

該表示說明了兩個基本行為感知之間的執(zhí)行順序, 根據(jù)文獻(xiàn)[19], PriActP1的輸入資源PriResourceIN可定義為PriActRelP的輸入資源, 而PriActP2的輸出資源PriResourceOUT可定義為PriActRelP的輸出資源.

引入兩個標(biāo)識符： START和END, 表示基本工作流感知的起始行為感知和終止行為感知, 詳細(xì)內(nèi)容可參考文獻(xiàn)[19]. 為了構(gòu)造抽象工作流行為庫, 引入功能感知的概念表示基本行為感知和基本行為關(guān)系感知的行為抽象.

定義7[19]一個功能感知是對一個行為感知或一個行為關(guān)系感知所完成的動作的抽象描述, 用形式FuncName(ResType1,ResType2)表示, 即功能感知FuncName處理資源ResType1, 同時生成結(jié)果資源ResType2.

基于功能的工作流抽象對象庫WfOa定義為由不同功能感知構(gòu)成的集合, 該集合可手動預(yù)生成或通過自動推導(dǎo)得出.

G-KRA模型中定義抽象對象時丟棄了對象的一些屬性信息, 但本文中定義的基于功能的工作流抽象對象庫WfOa中功能感知基于功能知識生成, 并可根據(jù)它們所處理的資源類型而自動推導(dǎo)生成. 本文用算法GeneWfOa表示基于功能的工作流抽象對象庫WfOa的生成過程. 雖然這樣生成的功能感知非常一般, 語義信息很弱, 但卻可極大簡化模型表示, 并完全保證推理能力不受損失. 也可用更復(fù)雜的表示, 根據(jù)真實的功能語義信息手工定義功能感知.

Procedure GeneWfOa

Input a specific workflow perception WfP; //假設(shè)S表示被感知工作流WfP 處理的可區(qū)分類型資源的集合, 每個行為感知只有一個輸入資源和一個輸出資源

S={ }; //S是通過對WfP 中的行為感知分類自動構(gòu)造生成的集合

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中不同資源類型的數(shù)量

WfOa+=Fk(Si,Sj); //Si,Sj∈S,Fk定義為輸入資源為Si, 輸出資源為Sj的抽象功能感知

假設(shè)WfP中行為感知數(shù)量為n, 不同類型的資源數(shù)量為m, 則算法GeneWfOa從漸近意義上的復(fù)雜性可表示為max{n,m2}×O(1), 生成m2個功能感知.

例1本文以文獻(xiàn)[20]中的工作流“Write travel report”為例, 基本工作流模型可如文獻(xiàn)[16]中描述的過程生成, 結(jié)果如圖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}).

根據(jù)算法GeneWfOa, 首先生成圖2中工作流的不同資源類型, 即{REPORT,INFO,ADVICE}, 然后根據(jù)行為處理的資源類型得到功能感知集合作為基于功能的工作流抽象對象庫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).

本文先構(gòu)造基本行為感知集合與WfOa中的基于功能的工作流抽象對象之間的映射關(guān)系, 再用相應(yīng)的映射關(guān)系替換PriWfM中的基本行為感知, 生成基于功能的抽象模型AbsWfM, 該過程用算法GeneAbsWfM描述. 通過基本行為感知集合與WfOa之間的映射關(guān)系, 可簡化基本工作流模型的表示.

Procedure GeneAbs WfM//假設(shè)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可將漸近的時間復(fù)雜性表示為O(nm2), 其中n和m含義與前面定義相同.

例2根據(jù)算法GeneAbsWfM, 可生成例1中構(gòu)造的基本行為感知集合PriActS與WfOa之間的映射關(guān)系, 同時進(jìn)一步生成圖2中工作流“write travel report”基于功能的抽象模型AbsWfM. PriActS與WfOa之間的映射關(guān)系如圖3所示. 工作流“write travel report”基于功能的抽象模型AbsWfM如圖4所示.

圖3 PriActS與WfOa之間的映射關(guān)系Fig.3 Mapping relations between PriActS and WfOa

圖4 基于功能的抽象模型AbsWfMFig.4 Function-based abstraction model AbsWfM

綜上可見, 本文提出了基于G-KRA模型的工作流建模過程, 并根據(jù)功能知識引入功能感知的概念, 自動生成了工作流抽象對象庫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]. 吉林大學(xué)學(xué)報: 理學(xué)版, 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]. 吉林大學(xué)學(xué)報: 理學(xué)版, 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.