Computing alignments with constraint programming : the acyclic case

Compu ing Alignmen s wi h Cons ain P og amming: The Acyclic Case Ma ´ıa Te esa G´omez-L´opez1, Diana Bo ego1, Josep Ca mona2, Ra ael M. Gasca1 1Uni e sidad de Se illa, Se ille, Spain, {may egomez,dianabn,gasca}@us.es 2Uni e si a Poli `ecnica de Ca alunya, Ba celona, Spain, [email p o ec ed] Abs ac . Con o mance checking con on s p ocess models wi h eal p ocess execu ions o de ec and measu e de ia ions be ween modelled and obse ed beha iou . The co e echnique o con o mance checking is he compu a ion o an alignmen . Cu en app oaches o alignmen compu a ion ely on a sho es -pa h echnique o e he p oduc o he s a e-space o a model and he obse ed ace, hus suffe ing om he well-known s a e explosion p oblem. This pape p esen s a esh al e na- i e o alignmen compu a ion o acyclic p ocess models, ha encodes he alignmen p oblem as a Cons ain Sa is ac ion P oblem. Since mod- e n sol e s o his amewo k a e capable o dealing wi h la ge ins ances, his con ibu ion has a clea po en ial. Rema kably, ou p o o ype imple- men a ion can handle ins ances ha ep esen a eal challenge o cu en echniques. Main ad an ages o using Cons ain P og amming pa adigm lie in he possibili y o adap pa ame e s such as he maximum sea ch ime, o he maximum misalignmen allowed. Mo eo e , using sea ch and p opaga ion algo i hms inco po a ed in Cons ain P og amming Sol e s pe mi s o find solu ions o p oblems unsol able wi h o he echniques. Keywo ds: Con o mance Checking, Cons ain P og amming 1 In oduc ion Nowadays o ganiza ions analyze and use he huge amoun o da a ha hei in o ma ion sys ems gene a e. This da a ep esen s an impo an sou ce o in- o ma ion, since i con ains many o he e idences an o ganiza ion may need o know in o de o each i s (business) goals. Among o he s pe spec i es, he ocus on he p ocess dimension is o pa amoun impo ance. P ocess mining has e ol ed in he las decade o ac as a mee ing poin be- ween da a and p ocess science. Techniques in p ocess mining enable he disco - e y o e idence-based p ocess models, he con o mance analysis and he enhance- men o p ocess models. Con o mance analysis, which is he opic conside ed in his pape , s udies he adequacy o a p ocess model in desc ibing he eal beha - io obse ed as a collec ion o aces deno ing he oo p in s o he execu ion o 96 a p ocess. While he e exis se e al echniques o disco e y and enhancemen o p ocess models, he cu en ew echniques a ailable o con o mance analysis a e no ye sa is ac o y. In his pape we ackle a cen al p oblem in con o mance analysis: he com- pu a ion o an alignmen be ween a p ocess model and an e en log. In o mally, an alignmen is a wo- ow ma ix whe e he fi s ow deno es he s eps in he obse ed ace, while he second ow desc ibes he s eps pe o med by he model in o de o fi as much as possible he ace. Alignmen s a e c ucial o e alua e he impo an me ics in con o mance, i.e., fi ness and gene aliza ion [2] and p ecision [3]. We de ia e om he cu en app oaches o alignmen compu a ion, which a e based on s a e-space explo a ions o models. Ins ead, we encode he p oblem o compu ing alignmen s as a Cons ain Sa is ac ion P oblem (CSP), and use a CSP sol e o compu e alignmen s. The CSP amewo k b ings many ad an ages when compa ed o he s a e-o - he-a app oaches o con o mance analysis: a po olio o a ailable sea ch echniques, na u al encoding o ce ain model con- s uc s, capabili y o handling la ge ins ances, abili y o in e ac wi h he sol e o ob ain alid solu ions, e c. In his pape we conside he compu a ion o alignmen s o acyclic p o- cess models. In spi e o his model es ic ion, cu en echniques may s ill ha e p oblems o handle ce ain ins ances, as i was demons a ed in [14]. In ou p o o ype implemen a ion, we show how he app oach p esen ed in his pape may be a solid al e na i e when cu en app oaches ail a de i ing an alignmen . This pape is o ganized as ollows: in Sec ion 2 a b ie in oduc ion o Con- s ain P og amming is p o ided, since i is he basis o he encoding p esen ed in he es o he pape . Then in Sec ion 3 he encoding is shown, oge he wi h u he ex ensions o op imize he compu a ion o alignmen s. Then in Sec ion 4 some he esul s on some ins ances om he li e a u e a e epo ed. Finally, Sec ion 6 p o ides he cu en con ex o con o mance analysis and Sec ion 7 concludes and discusses cu en esea ch di ec ions. 2 Cons ain P og amming A CSP ep esen s a easoning amewo k consis ing o a iables, domains and cons ain s, whe e he model is desc ibed decla a i ely. Fo mally, i is defined as a uple X,D,C,whe eX={x1,...,xn}is a fini e se o a iables, D={d(x1), ...,d(xn)}is a se o domains o he alues o he a iables, and C={C1,..., Cm}is a se o cons ain s. Each cons ain Ciis defined as a ela ion Ron a subse o a iables V={xi,xj,...,xl}, called he cons ain scope.The ela ion Rmay be ep esen ed as a subse o he Ca esian p oduc d(xi)×d(xj)×... ×d(xl). A cons ain Ci=(Vi,Ri) simul aneously specifies he possible alues o he a iables in V ha sa is y R.Le Vk={xk1,...,xkl}be a subse o X, and an l- uple (xk1,...,xkl) omd(xk1), ...,d(xkl) can he e o e be called an 97 ins an ia ion o he a iables in Vk. An ins an ia ion is a solu ion i and only i i sa isfies he cons ain s C. In o de o sol e a CSP, a combina ion o sea ch and consis ency echniques is commonly used [8][4]. The consis ency echniques emo e inconsis en alues om he domains o he a iables du ing o be o e he sea ch. Du ing he sea ch, a p opaga ion p ocess is execu ed which analyses he combina ion o alues o a iables whe e he cons ain s a e sa isfiable. Se e al local consis ency and op- imiza ion echniques ha e been p oposed as ways o imp o ing he efficiency o sea ch algo i hms. When i is no only necessa y o asce ain i a solu ion can be ound, and i is impo an o find he bes solu ion, a Cons ain Op imiza ion P oblem (COP) can be c ea ed and sol ed. A COP is a CSP wi h an op imiza ion unc ion whe e only he uple o possible alues ha op imize his unc ion is de e mined as he solu ion o he COP. Cons ain P og amming has al eady been used o compa e expec ed and obse ed beha iou o diagnose models acco ding obse a ions, and i has also been applied o business p ocess models [9, 11, 5]. A simple example o illus a e he usage o a CSP can be ound o ep esen he possible execu ion o de o he ac i i ies o a model. Imagine a model whe e ac i i y A mus be execu ed fi s , and ac i i ies B o C mus be execu ed a e , bu no bo h. Va iables modA,modB,modCcan be used o ob ain he possible execu ion momen s. And he cons ain s should ep esen ha (1) A mus be execu ed, (2) B o C mus be execu ed (bu only one), and (3) i B o C a e execu ed, his will happen a e he execu ion o A. modA,modB,modCin he domain {0..n}//{0..model.size()} modA>0 AND (modB>0XORmodC>0) AND i (modB=0) hen (modB>modA) i (modC=0) hen (modC>modA) Wi h his CSP, some solu ions p o ided by a cons ain sol e would be: sol1: modA=1, modB=2, modC=0 sol2: modA=1, modB=0, modC=2 sol3: modA=1, modB=3, modC=0 ... An example o op imiza ion unc ion can be o minimize(modA+modB+ modC). In his case only sol1 is ob ained. 3 Alignmen Compu a ion wi h Cons ain P og amming In his pape we p opose o encode by means o a CSP he cons ain s ha de- sc ibe he possible execu ion o de o he ansi ions in a Pe i ne ( he expec ed beha iou ), and he o de o he ansi ion in he logs (obse ed beha iou ) ol- lowing model-based diagnosis pa adigm [10]. The COP will find he minimum misalignmen be ween he obse ed and he expec ed ansi ions. The encoding consis s in he c ea ion o wo se s o a iables ha ep esen , espec i ely, he 98 Pe i ne model (se called Va -Model), and he eal obse ed beha iou eg- is e ed in each case o he e en log (se called Va -Log). These wo se s ha e he same numbe o a iables, since hey a e composed o all ac i i ies in he model, plus all ac i i ies appea ing in he e en log bu no in he model. Fo he alignmen compu a ion, he cons ain s ha ep esen he model a e de e mined once, while he cons ain s ha ep esen he e en log depend on each case. Conside ing all hese ac i i ies, hese wo se s o a iables ep esen he s ep o de whe e each ac i i y ( ansi ion in he Pe i ne ) can be execu ed ollow- ing he model (Va -Model) o in acco dance o he e en log (Va -Log ). I i is possible o assign he same alue o e e y a iable in Va -Model and Va -Log,i implies ha he e is a o al alignmen be ween he model and he eali y. This way, in o de o model bo h sequences o ac i i ies (i.e. modelled and obse ed beha iou ), each a iable is modelled as an in ege ha is e alua ed in acco - dance wi h he posi ion ha i akes in he execu ion o de . Then, he posi ions assigned o each ac i i y in he modelled (Va -Model) and expec ed (Va -Log ) beha iou s a e compa ed o de e mine whe he some e en wi hin a case in he e en log is misaligned. 3.1 Modelling he Va iables o ep esen he Pe i Ne As men ioned, he expec ed and obse ed occu ences o ac i i ies should be modelled wi hin he CSP, so ha he modelled and obse ed sequences o exe- cu ion o ac i i ies can be compa ed. The e o e, ce ain se s o a iables should be pa o he CSP, wi h he ollowing meanings: –Va -Model: Se o decision a iables {moda,modb,...,modn} ep esen ing he posi ion ha all ac i i ies a,b,...,n ake in he expec ed execu ion o de , whose domains a e In ege s in 0..n,beingn he numbe o ansi ions plus he log size -i.e. he wo s possible alue o alignmen -. –Va -Log: Se o decision a iables {loga,logb,...,logn}, ep esen ing he s ep o de o he ansi ions in he obse ed ace, and whose domains a e equal o he a iables in Va -Model. –Va -Diffe ence:Se o nin ege a iables {di a,di b,...,di n}, one o each ansi ion, whose domains a e {0, 1, 2}, o ep esen ha : he e is alignmen be ween he obse ed and expec ed beha iou o he ansi ion (modx== logx→di x= 0); he ansi ion is in he modelled ace bu no in he eal ace o ice e sa (modx== 0 XOR logx== 0 →di x=1); o he ansi ion is in bo h aces bu in diffe en posi ions in he execu ion o de (else →di x= 2). I holds whe he he e is alignmen be ween he n- h alues o Va -Model and Va -Log. –Va -Alignmen : In ege ha ep esen s he sum o all alues in Va -Diffe ence, ep esen ing he wo s possible alue o alignmen . This alue is used in he op imiza ion unc ion, since i his alue can be se o 0, i means ha he model and he e en log a e o ally aligned. In o de o acili a e a clea unde s anding o he c ea ed COP, we use he example in Figu e 1 o show he model and solu ions ob ained. 99 Fig. 1. Simple Pe i Ne 3.2 Modelling he Cons ain s o ep esen he Pe i Ne The COP mus include he fi e necessa y pa s: defini ion o a iables, con- s ain s o ela e he o de o he ansi ions in he model, cons ain s o desc ibe he o de o he log, cons ain s o de e mine he misalignmen o each ac i i y, and he objec i e unc ion. The modelling o he cons ain s in he COP is based on he ans o ma ion o he Pe i ne model in o nume ical cons ain s. Fo his eason, e e y place (and hence, he s uc u e o he flow su ounding i ) is analysed, and he ollowing cons ain s a e included in o he COP o ep esen he con ol flow be ween he ansi ions. To diffe en ia e he cons ain s ha o m he c ea ed COP, om he p og amming s uc u es used o co e he Pe i ne o ob ain he ela ions be ween he ansi ions, i alic le e s a e used o dis inguish cons ain s. – S a place (i.e. place wi h no inpu a cs): Being o 1... o m he ou - pu ansi ions (as shown in Figu e 2), he ollowing cons ain is pa o he COP: (modo 1=0+... +modo m=0) =1 Fo he example: (modA=0) = 1 – In e media e place (i.e. place wi h some inpu and ou pu a cs): Being i 1...i n he inpu ansi ions, and o 1...o m he ou pu ansi ions (as shown in Figu e 3), he ollowing cons ain s a e pa o he COP: FOR EACH pai i i,o j i (modo j=0) hen (modo j>mod i i) END FOR (modi 1=0+...+modi n=0) ≤1 AND (modo 1=0+...+modo m=0) ≤1 (modi 1=0+... +modi n=0) =(modo 1=0+... +modo m=0) Fig. 2. S a place 100 Fig. 3. In e media e place Meaning ha : • o each ou pu ansi ion o j, ei he i is no pa o he execu ion, o i should be execu ed a e he execu ed inpu ansi ion (modo j> modi i); •and, i an inpu ansi ion is execu ed, one and only one o he ou pu ansi ions can be execu ed. O he wise, none o hem is execu ed. Applied o he example: //A→B//in e media e places i (modB=0) hen (modB>modA) (modA=0)≤1 AND (modB=0)≤1 AND (modA=0)=(modB=0) // he modelling o B→D,D→E,E→I,A→C,H→Iis equi alen //C→(F xo G) i (modF=0) hen (modF>modC) i (modG=0) hen (modG>modC) (modC=0)≤1 AND (modF=0 + modG=0)≤1 (modC=0)=(modF=0 + modG=0) // he modelling o I→J xo K is equi alen //(F xo G) →H i (modH=0) hen (modH>modF) i (modH=0) hen (modH>modG) (modF=0 + modG=0)≤1 AND (modH=0)≤1 (modF=0 + modG=0)=(modH=0) // he modelling o J xo K →Lis equi alen – End place (i.e. place wi h no ou pu a cs): Being i 1... i n he inpu ansi ions (as shown in Figu e 4), he ollowing cons ain is pa o he COP: (modi 1=0+... +modi n=0) =1 Fig. 4. End place 101 Applied o he example: (modL=0)=1 –E e y ansi ion aiappea ing in he case ( om he e en log) o check, bu no in he model, is included as a a iable modaiin he se Va -Model,wi h he cons ain : modai=0 3.3 Modelling he Cons ain s o ep esen he E en Log As i was a o emen ioned, he a iables in he se Va -Log a e c ea ed o s udy he posi ions in he execu ion o de o bo h he elemen s appea ing in a ce ain case and in he model. The e o e, diffe en se s a e c ea ed o each case in he e en log, and hen a diffe en CSP is c ea ed o each case. Fo e e y case in he e en log, composed o ac i i ies p esen ed as an o - de ed lis a1,a 2,...,a q, he cons ains ha should be c ea ed and included in he COP a e: loga1>0 AND loga2>log a1AND ... AND logaq>log aq−1 Meaning ha , since all e en s in he log we e execu ed, hey should ha e a alue g ea e han 0, keeping he execu ion o de eco ded in he case. Likewise, o each ac i i y aiappea ing in he model bu no in he log, he ollowing cons ain is included: logai=0 3.4 Modelling a COP o find he alignmen be ween model and e en log The alignmen can be desc ibed by he dis ance be ween he obse ed and he expec ed beha iou . The obse ed ac i i y execu ions a e ep esen ed by he a iables in he se Va -Log while he expec ed beha iou is modelled by he se Va -Model. The minimiza ion o he diffe ence be ween hem is he aim o he alignmen . In ou solu ion, i is modelled using he a iables in he se Va -Diffe ence, whe e each a iable di ai ep esen s he diffe ence be ween he expec ed and he obse ed beha iou o ac i i y ai(0, 1 o 2 as explained be- o e). The sum o all a iables in he se Va -Diffe en is s o ed in he a iable Va -Alignmen , which is he alue o minimize, objec i e o he op imiza ion unc ion. 102 FOR EVERY ac i i y aiDO: i (logai==modai) hen(di ai=0) else i (logai==0 ∨modai==0) hen (di ai=1) else (di ai=2) END Following he heo y o alignmen o p ohibi ha wo diffe en ac i i ies can be execu ed in he same ins an o ime, he ollowing cons ain s mus be included: FOR EACH pai o a iables modiand logjin Va -Model DO: i (modi=0) hen (modi=logj) END Finally, o include he objec i e unc ion ha minimize he summa ion o diffe ences, he ollowing cons ain s a e included: Va -Alignmen = di i∈Va −Di e ence di i minimize(Va -Alignmen ) 3.5 Some E alua ions o he example Likewise, and depending on he case o check, he es o he COP is defined. To illus a e his, h ee cases in he e en log, and hei esul ing cons ain s, a e shown as examples in he ollowing: –A fi ing case: {A, C, B, F, D, E, H, I, J, L} //Ac i i ies in he case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logD>logFAND logE>logDAND logH>logEAND logI>logHAND logJ>logIAND logL>logJ //Ac i i ies in he model bu no in he case logG=0 AND logK=0 –Unfi ing case 1, since he e is an ac i i y in he model ha should appea in he case (ac i i y l): {A, C, B, F, D, E, H, I, J} //Ac i i ies in he case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logD>logFAND logE>logDAND logH>logEAND logI>logHAND logJ>logI //Ac i i ies in he model bu no in he case logL=0 AND logG=0 AND logK=0 103 –Unfi ing case 2, since he e is an ac i i y in he log ha does no appea in a co ec ace o he model al hough i is in he model (o de o D and E): {A, C, B, E, D, F, H, I, J, L} //Ac i i ies in he case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logG>logFAND logD>logGAND logE>logDAND logH>logEAND logI>logHAND logJ>logIAND logL>logJ //Ac i i ies in he model bu no in he case logK=0 The au oma ic compu a ion o hese h ee examples ob ains he esul ing se s Va -Model,Va -Log,Va -Diffe ence and he alue o Va -Aligmen shown in Figu e 5. Fig. 5. Resul s o h ee case examples 104