This paper deals with the identification of controlled discrete event processes from timed input-output vector sequences; the sampling date of every vector is provided. An efficient method allowing building a transition timed interpreted Petri net (TTIPN) model is presented. The method is based on a threestage strategy: 1) the observable components of the TTIPN are first obtained, 2) the non-observable part is inferred, and 3) the time parameters associated to transitions are obtained. This paper focuses on the first and third phases of the method; a new method for building the observable model is proposed; additionally, a technique to compute the timing of transitions is presented. The derived algorithms are polynomial-time on the length of the input-output sequences.
Nowadays, many automated processes in operation do not have enough information about how they work. This is because the updates have not been documented or in many cases the specification does not exist.
Earliest identification methods, named language learning techniques, appear in
computer sciences. The aim of such methods was to build fine formal specifications
(finite automata, grammars) of languages from samples of accepted words [
In the field of workflow management systems (WMS) the problem is named
workflow mining. The aim of the approach is similar but the problem statement is
somehow different. A complete review of recent works can be found in [
Most of the proposed identification techniques process sequences of events and
obtain models expressed as Petri nets of finite automata (FA). However, few proposals
address the identification of timed systems. Relevant works on the matter are [
The work presented herein addresses identification of timed discrete event processes, in which the available data is only 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. Additionally, the instants when each vector is observed are considered. 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 and also timing information regarding the durations of operations. Timing is expressed through two parameters associated to transitions: a positive real value and pair of positive real values expressing an interval, which can be used according to the transition timed PN and time PN semantics respectively.
The method is based on a two-phase strategy presented in a recent previous work
[
The paper is organised as follows. Section II gives an overview of the basic notions on Petri nets. Section III presents the method for building the qualitative observable model. Section IV describes the non observable model synthesis. Section V presents the strategy for computing the time parameters. Finally concluding remarks are given.
This section presents the basic concepts and notation of Petri Nets (PN), Interpreted Petri nets (IPN), Timed and Time Petri Nets (TPN) used in this paper.
Definition 1: An ordinary Petri Net structure G is a bipartite digraph represented by the 4-tuple G = (P, T, Pre, Post) where: P = {p1, p2, ..., p|P|} and T = {t1, t2, ..., t|T|} are finite sets of vertices named places and transitions respectively; Pre(Post) : P × T o {0,1} is a function representing the arcs going from places to transitions (from transitions to places).
The incidence matrix of G is W = W+ W , where W = [wij ]; wij = Pre(pi, tj); and W+ = [wij+]; wij+ = Post(pi, tj) are the pre-incidence and post-incidence matrices respectively.
A marking function M : Po Z+ represents the number of tokens residing inside each place; it is usually expressed as a |P|-entry vector. Z+ is the set of nonnegative integers. In particular, in this paper M : Po {0,1}; the PN is referred as 1-bounded or safe.
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) Pre(pi, tj); an enabled transition tj can be fired reaching a new marking Mk+1. This behaviour is represented as Mk o tj Mk+1. The new marking can be computed as Mk+1 = Mk + Wuk, where uk(i) = ML 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).
Now it is defined IPN, an extension to PN that allows associating input and output
signals to PN models. This definition is adapted from [
Definition 3 : An interpreted Petri net (IPN) (Q, M0) is a labelled net structure Q = (G, Ȉ ) , O , M ) with an initial marking M0 where: - G is a PN structure, - 6 = {D 1, D 2, ..., D r} is the inputs alphabet, - ) = {E 1, E 2,..., E q} is the outputs alphabet, - O : To Evu C is a labelling function of transitions, where
C={C1, C2,… , C|T|} is the set of input conditions in which every Ci is a Boolean function on 6 ; when a Ci is always true it is denoted as “=1”, and Ev={Ev1, Ev2,…} is the set of input events conditions; every Evi is a Boolean function of input events, built on 6 ; events are denoted as D i_0 and D i_1 for representing that the input value changes from 1 to 0, or from 0 to 1 respectively. A condition Evi may not exist; this is denoted as “H ”.
In an IPN, a transition tj will be fired if a) tj is enabled, and b) condition Cj is true, and c) the event in E(tj) occurs. - M : R(Q,M0)o (Z+)q is an output function, that associates with each marking in R(G,M0) a q-entry output vector, where q=|) | is the number of outputs. M is represented by a q×|P| matrix, such that if the output symbol E i is present (turned on) every time that M(pj) 1, thenM (i, j) = 1, otherwise M (i, j) = 0.
The state equation of PN is completed with the marking projection Yk = M Mk, where Yk (Z+)q is the k-th output vector of the IPN.
Definition 4: A place pi P is said to be observable if the i-th column vector of M (denoted as M (x ,i)) is not null. Otherwise it is non-observable. P = Pobs Pnobs, and Pobs Pnobs = ; where Pobs is the set of observable places and Pnobs the set of non-observable places.
Now the definitions of timed and time PN are recalled.
Definition 5: A timed transition PN is the tuple NG = (G, M0, G ), where G is an
ordinary PN, M0 is the initial marking, and G : To t 0 is function that assigns a
nonnegative value to each tj T; such a value represents the firing time of is the
average firing of tj once it is enabled [
Definition 6: A time PN is the tuple NL = (G, M0,L ), where G is an ordinary PN,
M0 is the initial marking, L : To t 0u t 0 is the firing time interval function that
assigns a firing interval [lj, uj] to each transition tj T. The interval represents a time
window restriction; tj must be fired after lj or before uj (lj X j) time units computed
from the instant in which tj is enabled [
In both definitions, when G (tj)=0 or L (tj)=[0, 0], tj is called immediate. Timed and immediate transitions are usually represented by empty and filled boxes, respectively. 3
The process to identify consists of a pair controller-plant interacting in a closed loop (Fig. 1). The exchanged signals between them are sampled every time a signal changes and recorded for building a sequence of vectors representing input and outputs from the controller point of view.
The identification method developed in this paper follows the general approach
proposed in [
I(k) O(k)
I/O vectors sequence w
The method presented herein extends the previous one by proposing more efficient algorithms and addressing the temporal behaviour of the process and obtaining the identified model. Thus, besides the input-output vector sequence, the instants when each vector is sampled are considered. In this paper we will focus on the construction of the observable part and the computing of the time parameters associated to each transition. 3.2.1.
The input data is a timed I/O vector sequence w= w(1)w(2) ... w(|w|), where w(k)=[I(k)|O(k)]T such that I(k) {1,0}r, O(k) {1,0}q and w(k)z w(k-1), i.e. a new vector is recorded when an input or an output changes. Furthermore each w(k) has associated a date W (w(k)) t 0, which represents the instant when the k-th I/O vector is observed.
The aim of the method is to obtain an IPN Q and a timing function Tim that associates to each transition two parameters given by G and L , which express the firings duration and interval respectively from the timed and time PN definitions; Tim: To {(valj, intj)| valj=G (tj) and intj=L (tj)} t T}. In this paper a technique that builds the observable components given by Pobs is presented. It is assumed that the process formed by the controller and the plant behaves correctly, i.e. bounded, fault free, and deadlock free; besides, the sequence w is observed from the initial state. 3.2.2.
Definition 7. An elementary event is the difference between two consecutive I/O vectors E(k-1)=w(k) w(k-1)z 0, k>1. Each event vector is composed by two parts E(k)=[IE(k)|OE(k)]T, where IE(k-1)=I(k) I(k-1) and OE(k-1)=O(k) O(k-1) referred as input events and output events respectively. An E(k) is called a reactive event iff OE(k)z 0.
Remark. The event vectors are unknown a priori but the number is bounded by |3r+q| since E(k) {-1,0,1}r+q. The actual number of events is determined from the observed w. Another important issue on this definition is that the only events considered are those which are detected by changes in inputs or outputs (or both). Internal events that are not due to input changes or do not cause output changes are not considered.
The timed event sequence is then E=e(1)e(2)e(3)…e(k-1), where the instants when they are observed are given by W (e(k))= W (w(k+1)). It is assumed that W (w(0))=0.
In this work we are interested in determining the reactive behaviour of the controller; thus we will focus on events that provoke changes in the outputs, i.e. reactive events.
A new sequence RE is formed by the reactive events re(h) from E by preserving the order in which they appear in E and their associated dates: W (re(h))= W (e(k)) such that e(k) is a reactive event.
Given that between two reactive events in E there could be other non reactive events, RE is usually shorter than E.
Example 1. Consider a controlled process that handles 7 inputs (m, a, b, c, d, e, f) and 4 outputs (R1, L1, R2, L2); the I/O vectors have the format [m a b c d e f |R1 L1 R2 L2]T. Figure 2 shows the first vectors of the I/O sequence w, and the derived event sequences E, and R.
Every OE part of a reactive event re(h) represents a change in the output variables E i of the system whose entries are different of zero; E i_1 and E i_0 denote the changes of the variable E i from 0 to 1 and from1 to 0 respectively. The number of different OE in the observed reactive events is the minimum number of transitions in the IPN. All the different OEs are stored in a set OES.
For every OE(h), the symbolic expression of the event part is SOE(k)=ς ܧܱܵ (݇ ) i s.t. OEi(k)z 0, where SOEi(k)=E i_1 if OEi(k)=1 or SOEi(k)=E i_0 if OEi(k)=-1.
In Example 1 the symbolic representation of the OE of re(1) and re(2) are SOE(1) = R1_1 R2_1 and SOE(2) = R1_0 L1_1 respectively.
There are as many observable places as output variables. The corresponding observable places to a re(h) are marked or unmarked when the value is 1 or -1 accordingly.
A substructure relating observable places pi, such that I (pi)=E i, by a transition tj that represents the event re(h) must be created through arcs (tj, pi) and (pi, tj) for the values 1 and -1 in the entry corresponding to pi in OE(h).
In Example 1 the reactive events re(1)=e(2) and re(2)= e(7) define the structures shown in figure 3.
In a very long event sequence, reactive events that have identical OEz 0 may appear repeatedly; such events may have different IE. This means that several IE provoke the same changes in the system outputs. Thus, it is necessary to define a function that embeds all the IE for the same OE; such firing function is associated to the transition of the substructure i.e. that associated by O of the IPN definition.
For every reactive event re(h) one must consider the corresponding IE(k) and also the previous IE whose OE=0 to build a function f in the form Evu C; such functions are named Event and Context parts respectively of the input event function fr. x Event part. It represents the changes of the inputs that yield the outputs change. It is often determined from IE(k) or IE(k-1) if IE(k)=0. The symbolic expression of the event part is SRE(k)= SIEi(k) i s.t. IEi(k)z 0, where SIEi(k)=D i_1 if IEi(k)=1 or SIEi(k)=D i_0 if IEi(k)=-1. x Context part. It represents the values of the input variables of w(k). The symbolic expression of the condition part is SCRE(k)=ς ܵܥܫ (݇ ) i, where SCIi(k)=D i if Ii(k)=1or SCIi(k)=D ഥ i if Ii(k)=0. Furthermore, if a literal D i has changed twice its value during the previous E(k) in which OE(k)=0, D i must not be included in SCRE(k).
For every computed fr, the symbolic expression of the OE is associated through a function U , and the instants W (re(h)) are associated in a set of real values; when a fr is computed again along the RE, then the corresponding date is added to the set. Based in the previous notions the procedure to build the input event functions is given below.
Algorithm 1. Input event functions Input: Sequences w and RE Output: F and the sequence FS 1.FmØ; FS mØ; rm 1; OESmØ 2. re(h) in RE where h=1, ... , |RE|
Let IE(k) be the k-th input event corresponding to re(h) 2.1. If IE(k) ሬ 0Ԧ then Compute SRE (k);
If SRE(k) OES then OESmOES SRE (k) else Compute SRE (k-1);
If SER(k-1) OES then OESmOES SRE (k-1) 2.2. Compute SCRE(k) from w(k) 2.3. If IE(k) ሬ 0Ԧ then fr m (SRE (k), SCRE(k)); else fr m (SRE (k-1), SCRE(k)) 2.4. U (fr)mSOE(k) 2.5. If fr ב F then FmF fr; FSm FS • fr; r= r+1; W ( fr)mW (re(h)) else Let fs F the function already computed s.t. fs = fr; FSmFS • fs ; W (fs)m W
(fs)W (re(h)) 3. Return F and FS Property 1 x The previous algorithm produces a set F of functions that represent all the different reactive events in RE and their corresponding execution contexts. Consequently FS has a correspondence with the sequence of events E. Thus, FS reproduces the inputoutput sequence w. x It is easy to see that the complexity of the procedure for building inputs events functions is O(|RE|).
In Example 1, regarding the reactive event re(1) which corresponds to e(1), SIE(1)=m_1 a_0 d_0 and SCI(2)=ܾത ܿҧ݂݁ ;ҧ then f1(R1_1 R2_1)= (m_1 a_0 d_0, ܾത ܿҧ݂݁ )ҧ. Additionally, f2(R1_0 L1_1)= (c_1, ݉ ഥ ܽ ത݀ ҧ݂ )ҧ; notice that b changed twice between re(1) and re(2). Also f3(R1_1 L1_0)=(f_1, ݉തܽ ത ത ത ܾത ݀ܿത ത ത ҧ݁ ).
Once the reactive functions fh are obtained, several input event functions could correspond to a same output event vector. In the sequence RE of figure 4 regarding Example 1, the output event R1_0 L1_1 is found several times with different fh, i.e. e(7), e(23), e(39), etc. These events are enhanced with rectangles in the sequence shown in figure 4.
Such functions could be associated to the transition that yields the marking change in the obtained IPN structures as a compound event. The functions that provoke a given oe OES are associated through the function : : OESo 2F.
Afterwards, functions associated to every oe must be gathered according to the event part of the input function; then the condition part can be expressed as a disjunction of contexts of the corresponding functions, and then compacted by Boolean simplifications.
In the example, the output event oe= R1_0 L1_1 is provoked by the input events represented by the functions: f2(R1_0 L1_1) = (c_1, ݉തܽ ത ത ത ݀ ҧ݂ )ҧ, and f10(R1_0 L1_1) = (c_1, ݉തܽ ത ത ത ܾത݀ ത ത ത ҧ݂݁ ҧ), which can be embedded by the composed function g1= f2,10= c_1x (݉തܽ ത ത ത ݀ ҧ݂ ҧ + ݉തܽ ത ത ത ܾത݀ ത ത ത ҧ݂݁ ҧ) = (c_1, ݉ ഥ ܽ ത݀ ҧ݂ )ҧ, which is associated to t2 in figure 3.
Once the observable components are obtained, the sequence of transitions S that reproduces the reactive events is computed. This is straightforward performed by tracking the firing functions sequence FS and applying a mapping O :To {gi}.
The technique above described is summarised in Algorithm 2 given below. Algorithm 2. Compound functions Input: F, FS, and OES Output: T, O , S, Timed sequence SW 1.Sm Ø; SW m Ø; Tm Ø; 2.// Finding functions with the same output event (oe) oe OES: ȍRHĸ ; fr F: If U (fr)=oe then ȍRHĸ fr 3.// Gathering the functions in ȍRHDWYKV6P(5 oe OES 1; Z iĸ ; Z Vĸ z 6. Return T, O , S, SW Property 2 x Algorithm 2 returns the set of Transitions T and the labelling O , which associates the input firing functions. Furthermore, the procedure builds both sequences S and St. As defined in the Step 5, S is formed by transitions ti that correspond to fr in FS; then by Property 1, S correspond to event sequence E, consequently to w. x Step 2 of Algorithm 2 is performed in O((|OES|)(|F|)). Step 3 is executed in O((|OES|)(|ȍRH|) 2). Step 4 is completed in O(|Z s|). Step 5 is performed in O(|FS|). The length of diverse structures is as follows: ȍRH_ |Z s_ 2(6_ )_ 6)_ . Then, the approximated complexity of the procedure O(|FS|). Given that |w|=N |RE| and |FS|=|RE|, this complexity is linear on the length of w.
In Example 1, 12 different input functions for 6 output events were computed. They are summarised in Table 1. The observable sub-model is depicted in figure 4.
Proposition 1. The observable model reproduces the input-output sequence w and behaves 1-bounded with respect to the execution of such a sequence.
Proof. The non-observable model is built from the output part of the reactive events, which mark and unmark the observable places following the reactive events sequence RE. In turn RE reproduces w by property 1; then, the model is able to execute w. Since by assumption the process behaves correctly, there is not two successive requests to activate an operation before deactivate it and then the places have zero or one tokens during the execution of w.
In order to complete the model, a technique that finds a PN model, which reproduces the transitions sequence S has to be applied. This model, called the non observable PN, is merged with the observable model to obtain the IPN that reproduces the input/output sequence w.
The method used for computing the non observable model is presented in [
Both the non observable and the observable models are combined by merging the transitions that have the same name. In the example the merging of models in figures 4 and 5 yields the IPN shown in figure 6. Afterwards, non observable implicit places are removed, and then the model yield is shown in figure 7.
p7 p8 t1 p2 p1 t2 t3 Proposition 2. The partially observable IPN model (Q, M0) obtained through the proposed method is able to reproduce the input-output sequence w. Such a model behaves 1-bounded when w is fired.
Proof. By property 2, the observable model reproduces w, hence the transitions sequence S. The method for computing the non observable models also guarantees the reproduction of S; therefore, the compound model reproduces the sequence w. In this model, by Proposition 1 and by the 1-boundedness of the non observable model, the final model is also 1-bounded.
The last stage of the identification method is to obtain the timing parameters of the IPN models. For this purpose, the Tim function is determined from the timed sequence SW and the structure of the synthesized PN.
The strategy consists in parsing SW by comparing the transition tk in SW (k) with one or several previous transitions in the sequence, and then determining the time elapse between W (fr) of SW (k) and the corresponding W (fr) in the upstream SW (k-i). This reasoning is based on the semantics of transition-timed Petri nets in which the time elapse associated to a transition tk represents the maximum stay duration of the marking that enables tk. Thus, every time tk appears in the sequence one must analyze the occurrence of x (x tk) in the subsequence preceding SW (k), up to the previous appearance of tk or SW (1). Figure 8 illustrates the general structure of the PN fragment to analyze. . . .
tk
W (tk)
For every place in x tk, one must detect one of the input transitions (since the PN is 1-bounded) in the subsequence preceding tk in SW ; among these transitions, let tr be that whose date is the latest, then the maximum residence time of tokens in the marking that enables tk is G= W (tk) W (tr), which is indeed the time elapse associated to tk for this subsequence. The above strategy is summarized and structured in Algorithm 3 given below.
Algorithm 3. Determining timing function Input: SW Output: function Tim 1. tj T: J (tj) m 2. tj T:
For k=1 to |SW | // analysing the occurrences of tj in SW
If tj= GetTrans(SW (k)) then {W (tj) m GetTime(SW (k)); r m k - 1 While (GetTrans(SW (r)) x (x tj)) do
r m k – 1
Endwhile W (tr) m GetTime(SW (r));
J (tk) m J (tk) (W (tk) W (tr))}
Endfor 3. tj T
G (tj) m average(J (tj)); L (tj) m [min(J (tj)), max(J (tj))]
Tim(tj)m (G (tj), L (tj)) 4. Return Tim Property 3 x The algorithm obtains for every transition tj, both the average of the duration of the making enabling tj, and their minimum and maximum values. It is easy to see the SW is executed witin the instants given by the computed interval. x The first and the third steps are performed in O(|T|). The second step is more time consuming; inside the two for iterations (executed in O(|T||SW |)), one must explore in S a subsequence preceding tj, which contains x tj. Since the maximum value of the |x tj| is small compared to |SW |, the complexity is O(|T||SW |)).
In Example 1, the timing parameters obtained from SW are given in Table 2.
In this paper the problem of identifying timed discrete event processes is addressed. A novel method that obtains the observable components of an IPN model and determines the timing parameters is proposed.
In this problem the only available input data is a sequence of input-output vectors and the instants when they are recorded. Using the method that discover the non observable model, the final obtained model is an IPN in which the process outputs are associated to some places, and the transitions are labelled with functions of inputs that express the reactive behaviour of the process. The time parameters are given as a pair (G, L ) corresponding to the parameters of timed and time PN respectively.
The proposed method for computing the observable components is simpler than a
previous work [
Current research studies the obtained time parameters; the time elapsed can be highly dispersed and then a refinement of the untimed model could be required.