Repositorio Institucional de Documentos

M´aster en Ingenier´ıa de Sistemas e Inform´atica Trabajo Fin de M´aster On State Estimation of Timed Petri Nets Xu WANG Director: Cristian Mahulea Codirector: Manuel Silva Su´arez Departamento de Inform´atica e Ingenier´ıa de Sistemas Escuela de Ingenier´ıa y Arquitectura Universidad de Zaragoza Septiembre 2011 Abstract This report presents an online algorithm for state estimation of timed choice-free Petri nets. We assume that the net structure and initial marking are known, and that the set of transitions is divided in observable and unobservable one. Given an observed word and assuming that the time durations associated to the unobservable transitions are unknown, the problem is to estimate the possible states in which the timed net system can be. This work extends the notion of basis markings defined for untimed Petri nets considering now the time information. The proposed algorithm deals with three main steps: (1) wait for a new observation and compute the set of basis markings without considering the time; (2) update the set of time equations that contain the time restriction for the unobservable transitions; (3) update the set of basis markings removing the time-inconsistent markings. The extension of the algorithm to general nets is discussed, as well. Finally, the adaption of the proposed algorithm to distributed system is discussed. A distributed system is composed by a set of timed PN called sites connected by buffers. An agent is assigned for each site and it observes the firing of transitions and performs state estimation algorithm. Keyword: Petri nets, timed Petri nets, state estimation, observability Contents List of Figures iii 1 Introduction 1 2 Basic Concepts 3 2.1 TimedPetriNets................................ 3 2.2 BasisMarking.................................. 5 3 Time Duration of Firing Sequence and Reduction Rules 6 3.1 Time Duration of Firing Sequence . . . . . . . . . . . . . . . . . . . . . . . 6 3.2 ReductionRules................................. 7 4 State estimation of choice-free nets 9 4.1 Computation of basis markings . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 Computation of the set of time equations . . . . . . . . . . . . . . . . . . . 10 4.3 Algorithm for state estimation . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.4 Extension to nets with choices . . . . . . . . . . . . . . . . . . . . . . . . . 14 5 State estimation of distributed systems 15 6 Conclusions and Future Work 19 Bibliography 20 ii List of Figures 2.1 Example of w=λ(σ).............................. 4 2.2 Example of the set of basis markings . . . . . . . . . . . . . . . . . . . . . 5 3.1 Example of ι(σ) = ι(σ1) + ι(σ2) + ···+ι(σn)................. 7 3.2 Illustration of the reduction rules . . . . . . . . . . . . . . . . . . . . . . . 8 4.1 PN system used in Example 4.1 . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 Example of the algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 Example of PN’s with choice . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5.1 Immediate transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 5.2 Global model for Example 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . 17 iii Chapter 1 Introduction Reconstructing the state of a system from available measurements is a fundamental issue in several applications. State observation can be seen as a self-standing problem, but also as a pre-requisite for solving problems of different nature. This problem has been extensively investigated in time driven systems. On the contrary, despite the attention payed by several authors in the last years, there are relatively few works addressing this topic in discrete and hybrid systems, thus several related problems are still open. In the case of discrete event systems modeled by Petri nets (PN), different approaches for observability have been recently proposed. In [7] the problem was that of reconstructing the initial marking (assumed only partially known) from the observation of transition firings. In [9] this approach was extended to the observation and control of timed nets. In other works it was assumed that some of the transitions of the net are not observable [4] or undistinguishable [6], thus complicating the observation problem. In [1] the author has studied the possibility of defining the set of markings reached firing a “partially specified” step of transitions using logical formulas, without having to enumerate this set. In [11] the authors have discussed the problem of estimating the marking of a Petri net using a mix of transition firings and place observations. In this work, we study the problem of state estimation of discrete event systems modeled by timed Petri nets. We assume that the set of transitions is split into two subsets: observable and unobservable. The firing of the observable transitions can be detected, while the firing of the unobservable transitions cannot and the time durations associated to unobservable transitions are unknown. The basic idea is to extend the notion of basis markings to timed nets. The set of basis markings is proposed in [8] to characterize the set of consistent markings, i.e., the set of possible markings of a PN after an observed word. Knowing the set of basic markings, the set of consistent markings is obtained from the first one by firing the unobservable transitions. Using some reduction rules, we show how to reduce both the structure and the state space of the unobservable net. The reduction rules merge indistinguishable transitions, 1 in order to reduce the complexity of the state estimation procedure. To reconstruct the marking of the original net it is necessary to determine the markings of the input/output places of merged transitions. These markings can be expressed as the solution of a linear system that expresses their dependence from the marking of the new places. Assuming that the time durations of the unobservable transitions are not known, we compute together with the set of basis markings a set of time equations. This set represents the relation between the observation and time durations of unobservable firing sequences. The set of time equations is used after to reduce the set of basic markings. The online algorithm that we propose estimates the state of a timed PN and is based on the following three main steps: 1) compute the set of basis markings; 2) compute the set of time equations; 3) reduce the set of basis markings according to the set of time equations. In the context of state estimation of distributed systems, [10] proposed an algorithm for timed Petri net with the assumption that the time durations of transitions are known. We assume that the PN model of each site is a state machine, while the global system is aDeterministically Synchronized Sequential Processes (DSSP) system [3]. We discuss the state estimation of timed DSSP with the assumption that all time durations of transitions are unknown. The following chapters are organized as follows: a background on Petri nets are given in Chapter 2; in Chapter 3 we characterize the time duration of a firing sequences and reduction rules; and, an online algorithm for state estimation of timed PN is introduced in Chapter 4. At last, the discussion of adapting the online algorithm to distributed systems is given in Chapter 5. Chapter 2 Basic Concepts In this section, we recall the basic definition of (timed) Petri net system (for a general introduction, see [12]). 2.1 Timed Petri Nets Definition 2.1. A PN system is a pair hN ,m0i, where N=hP, T, P re,P ostiis a net structure with a set of places P; a set of transitions T; the pre and post incidence matrices P re,P ost ∈N|P|×|T| ≥0; and m0∈N|P| ≥0is the initial marking, where |P|is the number of places and |T|is the number of transitions. The incidence matrix is C=P ost −P re. For every node v∈P∪T, the set of its input and output nodes are denoted as •vand v•, respectively. A directed circuit of PN is a sequence pi1ti1pi2ti2···pintin, where pij ∈P, tij ∈T, pij ∈•tij, tij ∈•pi,j+1, and ∃j6=k, pij =pik or tij =ti,j+1. A net having no directed circuit is called acyclic. A transition t∈Tis enabled at a marking mif and only if m≥P re[·, t]. If a marking m′is reachable from mby firing a sequence σ=ti1ti2···tin, where tij ∈T, j = 1,2,...,n: the fundamental state equation can be written as m′=m+C·σ, where σ∈N|T| ≥0is the firing count vector of σ;m[σidenotes that σis firable from m, while m[σim′means the firing of σdrives mto m′. The set of transitions Tis partitioned into two sets: Toand Tu, where Tois the set of observable transitions, whose firing can be detected by an external observer, and Tuis the set of unobservable transitions. The firing sequence σois an observable firing sequence, if t∈σo, then t∈To;σuis an unobservable firing sequence, if t∈σu, then t∈Tu. An observation function λ:T∗→T∗ o, where T∗ ois the Kleene closure of To, extracts a sequence of observable transitions λ(σ) from σ. Let σ=σu 1σo 1σu 2σo 2···σu n, then λ(σ) = σo 1σo 2···σo n−1. Observable transitions are represented as white rectangles, while unobservable ones as black rectangles. 3 ε3ε4 ε1t5 t2p2 p1p3p4 Figure 2.1: Example of w=λ(σ) Example 2.1. For the PN in Fig. 2.1, observable transitions are t2, t5, and unobservable transitions are ε1, ε3, ε4. Let σ=ε1t2ε3ε4t5, then the observed word of σis w=λ(σ) = t2t5. Definition 2.2. A timed PN system is a triple hN ,θ,m0i, where hN ,m0iis a PN system and θ∈R|T| ≥0is the time vector that associates to each transition tja constant time delay, θj=θ[tj]. The time duration of a transition is deterministic, i.e., if a transition tjis enabled at time τ,tjis fired at τ+θ[j]. The single server semantic is used, which means a transition cannot be enabled simultaneously more than once. We make the following assumptions: (A1) the initial marking and net structure are known; (A2) the unobservable induced subnet (P Nu=hP, Tu,P reu,P ostui)is acyclic, where P reuand P ostuare pre and post incidence matrices constrained by Tu; (A3) The time durations of observable transitions are known, while the time durations of unobservable transitions are unknown. The second assumption implies that there are not spurious solutions in the unobservable subnet, i.e., all markings, solution of the state equation are reachable. Therefore, the set of basis markings can be characterized using the state equation. Even if the initial marking is known, because of the partial observation, the state of timed PN’s cannot be determined by the observation. To characterize the possible set of markings we use a subset of it, which is called the set of basis markings. Knowing the set of basis markings, the consistent markings, which are the possible markings in the net system, can be obtained by simply firing the unobservable transitions from the basis markings. Definition 2.3. [8] Given a marking mand an observable transition t∈To, we define the set of explanations of tat mas Σ(m, t) = {σ∈T∗ u|m[σim′,m′≥P re[·, t]}. The set of minimal explanations of tat mas Σmin(m, t) = {σ∈Σ(m, t)|∄σ′∈ Σ(m, t) : σ′σ}, where σ′σmeans that for every t,σ′[t]σ[t]and there exists t such that σ′[t]<σ[t]. 2. Basic Concepts 5 2.2 Basis Marking In the following, the set of basis markings without time is introduced. The set of basis markings of observation wis denoted by Mb(w). Definition 2.4. The set of basis markings of observation w=vt is defined as Mb(w) = {m∈N|P| ≥0|∀m′∈ Mb(v) : ∀σ∈Σmin(m′, t),m′[σtim}. For empty word ǫ,Mb(ǫ) = {m0}. p2p3p4 p1ε3 ε2t1 Figure 2.2: Example of the set of basis markings Example 2.2. Let us consider the PN in Fig. 2.2 with m0= [1,1,0,0]T. The unobservable transitions are ε2and ε3, while the observable transition is t1. Assume t1has been observed. The set of basis markings before any observation is Mb(ǫ) = {m0}, where ǫis the empty word. When w=t1is observed, the set of explanations is Σ(m0, w) = {σ1, σ2}, where σ1=ε3, σ2=ε2ε3. Therefore, the set of minimal explanations is Σmin(m0, w) = {σ1}. By firing σ1t1, the marking m1= [1,0,0,1]Tis obtained and the new set of basis marking is Mb(t1) = {m1}. For a marking min the set of basis markings, there exists σsuch that m0[σim. The sequence σis composed by the observable transitions and unobservable firing sequences, which are minimal explanations. In order to represent the firing sequences that drive the marking from m0to m, based on the set of minimal explanation, we present the set of minimal firing sequences. Definition 2.5. Given a marking mand an observed word w=ti1ti2···ti,n−1tin, we define the set of firing sequences consistent with was Γ(m, w) = {σ∈T∗|σ=σu 1ti1σu 2ti2··· ti,n−1σu ntin,m0[σim}. Based on Γ(m, w), we define the set of minimal firing sequences as Γmin(m, w)⊆ Γ(m, w), that σu j, j = 1,...,n is a minimal explanation of corresponding marking and observation. Definition 2.6. The set of basis markings at time τof a timed Petri net is defined as Mb(w, τ) = {m∈ Mb(w)|∃σ∈Γmin(m, w), σ =σ′t, λ(σt) = w, t is observed at τ}. The firing sequences consistent with wdefines the firing sequences whose observation word is wand lead the system to the marking m. State Estimation of Timed Petri Nets and let ojbe the time equation obtained at time τj> τq, where oj:min{ι(σj,1), ι(σj,2),..., ι(σj,kj)}=τj, with q, kq, j ∈N>0. Let ι(σj)∈ {ι(σj,1), ι(σj,2),...,ι(σj,kj)}and decompose σjas σj=σ1 jσ2 j. . . σr j. Find all σi k,l in Osuch that σi k,l is a subsequence of a σl jand ∀l, ι(σi k,j )≥σl j. If Piι(σi k,j )> τj then remove ι(σj)from oj. Proof. Obviously, If the previous conditions are satisfied, ι(σj)> τj. Hence it is not timed-consistent with the observation. 4.3 Algorithm for state estimation In this section, we present an algorithm for state estimation of systems modeled by timed PN’s. When a new observation is available, the four steps in Algorithm 1 are performed. Algorithm 1 Estimate the state of timed PN’s 1: Compute the set of basis markings Mb(wtj, τj) based on the current observation tj at τj. 2: Compute the time equation oj. 3: Reduce ojbased on Prop. 4.1. 4: Reduce the set of basis markings Mb(wtj, τj) accordingly. p3 p6 p12 ε23 t1 ε4 ε6 p7 p5 t5 ε7p4 p3 p7 p2 p6 p5p1 t5 ε3 t1 ε7 ε6 ε2 ε4 p4 (a) (b) Figure 4.2: Example of the algorithm Example 4.3. Let us consider the PN in Fig. 4.2(a). with observable transitions t1and t5, θ1=θ5= 1, and the initial marking m0= [p1, p2, p3, p4, p5, p6, p7]T= [1,0,0,0,0,0,0]T. Applying reduction rule # 1, transitions ε2and ε3are merged into ε23, and places p1 and p2are merged into p12. Fig. 4.2(b) shows the reduced model. The initial marking is m0= [p12, p3, p4, p5, p6, p7]T= [1,0,0,0,0,0]T. The state estimation algorithm is applied on the reduced PN in Fig. 4.2(b). Let us assume the following observations: t1at 5,9and t5at 10. 4. State estimation of choice-free nets 13 •At time 0, the set of basis markings is Mb(ǫ, 0) = {m0}and the set of time equations is O=∅. •At time 6,t1is observed (w=t1). The set of minimal explanations is Σmin = (m0, t1) = {σ1.σ2}, where σ1=ε23ε6,σ2=ε23ε4, meaning that σ1or σ2has been fired in order to enable t1. By firing σ1t1and σ2t1, the set of basis markings is obtained as Mb(w, 6) = {m1,m2}, where m1= [1,2,0,0,0,0]T,m2= [1,0,1,1,0,0]T, and the sets of minimal firing sequences are Γmin(m1, w) = {σ1t1}and Γmin(m2, w) = {σ2t1}. The time equation at time 6is min{ι(σ1t1), ι(σ2t1)}= 6, the only equation that will compose O. •At time 9,w=t1t1and the sets of minimal explanations are Σmin(m1, t1) = {σ1, ε4},Σmin(m2, t1) = {σ2, ε6}. By firing σ1t1and ε4t1from m1, we obtain m3= [1,4,0,0,0,0]Tand m4= [2,1,1,0, 0,0]T, respectively; by firing σ2t1and ε6t1from m2,m4and m5= [1,0,2,2,0,0]Tare obtained. Therefore, Mb(w, 9) = {m3,m4,m5}and Γmin(m3, w) = {σ3},Γmin(m4, w) = {σ4, σ6}and Γmin(m5, w) = {σ5}, where σ3=σ1t1σ1t1},σ4=σ1t1ε4t1,σ6=σ2t1ε6t1, and σ5=σ2t1σ2t1}. From previous sets the time equation at time 9is obtained as min{ι(σ3), ι(σ4), ι(σ5), iota(σ6)}= 9. Observe that σ3=σ1(t1σ1)t1satisfying Prop. 4.1, and ι(σ3) = ι(σ1) + ι(t1σ1) + ι(t1). Form the equations of Ocan be observed immediately that ι(t1σ1)≥6and ι(σ1) = ι(t1σ1)− θ1≥5. Therefore, ι(σ3)≥5 + 6 + 1 = 12 >11. Hence, ι(σ3)should be removed. For the same reason, ι(σ5)is also redundant and can be removed. The set of time equations becomes: O=(min{ι(σ1t1), ι(σ2t1)}= 6, min{ι(σ4), ι(σ6)}= 9.) The set of basis markings is reduced to Mb(w, 9) = {m4}. •At time 10,t5is observed (w=t1t1t5). The set of minimal explanations is Σmin = (m4, t5) = {ε7}. Firing ε7t5, the set of basis markings is obtained as Mb(w, 10) = {m6}, where m6= [2,1,0,1,0,0]T, and the set of minimal firing sequences as Γmin(m6, w) = {σ7, σ8}, where σ7=σ4ε7t5and σ8=σ6ε7t5. The time equation obtained at this time moment is min{ι(σ7), ι(σ8)}= 10. Hence, the set of time equations is O=     min{ι(σ1t1), ι(σ2t1)}= 6, min{ι(σ4), ι(σ6)}= 9, min{ι(σ7), ι(σ8)}= 10.      Being an online procedure, seems that the set of time equations is growing indefinitely. However, dealing only with time deterministic Petri nets, this is not true and there exists State Estimation of Timed Petri Nets a moment from which any other time equation does not provide new information and the set of time equations is not updated anymore. In the following, we discuss the time in a structurally live (SL) and structurally bounded (SB) choice-free net with a minimal T-semiflow x. We assume the upper bound of time duration of every transition is u, and then the upper bound of a firing vector σis u(σ) = u·P|T| i=1 σ[i]. Let mhbe home state, i.e., it can be reached from every reachable marking [5]. Based on [13], mhwill be reached by a firing sequence σh, with σh≤x. Proposition 4.2. In a SL&SB choice-free net with minimal T-semiflow x, if the initial marking is live, it is not necessary to update the set of time equations after the time instant 2·u(x). Proof. Because the net is SL&SB and the initial marking is live, then there exists a circle in the reachability graph and a home state mh. From m0, after firing σh, the home state is reached and the system behavior starts to repeat. Therefore, from this moment, it is not necessary to update the set of time equations. 4.4 Extension to nets with choices p2 t1 ε5 ε4 ε3 ε2 p3 p4 p1 Figure 4.3: Example of PN’s with choice Let us consider the PN in Fig. 4.3 with ε2and ε4immediate transitions, i.e., θ2= θ4= 0, θ1= 1, and m0= [1,0,0,0]T. Assume t1is observed at time 4. Obviously, ε2ε3or ε4ε5has been fired to enable t1, but we don’t know exactly which one. Since t1has been observed at 4, we can say that ι(ε2ε3t1) or ι(ε4ε5t1) is 4, but we cannot say nothing about the time duration of the other. Hence, we cannot say that the minimum of ι(ε2ε3t1) and ι(ε4ε5t1) is 4. Therefore, to apply the algorithm to general nets, there exist two possibilities: (1) reduce the net using the reduction rules, to obtain a choice-free one (2) enumerate all possible combinations of firing sequences. This approach is similar with the one of state estimation of untimed PN’s. Chapter 5 State estimation of distributed systems Let us consider distributed system, for which each site is a timed Petri net system monitored by an agent. Every agent knows the structure and the initial marking of its site. The model of each site is a state machine, while the model of global system is a Deterministically Synchronized Sequential Processes (DSSP) system [3]. Definition 5.1. [3] A PN system, S=hP1∪· · ·∪PK∪B, T1∪· · ·∪TK,P re,P ost,m0i, is a DSSP, if: 1. Pi∩Pj=∅, Ti∩Tj=∅, Pi∩B=∅,∀i, j ∈ {1,...,K}, i 6=j; 2. hSMi,m0ii=hPi, Ti,P rei,P osti,m0ii,∀i∈ {1, . . . , K}is a strongly connected and 1-bounded state machine (where P rei,P ostiand m0iare the restrictions of P re,P ost and m0to Piand Ti); 3. The set Bof buffers is such that ∀b∈B: (a) |•b| ≥ 1and |b•| ≥ 1, (b) ∃i∈ {1,...,K}such that b•⊂Ti, (c) ∀p∈P1∪ · · · ∪ PK:t, t′∈p•⇒P re[b, t] = P re[b, t′]. Transitions belonging to the set T I =•B∪B•are called interface transitions. The remaining ones (T1∪ · · · ∪ TK\T I) are called internal transitions. In this chapter, immediate transitions, whose time delays are 0, are introduced to solve conflicts, i.e., if |p•|>1, then ∀t∈p•has its time delay θt= 0. In order to let representation of models to be compact, immediate transitions are not shown in models. In Fig. 5.1(a), immediate transitions are t1and t2, while they are not shown in Fig. 5.1(b), 15 p1p6 p2 p3 p4 p5 t1 t2 t3 t4 t3 t4 p4 p5 (a) (b) Figure 5.1: Immediate transitions which is the compact representation, and the marking of p6is m[p6] = m[p1] + m[p2] + m[p3]. In each site, the set of transitions Tiis partitioned into two sets: Tio and Tiu, where Tio is the set of observable transitions, whose firing can be detected by an external observer, and Tiu is the set of unobservable transitions. The firing sequence σois an observable firing sequence, if t∈σo, then t∈Tio;σuis an unobservable firing sequence, if t∈σu, then t∈Tiu. An observation function λ:T∗ i→T∗ io, where T∗ io is the Kleene closure of Tio, extracts a sequence of observable transitions λ(σ) from σ. Let σ=σu 1σo 1σu 2σo 2···σu n, then λ(σ) = σo 1σo 2···σo n−1. Observable transitions are represented as white rectangles, while unobservable ones as black rectangles. We make the following assumptions: (A1) the initial marking and the net structure are known; (A2) the unobservable induced subnet is acyclic; (A3) the time durations of transitions are unknown; (A4) an agent only observes the firing of transition in its site; (A5) an agent only knows the structure and initial marking of its site. When the firing of an observable transition tjis observed, the marking of SMiis mi, that, for k= 1,...,|Pi|, mi[k] = (1, pk∈tj•, 0, otherwise. Definition 5.2. Two agents Aiand Ajare neighbor agents, if ∃b∈B, •b∩Ti6=∅, b•∩Tj6= ∅, where Tiand Tjare sets of transitions of sites monitored by Aiand Aj, respectively. The proposed state estimation algorithm estimates the firing of transitions. An agent observes its site and computes possible firing sequences using the algorithm. The local 5. State estimation of distributed systems 17 estimation is improved based on the communication between agents. Using the communicaton information, the marking of buffers are interchanged between agents. t4 t5 t6 t7 t8 t9 t10 b1 b2 p4 p5 p6 p7 p8 p9 Agent A1 t1 t2 t3 p1 p3 p2 Site S1Site S2 Agent A2 Figure 5.2: Global model for Example 5.1 Example 5.1. The model in Fig. 5.2 represents a DSSP system. There are two sites and two agents monitoring each sites. The sites S1and S2are connected with buffers b1 and b2. The only observable transition in S1is t2, while in S2is t7. The observation is given in Tab. 5.1. We assume that an agent sends information to its neighbor agents immediately after it computes the estimation. Let us discuss the state estimation of A2 according to its observation and to the information received from A1. Table 5.1: The observation in Example 5.1 tt2t7t2, t7 τ3 6 11 •At time 3, agent A1observes the firing of t2. At this moment, the information regarding b1and b2are: “from time 0to 3, no token has been produced in b1” and “from time 0to 3, no token has been consumed from b2”, respectively. These information are sent to A2. •At time 6,t7is observed by A2. From the initial marking, the possible firing sequences are σ1=t4t5t6t7and σ2=t8t9t10t7. From time 0to 6,σ1consumes 1token from b1and State Estimation of Timed Petri Nets produces 1token in b2, while σ2does not consume or produce any token to buffers. The information from A1says that no token is produced in b1from time 0to 3, but there is no information of b1from time 3to 6. Therefore, σ1may be consistent with the observation and with the information received from A1. Obviously, σ2is consistent with the received information. •At time 11,A1observes t2and A2observes t7. The agent A1computes the information of b1and b2, which are “from time 0to 11, one token has been produced in b1” and “from time 0to 11, one token has been consumed from b2”, respectively. The possible firing sequences of S2are σ5=σ1σ1,σ6=σ1σ2,σ7=σ2σ1and σ8=σ2σ2. With the information from A1,A2concludes that: 1) only one token has been produced in b1from time 0to 11, and then the firing sequences which consume more than one tokens from b1 are not possible; 2) one token has been consumed from b2from time 0to 11, and then the firing sequences which do not produce more than one tokens in b2should be eliminated. Because σ5consumes two tokens from b1and σ8does not produce any token in b2, so they are eliminated from possible firing sequences. The possible firing sequences at time 11 in S2are σ6and σ7. Therefore, the agents should use the information of buffers to eliminate inconsistent firing sequences. Inconsistent can come from the following situations: (1) if the information says itokens are produced in a buffer, then firing sequences which consume more than itokens are inconsistent; (2) if in the information, itokens are consumed from a buffer, then firing sequences which produce less than itokens are inconsistent sequences. When a system starts to evolve, each agent performs local estimation and computes information of buffers. Because the information includes time information, which is “from time τ1to τ2,itokens are produced to (or consumed from) a buffer”, so the problem that it should be considered whether there exists a global clock in the system or not. In the affirmative case, the time instants are interchanged between agents, as the one in Example 5.1. Otherwise, in the situation that each site has a local clock, the time instants are not included in information, while when an agent receives an information, it computes time instants for the information as following: (1) the information is “from last commmunication until this moment, itokens are produced into (or consumed from) a buffer”, (2) assume last and present communication are at τ1and τ2, (3) the information in the receiver agent is “from τ1(last communication) until τ2(current communication), itokens are produced into (or consumed from) a buffer”. All these consideration will be considered when the state estimation will be developed for distributed systems. Chapter 6 Conclusions and Future Work In this work, we provide an online algorithm for state estimation of timed choice-free PNs, and we give some ideas on how the procedure is adapted to a paticular class of distributed systems. First, an algorithm to compute the set of consistent markings is given, and then the time information are grouped into a set of time equations that is used to reduce the set of consistent markings. Some reduction rules are presented that can be used also to reduce the state space of the timed systems merging the indistinguishable transitions. Second, we discuss the general case, i.e., nets with choices, and we show that the procedure is similar with the standard one of untimed Petri nets. Finally, the adaption of the approach to distributed systems is illustrated with an example. Communication is introduced into state estimation by agents in distributed systems. As a future work, we plan to continue working on state estimaton of distributed systems and to implement the algorithms in MATLAB. 19 Bibliography [1] A. Benasser. Reachability in Petri nets: an approach based on constraint programming. PhD thesis, Universit´e de Lille, 2000. [2] M.P. Cabasino, A. Giua, C. Mahulea, L. Recalde, C. Seatzu, and M. Silva. State estimation of Petri nets by transformation. In IEEE International Conference on Automation Science and Engineering, 2007. CASE 2007, pages 194–199, 2007. [3] J. Campos, S. Donatelli, and M. Silva. Structured solution of stochastic DSSP systems. In Petri Nets and Performance Models, IEEE International Workshop on, pages 91–100, Los Alamitos, CA, USA, 1997. IEEE Computer Society. [4] D. Corona, A. Giua, and C. Seatzu. Marking estimation of Petri nets with silent transitions. IEEE Transaction on Automatic Control, 52(9):1695–1699, 2007. [5] J. Esparza and M. Nielsen. Decidability issues for Petri nets. Technical report, BRICS, Department of Computer Science, University of Aarhus, 1994. [6] A. Giua, D. Corona, and C. Seatzu. State estimation of λ-free labeled Petri nets with contact-free nondeterministic transitions. Discrete Event Dynamic Systems, 15(1):85 – 108, 2005. [7] A. Giua and A. Seatzu. Observability of place/transition nets. IEEE Transactions on Automatic Control, 47(9):1424–1437, 2002. [8] A. Giua and C. Seatzu. Fault detection for discrete event systems using Petri nets with unobservable transitions. In 44th IEEE Conference on Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC’05, pages 6323–6328, 2005. [9] A. Giua, C. Seatzu, and F. Basile. Observer-based state feedback control of timed Petri nets with deadlock recovery. IEEE Transaction on Automatic Control, 49(1):17 – 29, 2004. 20 BIBLIOGRAPHY 21 [10] G. Jiroveanu and RK Boel. A distributed approach for fault detection and diagnosis based on time Petri nets. Mathematics and Computers in Simulation, 70(5-6):287– 313, 2006. [11] A. Ramirez-Trevino, I. Rivera-Rangel, and E. Lopez-Mellado. Observability of discrete event systems modeled by interpreted Petri nets. IEEE Trans. on Robotics and Automation, 19(4):557–565, 2003. [12] M. Silva. Practice of Petri Nets in Manufacturing, chapter Introducing Petri nets, pages 1–62. Chapman & Hall, 1993. [13] E. Teruel, JM Colom, and M. Silva. Choice-free Petri nets: A model for deterministic concurrent systems with bulk services and arrivals. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 27(1):73–83, 2002. State Estimation of Timed Petri Nets