Fault Diagnosis of P-Time Labeled Petri Net Systems Patrice Bonhomme University François-rabelais CNRS, LI EA 6300, OC ERL CNRS 6305 64 avenue Jean Portalis 37200 Tours France bonhomme@univ-tours.fr This paper focuses on the fault diagnosis problem of systems modeled with P-time labeled Petri nets with partial information. Indeed, the set of transitions is partitioned into those labeled with the empty string ǫ called silent (as their firin cannot be detected) including the faulty transitions and the observable ones. The proposed approach is based on the synthesis of a function called diagnoser allowing to determine the diagnosis state of the system based on the current observation. The novelty of the developed approach resides in the fact that, although the time factor is considered as intervals, the diagnoser is computed thanks to the underlying untimed Petri net structure of the P-time labeled model considered. Furthermore, the method relies on the schedulability analysis of particular firin sequences exhibited by the analysis of the obtained diagnoser and does not require the building of the state class graph. Discrete event systems. Petri nets. Time labeled systems. Observability. State estimation. Fault diagnosis. 1. INTRODUCTION Thus, being given a sequence of observed events (called word or trace) the challenge consists in determining if a The correct behavior of a real-world application is the fault has occurred, eventually or for sure! ultimate requirement, particularly for systems such as communication protocols, manufacturing and real-time It can be noticed that the problems of fault diagnosis systems. Indeed, a drift from an expected behavior can has receive extensive attention these recent years and be of crucial importance and can even lead, in extreme particularly in the framework of automata models and cases, to severe consequences including human losses. So, regular languages (Sampath et al. (1995), Cassandras and knowing the current state of a system in order to take the Lafortune (2008), Lin (1994), Cassez and Tripakis (2008)) appropriate decisions and determining the malfunction of but there are few studies in the time discrete event systems a system component are nowadays fundamental issues. context. From a practical point of view, associating a dedicated A preliminary version of this paper was presented in sensor to each variable of interest in order to monitor (Bonhomme (2014)) where an approach allowing to its internal state is inconceivable. This restriction, due to estimate the marking of a P-time labeled Petri net (P- economical or physical accessibility reasons leads to a TLPN) system based on the observation of particular system analysis in presence of uncertainties as the state labels was presented. The plant observation is given by information cannot be directly obtained. This particularity a set of labels whose occurrence can be detected/observed has gave rise to the introduction of the observers paradigm by an external agent (called observer or estimator) - these in the classical system theory. Indeed, an observer can particular labels are associated to observable transitions. be viewed as a mechanism allowing to estimate or The other transitions, the unobservable ones (called silent reconstruct the internal state of a system based on some transitions) are labeled with the empty string ǫ. measurements. From a discrete event dynamic systems point of view and more precisely from a Petri net (PN on In this extended and enriched version, a fault diagnosis short) perspective this issue corresponds to the estimation problem is solved thanks to the introduction of a function of a PN marking based on some event observations. called diagnoser which associates to each observation a diagnosis state. In the proposed technique the set of unobservable transitions is further partitioned into the set of faulty transitions and the set of regular ones. The Note that a complete survey of fault diagnosis methods regular transitions are unobservable and non faulty. for DES can be found in (Zaytoon and Lafortune (2013)). In (Cabasino et al. (2010)) the authors proposed a The proposed approach does not require the state class diagnosis approach based on the concept of basis marking graph construction and consequently it is designed to and justificatio under the acyclicity assumption of the alleviate the state space explosion problem. Indeed, the unobservable subnet of the system considered. Intuitively, construction of the considered state observer is based on for an observed sequence (word) ω, a justificatio can be the analysis of the underlying untimed PN structure of the thought as the set of minimal (in terms of firin vector) P-time labeled PN considered. unobservable transitions interleaved with ω necessary to complete ω into a fireabl sequence on the net considered, In particular, the following four assumptions are made: from the initial marking. They extended their work in (Cabasino et al. (2014)) to provide a diagnosability 1. the net structure and the initial marking are known, approach for bounded labeled PN by introducing two 2. the fault model is known, graphs, namely the modifie basis reachability graph (MBRG) and the basis reachability diagnoser (obtained 3. the underlying untimed PN, of the P-TLPN from the MBRG). Necessary and sufficien conditions for considered is bounded, diagnosability are given but the construction of the two graphs is of exponential complexity with respect to the 4. the Petri net induced by the set of unobservable structure of the PN considered and its initial marking. transitions does not contain circuit of null length. There are relatively few works in this topic in the time Note that this latter assumption is adopted to exclude discrete event systems scheme where the time factor is the situation where an infinit of actions may take place modeled as intervals, so, numerous problems are still in a finit amount of time: it prevents the net induced open. Concerning the time Petri net model of Merlin by the set of unobservable transitions from being Zeno (Merlin and Faber (1976)), the authors in (Basile et al. (Hadjidj et al. (2007)) which is in contradiction with a (2013)) proposed a procedure for estimating the marking diagnosability scheme. In addition, there is no assumption of the model in presence of unobservable transitions. They on the backward conflic freeness of the subnet induced introduced a modifie state class graph which captures by the set of unobservable transitions as in (Giua et al. the required information on the possible evolution of the (2007)). system starting from a given initial marking. Thanks to The paper is organized as follows: after an overview this graph, being given a timed sequence and a time of the relevant literature in the next section, a brief instant, the set of markings consistent with the current reminder of the basics of untimed Petri nets followed by a observation is determined via integer linear programming formal definitio of P-time labeled Petri nets is realized techniques. The approach is restricted to bounded time in the third section. Section four covers the procedure Petri nets. of estimation and the construction of the state observer. In a recent paper, the authors in (Basile et al. (2015)) The schedulability analysis of the occurrence sequence extend the previously mentioned approach developed in highlighted by the state observer and its application to the (Basile et al. (2013)) to deal with the state estimation and estimation problem are studied in the fift section. In the the fault diagnosis problem for systems modeled by time sixth section the fault diagnosis problem is solved. Section PN augmented with labels. seven presents an illustration of the developed method and the last section concludes the paper and gives suggestions The authors in (Wang et al. (2013)), thanks to a fault for future research. diagnosis graph (FDG) which is a truncation of the conventional state class graph (SCG) (Berthomieu and 2. LITERATURE REVIEW Diaz (1991)), developed an online technique for the fault diagnosis of systems modeled by unlabeled time For discrete event system (DES) state estimation has Petri nets. The FDG is constructed incrementally with been addressed by several researchers. For instance, in respect to the current observation and its number of states (Giua et al. (2007)) the authors deal with the marking can be, in the worst case, the same as the one of the estimation of a labeled Petri net system. Thanks to traditional state class graph. Indeed, the FDG is obtained structural assumptions on the subnet induced by the set from the SCG by only keeping the information required of unobservable transitions, they propose an algebraic for the evaluation of the fault states and the authors characterization of the set of consistent markings once a concentrate on the sequence information and remove the sequence is observed. irrelevant state classes (i.e., which are not used in the fault diagnosis). Intuitively, the state classes which are obtained In the framework of fault detection or fault diagnosis after the firin of an unobservable transition are discarded several approaches can also be found in the literature - as the diagnosis state is updated after an observation. fault diagnosis is closed to the state estimation problem. The acyclicity assumption of the subnet induced by the In the proposed approach, the set of transitions is unobservable transitions is also considered. The authors partitioned into two sets: observable transitions whose further extend the method in (Wang et al. (2014)) by using firin can be detected by an external observer, denoted reduction rules and model checking techniques. as To and unobservable transitions whose firin cannot be detected, denoted as Tu with T = To ∪Tu and To ∩Tu = ∅. 3. PETRI NETS More precisely, the following stands: 3.1. Untimed Petri Nets • Tu = {t ∈ T |LM(t) = ǫ}, transitions in Tu are The reader unfamiliar with Petri nets can refer to (Murata also called silent, (1989)), in the following only the basic notions are • To = {t ∈ T |LM(t) 6= ǫ} (i.e., To is the set of recalled. transitions labeled with a symbol in Ω). A Place/Transition net (P/T net) is a structure N = In the proposed approach, the same label ζ ∈ Ω can be (P, T, P re, P ost), where P is a set of m places; T is a set shared by several transitions, i.e., two transitions ti , tj of n transitions. P re : P ×T → N and P ost : P ×T → N with ti 6= tj will be called indistinguishable if: are the pre and post incidence functions that specify the arcs; C = P ost − P re is the incidence matrix. The preset LM(ti ) = LM(tj ) = ζ. and postset of a node X ∈ P ∪ T are denoted ◦ X and X ◦ . A marking is a vector M : P → N that assigns to The extension of the label mapping can be realized over each place of a P/T net a non-negative integer number of sequences, LM : T ⋆ → Ω⋆ , recursively as follows: tokens, represented by black dots. M (p) is the marking of place p. 1. LM(ti ) = ζ ∈ Ω if ti ∈ To , A net system hN ; M0 i is a net N with an initial marking 2. LM(ti ) = ǫ if ti ∈ Tu , M0 . A transition t is marking enabled at M if M ≥ P re(·, t). A transition t enabled at M may fire yielding 3. let σ ∈ T ⋆ and ti ∈ T then LM(σti ) = the marking M ′ = M + C(·, t). We write M [σ > to LM(σ)LM(ti ), denote that the sequence of transitions σ is enabled at M , 4. LM(λ) = ǫ where λ is the empty sequence. and we write M [σ > M ′ to denote that the firin of σ yields M ′ . A marking M is reachable in hN ; M0 i iff there 3.3. P-time Petri Nets exists a firin sequence σ such that M0 [σ > M . Definitio 1 The formal definitio of a P-TPN (Khansa The set of all sequences that are enabled at the initial et al. (1996)) is given by a pair hN ; Ii where: marking M0 is denoted L(N, M0 ) i.e., L(N, M0 ) = {σ ∈ T ⋆ |M0 [σ >} with T ⋆ the Kleene closure of set T • N is a marked Place/Transition net (a P/T net i.e. the set of all firin sequences of elements of T of system augmented with a marking) arbitrary length, including the empty sequence λ. The notation σ ′ σ will correspond to the firin sequence σ ′ • P → (Q+ ∪ {0}) × (Q+ ∪ {∞}), followed by firin sequence σ, i.e., the concatenation • pi → I(pi ) = [ai , bi ] with 0 ≤ ai ≤ bi operation ; σ ′ is the prefi of firin sequence σ ′ σ. With: The set of all markings reachable from M0 define the reachability set of hN ; M0 i and is denoted R(N, M0 ). • P : the set of places of the net N , Given a net N = (P, T, P re, P ost) and a subset • Q+ : the set of positive rational numbers, Ts ⊆ T , the Ts -induced subnet of N is the net Ns = (P, Ts , P res , P osts ) where P res and P osts are the • Ii define the static interval of the operation restrictions of P re and P ost to Ts . So, the net Ns is duration of a token in a place pi . obtained from N by removing all transitions in T \ Ts , it is denoted also by Ns ∠Ts N . A token in place pi will be considered in the enabledness of the output transitions of this place if it has stayed for 3.2. Labels mapping ai time units at least and bi at the most. Consequently, the token must leave pi, at the latest, when its operation A labels mapping LM is associated to each transition of duration becomes bi . After this duration bi , the token the net considered as follows will be ”dead” and will no longer be considered in the S enabledness of the transitions. According to the strong LM : T → Ω {ǫ} , firin mode, a transition in a P-TPN, is forced to fir unless it is disabled by the firin of another conflictin transition. with Ω a finit alphabet and ǫ the empty string. Let consider αi the clock associated with the token Finally, given a sequence of labels (a word) ω ∈ Ω⋆ , it denoted i ∈ T K of the P-TPN (T K being the set of is denoted by ω k the k th element in ω and the number tokens of the P-TPN considered). υ is a valuation of the of elements of ω is denoted by |ω|. For a ∈ Ω, we write system, i.e., a mapping associating to each token i of a ∈ ω if there exists k ≥ 1 such that ω k = a (i.e., a is an the P-TPN, an element of (R≥0 ), υi , representing the element of the word ω). time elapsed since the token i has been created (i.e., the valuation of the clock αi ). So, υ ∈ (R≥0 )T K with the Furthermore, let ω1 , ω2 , . . . , ωn be n sequences of labels notation AX representing the set of mappings from X to (i.e., wi ∈ Ω⋆ , 1 ≤ i ≤ n), the notation ω = ω1 ω2 . . . ωn A. 0 is the initial valuation with ∀i, 0i = 0 will be the concatenation of ω1 , ω2 , . . . , ωn . The semantics of a P-TPN can be define as a Timed The next section recalls the procedure (Bonhomme Transition System (TTS). A state of the TTS is a couple (2015)) to construct the state observer. s = (M, υ) where M is a marking and υ a valuation of the system. 4. ESTIMATION PROCEDURE Definitio 2 The semantics of a P-TPN hN ; Ii is define The goal of the observer is to give the current state by the Timed Transition System SN = (Q, {q0 } , Σ, −→): estimate of the system based on the information of the observed traces. The state of the observer will consist in a 1. Q = NP × (Q≥0 )T K set of states the model can be in after a label observation. 2. q0 = (M0 , 0) The following set will be associated to any observed word 3. Σ = T ω (i.e., the observed labels sequence): 4. −→∈ Q × (Σ ∪ Q≥0 ) × Q • L(ω) is the set containing all sequences of transitions that are consistent with ω, i.e., the • The continuous transition is define ∀d ∈ R≥0 by: set of all possible firin sequences that produce  ′ observation ω. d υ = υ + d. (M, υ) → (M, υ ′ ) iff ∀ token k in ps ⇒ υk′ ≤ bs . In general, if ω is an observed word, the associated firin sequence σ ∈ LM−1 (ω) is not necessarily fireabl on the • The discrete transition is define ∀ti ∈ T by: net as some unobservable transitions should be interleaved t to obtain a fireabl sequence that produce ω. i (M, υ) → (M ′ , υ ′ ) iff: Definitio 4 Let N be a P-TLPN with T = To ∪ Tu . The M ≥ ◦ ti . following operator is defined   ∀ token k in pl , υk ≤ bl .    • The projection over To is Po : T ⋆ → To⋆ define as:  Tps ∈ ti ,∀ token k in ps involved in ti ’s firin : ◦   ∀   [max(0, as − υk ), (bs − υk )] 6= ∅. – Po (λ) = λ,  k′ = M − ◦ ti +  ti . ◦   M – for all σ ∈ T ⋆ and t ∈ T, Po (σt) = Po (σ)t if 0 if created by ti .    ∀ token r, υr′ = t ∈ To and Po (σt) = Po (σ) otherwise (with   υr otherwise.  λ representing the empty sequence). The dynamic evolution of a P-TPN depends on the Given a sequence σ ∈ L(N, M0 ), ω = LM(Po (σ)) timing situation of each token. Indeed, each token will denotes the corresponding observed word. be associated with a potential firin interval (or dynamic interval) which can be different from its static one. For Definitio 5 Let N be a P-TLPN with T = To ∪ Tu and instance, consider place pi with static interval [ai , bi ], ω ∈ Ω⋆ be an observed word. L(ω) is define as: let a token arrive in place pi at absolute time τ . At τ its potential firin interval will correspond to [ai , bi ]. At L(ω) = Po−1 (LM−1 (ω)) ∩ L(N, M0 ) = time τ + c with c ≤ bi the dynamic interval of the {σ ∈ L(N, M0 )|LM(Po (σ)) = ω}, considered token will become [max(ai − c, 0), bi − c]. It can be noticed that a token is considered as dead when i.e., the set of firin sequences consistent with ω ∈ Ω⋆ . its dynamic interval becomes [0, 0]. Definitio 6 Let N be a P-TLPN with T = To ∪ Tu and Definitio 3 A P-time labeled Petri net (P-TLPN on ω ∈ Ω⋆ be an observed word. C(ω) is define as: short) over an alphabet Ω is a triple hN, S I, LMi where C(ω) = {M ∈ R(N, M0 )|∃σ ∈ L(ω) : M0 [σ > M }, hN, Ii is a P-TPN and LM : T → Ω {ǫ} is a labeling function. i.e., the set of markings consistent with ω. So, being given an observed word ω, L(ω) is the set of • ςso : Yso → 2R(N,M0 ) is a function associating to sequences that may have fire while C(ω) is the set of each state yso ∈ Yso a set of reachable markings, markings in which the system may actually be. • y0 is the initial state of the state observer and t5 ςso (y0 ) = SEM (N0 ) ∪ SSM (N0 ), [1, 3] P1 P2 [1, 2] a [0, 6] t6 P4 t7 P5 • fso : Yso × Eso ⋆ → Yso is the transition function define as : for yl ∈ Yso a state of the observer and t4 t1 P3 [1, 3] [2, 4] a string of observable labels t2 ⋆ b ω ∈ Eso b fnso (y0 , ω) = yl if ςso (yl ) ∈ / ∅ where o ςso (yl ) = t3 τ Ml : M0 → Ml ∧ LM(Po (τ )) = ω = Figure 1: P-TLPN model. SEM (Nl ) ∪ SSM (Nl ). Let consider the P-TLPN of Figure 1 with Tu = With the two sets SSM and SEM define as follows: {t4 , t5 , t6 , t7 }, To = {t1 , t2 , t3 }, Ω = {a, b}. It holds LM(t1 ) = a, LM(t2 ) = LM(t3 ) = b (transitions t2 Definitio 9 Sets SSM and SEM and t3 are indistinguishable) and LM(ti ) = ǫ, ∀ti ∈ Tu . • SEM (Nj ), the Set of Entry Markings of Nj , If the observed word is ω = ab then LM−1 (ω) = {t1 t2 , t1 t3 } and L(ω) = {t4 t1 t2 , t4 t1 t6 t7 t3 } and C(ω) = [10000]. SEM (Nj ) = {Ms ∈ Nj |∃Mu ∈ Ni , tk ∈ To , Definitio 7 Let N be a P-TLPN with T = To ∪ Tu , the ak ∈ Ω, LM(tk ) = ak : Mu [tk > Ms } unobservable reachability mapping UR, which enables to fin the markings reachable from a given marking • SSM (Nj ), the Set of Shadow Markings of Nj , Mi , following the firin of all unobservable sequences is define as: SSM (Nj ) = {Ms ∈ Nj |∃Mu ∈ SEM (Nj ), UR : Nm → 2N , m σu ∈ Tu⋆ : Mu [σu > Ms } Mi → UR(Mi ) = {Mj ∈ Nm |∃σu ∈ Tu⋆ , Mi [σu > Mj } , or equivalently, SSM (Nj ) = U R(SEM (Nj )). m with 2N the power set of the markings of the PN considered. Intuitively, for a given node Ns of the state observer, after the observation of the word ω, the set SEM (Ns ) ∪ 4.1. State observer SSM (Ns ) represents the set of markings that are consistent with the current observed word (i.e., C(ω)). The Let Ni and Nj be two nodes of the graphical representa- other nodes can be computed recursively as explained in tion of the state observer (associated respectively to the the following. states yi and yj of the observer) such that it exists a directed arc linking Ni to Nj (Ni → Nj , i.e., Ni is 1. The state observer starts in the initial state y0 a predecessor of Nj ) labeled with ak with ak ∈ Ω as and its associated initial node N0 is composed of illustrated on Figure2. SEM (N0 ) = {M0 } and SSM (N0 ) = U R(M0 ). Nj 2. as soon as a label ak (associated with an observable transition tk ∈ To ) is observed a new state yl of the Ni ak observer is calculated yielding a new node Nl : • the set of entry markings of node Nl is Figure 2: nodes of the state observer. obtained by investigating the set of markings resulting from the firin of transition tk Definitio 8 The state observer for the partially observ- starting from any marking (SEM ∪ SSM ) of able P-TLPN N with initial marking M0 and T = To ∪Tu N0 , is define by the 5-tuple (Yso , Eso , fso , y0 , ςso ) where: • the set of shadow markings of Nl corresponds • Yso is the set of states of the state observer, to the set of markings obtained by the firin of all unobservable sequences of transitions • Eso = Ω is the set of labels (associated to the starting from any entry marking of Nl , observable events), 3. return to 2 with the newly calculated state as the as soon as the token has been dropped in the place as seen initial state. previously. To compute the firin instants, this approach requires that a token is identifie by three parameters: Definitio 10 Let Ni and Nj be two nodes of the state the place that contains it, the information of its creation observer, Ni and Nj are said to be equivalent (Ni ⇔ Nj ) instant and of its consumption one. if and only if: Function T OK is define with this purpose assuming that SEM (Ni ) = SEM (Nj ) and SSM (Ni ) = SSM (Nj ). a FIFO queuing policy in the net is used in the sequel: Proposition 1 Two nodes Ni and Nj of the state observer T OK:N × (N \ {0}) × T ⋆ → ℘(P )), will be equivalent if and only if, the following holds: T OK(j, n, σ) = {p ∈ P |p contains a token created by SEM (Ni ) = SEM (Nj ). the j th firin instant and consumed by the nth one in firin sequence σ}. Definitio 11 Given a marking Mi ∈ R(N, M0 ) and a transition tf ∈ To (associated with a label lf ∈ Ω, i.e., With ℘(P ) the set of subsets of P (also noted 2P ). LM(tf ) = lf ), the set of candidate sequences denoted CS(Mi , tf ) is the set of firin sequences, composed of When it is clear from the context σ will be omitted in the the unique fina observable transition tf , which can occur notation of T OK(.). from Mi , i.e.: When the weight of the P-TPN arcs is element of N, CS(Mi , tf ) = {s.tf |s ∈ Tu⋆ ∪ λ, tf ∈ To : Mi [s.tf >}. T OK(j, n) is a multi-set. For the sake of simplicity, only ordinary P-TPN are considered (the arcs weight are With respect to the timing constraints to be satisfied element of {0, 1}). candidate sequences can be in the state possible or impossible. Tokens, with the same creation instant, located in different places and involved in the same transition firin may As Nu ∠Tu N (i.e., the Petri net induced by the set of mutually constrained their sojourn time, the following unobservable transitions) is not Zeno by assumption, it quantities, Dsmin and Dsmax, are introduced in order is ensured that the time is diverging with regard to the to evaluate the contribution of these tokens. So, Dsmin length of the firin sequences, thus, the set of candidate represents their availability in order to participate to this sequences from a marking is necessarily finit (at the firin and similarly, Dsmax expresses the fact that they instant of observation) and it can be investigated. The all must be prevented from dying (with [ai , bi ] the static following section addresses the schedulability analysis interval associated with the place pi ). (Bonhomme (2013b)) of an occurrence sequence (i.e., a max (ai ), i | pi ∈ T OK(j, n)  procedure verifying if the considered firin sequence can Dsmin(j, n) = , occur without any violation of timing constraints) and its else 0 if T OK(j,n) = ∅ application to the estimation problem. min (bi ), i | pi ∈ T OK(j, n)  Dsmax(j, n) = . else + ∞ if T OK(j,n) = ∅ 5. SCHEDULABILITY ANALYSIS AND ESTIMATION The definitio of the following set SEN (q), allowing to Let σ = ta tb tc . . . tq be a firin sequence of length s determine the creation instants of tokens involved in the (denoted |σ| = s). The j th fire transition of σ will q th firin instant, is also necessary: be associated with the j th firin instant (Bonhomme (2013a)). A variable xi will represent the elapsed time SEN (q) = {u|T OK(u, q) ⊂ ( °tq )} between the (i − 1)th firin instant and the ith one (with x0 = 0). To express more simply the obtained results, the definitio of the following coefficient is required: For instance on Figure 3, (x2 + x3 ) is the time elapsed Dsmin(u, q) if u ∈ SEN (q)  between the firs firin instant (associated with transition cuq = , ta ) and the third one (transition tc ). 0 else Dsmax(j, k) if T OK(j, k) 6= ∅  firing of ta firing of tb firing of tc firing of tq djk = x1 x2 x3 ......... xs +∞ else Figure 3: Firing instants. With, ∀(j, k) ∈ [0, q − 1] × [1, q], j ∈ / SEN (q) and k 6= q, then cjk = 0, and ∀k ∈ [0, q], xk ≥ 0. In a P-TPN, the sojourn time (i.e., the amount of time that a token has been waiting in a place) is counted up The following proposition is finall obtained: Proposition 2 A sequence of transitions σ = t1 t2 ....tq • for each σf ∈ CS(M0 , tf ) (with Po (σf ) = tf ) the is schedulable (i.e., it may be fi ed respectively at firin associated linear system Sσf will be constructed, instants 1, 2, . . . , q) if and only if there exist x1 ≥ 0, x2 ≥ 0,..., xq ≥ 0 such that: • and each σf will be checked for schedulability with the following additional constraint: c0k ≤ x1 ≤ d0k , k = 1, ..., n  P|σf | i=0 xi = τf .   max (c0k , c1k + x1 ) ≤ x1 + x2 ≤ min (d0k , d1k + x1 )    k=2,...,n k=2,...,n   ...   j X q X j X Thanks to these considerations it is ensured that sequence max (cjk + xs ) ≤ min (djk + xs ) σf is schedulable and the firin of tf occurs at τf . Once a    xs ≤  j=0,...,q−1  j=0,...,q−1 s=0 s=0 s=0 k=q,...,n k=q,...,n firin sequence is proved to be possible the set of markings the system can be in is then determined. In the sequel this system will be denoted as Sσ (q) or simply Sσ when it is clear from the context. Let denote by F EAS(N0 , tf ) the set of schedulable firin sequences from node N0 ending with the unique Definitio 12 The firin space at the q th firin instant, observable transition tf (it is a subset of the set of associated with a firin sequence σ, denoted by FS σ (q) candidate sequences). is the set of non negative vectors (x1 , ..., xq ) such that the fi st, the second, . . . and the q th firin conditions F EAS(N0 , tf ) = {σ ∈ CS(M0 , tf )|FS σ (|σ|) are satisfied Thus, a firin sequence σ = t1 t2 ....tq is schedulable if and only if its associated firin space P|σ| o augmented with x = τ is non-empty . FS σ (q) is non-empty. i=0 i f Thanks to this characterization of a firin sequence, the Furthermore, based on the knowledge of the schedulable Zenoness property can be checked by evaluating the candidate firin sequences only a subset of the set of minimal duration of the circuit of unobservable transitions entry markings of node Nf (resulting from the firin of under consideration (for instance, by minimizing the sum transition tf ), denoted SEM ′ (Nf ), will be considered for of the xi associated with the considered transitions). the next step. It holds: Definitio 13 A P-TLPN Nr firin schedule, will be a i SEM ′ (Nf ) = {M ∈ SEM (Nf )|M0 [σ > M, sequence of ordered pairs (ti , xk ) ; transition ti P k=0 σ ∈ F EAS(N0 , tf )}. i fi able at time ( xk ), obtained from the state reached P k=0 With SEM ′ (Nf ) ⊆ SEM (Nf ). by starting from Nr initial state and firin the transitions tj , 1 ≤ j < i, in the schedule at the given times. Afterwards, if another label ax is observed at absolute time τx then: Finally, as in (Basile et al. (2015)), let denote: • The set of associated observable event Tax = ωt = ((a1 , τ1 ), (a2 , τ2 ) . . . (an , τn )) ∈ (Ω × Q+ )⋆ , {t ∈ To |LM(t) = ax } will be evaluated, a time-label sequence (TLS), i.e., a sequence of pairs • then, ∀tx ∈ Tax the set of feasible candidate (observed label-time instant). sequences CS(Mi , tx ) will be computed with Mi ∈ SEM ′ (Nf ), Indeed, in the considered sequence, label ai is observed at absolute time τi (i ≥ 1) and τ1 ≤ τ2 . . . ≤ τn . • a switch from node Nf to node Nx is realized in the state observer, Now all the required material for the proposed method is • for each feasible firin sequence (on the underlying given, the principle is presented as follows: untimed PN) σf′ σx (i.e., M0 [σf′ σx >) with σx ∈ CS(Mi , tx ) and σf′ ∈ F EAS(N0 , tf ) the • starting from the initial state, once a label af will be associated linear system Sσf′ σx will be constructed. observed at the absolute time τf , It is recalled that σf′ is a schedulable firin sequence • the set of associated observable event Taf = determined in the previous step with label af {t ∈ To |LM(t) = af } will be evaluated, observed at τf and Po (σf′ σx ) = tf tx . • then, ∀tf ∈ Taf the set of feasible candidate • each previously determined σf′ σx will be checked sequences CS(M0 , tf ) will be computed, for schedulability with the following additional • a switch from node N0 to node Nf (created by constraint: the observation of label af ) is realized in the state P|σf′ |+|σx | observer, i=0 x i = τx . ensuring that the firin of tx occurs at τx . can be completed by schedulable sub-sequences into a schedulable firin sequence starting from the initial And so on, the same method is iteratively applied with marking of the P-TLPN considered. respect to the current observation. So, by this way it is ensured that the feasible So, more formally the following principle is obtained: firin sequences associated with the observed time- let ωobs be an observed word (i.e., a sequence of labels label sequence ((a1 , τ1 ), (a2 , τ2 ) . . . (ai+1 , τi+1 )) are ωobs = a1 a2 a3 . . . ai ai+1 . . . ∈ Ω⋆ ) and let Ni (i ≥ 1) effectively computed. be the node of the associated state observer obtained after the observation of label ai ∈ ωobs detected at absolute In the next section, addressing the fault diagnosis problem time τi , as illustrated on the following figur (Figure 4). of a P-TLPN system, this set will be used to evaluate the state diagnosis associated with an observed TLS. N0 N1 N2 Ni a1 a2 ai a i+1 .... .... 6. FAULT DIAGNOSIS Figure 4: Observable sequence. The set of unobservable transitions is partitioned into two subsets, Tu = Tf ∪ Treg where the set Tf includes all the The associated sets F EAS and SEM ′ are computed as fault transitions (modeling anomalous or faulty behavior) follows: while Treg includes all unobservable transitions which correspond to regular events. Furthermore, the set Tf is Let t1 ∈ Ta1 = {t ∈ To |LM(t) = a1 }, partitioned into r different subsets Tfi , where i = 1, . . . , r, that models the different fault classes. F EAS(N0 , t1 ) = {σ ∈ CS(M0 , t1 )|FS σ (|σ|) augmented P|σ| o Definitio 14 Let hN ; M0 i be a net S system with labeling with k=0 xk = τ1 is non-empty . function LM : T → Ω {ǫ} , where N = (P, T, P re, P ost) and T = To ∪ Tu . Let consider the TLS ωt = ((a1 , τ1 ), (a2 , τ2 ) . . . (an , τn )) associated with the SEM ′ (N0 ) = SEM (N0 ) = {M0 } and state observer of Figure 4. SEM ′ (N1 ) = {M ∈ SEM (N1 )|M0 [σ > M, Let define σ ∈ F EAS(N0 , t1 )}. (M0 , ωt ) = {σ ∈ T ⋆ |M0 [σ >, σ = σ1 σ2 . . . σn : P ∀i > 0, LM(σi ) = ai , i = 1, . . . , n, σs ∈ F EAS(Ns−1 , ts ), Let LM(ti+1 ) = ai+1 , LM(ts ) = as , s = 1, . . . , n} ′ F EAS(Ni , ti+1 ) = {σ ∈ CS(Mb , ti+1 )|Mb ∈ SEM (Ni ), Indeed, σ can be viewed as a concatenation of M0 [̟ >, FS ̟ (|̟|) augmented subsequences, namely σi , i ≥ 1. Each subsequence σi is o with P|̟| of the form s.ti with s ∈ Tu⋆ , LM(ti ) = ai and absolute x k=0 k = τ i+1 is non-empty . firin instant of ti is τi . So, it holds: With firin sequence ̟ = σ1 σ2 . . . σi σ where σs ∈ F EAS(Ns−1 , ts ), s ∈ {1, . . . , i} and Po (̟) = σi ∈ CS(Mb , ti ) with Mb ∈ SEM ′ (Ni−1 ). t1 t2 t3 . . . ti ti+1 . Definitio 15 A diagnoser is a function More precisely: Po (σj ) = tj , j ∈ {1, . . . , i} with LM(tj ) = aj . Γ : [Ω × Q+ ]⋆ × Tf1 , Tf2 , . . . , Tfr → {N, U, F }  ′ SEM (Ni+1 ) = {M ∈ SEM (Ni+1 )|Mk [σ > M, σ ∈ F EAS(Ni , ti+1 ), Mk ∈ SEM (Ni )}. that associates with each observed time-label sequence ωt and each fault class Tfi , where i = 1, . . . , r, a diagnosis SEM ′ (Ni ) is the set of entry markings of node Ni state. resulting from the firin of schedulable firin sequences • Γ(ωt , Tfi ) = N if ∀σ ∈ (M0 , ωt ) and ∀tf ∈ Tfi , P with respect to the current observation. it is tf ∈ / σ. Roughly speaking, F EAS(Ni , tk ) is the set of candidate In such a case the ith fault cannot have occurred, sequences of node Ni ending with tk and which because none of the firin sequences consistent with the considered observation contains a fault It holds t7 ∈ Tf2 and t7 ∈ ω2 (t7 ∈ / ω1 ), and t5 ∈ Tf1 , transition of class i. t5 ∈ / ω2 . / ω1 , t5 ∈ • Γ(ωt , Tfi ) = U if: So, Γ(ωt , Tf1 ) = N and Γ(ωt , Tf2 ) = U . 1. ∃σ ∈ (M0 , ωt ) and tf ∈ Tfi such that P It means, that according to the previous observed time tf ∈ σ, label sequence ωt , it is known for sure that the fault of 2. ∃σ ′ ∈ (M0 , ωt ) such that ∀tf ∈ Tfi , it is P class 1 (corresponding to fault transition t5 ) cannot have tf ∈/ σ′ . occurred while fault transition t7 ∈ Tf2 may have occurred In such a case a fault transition of class i may (via ω2 ). have occurred or not, the diagnosis is in this case, uncertain. If the observed TLS P corresponds to ωt = (b, 1), it is easy to verify that (M0 , ωt ) = {ω3 } with ω3 = t5 t2 • Γ(ωt , Tfi ) = F if ∀σ ∈ (M0 , ωt ), ∃tf ∈ Tfi such (the associated firin schedule is ((t5 , 1), (t2 , 1))) and P that tf ∈ σ. consequently, Γ(ωt , Tf1 ) = F and Γ(ωt , Tf2 ) = N (i.e., a In such a case the fault of class i must have fault of class Tf1 occurs for sure and a fault of the second occurred, because all firabl sequences consistent class cannot have occurred). with the considered observation contains at least one fault transition of class i. In the next section an illustrative example is presented where the Tu -induced subnet is cyclic. Let consider the P-TLPN of Figure1 with Tu = {t4 , t5 , t6 , t7 }, To = {t1 , t2 , t3 }, Ω = {a, b}. It holds 7. ILLUSTRATIVE EXAMPLE LM(t1 ) = a, LM(t2 ) = LM(t3 ) = b (transitions t2 and t3 are indistinguishable). Furthermore, Tf1 = {t5 } and Let consider the P-TLPN of Figure 6 with To = {t2 , t5 }, Tf2 = {t7 }, i.e., there are two fault classes. Tu = {t1 , t3 , t4 , t6 , t7 }, Tf = {t6 } and LM(t2 ) = a, LM(t5 ) = b. The Tu -induced subnet contains the cycle b (p3 − t4 − p4 − t6 − p3 ). N1 N0 a SSM SSM SEM P1 SEM [01000] [00010] [00100] [1, 3] [00100] [10000] [00001] t1 [00010] [00001] P2 b [2, 8] Figure 5: State observer. a t2 [1, 12] P4 [10, 15] The corresponding state observer with two nodes is [2, 2] P3 t5 b t4 depicted on Figure 5. t3 P5 t3 t7 Let consider the following observed TLS ωt = t6 ((a, 2), (b, 5)) then: Figure 6: P-TLPN with a cyclic Tu -induced subnet. (M0 , ωt ) = {ω1 , ω2 } with ω1 = t4 t1 t2 and ω2 = P t4 t1 t6 t7 t3 . The state observer is depicted on Figure 7, it consists of We have (according to the notations of definitio 14): three nodes X0 , X1 and X2 . • ω1 = σ1 σ2 with σ1 = t4 t1 and σ2 = t2 , X1 a X2 b X0 SEM SSM SEM SSM • ω2 = σ1 σ2 with σ1 = t4 t1 and σ2 = t6 t7 t3 . SEM SSM [01000] [01000] a b [10000] [01000] [00100] [00010] [00001] [00100] The two obtained candidate sequences are feasible [00100] [00010] with regard to the timing constraints. Indeed, the a two associated firin schedules can be, for instance, considered respectively for ω1 and ω2 : Figure 7: State observer of the P-TLPN of Figure 6. • ((t4 , 1), (t1 , 2), (t2 , 5)), If the observed word is ω = (a, b) then the set of possible • ((t4 , 1), (t1 , 2), (t6 , 2), (t7 , 3), (t3 , 5)). associated firin sequences is of the form t1 t2 t4 (t6 t4 )⋆ t5 with the ⋆ after the subsequence (t6 t4 ) (derived from the Kleene star operator) indicating that it is allowed to occur observer which is an automaton allowing to estimate the from zero time to infinitel . Thanks to the time instant set of markings in which the system may be, being given of occurrence of each label the set of feasible associated a sequence of observed labels. firin sequences is necessarily finite Furthermore, the considered state observer is computed For instance if the TLS considered is: on the basis of the untimed underlying Petri net of the P-time labeled PN considered. This particularity allows ωt = ((a, 3), (b, 6)) then (M0 , ωt ) = {ω1 } with to avoid the combinatorial state space explosion problem P ω1 = t1 t2 t4 t5 . The associated firin space FS ω1 (|ω1 |) usually associated with the consideration of the time augmented with the following constraints: factor modeled as time intervals. • x1 +x2 = 3 (absolute firin instant of transition t2 ), Thanks to a schedulability analysis technique, the feasibility of the candidate firin sequences associated • x1 + x2 + x3 + x4 = 6 (absolute firin instant of with the observed time-label sequence is evaluated via transition t5 ), linear programming techniques. is non-empty. An issue currently being investigated is the extension of It holds: the method to test the diagnosability property of P-TLPN systems, i.e., is the fault can be detected within a finit ω1 = σ1 σ2 with σ1 = t1 t2 and σ2 = t4 t5 and an example number of steps after its occurrence ? of firin schedule is: ̟ = ((t1 , 1), (t2 , 3), (t4 , 5), (t5 , 6)), REFERENCES and it is unique with respect to the static intervals of the Basile, F., M. Cabasino, and C. Seatzu (2015, April). State P-TLPN places. So, it is easy to see that Γ(ωt , Tf ) = N estimation and fault diagnosis of labeled time petri and the faulty transition t6 cannot have occurred. net systems with unobservable transitions. Automatic Control, IEEE Transactions on 60(4), 997–1009. If the TLS considered is now: ωt = ((a, 3), P (b, 9)) then Basile, F., M. P. Cabasino, and C. Seatzu (2013). Marking Γ(ωt , Tf ) = U , as the computation of the set (M0 , ωt ) estimation of time Petri nets with unobservable leads to the following possible firin schedules (with the transitions. In IEEE Emerging Technologies and same observable projection), one containing the faulty Factory Automation (ETFA), pp. 1–7. transition and the other one not: Berthomieu, B. and M. Diaz (1991, March). Modeling • ̟1 = ((t1 , 1), (t2 , 3), (t4 , 5), (t5 , 9)), and verificatio of time dependent systems using time • ̟2 = ((t1 , 1), (t2 , 3), (t4 , 5), (t6 , 6), (t4 , 8), petri nets. IEEE Trans. Softw. Eng. 17(3), 259–273. (t5 , 9)). Bonhomme, P. (2013a). Scheduling and control of real- time systems based on a token player approach. Journal If the TLS considered is now: ωt = ((a, 3), (a, 14)) of Discrete Event Dynamic Systems 23(2), 197–209. then P Γ(ωt , Tf ) = F . Indeed, the computation of the set (M0 , ωt ) leads to the following possible firin schedule Bonhomme, P. (2013b). Towards a new schedulability containing the faulty transition: technique of real-time systems modeled by p-time Petri nets. International Journal of Advanced Manufacturing • ̟2 = ((t1 , 1), (t2 , 3), (t4 , 5), (t6 , 10), (t3 , 12), Technology 67(1-4), 759–769. (t2 , 14)). Bonhomme, P. (2014). Estimation of p-time labeled petri nets with unobservable transitions. In Proceedings In this case the faulty transition occurs with certainty of the 2014 IEEE Emerging Technology and Factory thanks to the timing structure of the P-TLPN considered Automation, ETFA 2014, Barcelona, Spain, September and the occurrence date of the observed labels. 16-19, 2014, pp. 1–8. Bonhomme, P. (2015). Marking estimation of P-time Petri 8. CONCLUSION AND PERSPECTIVES nets with unobservable transitions. IEEE Transactions on Systems, Man, and Cybernetics: Systems 45(3), 508– In this paper, a new methodology allowing to analyze 518. the fault diagnosis of systems modeled by P-time labeled Petri nets is developed. It is based on the construction of Cabasino, M., A. Giua, and C. Seatzu (2010). Fault a function called diagnoser which associates with each detection for discrete event systems using Petri nets observation and each fault class a diagnosis state. This with unobservable transitions. Automatica 46(9), 1531– diagnoser is obtained thanks to the synthesis of a state 1539. Cabasino, M. P., A. Giua, and C. Seatzu (2014). Diagnosability of discrete event systems using labeled Petri nets. IEEE Transactions on Automation Science and Engineering 11(1), 144–153. Cassandras, C. G. and S. Lafortune (2008). Introduction to Discrete Event Systems. Springer-Verlag New York, Inc. Cassez, F. and S. Tripakis (2008). Fault diagnosis with dynamic observers. In Discrete Event Systems, 2008. WODES 2008. 9th International Workshop on, pp. 212– 217. Giua, A., C. Seatzu, and D. Corona (2007). Marking estimation of Petri nets with silent transitions. IEEE Transactions on Automatic Control 52(9), 1695–1699. Hadjidj, R., H. Boucheneb, and D. Hadjidj (2007). Zenoness detection and timed model checking for real time systems. In VECoS’07, pp. 120–134. Khansa, W., J. P. Denat, and S. Collart-Dutilleul (1996). P-time Petri nets for manufacturing systems. In WODES’96, Edinburgh UK, pp. 94–102. Lin, F. (1994). Diagnosability of discrete event systems and its applications. Discrete Event Dynamic Systems 4(2), 197–212. Merlin, P. and D. Faber (1976). Recoverability of communication protocols-implications of a theoretical study. IEEE Trans. Comm. 24(9), 381–404. Murata, T. (1989). Petri nets, properties, analysis and applications. Proceedings of the IEEE 77, 541–580. Sampath, M., R. Sengupta, S. Lafortune, K. Sinnamo- hideen, and D. Teneketzis (1995). Diagnosability of discrete-event systems. IEEE Transactions on Auto- matic Control 40(9), 15551575. Wang, X., C. Mahulea, and M. Silva (2013, 07/2013). Fault diagnosis graph of time petri nets. In ECC’13: European Control Conference, Zurich, Switzerland. Wang, X., C. Mahulea, and M. Silva (2014). Model checking on fault diagnosis graph. In 12th International Workshop on Discrete Event Systems, WODES 2014, Cachan, France, May 14-16, 2014., pp. 434–439. Zaytoon, J. and S. Lafortune (2013). Overview of fault diagnosis methods for discrete event systems. Annual Reviews in Control 37(2), 308 – 320.