Computing alignments with constraint programming : the acyclic case

Computing Alignments with Constraint Programming: The Acyclic Case Mar´ıa Teresa G´omez-L´opez1, Diana Borrego1, Josep Carmona2, Rafael M. Gasca1 1Universidad de Sevilla, Seville, Spain, {maytegomez,dianabn,gasca}@us.es 2Universitat Polit`ecnica de Catalunya, Barcelona, Spain, [email protected] Abstract. Conformance checking confronts process models with real process executions to detect and measure deviations between modelled and observed behaviour. The core technique for conformance checking is the computation of an alignment. Current approaches for alignment computation rely on a shortest-path technique over the product of the state-space of a model and the observed trace, thus suffering from the well-known state explosion problem. This paper presents a fresh alternative for alignment computation of acyclic process models, that encodes the alignment problem as a Constraint Satisfaction Problem. Since modern solvers for this framework are capable of dealing with large instances, this contribution has a clear potential. Remarkably, our prototype implementation can handle instances that represent a real challenge for current techniques. Main advantages of using Constraint Programming paradigm lie in the possibility to adapt parameters such as the maximum search time, or the maximum misalignment allowed. Moreover, using search and propagation algorithms incorporated in Constraint Programming Solvers permits to find solutions for problems unsolvable with other techniques. Keywords: Conformance Checking, Constraint Programming 1 Introduction Nowadays organizations analyze and use the huge amount of data that their information systems generate. This data represents an important source of information, since it contains many of the evidences an organization may need to know in order to reach its (business) goals. Among others perspectives, the focus on the process dimension is of paramount importance. Process mining has evolved in the last decade to act as a meeting point between data and process science. Techniques in process mining enable the discovery of evidence-based process models, the conformance analysis and the enhancement of process models. Conformance analysis, which is the topic considered in this paper, studies the adequacy of a process model in describing the real behavior observed as a collection of traces denoting the footprints of the execution of 96 a process. While there exist several techniques for discovery and enhancement of process models, the current few techniques available for conformance analysis are not yet satisfactory. In this paper we tackle a central problem in conformance analysis: the computation of an alignment between a process model and an event log. Informally, an alignment is a two-row matrix where the first row denotes the steps in the observed trace, while the second row describes the steps performed by the model in order to fit as much as possible the trace. Alignments are crucial to evaluate the important metrics in conformance, i.e., fitness and generalization [2] and precision [3]. We deviate from the current approaches for alignment computation, which are based on state-space explorations of models. Instead, we encode the problem of computing alignments as a Constraint Satisfaction Problem (CSP), and use a CSP solver to compute alignments. The CSP framework brings many advantages when compared to the state-of-the-art approaches for conformance analysis: a portfolio of available search techniques, natural encoding of certain model constructs, capability of handling large instances, ability to interact with the solver to obtain valid solutions, etc. In this paper we consider the computation of alignments for acyclic process models. In spite of this model restriction, current techniques may still have problems to handle certain instances, as it was demonstrated in [14]. In our prototype implementation, we show how the approach presented in this paper may be a solid alternative when current approaches fail at deriving an alignment. This paper is organized as follows: in Section 2 a brief introduction to Constraint Programming is provided, since it is the basis of the encoding presented in the rest of the paper. Then in Section 3 the encoding is shown, together with further extensions to optimize the computation of alignments. Then in Section 4 some the results on some instances from the literature are reported. Finally, Section 6 provides the current context for conformance analysis and Section 7 concludes and discusses current research directions. 2 Constraint Programming A CSP represents a reasoning framework consisting of variables, domains and constraints, where the model is described declaratively. Formally, it is defined as a tuple X,D,C,whereX={x1,...,xn}is a finite set of variables, D={d(x1), ...,d(xn)}is a set of domains of the values of the variables, and C={C1,..., Cm}is a set of constraints. Each constraint Ciis defined as a relation Ron a subset of variables V={xi,xj,...,xl}, called the constraint scope.Therelation Rmay be represented as a subset of the Cartesian product d(xi)×d(xj)×... ×d(xl). A constraint Ci=(Vi,Ri) simultaneously specifies the possible values of the variables in Vthat satisfy R.LetVk={xk1,...,xkl}be a subset of X, and an l-tuple (xk1,...,xkl)fromd(xk1), ...,d(xkl) can therefore be called an 97 instantiation of the variables in Vk. An instantiation is a solution if and only if it satisfies the constraints C. In order to solve a CSP, a combination of search and consistency techniques is commonly used [8][4]. The consistency techniques remove inconsistent values from the domains of the variables during or before the search. During the search, a propagation process is executed which analyses the combination of values of variables where the constraints are satisfiable. Several local consistency and optimization techniques have been proposed as ways of improving the efficiency of search algorithms. When it is not only necessary to ascertain if a solution can be found, and it is important to find the best solution, a Constraint Optimization Problem (COP) can be created and solved. A COP is a CSP with an optimization function where only the tuple of possible values that optimize this function is determined as the solution of the COP. Constraint Programming has already been used to compare expected and observed behaviour to diagnose models according observations, and it has also been applied to business process models [9, 11, 5]. A simple example to illustrate the usage of a CSP can be found to represent the possible execution order of the activities of a model. Imagine a model where activity A must be executed first, and activities B or C must be executed after, but not both. Variables modA,modB,modCcan be used to obtain the possible execution moments. And the constraints should represent that (1) A must be executed, (2) B or C must be executed (but only one), and (3) if B or C are executed, this will happen after the execution of A. modA,modB,modCin the domain {0..n}//{0..model.size()} modA>0 AND (modB>0XORmodC>0) AND if (modB=0) then (modB>modA) if (modC=0) then (modC>modA) With this CSP, some solutions provided by a constraint solver 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 of optimization function can be to minimize(modA+modB+ modC). In this case only sol1 is obtained. 3 Alignment Computation with Constraint Programming In this paper we propose to encode by means of a CSP the constraints that describe the possible execution order of the transitions in a Petri net (the expected behaviour), and the order of the transition in the logs (observed behaviour) following model-based diagnosis paradigm [10]. The COP will find the minimum misalignment between the observed and the expected transitions. The encoding consists in the creation of two sets of variables that represent, respectively, the 98 Petri net model (set called Var-Model), and the real observed behaviour registered in each case of the event log (set called Var-Log). These two sets have the same number of variables, since they are composed of all activities in the model, plus all activities appearing in the event log but not in the model. For the alignment computation, the constraints that represent the model are determined once, while the constraints that represent the event log depend on each case. Considering all these activities, these two sets of variables represent the step order where each activity (transition in the Petri net) can be executed following the model (Var-Model) or in accordance to the event log (Var-Log ). If it is possible to assign the same value to every variable in Var-Model and Var-Log,it implies that there is a total alignment between the model and the reality. This way, in order to model both sequences of activities (i.e. modelled and observed behaviour), each variable is modelled as an integer that is evaluated in accordance with the position that it takes in the execution order. Then, the positions assigned to each activity in the modelled (Var-Model) and expected (Var-Log ) behaviours are compared to determine whether some event within a case in the event log is misaligned. 3.1 Modelling the Variables to represent the Petri Net As mentioned, the expected and observed occurrences of activities should be modelled within the CSP, so that the modelled and observed sequences of execution of activities can be compared. Therefore, certain sets of variables should be part of the CSP, with the following meanings: –Var-Model: Set of decision variables {moda,modb,...,modn}representing the position that all activities a,b,...,ntake in the expected execution order, whose domains are Integers in 0..n,beingnthe number of transitions plus the log size -i.e. the worst possible value of alignment-. –Var-Log: Set of decision variables {loga,logb,...,logn}, representing the step order of the transitions in the observed trace, and whose domains are equal to the variables in Var-Model. –Var-Difference:Setofninteger variables {difa,difb,...,difn}, one for each transition, whose domains are {0, 1, 2}, to represent that: there is alignment between the observed and expected behaviour of the transition (modx== logx→difx= 0); the transition is in the modelled trace but not in the real trace or viceversa (modx== 0 XOR logx== 0 →difx=1); or the transition is in both traces but in different positions in the execution order (else →difx= 2). It holds whether there is alignment between the n-th values of Var-Model and Var-Log. –Var-Alignment: Integer that represents the sum of all values in Var-Difference, representing the worst possible value of alignment. This value is used in the optimization function, since if this value can be set to 0, it means that the model and the event log are totally aligned. In order to facilitate a clear understanding of the created COP, we use the example in Figure 1 to show the model and solutions obtained. 99 Fig. 1. Simple Petri Net 3.2 Modelling the Constraints to represent the Petri Net The COP must include the five necessary parts: definition of variables, constraints to relate the order of the transitions in the model, constraints to describe the order of the log, constraints to determine the misalignment for each activity, and the objective function. The modelling of the constraints in the COP is based on the transformation of the Petri net model into numerical constraints. For this reason, every place (and hence, the structure of the flow surrounding it) is analysed, and the following constraints are included into the COP to represent the control flow between the transitions. To differentiate the constraints that form the created COP, from the programming structures used to cover the Petri net to obtain the relations between the transitions, italic letters are used to distinguish constraints. – Start place (i.e. place with no input arcs): Being ot1... ot mthe output transitions (as shown in Figure 2), the following constraint is part of the COP: (modot1=0+... +modotm=0) =1 For the example: (modA=0) = 1 – Intermediate place (i.e. place with some input and output arcs): Being it1...it nthe input transitions, and ot1...ot mthe output transitions (as shown in Figure 3), the following constraints are part of the COP: FOR EACH pair iti,ot j if (modotj=0) then (modotj>mod iti) END FOR (modit1=0+...+moditn=0) ≤1 AND (modot1=0+...+modotm=0) ≤1 (modit1=0+... +moditn=0) =(modot1=0+... +modotm=0) Fig. 2. Start place 100 Fig. 3. Intermediate place Meaning that: •for each output transition otj, either it is not part of the execution, or it should be executed after the executed input transition (modotj> moditi); •and, if an input transition is executed, one and only one of the output transitions can be executed. Otherwise, none of them is executed. Applied to the example: //A→B//intermediate places if(modB=0) then (modB>modA) (modA=0)≤1 AND (modB=0)≤1 AND (modA=0)=(modB=0) //the modelling of B→D,D→E,E→I,A→C,H→Iis equivalent //C→(F xor G) if(modF=0) then (modF>modC) if(modG=0) then (modG>modC) (modC=0)≤1 AND (modF=0 + modG=0)≤1 (modC=0)=(modF=0 + modG=0) //the modelling of I→J xor K is equivalent //(F xor G) →H if(modH=0) then (modH>modF) if(modH=0) then (modH>modG) (modF=0 + modG=0)≤1 AND (modH=0)≤1 (modF=0 + modG=0)=(modH=0) //the modelling of J xor K →Lis equivalent – End place (i.e. place with no output arcs): Being it1... it nthe input transitions (as shown in Figure 4), the following constraint is part of the COP: (modit1=0+... +moditn=0) =1 Fig. 4. End place 101 Applied to the example: (modL=0)=1 –Every transition aiappearing in the case (from the event log) to check, but not in the model, is included as a variable modaiin the set Var-Model,with the constraint: modai=0 3.3 Modelling the Constraints to represent the Event Log As it was aforementioned, the variables in the set Var-Log are created to study the positions in the execution order of both the elements appearing in a certain case and in the model. Therefore, different sets are created for each case in the event log, and then a different CSP is created for each case. For every case in the event log, composed of activities presented as an ordered list a1,a 2,...,a q, the constrains that should be created and included in the COP are: loga1>0 AND loga2>log a1AND ... AND logaq>log aq−1 Meaning that, since all events in the log were executed, they should have a value greater than 0, keeping the execution order recorded in the case. Likewise, for each activity aiappearing in the model but not in the log, the following constraint is included: logai=0 3.4 Modelling a COP to find the alignment between model and event log The alignment can be described by the distance between the observed and the expected behaviour. The observed activity executions are represented by the variables in the set Var-Log while the expected behaviour is modelled by the set Var-Model. The minimization of the difference between them is the aim of the alignment. In our solution, it is modelled using the variables in the set Var-Difference, where each variable difairepresents the difference between the expected and the observed behaviour for activity ai(0, 1 or 2 as explained before). The sum of all variables in the set Var-Different is stored in the variable Var-Alignment, which is the value to minimize, objective of the optimization function. 102 FOR EVERY activity aiDO: if(logai==modai)then(difai=0) else if(logai==0 ∨modai==0) then (difai=1) else (difai=2) END Following the theory of alignment to prohibit that two different activities can be executed in the same instant of time, the following constraints must be included: FOR EACH pair of variables modiand logjin Var-Model DO: if (modi=0) then (modi=logj) END Finally, to include the objective function that minimize the summation of differences, the following constraints are included: Var-Alignment = difi∈Var−Difference difi minimize(Var-Alignment) 3.5 Some Evaluations of the example Likewise, and depending on the case to check, the rest of the COP is defined. To illustrate this, three cases in the event log, and their resulting constraints, are shown as examples in the following: –A fitting case: {A, C, B, F, D, E, H, I, J, L} //Activities in the case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logD>logFAND logE>logDAND logH>logEAND logI>logHAND logJ>logIAND logL>logJ //Activities in the model but not in the case logG=0 AND logK=0 –Unfitting case 1, since there is an activity in the model that should appear in the case (activity l): {A, C, B, F, D, E, H, I, J} //Activities in the case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logD>logFAND logE>logDAND logH>logEAND logI>logHAND logJ>logI //Activities in the model but not in the case logL=0 AND logG=0 AND logK=0 103 –Unfitting case 2, since there is an activity in the log that does not appear in a correct trace of the model although it is in the model (order of D and E): {A, C, B, E, D, F, H, I, J, L} //Activities in the case logA>0 AND logC>logAAND logB>logCAND logF>logBAND logG>logFAND logD>logGAND logE>logDAND logH>logEAND logI>logHAND logJ>logIAND logL>logJ //Activities in the model but not in the case logK=0 The automatic computation of these three examples obtains the resulting sets Var-Model,Var-Log,Var-Difference and the value of Var-Aligment shown in Figure 5. Fig. 5. Results of three case examples 104