The problem of refining a Petri net (PN) discovered from a single sequence S of events T generated by discrete event processes is addressed. The refinement aims to reduce a possible exceeding language in the discovered model. A technique that extends a t-invariant based discovery method is presented. Given a discovered PN and its set of minimal t-invariants Y, the technique analyses the execution of the t-components in S and determines a sequencing pattern SY that schedules the execution of t-components in the initial PN. Then, SY is used to discover a PN' that uses transitions in T and new places; PN' schedules representative transitions of each t-invariant in SY. The refined model is obtained by merging the representative transitions of both PN and PN' if the pattern is discovered. A first result coping with a subclass of safe PN in which each t-component has at least a transition not shared with any other component is reported.
Automated modelling of discrete event processes from external behaviour is nowadays studied by numerous research groups along the two last decades. The main motivation is to discover the current behaviour of unknown or ill known systems, because the documentation is not updated or missing. The aim is to obtain models that express clearly causal and concurrency relationships between the events generated by the process. Petri nets have been mostly used to represent such models.
Variations on this problem have been named differently in the research community.
Earlier methods were called language learning techniques, which aimed to build finite
automata, or grammars of languages from samples of accepted words [
Input-output identification of automated production process is addressed in [
In the field of workflow management systems (WMS) the problem is named process
mining: discovery. Most of the proposals obtain Petri nets from a set of event traces
representing the system behaviour as process cases. A complete review of recent
works can be found in [
The work presented herein concerns to identification of discrete event processes, in
which the available data is a set of sequences of input-output vectors, which represent
the exchanged signals between a controller and a plant from the controller point of
view. The events, the number of places, and the number of transitions are not known a
priori. The proposed method yields a Petri net model including input functions and
outputs. The method is based on a two-phase strategy presented in a recent previous
work [
This paper focuses on the second phase in which a PN is obtained from a sequence S
of events (transitions) from a given alphabet T. More precisely, a method based on the
computation of the t-invariants [
The paper contains a) an overview of the t-invariant based discovery method and b) the repetitive component scheduling technique.
The present paper follows the approach presented in [
Example 1. Consider a process handling 3 inputs (s, x, y) and 3 outputs (A, B, C), from which the following I/O sequence is captured: s ⎡0⎤⎡1⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡1⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡1⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤⎡1⎤⎡0⎤⎡0⎤⎡0⎤⎡0⎤ ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥ x ⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥ w = y ⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢1⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢0⎥⎥⎢⎢1⎥⎥⎢⎢0⎥⎥
A ⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥ B ⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢1⎥⎢1⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥⎢0⎥ ⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥
C ⎢⎣0⎥⎦⎢⎣0⎦⎥⎣⎢0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎣⎢0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣1⎦⎥⎢⎣1⎦⎥⎢⎣0⎦⎥⎣⎢0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎣⎢0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣0⎦⎥⎢⎣1⎦⎥⎢⎣1⎦⎥
The construction of an interpreted Petri net (IPN) model from w is performed in
two stages. The first stage processes the sequence w and obtains the observable part of
the model consisting of components using observable places and transitions labelled
with output symbols and expressions of input symbols respectively (Fig. 1). This
determines the set of transitions T. A transition sequence S that corresponds to the
observed event sequence is also delivered. In the example S1=t1 t2 t3 t4 t1 t2 t5 t6 t1 t2 t3
t4 t1 t2 t5 t6 t1 is obtained. A simpler technique for this stage is proposed later in [
The second stage builds a PN model that is able to reproduce S with a reduced excessive behaviour; furthermore, the number of nodes is small since only the necessary places to represent the discovered structural constrains are added. The resulting PN corresponds to the process’ internal behaviour represented by non observable places. In the example the obtained PN showed in figure 2 reproduces S1 (thus w). Merging this model with the observable model and eliminating implicit places (p11, p22, p33) yields the final IPN model shown in figure 3.
A technique that allows determining more complex behaviours, in particular
implicit dependencies, is proposed in [
In the present paper we are extending the method in [
In Example 1, notice that the execution of S exhibit always the occurrence of tcomponents in alternate way: SY=τ1τ2τ1τ2τ1τ2..., where τi is a sub-sequence of S including transitions in <Yi>. However, in the model sub-sequences of repeated components (τ1τ1τ1 ...τ2τ2) may occur, which is a kind of exceeding behaviour.
A possible refining of the PN N of figure 3 to reduce this behaviour can be done by adding a component that ensures the occurrence of the t-components. Being ρ(τ1)=t3 and ρ(τ1)=t5 the representative transitions of each component, it is easy to determine that a circuit N’ including such transitions and new places can be added to the PN to ensure the order of occurrence, as shown in figure 4. Next section describes this metaanalysis technique.
t1 p1 t2 s_1 A ε t3 P22
This section presents the basic concepts and notations of ordinary PN.
Definition 1. An ordinary Petri Net structure G is a bipartite digraph represented by the 4-tuple G = (P, T, I, O) where: P = {p1, p2, ..., p|P|} and T = {t1, t2, ..., t|T|} are finite sets of vertices named places and transitions respectively; I(O) : P × T → {0,1} is a function representing the arcs going from places to transitions (from transitions to places). For any node x ∈ P∪T, •x = {y | I((y, x))=1}, and x• = {y | O((x, y)=1}.
The incidence matrix of G is C = C+ − C−, where C− = [cij−]; cij− = I(pi, tj); and C+ = [cij+]; cij+ = O(pi, tj) are the pre-incidence and postincidence matrices respectively.
A marking function M : P→ Z+ represents the number of tokens residing inside each place; it is usually expressed as an |P|-entry vector. Z+ is the set of nonnegative integers.
Definition 2. A Petri Net system or Petri Net (PN) is the pair N = (G,M0), where G is a PN structure and M0 is an initial marking.
In a PN system, a transition tj is enabled at marking Mk if ∀pi ∈ P, Mk(pi) ≥ I(pi, tj); an enabled transition tj can be fired reaching a new marking Mk+1, which can be computed as Mk+1 = Mk + Cuk, where uk(i) = 0, i≠j, uk(j) = 1; this equation is called the PN state equation. The reachability set of a PN is the set of all possible reachable markings from M0 firing only enabled transitions; this set is denoted by R(G,M0).
Definition 3. A PN system is 1-bounded or safe iff for any Mi ∈ R(G,M0) and any p ∈ P, Mi(p) ≤ 1. A PN system is live iff for every reachable marking Mi ∈ R(G,M0) and ∀t ∈ T there is a reachable marking Mk ∈ R(G, Mi) such that t is enabled in Mk.
Definition 4. A t-invariant Yi of a PN is an integer solution to the equation CYi=0 such that Yi≥0 and Yi≠0. The support of Yi denoted as <Yi> is the set of transitions whose corresponding entries in Yi are strictly positive. Y is minimal if its support is not included in the support of other t-invariant. A t-component G(Yi) is a subnet of PN induced by a <Yi>: G(Yi)=(Pi, Ti, Ii, Oi), where Pi =•<Yi>∪<Yi>•, Ti =<Yi>, Ii= Pi×Ti∩I, and Oi=Pi×Ti∩O. G(Yi) is usually denoted as ||Yi||.
In a t-invariant Yi, if we have initial marking (M0) that enables a ti ∈ <Yi>, when ti is fired, then M0 can be reached again by firing only transitions in <Yi>. 3
Consider the t-invariant based discovery method, which treats a single sequence
S∈T* and delivers a safe PN N and a set of minimal t-invariant supports <Y>={<Yi>}
such that PN executes all the t-invariants Y [
A sequence SY of t-components execution can be determined by parsing S from the first transition. Every component ||Yi|| can be identified when a given transition that distinguishes the component is found or, in the worst case, the whole set <Yi> is found during the tracking of S.
Definition. The distinguishable transitions of a t-component ι(||Yi||)⊆<Yi> are the transitions that only belong to this support. When such transitions are fired, we are sure that a t-component is executed. ι(||Yi||)=<Yi>∩(⊗j<Yj>∀j).
Notice that ι(||Yi||)=∅ when every tj ∈ <Yi> belongs also to other t-invariant supports. Eventually, all the ι(||Yi||)=∅.
Definition. The representative transition ρi of <Yi> is a tj∈<Yi> such that it determines precisely the t-component is being executed is S. If ι(||Yi||)≠∅ then ρi is the first transition in ι(||Yi||) that occurs in S; else, ρi is the last transition in <Yi> found in the current subsequence tracked in S, then τi is determined.
In Example 1, ι(||Y1||)={t3, t4} and ι(||Y2||)={t5, t6}; ρ1= t3 and ρ2=t5.
Property 1. In a firing sequence S all the transitions of a t-component are fired consecutively as a subsequence τi if there is no other nested t-components (τj, τk ...) sharing transitions with τi. In case of nested t-components, part of τi is fired, then one or several occurrences of τj may appear; afterwards some other transitions of τi are fired, then other nested τk may occur and so on; finally, the remainder transitions of τi are fired.
Proof. In a repetitive execution of a PN if a t-invariant is executed, all the transitions of the support must be fired. When a nested t-component is executed, then this component will be executed (one or several times), and then the remaining transitions of the first t-component will be fired.
It is clear from S of Example 1 that all the transitions of <Y1> are fired first and then those of <Y2>. Thus, it can be expressed as SY=τ1τ2τ1τ2τ1τ2...
Example 2. The PN in Figure 5, discovered from S= t1 t2 t4 t2 t3 t1 t2 t4 t2 t3 t1 t2 t4 t2 t3..., has two supports: <Y1>={t1, t2, t3} and <Y2>={t2, t4}. ι(||Y1||)={t1, t3} and ι(||Y2||)={t4}; ρ1= t1 and t3, and ρ2=t4. Then SY=τ11τ2τ12τ11τ2τ12..., which means that τ1 is split into two sub-sequences τ11 and τ12. Since ||Y2|| is a nested t-component, ρ11= t1 ρ12= t3
When some ι(||Yi||)=∅, the transitions in <Y1> must be tracked during the parsing of S until the last transition or the support is found; then τk is determined.
The sequence of t-components SY, thus Sρ can be obtained from S by considering the representative transitions and the cardinality of the t-invariant support. A procedure that parses S and delivers Sρ is decidable and yields always the same Sρ; the outline of a simple procedure for the case in which all ι(||Yi||)≠∅, and there are not nested t-invariants is given below.
Input: S, <Y> = {<Y1>,<Y2>,... <YNY>} Output: Sρ 1. Determine ρ={ρ1, ρ2, ...ρNY} from S and <Y> 2. SY ← ε; k ← 1 3. Repeat a. If S(k)∈ ρ, where S(k)= ρr b. Then Sρ← Sρ•ρr; SY← SY•τr c. Endif 4. k ← k+1 5. Until k>|S| 6. Return Sρ
The procedure for determining ρ must deal with the case in which some ι(||Yi||)=∅; in the worst all the transitions in <Yi> must be tracked in S to determine uniquely the t-component that is being executed. Furthermore, when there are nested tcomponents, a stack can be used to parse the components execution, in particular when there is nesting at several levels; in this case, regarding the t-component at higher level ρr, several representative transitions ρr1, ρr2, ... could be determined to go ahead the execution of the “interrupted” t-component. The structure of the discovered PN can be also exploited.
In Example 1, SY=τ1τ2τ1τ2τ1τ2... can be straightforward obtained by observing ρ1 and ρ2 in S=...t3...t5...t3...t5.... In Example 2 instead, one must consider two representative transitions ρ11=t1 ρ12=t3 for one component; S = t1...t4...t3...t1...t4...t3..., thus SY=τ11τ2τ12τ11τ2τ12... Finally, the sequence of representative transitions Sρ is derived. In Examples 1 and 2 the sequences are Sρ=t3 t5 t3 t5... and Sρ=t1 t4 t3 t1... respectively.
Now, the next stage is to determine from Sρ the repetitive pattern that schedules the execution of the t-components. The problem is similar to that of process discovery but some other facts must be considered.
Consider a sequence S1=t1 t2 t3 t4 t1 t2 t5 t6 t1 t2 t5 t6 t1 t2 t3 t4 t1 t2 t5 t6 t1 t2 t5 t6 t1... The invariant-based method discovers the same PN of Figure 2 and the same tinvariants. Thus, the representative transitions are the same; however, the sequence of representative transitions is not the same: Sρ=t3 t5 t5 t3 t5 t3...; in the pattern the tcomponent ||Y1|| is executed once, whilst ||Y2|| twice. This cyclic pattern, which establishes a production rate 1-2 for the jobs, is designed as a 2-bounded PN N’ that is shown in Figure 8. For patterns that handle k jobs given by SY=(τ1)n(τ2)m...(τk)r(τ1)n... with regular executions (fixed n, m, ..., r) of jobs, the PN can be designed similarly.
Now, consider the discovered PN, which describes the behaviour of a process involving three jobs. The t-invariant supports are: <Y1>= {t1, t2, t3}, <Y2>= {t1, t4, t5}, and <Y1>= {t1, t6, t7}; the representative transitions are: ρ1= t2, ρ2= t4, and ρ3= t6. Bet4
t2
It is easy to see in Example 1 that the Sρ=t3 t5 t3 t5 corresponds to a pattern that can be represented by a PN N’ that is a cycle p6 t3 p7 t5 p6 with p6 initially marked. Similarly, in Example 2, the pattern N’ derived from Sρ=t1 t4 t3 t1 is a cycle including the representative transitions; the merging of N’ with N is shown in Figure 6; when the implicit place (marked) is removed, the simplified PN is shown in Figure 7. Notice that in previous examples, the refined PNs have one t-component. p1 sides consider that Sρ=t2 t4 t2 t6 t2 t4 t2 t6..., that is, τ1 is executed between the alternation of τ2 and τ3. The PN N’ that describes this pattern is shown in Figure 10. Notice that N’ has two invariants; thus, in a recursive manner, being t4 and t6 the representative transitions of these t-components, N’’ can be obtained (Figure 11). The refined PN is obtained by merging N with N’’; such a PN, shown in Figure 12 has only a tinvariant.
p4 t1 Fig. 8. Sequencing jobs rate t3 p22 t4 p8 t4 t6
p9 Fig. 11. Refining N’: N’’
Fig. 12. The refined PN: N||N’’
We have sketched a refining technique for PN discovered by a t-invariant method. If the scheduling pattern can be determined, t-components relied by N’ become a single t-component; thus, the refined PN has less exceeding behaviour than the first discovered PN. In this meta-analysis of a discovered model, the patterns considered in this short paper are found often in discrete manufacturing systems; however, the strategy to discover more complex patterns is still being studied.
Determining the patterns from SY is an interesting problem. In general, the dependency of occurrence among the τi must be found; this pose a new discovery problem in which, besides the order of execution of the τi in SY, the regularity of the repetitions of τi must be established.