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.
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 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 [
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 [
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
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 , where X= {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 Ci is defined as a relation R on a subset of variables V = {xi, xj , . . ., xl}, called the constraint scope. The relation R may 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 V that satisfy R. Let Vk = {xk1 , . . ., xkl } be a subset of X, and an l-tuple (xk1 , . . ., xkl ) from d(xk1 ), . . ., d(xkl ) can therefore be called an 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 [
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 [
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, modC can 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, modC in the domain {0..n} //{0..model.size()} modA>0 AND (modB>0 XOR modC >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
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 [
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, . . . , n take in the expected execution order, whose domains are Integers in 0..n, being n the 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: Set of n integer 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. 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 . . . otm the output transitions (as shown in Figure 2), the following constraint is part of the COP: (modot1 =0 + . . . + modotm =0) = 1
(modA=0) = 1 – Intermediate place (i.e. place with some input and output arcs): Being it1 . . . itn the input transitions, and ot1 . . . otm the output transitions (as shown in Figure 3), the following constraints are part of the COP:
if (modotj =0) then (modotj > moditi ) END FOR (modit1 =0 + . . . + moditn =0) ≤ 1 AND (modot1 =0 + . . . + modotm =0) ≤ 1 (modit1 =0 + . . . + moditn =0) = (modot1 =0 + . . . + modotm =0)
• 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 → I is 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 → L is equivalent – End place (i.e. place with no output arcs): Being it1 . . . itn the input transitions (as shown in Figure 4), the following constraint is part of the COP: (modit1 =0 + . . . + moditn =0) = 1 Applied to the example: (modL=0)=1 modai =0 – Every transition ai appearing in the case (from the event log) to check, but not in the model, is included as a variable modai in the set Var-Model, with the constraint: 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, a2, . . ., aq, the constrains that should be created and included in the COP are: loga1 > 0 AND loga2 > loga1 AND . . . AND logaq > logaq−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 ai appearing 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 difai represents 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. FOR EVERY activity ai DO: 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 modi and logj in Var-Model DO:
if (modi=0) then (modi=logj) END
difi∈V ar−Difference difi
Finally, to include the objective function that minimize the summation of differences, the following constraints are included: Var-Alignment = 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 >logA AND logB>logC AND logF >logB AND logD>logF AND logE>logD AND logH >logE AND logI >logH AND logJ >logI AND 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 >logA AND logB>logC AND logF >logB AND logD>logF AND logE>logD AND logH >logE AND logI >logH AND logJ >logI //Activities in the model but not in the case logL=0 AND logG=0 AND logK =0 – 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 >logA AND logB>logC AND logF >logB AND logG>logF AND logD>logG AND logE>logD AND logH >logE AND logI >logH AND logJ >logI AND 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. The addressed problem presents a high computational complexity. However, thanks to the aforementioned characteristics of Constraint Programming, it can be improved by reducing the search space. In order to do it, some analyses of the Petri net graph have been performed to reduce the domain of the variables and the possible combinations, including more constraints into the problem and reducing the search: – Minimum and maximum number of zeros in the set Var-Model : In order to reduce the search space by avoiding the exploration of non-valid solutions, the valuation of the variables in Var-Model (regarding the amount of zeros) is limited. Therefore, and since a zero in a variable of Var-Model means that the corresponding transition may not be executed, we can deduce from the model the minimum and maximum number of zeros that can appear in Var-Model. To ascertain the number of zeros, a COP is created with the constraints related to the model minimizing or maximize the summation of zeros to obtain maxNumZeros and minNumZeros respectively. The obtained values and the following constraints are included in the explained COP. countNumZeros[Var-Model.size()] in the domain model.size() int sumCountZeros in the domain
[model.size()−maxNumZeros..model.size()−minNumZeros]
if(modi == 0)
then (countNumZeros[i] = 1)
else (countNumZeros[i] = 0)
END FOR
sumNumZeros = countNumZeros[
FOR EACH modi in Var-Model
modi in the domain [0..size−floyd[i][closestEndTransition]]
END FOR – Maximum value in Var-Log : A reduction in the domain of each variable composing Var-Log is also carried out following a similar idea. The possible order when a transition can be executed in the log, can take into account the events that appear after it.
logai ≤ size − case.size() + i
END FOR – Mandatory transition relation: A mandatory matrix is built, where each position [i][j] of the matrix can take two values {0, 1}, being 0 if every correct case that includes the transition i must include the transition j, and 1 otherwise. Thus, for every 1 found in a position [i][j], a constraint is created: FOR EACH pair ai, aj of transitions
IF (ai is a start transition)
THEN (modaj > floyd[i][j])
ELSE (if (modai =0) then ((floyd[i][j]+modai ) ≤ modaj )
END IF
END FOR – Define Goal to Propagate Solutions: Since the CSPs analyse all the promising possible values of the variables, in order to reduce this analysis we propose to include in the COP a goal over the Var-Log variables to generate only the possible values of this array and propagate the solution to the rest of variables. This enables the search to stop the instantiation in the branches where no new values of decision variables can be found, thereby bounding the unnecessary combinations of values for the rest of the variables but ensuring that there exists a solution inside. 4
This proposal has been implemented using JsolverT M as COP solver, XES library
and PNML framework3. We used the benchmarks from [
The COPs have been tested using the example whose characteristics are shown in Table 1. All XES for each Petri net in PNML are formed by several cases, 500 for C−petri and 1200 for the rest. Each case is evaluated in an independent way, it implies that the files of PNML and XES are load from the beginning, and the mentioned algorithms to analyse the Petri net graph are repeated for each case and included in the evaluation times of the table.
Since some of the examples are very hard, Constraint Programming offers the possibility to know the best solution found so far in the exploration. With this capacity we can wait or abort the search keeping a possible solution, although sometimes it cannot be ensured that this is the best solution. The information about the tests is: – Test: Name of the Petri net analysed in the test. 3 The test cases are measured using a Windows 10 machine, with an Intel Core I7 processor, 3.4 GHz and 32.0 GB RAM. – Num. Trans.: Number of transitions in the Petri net. – Num. Places: Number of places in the Petri net. – Width: Minimum distance from a start place to an end place, equal to the position {startTransition, endTransition} in the Floyd Matrix. – Min. Num of Trans.: The minimum number of transitions that can appear in a correct case for the model (model.size()−maxNumZeros). – Max. Num of Trans.: The maximum number of transitions that can appear in a correct case for the model (model.size()−minNumZeros). – time: The summation of the evaluation time for every cases (1200). This value is included only if we can ensure that the minimum is found in a bounded time (one minute in our case). – Minimal found?: Field to indicate if we can ensure that the minimum is found or we have abort the execution. The possibilities are Yes or Not, to describe if the best solution in a bounded time is found for every case. – Best solution in a Bounded Time: When the minimum cannot be ensured to be found, we need to decide the time that we are going to wait until stopping the process. We have included some examples of the minimum misalignment found and the spending time to obtain this solution.
Analysing Table 1, it is possible to ascertain that the evaluation time is not totally related to the size of the Petri net, nor with the number of variables. Actually there exists a dependency between the evaluation time and the size of the log. This size is not included in the table since they are 1200 different for each case, but the min. and max. number of transitions determine the bound of the log size in each case. We can observe that two COPs for the same model, but for 1703.829s All 1564.647s All 22754.087 All 2976.404s All 57390.782s All
None
None
19 in 18.426s
26 in 15.590s
26 in 16.201s
24 in 17.922s
25 in 18.524s
different log (then with the same number of variables), can have very different
evaluation times. Our proposal found solutions for the examples prDm6, prEm6,
prFm6, prGm6, whereas they cannot be found in previous works [
This proposal presents three main benefits: 1) the solutions found during the search can be known, then we can abort the process when considering that the alignment is good enough, or even to bound the waiting time; 2) the capacity to interact with the model, by allowing the parametrization of values for each particular case and model; and 3) Constraint solver tools are in constant development, therefore every improvement in constraint programming research can be easily included in our implementation. Some example of the variables that can be parametrized are: – Limitation of the maximum search time. – A lower bound on the degree of alignment. – Maximum or minimum allowed misalignment. – Types of supported cases, described by means of: 1) those containing a minimum or maximum number of transitions; 2) those containing a set of transitions in a mandatory way.
Among the limitations of the current state of our proposal are that: – Only Petri nets with one token is considered, and different transitions with the same name are not allowed. – It is restricted to acyclic process models. – Only safe nets are considered and with exactly one input and output place. – For some cases, we cannot always ensure that the found solution is minimal. 6
The seminal work by [
The work in [
Decompositional techniques have been recently presented [
Finally, the work in [
The Constraint Programming paradigm has been used in various and complex scenarios where different combinations and possibilities need to be analysed, obtaining promising solutions. For this reason, we have considered interesting to carry out the alignment computation in conformance checking by using Constraint Programming. The creation and solution of Constraint Optimization Problems allows to incorporate in the computation of alignments propagation algorithms incorporated in Constraint Programming Solvers. It has enabled to find solutions for complex Petri nets and logs that represent a challenge for other techniques. Obviously there exist computational complex problems, very hard to optimize also using Constraint Programming. For this reason, and since the solutions found during the search can be known, the user has the choice to stop the search when a satisfactory (perhaps not minimal) solution is found in the exploration.
In addition, the use a declarative model as Constraint Programming facilitates the incorporation of parameters in the problems, with no extra implementation, such as the maximum time of search of solutions, or the maximum and minimum misalignment allowed.
For the future, several research directions will be taken. First, extending the theory to deal with models containing cyclic behaviour is a necessary step. Second, we plan to explore the correlation between the characteristics of the model and the log, and the evaluation time. Also we consider very interesting to combine various cases to find the minimal diagnosis of the model or the log, to ascertain the activities responsible of a misalignment.
Acknowledgments. This work has been partially funded by the Spanish Ministry for Economy and Competitiveness (TIN2015-63502-C3-2-R, TIN2013-46181-C2-1-R) and the European Regional Development Fund (ERDF/FEDER).