# Detection of Temporal Anomalies for Partially Observed Timed PNs

Authors: Dimitri Lefebvre
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

This article concerns faults detection and isolation for timed stochastic discrete event systems modeled with partially observed timed Petri nets. Events occur according to arbitrary probability density functions. The models include the sensors used to measure events and markings and also the temporal constraints to be satisfied by the system operations. These temporal constraints are defined according to tolerance intervals specified for each transition. A fault is an operation that ends too early or too late. The set of trajectories consistent with a given timed measured trajectory is first computed. Then, the probability that the temporal specifications are unsatisfied is estimated for any sequence of measurements and the probability that a temporal fault has occurred is obtained as a consequence.


---

## Body

## 1. Introduction

The prevention of faults is a critical issue in numerous systems to preserve the safety of both equipment and human operators. These issues have been addressed in numerous studies with fault detection and diagnosis (FDD) methods. The aim of fault detection is to create an alarm each time a fault occurs, and the aim of diagnosis is to isolate the fault within a group of candidates [1]. In the domain of discrete event systems (DESs), FDD has been often formulated with automata, Petri nets (PNs) [2], in particular labeled PNs (LPNs) [3] or partially observed Petri nets (POPNs) [4]. The main reason for developing FDD tests with PN extensions is that such models include graphical representations that can be disseminated widely in numerous application domains. They also offer mathematical supports that are consistent with standard tools. The proposed methods are useful for a large variety of technological systems, ranging from computer or chemical engineering to manufacturing and intelligent transportation systems.In numerous contributions, the faults that are considered are unexpected events that may occur in event sequences and that cannot be directly measured. Various approaches have been proposed with PN extensions to detect and isolate such unexpected events. These approaches are based either on the analysis of the PN reachability graph [5–9], on the direct properties of the PNs [10, 11], or on PN unfolding [12, 13]. A few results also concern the introduction of temporal information in the diagnosis process. At first, dates of events have been introduced in usual extensions of untimed PNs. Such dates lead to a more accurate estimation of the past and future fault occurrence probabilities [14] and are also useful to propose an evaluation of the unknown fault dates [15]. The design and identification of models that include temporal faults have been also considered [16, 17]. Then, fuzzy Petri nets have been used to model and check temporal constraints between event occurrences [18]. Partial orders with unfolding and (max, +)-linear inequalities have been used with timed PN models [19, 20]. Monotonic monitoring and stratification have been introduced, when the monitoring is fragmented because of the uncertain temporal observation [21]. Finally, indirect monitoring has been used by comparing the actual cycle periods with the expected one in order to detect faults [22].This paper takes place in the context where both transitions and places are assumed to be partially observed and consider only temporal faults. For that purpose, temporal constraints are defined by tolerance intervals that are associated with the transitions and that represent the normal durations of the system operations. The aim of the diagnosis system is to generate alarms when the temporal constraints are no longer satisfied. For that purpose, timed POPNs (POTPNs) are introduced. POTPNs take into consideration some measurable events that correspond to dated and labeled transition firings and also to partial measurements of the marking vector that is dated. This formalism, fully described in [23], is useful to represent incomplete history of dated measurements collected by SCADA systems. In the present work, this model is extended by adding temporal constraints that give upper and lower bounds for each transition duration. The paper is organized as follows. In Section 2, temporal constraints and POTPNs are introduced. In Section 3, the main results are detailed. Examples are detailed throughout the paper. Section 4 concludes the paper.


## 2. Context and Notations

### 2.1. PNs with Temporal Specifications

A PN structure is defined asG=P,T,WPR,WPO, where P={P1,…,Pn} is a set of n places and T={T1,…,Tq} is a set of q transitions, WPO∈Nn×q and WPR∈Nn×q are the post- and preincidence matrices (N is the set of nonnegative integer numbers), and W=WPO-WPR is the incidence matrix. A PN is choice-free if Pi°≤1 (the postset of Pi contains at most a single transition). G,MI is a PN system with initial marking MI and M∈Nn represents the PN marking vector. A PN system is 1-bounded if and only if (iff) M≤1n where 1n=1⋯1T (inequality M≤1n is considered component wise). A transition Tj is enabled at marking M iff M≥WPR(:,j), where WPR(:,j) is the column j of preincidence matrix; this is denoted as MTj. When Tj is enabled, it may fire, and when Tj fires once, the marking varies according to ΔM=M′-M=W(:,j). This is denoted as MTjM′. A sequence of size H=σ fired at marking M is a sequence of H transitions σ=T1T2⋯T(H), with Tj∈T,j=1,…,H that consecutively fire from marking M to marking M′. This is denoted as MσM′. The integer xj(σ) is the number of occurrences of transition Tj in σ, and Xσ=xjσ∈Nq is the firing count vector for σ. A sequence σ fired at M leads to an untimed trajectory (σ,M) detailed in (1)σ,M=M0T1M1⋯THMH,with M(0)=M. A marking M is said to be reachable from initial marking MI if there exists a firing sequence σ such that MIσM. The set of all reachable markings from initial marking MI is R(G,MI).Timed Petri nets are PNs whose behavior is driven by time. Time is measured with time units (TU). The time can be associated with the firing of the transitions or with the sojourn of the tokens in the places. In this paper the time is associated with the transitions and the firing of each transitionT occurs after a firing duration d that can eventually be zero. In that case the firing is immediate; in the other cases it is delayed. In this last case, the duration d can be deterministic (d is a constant) or stochastic (d is a random variable (RV)) with a probability density function (pdf) f(d). In this article, stochastic durations are concerned at first but the results are also applicable to deterministic durations. No particular assumption is made on the pdfs of the firing durations but the pdf of each transition is assumed to be known. The set of pdfs for all transitions is referred to as PDF. Two classes of pdfs are of particular interest for this work: bounded uniform (Figure 1(a)) and symmetrical triangular pdfs (Figure 1(b)) defined, respectively, with equations (2) and (3).Figure 1
Probability density functions of the transition firing durations: bounded uniform (a); symmetrical triangular (b).
(a)
(b)Bounded uniform pdf is as follows:(2)fd=1b-aifd∈a,b,otherwisefd=0.Symmetrical triangular pdf is as follows:(3)fd=4b-a2·d-aifd∈a,a+b2,fd=4b-a2·b-difd∈a+b2,b,otherwisefd=0.The motivations to consider these pdfs are that uniform random processes may be obtained as a limit case of (2) for a=0 and b=∞ and that (3) is useful to describe the dispersion of the duration around an average value. Note however that other pdfs can be considered. Note also that deterministic durations are obtained as the limit behavior of both pdfs when the support [a,b] of the pdfs tends to zero.The considered timed PNs have a time semantic [24, 25] that is defined according toinfinite server as server policy (Assumption A1), where each transition is considered as a server for firings and, in a given marking, each transition may fire simultaneously several times depending on its enabling degree;race as choice policy (Assumption A2), where the transition whose firing time elapses first is assumed to be the one that will fire next; andenabling memory as memory policy (Assumption A3), where, at the entrance in a marking, the remaining durations associated with still enabled transitions are kept and decremented and the remaining durations associated with disabled transitions are forgotten. Note that an interaction may exist between enabling memory and infinite server policies. At the entrance in a marking, the enabled degree of some transitions may decrease to a nonzero value. In the next, the considered nets are assumed to be 1-bounded and choice-free (Assumption A4); thus this situation never occurs and the reachability set of the net is of finite cardinality N. Finally, firings are assumed not to be immediate and d>0 (Assumption A5).The nominal behavior of the timed Petri nets is also assumed to be constrained by temporal constraints. A time interval TC =[δ,Δ] is associated with each transition T. The timed PN system satisfies the temporal constraints as long as the firing of the transitions has a duration not less than δ or larger than Δ. The duration is measured from the transition enabling date to the date when it effectively fires. The set of all temporal constraints is referred to as TC. Such temporal constraints are useful to characterize the validity and the performance of the activities that are represented (e.g., operation of machines in manufacturing systems, transfer in automated transportation systems, and server load in communication systems). An activity with an exact duration d without any tolerance is represented by a transition T constrained by the time interval [d,d] and an activity with no temporal specification is represented by a transition T constrained by the time interval [0,∞].A timed firing sequenceσ of length |σ|=H fired at marking M in time interval [τ0,τend] is defined as σ=Tj1,t1Tj2,t2⋯T(jH,tH) where j1,…,jH are the labels of the transitions and t1,…,tH represent the dates of the firings that satisfy τ0≤t1≤t2≤⋯≤tH≤τend. This leads to the timed trajectory (σ,M) detailed in the following with M(τ0)=M:(4)σ,M=Mτ0Tt1Mt1⋯TtHMτend. Note that we refer to timed and untimed firing sequences with the same notation σ as long as the notation is not confusing; otherwise we use σU to refer to untimed firing sequence and σ to refer to timed ones.


### 2.2. Partially Observed Timed Petri Nets

Partially observed Petri nets are considered to represent the system sensor.L:T→E∪{ε} is a labeling function that assigns a label to each transition where E={e1,…,ep} is the set of p labels that are assigned to observable transitions and ε is the null label that is assigned to the silent ones. The concatenation of labels obviously satisfies the following: εε=ε and εek=ek. For simplicity, each label ek is represented by the elementary vector ek of dimension p such that ek=(ekj) with ekj=0 for j≠k and ekk=1. The null label is represented by the zero vector ε=0p of dimension p. The labeling function is linear and defined by the matrix L=lkj∈Np×q such that lkj=1 if L·X(Tj)=ek; otherwise lkj=0 (“·” stands for the product operator). The marking sensor matrix H∈Rno×n (R is the set of real numbers) defines the projection of the marking vector M over no subsets of places. The observable part of the marking is denoted as MO=H·M.Thus, partially observed timed PNs with temporal constraints (POTPN) are defined asG,L,H,PDF,TC,MI where PDF is the set of pdfs, TC is the set of temporal constraints, G is a Petri net structure, L is an event sensor matrix, and H is a marking sensor matrix. The matrices L and H define the sensor configuration.Measurements are collected over the time interval[τ0,τend]. When the POTPN marking varies with the firing of a single transition T at date t∈[τ0,τend], the measurement function Γ(T,τ0,τend) is defined by (5)ΓT,τ0,τend=H·Mτ0L·XTtH·MτendifH·Mτ0≠H·Mτend∨L·XTt≠ε,ΓT,τ0,τend=H·MτendifH·Mτ0=H·Mτend∧L·XTt=ε.Roughly speaking, the measurement function Γ collects a new label each time a transition fires that is not silent or that changes the measurement of the marking. The measurement function Γ is then extended to timed trajectories of the form (4) measured over the time interval [τ0, τend]: (6)ΓσT,M,τ0,τend=Γσ,M,τ0,τendL·XTtH·MτendifH·Mt≠H·Mτend∨L·XTt≠ε,ΓσT,M,τ0,τend=Γσ,M,τ0,τendifH·Mt=H·Mτend∧L·XTt=ε. The measurement function Γ collects K successive dated marking and event measurements of a timed trajectory (σ,M) of length h over time interval [τ0,τend] and organizes these measurements in a timed measured trajectory that is written as follows(7)Γσ,M,τ0,τend=MOτ0eOτ1MOτ1eOτ2⋯MOτK-1eOτKMOτend, where MO(τ0)=M, K is the length of the sequence that satisfies K≤h, and τ={τk,k=1,…,K} refers to the set of measurement dates. Note that MO(τ0) does not necessarily correspond to the measurement of initial marking MI. A timed trajectory (σ,M) is said to be consistent with a given timed measured trajectory TRO in time interval [τ0,τend] if it satisfies Γ((σ,M),τ0,τend)=TRO. In the next, it is assumed that the time interval starts at time 0 (i.e., τ0=0) and that it ends at the last measurement date (i.e., τend=τK) (Assumption B).The objective of the present work is to estimate the probability that any given timed measured trajectory satisfies the temporal constraints. An immediate application of the proposed estimation is to provide an algorithm that generates alarms when this probability goes down a specific thresholdγ. To the best of our knowledge, it is the first time that this problem is considered with PNs. Note that POTPNs cannot be encoded as a Hidden Markov Model (HMM) [26] because in a HMM each state successively reached by the system delivers an observation that is not certain and depends on the emission probabilities. On the contrary, in a POTPN model, the states and the transitions deliver certain but partial observations and in some cases the states do not deliver any observation at all.


## 2.1. PNs with Temporal Specifications

A PN structure is defined asG=P,T,WPR,WPO, where P={P1,…,Pn} is a set of n places and T={T1,…,Tq} is a set of q transitions, WPO∈Nn×q and WPR∈Nn×q are the post- and preincidence matrices (N is the set of nonnegative integer numbers), and W=WPO-WPR is the incidence matrix. A PN is choice-free if Pi°≤1 (the postset of Pi contains at most a single transition). G,MI is a PN system with initial marking MI and M∈Nn represents the PN marking vector. A PN system is 1-bounded if and only if (iff) M≤1n where 1n=1⋯1T (inequality M≤1n is considered component wise). A transition Tj is enabled at marking M iff M≥WPR(:,j), where WPR(:,j) is the column j of preincidence matrix; this is denoted as MTj. When Tj is enabled, it may fire, and when Tj fires once, the marking varies according to ΔM=M′-M=W(:,j). This is denoted as MTjM′. A sequence of size H=σ fired at marking M is a sequence of H transitions σ=T1T2⋯T(H), with Tj∈T,j=1,…,H that consecutively fire from marking M to marking M′. This is denoted as MσM′. The integer xj(σ) is the number of occurrences of transition Tj in σ, and Xσ=xjσ∈Nq is the firing count vector for σ. A sequence σ fired at M leads to an untimed trajectory (σ,M) detailed in (1)σ,M=M0T1M1⋯THMH,with M(0)=M. A marking M is said to be reachable from initial marking MI if there exists a firing sequence σ such that MIσM. The set of all reachable markings from initial marking MI is R(G,MI).Timed Petri nets are PNs whose behavior is driven by time. Time is measured with time units (TU). The time can be associated with the firing of the transitions or with the sojourn of the tokens in the places. In this paper the time is associated with the transitions and the firing of each transitionT occurs after a firing duration d that can eventually be zero. In that case the firing is immediate; in the other cases it is delayed. In this last case, the duration d can be deterministic (d is a constant) or stochastic (d is a random variable (RV)) with a probability density function (pdf) f(d). In this article, stochastic durations are concerned at first but the results are also applicable to deterministic durations. No particular assumption is made on the pdfs of the firing durations but the pdf of each transition is assumed to be known. The set of pdfs for all transitions is referred to as PDF. Two classes of pdfs are of particular interest for this work: bounded uniform (Figure 1(a)) and symmetrical triangular pdfs (Figure 1(b)) defined, respectively, with equations (2) and (3).Figure 1
Probability density functions of the transition firing durations: bounded uniform (a); symmetrical triangular (b).
(a)
(b)Bounded uniform pdf is as follows:(2)fd=1b-aifd∈a,b,otherwisefd=0.Symmetrical triangular pdf is as follows:(3)fd=4b-a2·d-aifd∈a,a+b2,fd=4b-a2·b-difd∈a+b2,b,otherwisefd=0.The motivations to consider these pdfs are that uniform random processes may be obtained as a limit case of (2) for a=0 and b=∞ and that (3) is useful to describe the dispersion of the duration around an average value. Note however that other pdfs can be considered. Note also that deterministic durations are obtained as the limit behavior of both pdfs when the support [a,b] of the pdfs tends to zero.The considered timed PNs have a time semantic [24, 25] that is defined according toinfinite server as server policy (Assumption A1), where each transition is considered as a server for firings and, in a given marking, each transition may fire simultaneously several times depending on its enabling degree;race as choice policy (Assumption A2), where the transition whose firing time elapses first is assumed to be the one that will fire next; andenabling memory as memory policy (Assumption A3), where, at the entrance in a marking, the remaining durations associated with still enabled transitions are kept and decremented and the remaining durations associated with disabled transitions are forgotten. Note that an interaction may exist between enabling memory and infinite server policies. At the entrance in a marking, the enabled degree of some transitions may decrease to a nonzero value. In the next, the considered nets are assumed to be 1-bounded and choice-free (Assumption A4); thus this situation never occurs and the reachability set of the net is of finite cardinality N. Finally, firings are assumed not to be immediate and d>0 (Assumption A5).The nominal behavior of the timed Petri nets is also assumed to be constrained by temporal constraints. A time interval TC =[δ,Δ] is associated with each transition T. The timed PN system satisfies the temporal constraints as long as the firing of the transitions has a duration not less than δ or larger than Δ. The duration is measured from the transition enabling date to the date when it effectively fires. The set of all temporal constraints is referred to as TC. Such temporal constraints are useful to characterize the validity and the performance of the activities that are represented (e.g., operation of machines in manufacturing systems, transfer in automated transportation systems, and server load in communication systems). An activity with an exact duration d without any tolerance is represented by a transition T constrained by the time interval [d,d] and an activity with no temporal specification is represented by a transition T constrained by the time interval [0,∞].A timed firing sequenceσ of length |σ|=H fired at marking M in time interval [τ0,τend] is defined as σ=Tj1,t1Tj2,t2⋯T(jH,tH) where j1,…,jH are the labels of the transitions and t1,…,tH represent the dates of the firings that satisfy τ0≤t1≤t2≤⋯≤tH≤τend. This leads to the timed trajectory (σ,M) detailed in the following with M(τ0)=M:(4)σ,M=Mτ0Tt1Mt1⋯TtHMτend. Note that we refer to timed and untimed firing sequences with the same notation σ as long as the notation is not confusing; otherwise we use σU to refer to untimed firing sequence and σ to refer to timed ones.


## 2.2. Partially Observed Timed Petri Nets

Partially observed Petri nets are considered to represent the system sensor.L:T→E∪{ε} is a labeling function that assigns a label to each transition where E={e1,…,ep} is the set of p labels that are assigned to observable transitions and ε is the null label that is assigned to the silent ones. The concatenation of labels obviously satisfies the following: εε=ε and εek=ek. For simplicity, each label ek is represented by the elementary vector ek of dimension p such that ek=(ekj) with ekj=0 for j≠k and ekk=1. The null label is represented by the zero vector ε=0p of dimension p. The labeling function is linear and defined by the matrix L=lkj∈Np×q such that lkj=1 if L·X(Tj)=ek; otherwise lkj=0 (“·” stands for the product operator). The marking sensor matrix H∈Rno×n (R is the set of real numbers) defines the projection of the marking vector M over no subsets of places. The observable part of the marking is denoted as MO=H·M.Thus, partially observed timed PNs with temporal constraints (POTPN) are defined asG,L,H,PDF,TC,MI where PDF is the set of pdfs, TC is the set of temporal constraints, G is a Petri net structure, L is an event sensor matrix, and H is a marking sensor matrix. The matrices L and H define the sensor configuration.Measurements are collected over the time interval[τ0,τend]. When the POTPN marking varies with the firing of a single transition T at date t∈[τ0,τend], the measurement function Γ(T,τ0,τend) is defined by (5)ΓT,τ0,τend=H·Mτ0L·XTtH·MτendifH·Mτ0≠H·Mτend∨L·XTt≠ε,ΓT,τ0,τend=H·MτendifH·Mτ0=H·Mτend∧L·XTt=ε.Roughly speaking, the measurement function Γ collects a new label each time a transition fires that is not silent or that changes the measurement of the marking. The measurement function Γ is then extended to timed trajectories of the form (4) measured over the time interval [τ0, τend]: (6)ΓσT,M,τ0,τend=Γσ,M,τ0,τendL·XTtH·MτendifH·Mt≠H·Mτend∨L·XTt≠ε,ΓσT,M,τ0,τend=Γσ,M,τ0,τendifH·Mt=H·Mτend∧L·XTt=ε. The measurement function Γ collects K successive dated marking and event measurements of a timed trajectory (σ,M) of length h over time interval [τ0,τend] and organizes these measurements in a timed measured trajectory that is written as follows(7)Γσ,M,τ0,τend=MOτ0eOτ1MOτ1eOτ2⋯MOτK-1eOτKMOτend, where MO(τ0)=M, K is the length of the sequence that satisfies K≤h, and τ={τk,k=1,…,K} refers to the set of measurement dates. Note that MO(τ0) does not necessarily correspond to the measurement of initial marking MI. A timed trajectory (σ,M) is said to be consistent with a given timed measured trajectory TRO in time interval [τ0,τend] if it satisfies Γ((σ,M),τ0,τend)=TRO. In the next, it is assumed that the time interval starts at time 0 (i.e., τ0=0) and that it ends at the last measurement date (i.e., τend=τK) (Assumption B).The objective of the present work is to estimate the probability that any given timed measured trajectory satisfies the temporal constraints. An immediate application of the proposed estimation is to provide an algorithm that generates alarms when this probability goes down a specific thresholdγ. To the best of our knowledge, it is the first time that this problem is considered with PNs. Note that POTPNs cannot be encoded as a Hidden Markov Model (HMM) [26] because in a HMM each state successively reached by the system delivers an observation that is not certain and depends on the emission probabilities. On the contrary, in a POTPN model, the states and the transitions deliver certain but partial observations and in some cases the states do not deliver any observation at all.


## 3. Temporal Specifications Checking

The proposed diagnosis systems operate with three stages.(i)
For any timed measured trajectoryTRO with K measurements, the set of timed trajectories that are consistent with TRO are first computed with an integer linear programming approach developed in our previous work [23, 27].(ii)
For each possible trajectory, the probability that this trajectory is consistent with the temporal constraints is estimated.(iii)
The probability that a timed measured trajectory is consistent with the temporal constraints is obtained as a consequence by computing the probability of each consistent trajectory [15].


### 3.1. Untimed Trajectories Consistent withTRO

In this section, the setΓU-1(TRO) of all untimed trajectories (σU,M) that are consistent with a given measured trajectory TRO is computed. Note that this problem cannot be solved using standard algorithms (as the Viterbi algorithm) [28] issued from dynamic programming because such algorithms aim to find only the trajectory of maximum probability from the measured trajectory, but not all trajectories. For diagnosis issues it is however required to consider all trajectories. It is assumed that the set of the reachable states and also the reachability graph of the net are known. Let us define Aε as the matrix of the reachability graph of the unobservable part of the PN where all transitions that are observable or whose firing changes the measured part of the marking have been removed and assume that this graph is acyclic (Assumption C). In that case, the maximal number of consecutive silent events is upper bounded by hmax-1 [23] with(8)hmax=minh≥0suchthatAεh=0. Let us consider a timed measured trajectory TRO of the form (7) with K measurements in time interval [0,τK]. An untimed trajectory (σU,M) with σU=T1T2⋯T(H) is consistent with TRO iff the following conditions are satisfied [27]: (1)
H·M=MO(0);(2)
There existsh0=0,h1,…,hK, such that hk-hk-1≤hmax,k=1,…,K, and the untimed firing sequence σU is rewritten as σU=T(1)⋯T(h1)⋯T(hK) and satisfies the following:(9)-Iq0⋯000-Iq⋱⋮0⋮⋱⋱0⋮0⋯0-Iq01qT0⋯0001qT⋱⋮0⋮⋱⋱0⋮0⋯01qT0WPR0⋯0-In-WWPR⋱⋮-In⋮⋱⋱0⋮-W⋯-WWPR-In·XT1⋮XTh1XTh1+1⋮XTh2⋮XThKM≤0q0q⋮0q11⋮10n0n⋮0n(10)L0⋯00⋱⋱⋮0⋱L00⋯0LH·W0000⋱0⋮00H·W0H·W⋯H·WH·W·XThk-1+1⋮XThk-1XThk=ε⋮εeOτk0no⋮0noMOτk-MOτk-1fork=1,…,K,where all inequalities are taken component wise. Roughly speaking inequality (9) means that the firing count vector of each transition in σ is positive, unitary, and feasible (i.e., leading to a positive marking). Equality (10) means that for k=1,…,K, hk-1 first transitions are silent and only the last one may provide a label eO(τk). Similarly it ensures that hk-1 first marking measurement does not provide any information and only the last one may provide marking changes MO(τk)-MO(τk-1). The combined use of (9) and (10) leads to the exhaustive set of untimed trajectories that are consistent with TRO [23, 27]. Note that ΓU-1(TRO) does not include the silent closure of the trajectories (i.e., the continuations of the trajectories that provide no event nor marking measurement) because the time interval [0,τK] ends with the last measurement (Assumption B) and the no immediate firing occurs (Assumption A5). If required, the silent closure can easily be added to ΓU-1(TRO) by considering the following equation in addition to (9) and (10):(11)L000⋱000LH·W000⋱000H·W·XThK+1⋮XThK+1=ε⋮ε0no⋮0no,where ThK+1⋯T(hK+1) stands for the silent closure.Let us consider the marked POTPN1 of Figure2 with MI=100T, a single observable transition T2, and no observable place (unobservable places and transitions are highlighted in grey). The set of labels is E={e} and the matrices L=01 and H=000 define the sensor configuration. Measurements are collected over the time interval [0,τ1]. Assume that the measured trajectory TRO=0(0)e(τ1)0(τ1) is measured according to L and H. Note at first that the given example satisfies Assumptions A to C and that (8) leads to hmax=2. Thus, untimed trajectories (σU,M) are searched with M∈{100T;010T;001T} and σU=T(1)T(2) with T(2)=T2. Two untimed trajectories (T1T2,100T) and (T2,010T) are consistent with TRO in this particular example. If we assume that the first measured marking is MI, then the single trajectory (T1T2,100T) remains consistent with TRO.Figure 2
POTPN1.


### 3.2. Probability of a Timed Trajectory with a Set of Given Firing Dates

A timed trajectory(σ,M) with σ=Tt1⋯Tth⋯T(tH) is consistent with TRO iff the corresponding untimed trajectory (σU,M) obtained by making abstraction of time satisfies the previous conditions (conditions 1 and 2 in Section 3.1) and if the date th,h=1,…,H satisfies the following conditions [23, 27]:(3)
t1≤t2≤⋯≤tH (i.e., the chronological order of the events results from σU).(4)
There existsK dates th1,…,thK such that thK=τk.(5)
The probability that each transitionTth∈σ,th∉{th1,…,thK} fires within a small interval [th,th+dt] of width dt is nonzero.For each transition T(th)∈σ that fires at date th, let us consider the firing duration dh of transition T(th) and introduce th′ and M(th′) as the date and marking from which transition T(th) remains enabled. Thus T(th) is enabled from date th′ and fires at date th.(12)σ,M=M0Tt1Mt1⋯Tth′Mth′⋯TthMth⋯TtHMτK,mim[---------------------]mmmdh=th-th′.The problem solved in this section is to evaluate the probability that the transitions of (σ,M) in (12) fire in specific intervals [th,th+dt],h=1,…,H knowing that the measurement dates are τ and that the untimed trajectory (σU,M) is the true one. This probability is noted prob(th,h∈1:H∣σU,Mandτ). In the case where dh=th-th′ are independent RV, the following holds:(13)probth,h∈1:H∣σU,Mandτ=∏h=1,…,Hfhdh·dt.The difficulty is that variables dh are not necessarily independent RV. Table 1 details the different situations (type 1, 2, or 3) that may occur depending on whether the dates th and th′ are measured or not.Table 1
Deterministic and random variables introduced to evaluateprob({th,h∈[1:H]}∣σU,Mandτ).
t
h
′/th
Measured:th=τk
Unmeasured:th is a RV
Measured:th′=τk′
Type 1:dh is a deterministic variable  dh=τk-τk′ is measured
Type 3:dh is a new RV   dh=th-τk′
Unmeasured:th′ is a RV
Type 2:dh is a RV that depends on a RV of type 3 dh′  dh=τk-th′
Type 3:dh is a new RV   dh=th-th′Situations of type 1, 2, or 3 will be used in the next section to evaluate the probability that a timed trajectory satisfies the temporal constraints.


### 3.3. Probability That a Timed Trajectory Satisfies the Temporal Constraints

The probability that any timed trajectory(σ,M), obtained from untimed trajectory (σU,M) and consistent with TRO, satisfies the set of temporal constraints TC results from the extension and integration of (13) with respect to the 3 types of situations described in Table 1. This leads to the following:(14)probσ,MsatisfiesTC∣σU,Mandτ=S1σU,M,TC,τS2σU,M,τ with(15)S1σU,M,TC,τ=∫b1B1g1t1-τ0⋯∫bhBhghth-th′⋯∫bHBHgHtH-tH′·dtH⋯dth⋯dt1,S2σU,M,τ=∫τ0τKg1t1-τ0⋯∫th-1τKghth-th′⋯∫tH-1τKgHtH-tH′·dtH⋯dth⋯dt1,where dates bh and Bh and functions gh are defined in Table 2 for h∈[1:H]. Note that if dh is of type 1 (i.e., dh is a deterministic variable), then prob(th∣(σU,M) and τ)=1 if dh∈[δh,Δh]; otherwise prob(th∣σU,Mandτ)=0. Thus situations of type 1 are no longer considered and (15) does not necessarily include all variables dh. To simplify the notation let us also divide the transitions of type 2 in several classes referred to as Class(h′) formally defined by the following: (16)Classh′=hsuchthatTthis of type 2 andTthremains enabled fromMth′.In other words, Class(h′) is the set of transitions of type 2 (their firing date is measured) that are enabled at the same date th′.Table 2
Bounds and functions for (15).
d
h
Type 2:th is a measured date
Type 3:th is an unknown date
g
h
(
t
h)
fh′(th′-th′′)⋅∏h∈Class(h′)fhth-th′
f
h
(
t
h
-
t
h
′
)
b
h
max
⁡
(
t
h
-
1
,
t
h
′
′
+
δ
h
′
,
max
h
∈
Class
h
′
⁡
(
t
h
-
Δ
h
)
)
∗
max
⁡
(
t
h
-
1
,
t
h
′
+
δ
h
)
B
h
min
⁡
(
τ
K
,
t
h
′
′
+
Δ
h
′
,
min
h
∈
Class
h
′
⁡
⁡
(
t
h
-
δ
h
)
)
∗
min
⁡
(
τ
K
,
t
h
′
+
Δ
h
)
∗
b
1
=
δ
1 and B1=min⁡(τK,Δ1).Roughly speaking,S1(σU,M,TC,τ) is a multi-integral that evaluates the sum of the duration variables dh over their possible range of variation constrained by the measurement time interval [0,τK], the dates of measurements τk, and the temporal specifications [δh,Δh]. Similarly, S2(σU,M,τ) evaluates the sum of the duration variables dh over their possible range of variation constrained only by the measurement time interval [0,τK] and the dates of measurements τk (the temporal specifications [δh,Δh] are not considered). The ratio of both evaluations leads to the probability that any timed trajectory (σ,M), resulting from untimed trajectory (σU,M) and consistent with τ, satisfies the set of temporal constraints TC. From a numerical point of view the calculation of S1(σU,M,TC,τ) and S2(σU,M,τ) is obtained with a recursive algorithm.


### 3.4. Detection of the Temporal Faults

In the general case, several untimed trajectories(σU,M) may be consistent with a given timed measured trajectory TRO in time interval [0,τK] (i.e., ΓU-1(TRO) contains more than one trajectory). This situation is due to two different reasons: (1) several markings M may be consistent with the first marking measurement MO(0); (2) from a given marking M, several untimed sequences may be consistent with the measured trajectory TRO. In order to deal with (1), let us consider M0(TRO) as the set of markings consistent with MO(0) and π0(M) as the probability that M is the current marking at date 0 such that ∑M∈M0TROπ0(M)=1. The set M0(TRO) and the probability π0(M) for each M∈M0(TRO) are assumed to be known (Assumption D). Note that Assumption D can be relaxed for PNs without absorbing subsets of markings by considering the steady state probability of M as π0(M). In order to deal with (2), the probability of each sequence issued from the same marking M and consistent with TRO is evaluated with the following: (17)probσU,M∣TROandM=S2σU,M,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τ. Finally the probability of each trajectory (σU,M) is obtained with (18)probσU,M∣TRO=π0M·S2σU,M,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τand prob(TRO satisfies TC)=probσU,M∣TRO·prob((σ,M) satisfies TC∣(σU,M) and τ). This last equation leads to(19)probTROsatisfiesTC=π0M·S1σU,M,TC,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τThen, the diagnosis of temporal faults results from the iterative evaluation of (19). For that purpose, a sampling period Δt is considered and for each date t=k·Δt, prob(TRO satisfies TC) is updated depending on the eventual new measurements that are collected during time interval [k-1·Δt,k·Δt[. Formally, if TRO(k) refers to the measured trajectory collected during time interval [0,k·Δt[, the probability prob(TRO(k) satisfies TC) will be compared to a given threshold γ and an alarm is generated each time prob(TRO(k) satisfies TC)<γ.Let us consider again POTPN1 of Figure2 introduced in Section 3.1. If the first measured marking is assumed to coincide with MI then M0(TRO) = {100T,010T} with π0100T=1 and π0010T=0. The timed trajectories (σ,M) consistent with TRO=0(0)e(τ1)0(τ1) satisfy also σ=T(t1)T(t2) with T(t1)=T1, T(t2)=T2, t2=τ1, and t1≤τ1. Two successive cases are considered to illustrate the computation of prob(TRO satisfies TC) with (19).In case A, the pdfs of the transition durations are assumed to be bounded uniform with the same support[0,10] for T1 and T2. The temporal constraints are arbitrarily defined by TC1=[4,6] for T1 and TC2=[3,7] for T2. Prob(TRO satisfies TC) computed with (19) is reported in Figure 3(a) (full line) in function of the date τ1. For the considered example, this equation can be rewritten as follows:(20)probTROsatisfiesTC=∫max⁡δ1,τ1-Δ2min⁡Δ1,τ1-δ2f1t·f2τ1-t·dt∫0τ1f1t·f2τ1-t·dt.Note that this probability is zero for τ1<7 TU (one lower bound at least is not satisfied for the temporal constraints) and also for τ1>13 TU (one upper bound at least is not satisfied for the temporal constraints). This computation is confirmed with a series of 1000 Monte Carlo simulations that coincide with TRO (dashed line). Depending on the choice of the threshold γ, an alarm may be generated. For example, for γ=0.2, an alarm is generated if τ1∈[8.5,11.3].Figure 3
Computation and Monte Carlo simulations to evaluateprob(TRO satisfies TC) in function of τ1: bounded uniform pdfs (a); symmetrical triangular pdfs (b).
(a)
(b)In case B, the pdfs of the transition durations are assumed to be symmetrical triangular with supports[1,4] for T1 and [2,7] for T2. The temporal constraints are, respectively, TC1=[2,3] for T1 and TC2=[3,6] for T2. Prob(TRO satisfies TC) is computed with (19) in Figure 3(b) (full line) in function of the date τ1. This computation is also validated with a series of 1000 Monte Carlo simulations that coincide with TRO (dashed line).


### 3.5. Numerical Complexity

The numerical complexity of the whole diagnosis schema is due (a) to the computation ofΓU-1(TRO); (b) to the numerical evaluation of (19).(a) The complexity to computeΓU-1(TRO) is related to the resolution of (9) and (10) that include hmax·K·(n+q+1) inequalities and hmax·K·(no+p) equalities with hmax·K·q+n unknown integer variables. Basically, the complexity is exponential with respect to the number N of reachable markings in R(G,MI) and to the length K of the measured trajectories (hmax⁡ is a constant parameter). Branch and bound algorithms can be used to solve (9)-(10) as an integer linear programming problem (LPP) [24]. These algorithms have a general nonpolynomial complexity but limit the computational effort in many practical situations. An algorithm of linear complexity has been also developed in our previous work that limits the length K of the timed measured trajectories under test. It considers measured trajectories within a sliding window of constant size K0 instead of increasing size K [25] and leads to an algorithm of linear complexity with respect to K. Note also that the complexity with respect to N is no longer exponential if the set M0(TRO) is known (Assumption D).(b) The numerical evaluation of (19) is obtained according to a recursive scheme with a deep equal to the number of transitions of type 2 or 3 in the considered sequence. Consequently the computation effort increases rapidly in time and in space with respect to the sequence length. To limit the computational complexity, the trajectory (σ,M) is divided into S subtrajectories that are considered successively and independently: (σ,M)=(σ1,M1)⋯(σS,MS) with M1=M. Each subtrajectory (σs,Ms) is of minimal length such that (i) (σs,Ms) ends with a measurement M(τk); (ii) all transitions in σs are enabled from a marking that belongs to the same subtrajectory (σs,Ms) and not to a previous one. For this reason each subtrajectory can include several measurements. For example, the trajectory in (21) is divided into two subtrajectories (σ1,M1) and (σ2,M2).Trajectory decomposition is as follows:(21)σ,M=σ1,M1σ,M=M0Tt1Mt1⋯Tth′′kkkkkkkkkkkkkk-----------dh′′=th′′-t1dh′′=th′′–t1dh′′=th′′–t1σ2,M2Mth′′⋯Tth′Mth′⋯TthMth⋯TtHMτK-----------dh=th-th′-------------------------------------------------------dH=tH-th′′.


### 3.6. Example

Let us consider the marked POTPN2 of Figure4 (unobservable places and transitions are highlighted in grey) that represents a cycle of tasks. The state of the system is not measured and only two events are observed. The set of labels is E={e1,e2}. The matrices L=10000T∣00001TT and H=00000 define the sensor configuration. Measurements are collected over the time interval [0,20] and the measured trajectory TRO=0(0)e1(3.7)0(3.7)e2(20)0(20) is considered. For this example hmax=4 and a single untimed trajectory (σU, MI) with σU=T1(1)T2(2)T3(3)T4(4)T5(5) is consistent with TRO. The timed trajectories (σ, MI) consistent with TRO satisfy σ=T(t1)T(t2)T(t3)T(t4)T(t5) with T(t1)=T1,T(t5)=T5,t1=3.7 TU, t5=20 TU, and t1≤t2≤t3≤t4≤t5. The pdfs of the transition durations are assumed to be bounded uniform with the same support [0,10] for Tj,j= 1 : 5. The temporal constraints are also assumed to be identical TCj=[1,9] for j = 1 : 5.Figure 4
POTPN2.P
r
o
b
(
T
R
O satisfies TC)=S1/S2=0.46 is obtained by (19) with(22)S1=∫τ1+δ2τ1+Δ2f2t2-τ1·∫t2+δ3t2+Δ3f3t3-t2·∫min⁡t3+δ4,τ5-Δ5max⁡t3+Δ4,τ5+δ5⁡f4t4-t3·f5τ5-t4dt4dt3dt2=0.024,S2=∫0τ5f2t2-τ1·∫t2τ5f3t3-t2·∫min⁡t3,τ5τ5f4t4-t3·f5τ5-t4dt4dt3dt2=0.054.This computation is validated with a series of simulations that leads to a probability of 0.47. The evaluation of Prob(TRO satisfies TC) with (19) saves time compared to the numerical evaluation based on simulation.


## 3.1. Untimed Trajectories Consistent withTRO

In this section, the setΓU-1(TRO) of all untimed trajectories (σU,M) that are consistent with a given measured trajectory TRO is computed. Note that this problem cannot be solved using standard algorithms (as the Viterbi algorithm) [28] issued from dynamic programming because such algorithms aim to find only the trajectory of maximum probability from the measured trajectory, but not all trajectories. For diagnosis issues it is however required to consider all trajectories. It is assumed that the set of the reachable states and also the reachability graph of the net are known. Let us define Aε as the matrix of the reachability graph of the unobservable part of the PN where all transitions that are observable or whose firing changes the measured part of the marking have been removed and assume that this graph is acyclic (Assumption C). In that case, the maximal number of consecutive silent events is upper bounded by hmax-1 [23] with(8)hmax=minh≥0suchthatAεh=0. Let us consider a timed measured trajectory TRO of the form (7) with K measurements in time interval [0,τK]. An untimed trajectory (σU,M) with σU=T1T2⋯T(H) is consistent with TRO iff the following conditions are satisfied [27]: (1)
H·M=MO(0);(2)
There existsh0=0,h1,…,hK, such that hk-hk-1≤hmax,k=1,…,K, and the untimed firing sequence σU is rewritten as σU=T(1)⋯T(h1)⋯T(hK) and satisfies the following:(9)-Iq0⋯000-Iq⋱⋮0⋮⋱⋱0⋮0⋯0-Iq01qT0⋯0001qT⋱⋮0⋮⋱⋱0⋮0⋯01qT0WPR0⋯0-In-WWPR⋱⋮-In⋮⋱⋱0⋮-W⋯-WWPR-In·XT1⋮XTh1XTh1+1⋮XTh2⋮XThKM≤0q0q⋮0q11⋮10n0n⋮0n(10)L0⋯00⋱⋱⋮0⋱L00⋯0LH·W0000⋱0⋮00H·W0H·W⋯H·WH·W·XThk-1+1⋮XThk-1XThk=ε⋮εeOτk0no⋮0noMOτk-MOτk-1fork=1,…,K,where all inequalities are taken component wise. Roughly speaking inequality (9) means that the firing count vector of each transition in σ is positive, unitary, and feasible (i.e., leading to a positive marking). Equality (10) means that for k=1,…,K, hk-1 first transitions are silent and only the last one may provide a label eO(τk). Similarly it ensures that hk-1 first marking measurement does not provide any information and only the last one may provide marking changes MO(τk)-MO(τk-1). The combined use of (9) and (10) leads to the exhaustive set of untimed trajectories that are consistent with TRO [23, 27]. Note that ΓU-1(TRO) does not include the silent closure of the trajectories (i.e., the continuations of the trajectories that provide no event nor marking measurement) because the time interval [0,τK] ends with the last measurement (Assumption B) and the no immediate firing occurs (Assumption A5). If required, the silent closure can easily be added to ΓU-1(TRO) by considering the following equation in addition to (9) and (10):(11)L000⋱000LH·W000⋱000H·W·XThK+1⋮XThK+1=ε⋮ε0no⋮0no,where ThK+1⋯T(hK+1) stands for the silent closure.Let us consider the marked POTPN1 of Figure2 with MI=100T, a single observable transition T2, and no observable place (unobservable places and transitions are highlighted in grey). The set of labels is E={e} and the matrices L=01 and H=000 define the sensor configuration. Measurements are collected over the time interval [0,τ1]. Assume that the measured trajectory TRO=0(0)e(τ1)0(τ1) is measured according to L and H. Note at first that the given example satisfies Assumptions A to C and that (8) leads to hmax=2. Thus, untimed trajectories (σU,M) are searched with M∈{100T;010T;001T} and σU=T(1)T(2) with T(2)=T2. Two untimed trajectories (T1T2,100T) and (T2,010T) are consistent with TRO in this particular example. If we assume that the first measured marking is MI, then the single trajectory (T1T2,100T) remains consistent with TRO.Figure 2
POTPN1.


## 3.2. Probability of a Timed Trajectory with a Set of Given Firing Dates

A timed trajectory(σ,M) with σ=Tt1⋯Tth⋯T(tH) is consistent with TRO iff the corresponding untimed trajectory (σU,M) obtained by making abstraction of time satisfies the previous conditions (conditions 1 and 2 in Section 3.1) and if the date th,h=1,…,H satisfies the following conditions [23, 27]:(3)
t1≤t2≤⋯≤tH (i.e., the chronological order of the events results from σU).(4)
There existsK dates th1,…,thK such that thK=τk.(5)
The probability that each transitionTth∈σ,th∉{th1,…,thK} fires within a small interval [th,th+dt] of width dt is nonzero.For each transition T(th)∈σ that fires at date th, let us consider the firing duration dh of transition T(th) and introduce th′ and M(th′) as the date and marking from which transition T(th) remains enabled. Thus T(th) is enabled from date th′ and fires at date th.(12)σ,M=M0Tt1Mt1⋯Tth′Mth′⋯TthMth⋯TtHMτK,mim[---------------------]mmmdh=th-th′.The problem solved in this section is to evaluate the probability that the transitions of (σ,M) in (12) fire in specific intervals [th,th+dt],h=1,…,H knowing that the measurement dates are τ and that the untimed trajectory (σU,M) is the true one. This probability is noted prob(th,h∈1:H∣σU,Mandτ). In the case where dh=th-th′ are independent RV, the following holds:(13)probth,h∈1:H∣σU,Mandτ=∏h=1,…,Hfhdh·dt.The difficulty is that variables dh are not necessarily independent RV. Table 1 details the different situations (type 1, 2, or 3) that may occur depending on whether the dates th and th′ are measured or not.Table 1
Deterministic and random variables introduced to evaluateprob({th,h∈[1:H]}∣σU,Mandτ).
t
h
′/th
Measured:th=τk
Unmeasured:th is a RV
Measured:th′=τk′
Type 1:dh is a deterministic variable  dh=τk-τk′ is measured
Type 3:dh is a new RV   dh=th-τk′
Unmeasured:th′ is a RV
Type 2:dh is a RV that depends on a RV of type 3 dh′  dh=τk-th′
Type 3:dh is a new RV   dh=th-th′Situations of type 1, 2, or 3 will be used in the next section to evaluate the probability that a timed trajectory satisfies the temporal constraints.


## 3.3. Probability That a Timed Trajectory Satisfies the Temporal Constraints

The probability that any timed trajectory(σ,M), obtained from untimed trajectory (σU,M) and consistent with TRO, satisfies the set of temporal constraints TC results from the extension and integration of (13) with respect to the 3 types of situations described in Table 1. This leads to the following:(14)probσ,MsatisfiesTC∣σU,Mandτ=S1σU,M,TC,τS2σU,M,τ with(15)S1σU,M,TC,τ=∫b1B1g1t1-τ0⋯∫bhBhghth-th′⋯∫bHBHgHtH-tH′·dtH⋯dth⋯dt1,S2σU,M,τ=∫τ0τKg1t1-τ0⋯∫th-1τKghth-th′⋯∫tH-1τKgHtH-tH′·dtH⋯dth⋯dt1,where dates bh and Bh and functions gh are defined in Table 2 for h∈[1:H]. Note that if dh is of type 1 (i.e., dh is a deterministic variable), then prob(th∣(σU,M) and τ)=1 if dh∈[δh,Δh]; otherwise prob(th∣σU,Mandτ)=0. Thus situations of type 1 are no longer considered and (15) does not necessarily include all variables dh. To simplify the notation let us also divide the transitions of type 2 in several classes referred to as Class(h′) formally defined by the following: (16)Classh′=hsuchthatTthis of type 2 andTthremains enabled fromMth′.In other words, Class(h′) is the set of transitions of type 2 (their firing date is measured) that are enabled at the same date th′.Table 2
Bounds and functions for (15).
d
h
Type 2:th is a measured date
Type 3:th is an unknown date
g
h
(
t
h)
fh′(th′-th′′)⋅∏h∈Class(h′)fhth-th′
f
h
(
t
h
-
t
h
′
)
b
h
max
⁡
(
t
h
-
1
,
t
h
′
′
+
δ
h
′
,
max
h
∈
Class
h
′
⁡
(
t
h
-
Δ
h
)
)
∗
max
⁡
(
t
h
-
1
,
t
h
′
+
δ
h
)
B
h
min
⁡
(
τ
K
,
t
h
′
′
+
Δ
h
′
,
min
h
∈
Class
h
′
⁡
⁡
(
t
h
-
δ
h
)
)
∗
min
⁡
(
τ
K
,
t
h
′
+
Δ
h
)
∗
b
1
=
δ
1 and B1=min⁡(τK,Δ1).Roughly speaking,S1(σU,M,TC,τ) is a multi-integral that evaluates the sum of the duration variables dh over their possible range of variation constrained by the measurement time interval [0,τK], the dates of measurements τk, and the temporal specifications [δh,Δh]. Similarly, S2(σU,M,τ) evaluates the sum of the duration variables dh over their possible range of variation constrained only by the measurement time interval [0,τK] and the dates of measurements τk (the temporal specifications [δh,Δh] are not considered). The ratio of both evaluations leads to the probability that any timed trajectory (σ,M), resulting from untimed trajectory (σU,M) and consistent with τ, satisfies the set of temporal constraints TC. From a numerical point of view the calculation of S1(σU,M,TC,τ) and S2(σU,M,τ) is obtained with a recursive algorithm.


## 3.4. Detection of the Temporal Faults

In the general case, several untimed trajectories(σU,M) may be consistent with a given timed measured trajectory TRO in time interval [0,τK] (i.e., ΓU-1(TRO) contains more than one trajectory). This situation is due to two different reasons: (1) several markings M may be consistent with the first marking measurement MO(0); (2) from a given marking M, several untimed sequences may be consistent with the measured trajectory TRO. In order to deal with (1), let us consider M0(TRO) as the set of markings consistent with MO(0) and π0(M) as the probability that M is the current marking at date 0 such that ∑M∈M0TROπ0(M)=1. The set M0(TRO) and the probability π0(M) for each M∈M0(TRO) are assumed to be known (Assumption D). Note that Assumption D can be relaxed for PNs without absorbing subsets of markings by considering the steady state probability of M as π0(M). In order to deal with (2), the probability of each sequence issued from the same marking M and consistent with TRO is evaluated with the following: (17)probσU,M∣TROandM=S2σU,M,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τ. Finally the probability of each trajectory (σU,M) is obtained with (18)probσU,M∣TRO=π0M·S2σU,M,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τand prob(TRO satisfies TC)=probσU,M∣TRO·prob((σ,M) satisfies TC∣(σU,M) and τ). This last equation leads to(19)probTROsatisfiesTC=π0M·S1σU,M,TC,τ∑σ′U,M∈ΓU-1TROS2σ′U,M,τThen, the diagnosis of temporal faults results from the iterative evaluation of (19). For that purpose, a sampling period Δt is considered and for each date t=k·Δt, prob(TRO satisfies TC) is updated depending on the eventual new measurements that are collected during time interval [k-1·Δt,k·Δt[. Formally, if TRO(k) refers to the measured trajectory collected during time interval [0,k·Δt[, the probability prob(TRO(k) satisfies TC) will be compared to a given threshold γ and an alarm is generated each time prob(TRO(k) satisfies TC)<γ.Let us consider again POTPN1 of Figure2 introduced in Section 3.1. If the first measured marking is assumed to coincide with MI then M0(TRO) = {100T,010T} with π0100T=1 and π0010T=0. The timed trajectories (σ,M) consistent with TRO=0(0)e(τ1)0(τ1) satisfy also σ=T(t1)T(t2) with T(t1)=T1, T(t2)=T2, t2=τ1, and t1≤τ1. Two successive cases are considered to illustrate the computation of prob(TRO satisfies TC) with (19).In case A, the pdfs of the transition durations are assumed to be bounded uniform with the same support[0,10] for T1 and T2. The temporal constraints are arbitrarily defined by TC1=[4,6] for T1 and TC2=[3,7] for T2. Prob(TRO satisfies TC) computed with (19) is reported in Figure 3(a) (full line) in function of the date τ1. For the considered example, this equation can be rewritten as follows:(20)probTROsatisfiesTC=∫max⁡δ1,τ1-Δ2min⁡Δ1,τ1-δ2f1t·f2τ1-t·dt∫0τ1f1t·f2τ1-t·dt.Note that this probability is zero for τ1<7 TU (one lower bound at least is not satisfied for the temporal constraints) and also for τ1>13 TU (one upper bound at least is not satisfied for the temporal constraints). This computation is confirmed with a series of 1000 Monte Carlo simulations that coincide with TRO (dashed line). Depending on the choice of the threshold γ, an alarm may be generated. For example, for γ=0.2, an alarm is generated if τ1∈[8.5,11.3].Figure 3
Computation and Monte Carlo simulations to evaluateprob(TRO satisfies TC) in function of τ1: bounded uniform pdfs (a); symmetrical triangular pdfs (b).
(a)
(b)In case B, the pdfs of the transition durations are assumed to be symmetrical triangular with supports[1,4] for T1 and [2,7] for T2. The temporal constraints are, respectively, TC1=[2,3] for T1 and TC2=[3,6] for T2. Prob(TRO satisfies TC) is computed with (19) in Figure 3(b) (full line) in function of the date τ1. This computation is also validated with a series of 1000 Monte Carlo simulations that coincide with TRO (dashed line).


## 3.5. Numerical Complexity

The numerical complexity of the whole diagnosis schema is due (a) to the computation ofΓU-1(TRO); (b) to the numerical evaluation of (19).(a) The complexity to computeΓU-1(TRO) is related to the resolution of (9) and (10) that include hmax·K·(n+q+1) inequalities and hmax·K·(no+p) equalities with hmax·K·q+n unknown integer variables. Basically, the complexity is exponential with respect to the number N of reachable markings in R(G,MI) and to the length K of the measured trajectories (hmax⁡ is a constant parameter). Branch and bound algorithms can be used to solve (9)-(10) as an integer linear programming problem (LPP) [24]. These algorithms have a general nonpolynomial complexity but limit the computational effort in many practical situations. An algorithm of linear complexity has been also developed in our previous work that limits the length K of the timed measured trajectories under test. It considers measured trajectories within a sliding window of constant size K0 instead of increasing size K [25] and leads to an algorithm of linear complexity with respect to K. Note also that the complexity with respect to N is no longer exponential if the set M0(TRO) is known (Assumption D).(b) The numerical evaluation of (19) is obtained according to a recursive scheme with a deep equal to the number of transitions of type 2 or 3 in the considered sequence. Consequently the computation effort increases rapidly in time and in space with respect to the sequence length. To limit the computational complexity, the trajectory (σ,M) is divided into S subtrajectories that are considered successively and independently: (σ,M)=(σ1,M1)⋯(σS,MS) with M1=M. Each subtrajectory (σs,Ms) is of minimal length such that (i) (σs,Ms) ends with a measurement M(τk); (ii) all transitions in σs are enabled from a marking that belongs to the same subtrajectory (σs,Ms) and not to a previous one. For this reason each subtrajectory can include several measurements. For example, the trajectory in (21) is divided into two subtrajectories (σ1,M1) and (σ2,M2).Trajectory decomposition is as follows:(21)σ,M=σ1,M1σ,M=M0Tt1Mt1⋯Tth′′kkkkkkkkkkkkkk-----------dh′′=th′′-t1dh′′=th′′–t1dh′′=th′′–t1σ2,M2Mth′′⋯Tth′Mth′⋯TthMth⋯TtHMτK-----------dh=th-th′-------------------------------------------------------dH=tH-th′′.


## 3.6. Example

Let us consider the marked POTPN2 of Figure4 (unobservable places and transitions are highlighted in grey) that represents a cycle of tasks. The state of the system is not measured and only two events are observed. The set of labels is E={e1,e2}. The matrices L=10000T∣00001TT and H=00000 define the sensor configuration. Measurements are collected over the time interval [0,20] and the measured trajectory TRO=0(0)e1(3.7)0(3.7)e2(20)0(20) is considered. For this example hmax=4 and a single untimed trajectory (σU, MI) with σU=T1(1)T2(2)T3(3)T4(4)T5(5) is consistent with TRO. The timed trajectories (σ, MI) consistent with TRO satisfy σ=T(t1)T(t2)T(t3)T(t4)T(t5) with T(t1)=T1,T(t5)=T5,t1=3.7 TU, t5=20 TU, and t1≤t2≤t3≤t4≤t5. The pdfs of the transition durations are assumed to be bounded uniform with the same support [0,10] for Tj,j= 1 : 5. The temporal constraints are also assumed to be identical TCj=[1,9] for j = 1 : 5.Figure 4
POTPN2.P
r
o
b
(
T
R
O satisfies TC)=S1/S2=0.46 is obtained by (19) with(22)S1=∫τ1+δ2τ1+Δ2f2t2-τ1·∫t2+δ3t2+Δ3f3t3-t2·∫min⁡t3+δ4,τ5-Δ5max⁡t3+Δ4,τ5+δ5⁡f4t4-t3·f5τ5-t4dt4dt3dt2=0.024,S2=∫0τ5f2t2-τ1·∫t2τ5f3t3-t2·∫min⁡t3,τ5τ5f4t4-t3·f5τ5-t4dt4dt3dt2=0.054.This computation is validated with a series of simulations that leads to a probability of 0.47. The evaluation of Prob(TRO satisfies TC) with (19) saves time compared to the numerical evaluation based on simulation.


## 4. Conclusion

This article has proposed a diagnosis system that checks if the heterogeneous measurements obtained from a stochastic timed discrete event system with an uncomplete sensor configuration are consistent or not with a set of temporal constraints that specify tolerance intervals for the system operations. For this purpose, the set of trajectories consistent with a given timed measured trajectory are first characterized. Then the consistency of each trajectory with the temporal constraints is estimated as a probability. Finally the probability of each trajectory is also evaluated and the global probability that the temporal constraints are satisfied results from the previous steps. The diagnosis system returns an alarm each time this probability goes below a given threshold. The contribution is validated with simulation results.In the future, we will consider the isolation of the temporal constraints that are unsatisfied. We will relax some assumptions, in particular Assumption B, in order to consider the silent closure of the trajectories. We will also study the problem from a structural point of view by providing some results to decide whether a set of sensors is suitable or not to check that a set of temporal constraints is satisfied. Finally we aim to apply the proposed approach to larger systems.



---

*Source: 2821078-2017-04-12.xml*