Repositorio Institucional de Documentos

Distributed Control of Large Scale Systems Modeled with Continuous Petri Nets Liewei Wang, Cristian Mahulea, Jorge J´ ulvez, and Manuel Silva Abstract—This paper addresses the distributed control of large scale systems that are modeled with timed continuous Petri nets (ContP N). Distributed structures are first obtained after the system is decomposed into subnets by cutting the original net through sets of places, and adding marking structurally implicit places. Then, local control laws are computed separately. Algorithms are proposed to make the locally computed laws to be compatible and fireable when the global state of the system is considered. It is proved that using the control laws computed with the proposed algorithms, the final state of the overall system can be reached in minimum time. A manufacturing system is taken as case study to illustrate the control method. I. INTRODUCTION Petri Nets (P N) is a well known paradigm used for modeling, analysis, and synthesis of discrete event systems (DES). With strong facility to depict the sequence, concurrency, conflict and other synchronous relationships, it is widely applied in the industry, for the analysis of manufacturing, traffic, software systems, etc. Similarly to other modeling formalisms for DES, it also suffers from the state explosion problem. To overcome it, a classical relaxation technique called fluidification can be used. Continuous Petri nets [7], [17] are fluid approximations of classical discrete Petri nets obtained by removing the integrality constraints, which means the firing count vector and consequently the marking are no longer restricted to be in the naturals but relaxed into the non-negative real numbers. An important advantage of this relaxation is that more efficient algorithms are available for their analysis, e.g., reachability and controllability [12], [10] problems. Different works about control of Petri nets can be found in the literature [9], [4], [2], etc. In the context of distributed systems, distributed timed automata is discussed in [11]. In [20], the author proposed a method for the modeling and decomposition of large and complex discrete event manufacturing systems, where a Petri net based controller is distributed in machines and exchanges signals with coordinators. An architecture for distributed implementation of Petri nets in control applications is proposed in [14]. A distributed control strategy is designed in [8] for forbidden This work has been partially supported by the European Community’s Seventh Framework Programme under project DISC (Grant Agreement n. INFSO-ICT-224498) and by CICYT - FEDER projects DPI2006-15390 and TIN2007-66523. The authors are with the Department of Computer Science and Systems Engineering, University of Zaragoza, Maria de Luna 1, 50018 Zaragoza, Spain {lwwang, cmahulea, julvez, [email protected]}. state avoidance for discrete event systems which are modeled as Petri nets. Coming back to the continuous Petri nets, in [3], a reachability control problem of timed distributed continuous Petri net systems is studied. The paper considers Petri nets composed of several subsystems that communicate through channels modeled by places. The proposed algorithm allows the subsystems to reach their respective target markings at different time instants and keep them as long as required. In this work, the distributed control of large scale systems which are modeled with timed continuous Petri nets is addressed. As a starting point of this research topic, it is assumed that the systems we handle are modeled with marked graphs ContP N. This paper mainly focuses on driving the system from an initial state to a desired final state. A large scale system is first structurally decomposed into smaller subsystems, then the local control law for each subsystem is computed separately. A supervisory controller is introduced to update the locally computed control laws in order to make them admissible when considering the system globally, without knowing the detailed structures of local subsystems. With these control laws, all the local controllers work independently, and the final state can be reached in minimum time. This paper is organized as follows: Section II briefly recalls some basic concepts. In Section IV, a structurally decomposition method for marked graphs is discussed, which is used here to obtain distributed structures. Section V proposed the approach for distributed control of large system. Section VI gives an example of manufacturing systems. The conclusions are in Section VII. II. BASIC CONCEPTS The reader is assumed to be familiar with basic Petri net concepts (see [7], [17] for a gentle introduction). A. Continuous Petri Nets Definition 2.1: A continuous Petri net system is a pair hN,m0iwhere N=hP, T, P re,P ostiis a net structure where: •Pand Tare the sets of places and transitions respectively. •P re,P ost ∈R| P |×| T | ≥0are the pre and post incidence matrices. •m0∈R| P | ≥0is the initial marking (state). For v∈P∪T, the sets of its input and output nodes are denoted as •vand v•, respectively. Let pi,i= 1,...,|P| and tj, j = 1,...,|T|denote the places and transitions. Each place can contain a non-negative real number of tokens, this number represents its marking. The distribution of tokens in places is denoted by m. A transition tj∈Tis enabled at m iff ∀pi∈•tj,m(pi)>0and its enabling degree is given by enab(tj,m) = min pi∈•tjm(pi) P re(pi, tj) which represents the maximum amount in which tjcan fire. Transition tjis called k-enabled under marking m, if enab(t, m) = k. An enabled transition tjcan fire in any real amount α, with 0< α ≤enab(tj,m)leading to a new state m′=m+α·C(·, tj)where C=P ost −P re is the token flow matrix and C(·, j)is its jth column. If mis reachable from m0through a finite sequence σ, the state (or fundamental) equation is satisfied: m=m0+C·~σ, where ~σ ∈R|T| ≥0is the firing count vector, i.e., ~σ(tj)is the cumulative amount of firings of tjin the sequence σ. A vector ~σ is said to be a fireable firing count vector, if there exist a corresponding sequence σwhich can be fired. Marked Graph (MG) is a well known subclass of Petri nets in which each place has at most one input and at most one output arc. Thus they are structurally choice-free, allow concurrency and synchronization but not decisions. Property 2.1: [5] Let Nbe a strong connected marked graph, Nis consistent and its unique minimal T-semiflow is x=1,1is a vector with all component equal to 1. In timed continuous Petri net(ContP N) the state equation has an explicit dependence on time: m(τ) = m0+C·~σ(τ) which through time differentiation becomes ˙ m(τ) = C· ˙ ~σ(τ). The derivative of the firing sequence f(τ) = ˙ ~σ(τ) is called the firing flow. Depending on how the flow is defined, many firing semantics appear, being the most used ones infinite and finite server semantics [17]. For a broad class of Petri nets it is shown that infinite server semantics offers better approximation to discrete systems than finite server semantics [13]. This paper deals with infinite server semantics for which the flow of a transition tjat time τis the product of the firing rate, λj, and the enabling degree of the transition at m(τ) f(tj, τ) = λj·enab(tj,m(τ)) = λj·min pi∈•tjm(pi, τ) P re(pi, tj) (1) For the sake of clarity, τwill be omitted in the rest of the paper when there is no confusion: f(tj),mand m(pi)will be used instead of f(tj, τ),m(τ)and m(pi, τ). B. Implicit places and continuous marked graphs A place pis called implicit when it is never the unique place restricting the firing of its output transitions. Hence, an implicit place can be removed without affecting the behavior of the rest of the system, i.e., the language of firing sequences of the original system is preserved [16]. t2 t1 t3 t4t5t6t7t8 t9 t10 t11 t12 t13 p1 p2 p3 p5p6p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p4 p12,4 p5,11 p11,11 Fig. 1. Marked Graph and Marking Structurally Implicit Places, with initial marking m0(p1) = m0(p7) = m0(p9) = m0(p12) = m0(p14) = m0(p15) = 1. Normally, implicit places are determined by the structure but also depend on their initial markings. A place pthat can be made implicit (with a proper initial marking m0(p)) for any initial marking of the rest of the system is called structurally implicit place. A structurally implicit place whose minimal initial marking can be deduced from the marking of other places is said to be marking structurally implicit, more formally: Definition 2.2: [18] Let N=hP∪p, T, P re,P osti. The place pis marking structurally implicit place, iff there exists y≥0, such that C(p, T ) = y·C(P, T ). For strongly connected marked graphs, a marking structurally implicit place pverifies: C(p, ·) = X pj∈π C(pj,·)for ∀π∈ P(te, ts)(2) where te=•p,ts=p•,P(te, ts)is the set of simple paths (i.e., the paths without repeated nodes), from teto ts[6]. It is proved in [6] that, given a marking structurally implicit place p, the minimal initial marking to make p implicit is: m0(p) = mmin 0(p) = min   X pj∈π m0(pj)|π∈ P(te, ts)   (3) Example 2.1: Fig. 1 shows a marked graph. It is easy to observe that from t12 to t4there exist two simple paths, π1= {t12p15t13p16t1p1t2p3t4},π2={t12p15t13p16t1p2t3p4t4}. Therefore, P(t12, t4) = {π1, π2}. With respect to P(t12, t4), the added place p12 4is marking structurally implicit with input transition t12 and output transition t4. Similarly, if considering the path from t5to t11,π3={t5p6t6p7t7p8t8p10t9p11t10p12t11},p511 is the corresponding marking structurally implicit place. There is a loop path from t11,π4={t11, p13, t10, p12, t11}, therefore p11 11 is constructed. In order to compute minimal initial marking to make p12 4 implicit, the sum of markings in each path from t12 to t4is considered. Because the sum of markings of places in π1 is 2, while for π2it is 1, according to (3), the minimal is chosen, so one token should be put into p12 4. Similarly, two tokens in p511, and one token in p11 11. When the net system is considered as continuous, the minimal initial marking of marking structurally implicit places can also be calculated using (3). III. PROBLEM STATEMENT The classical centralized control theory has been proved inefficient for large scale distributed systems, in which the communication delay, time synchronization problems become significant. Therefore distributed or decentralized control is extensively explored in recent decades. In a distributed controlled system, normally a complex dynamic system, the controllers are not centralized in one location, but are distributed in the subsystems, while typically, each controller can only access local resources and limited information from its neighbor subsystems. Under the framework of ContPN, the large scale system is decomposed into subsystems that are modeled with ContPNs and controlled by the local controllers. Each local controller can obtain information from its neighbor subsystems through the interface places and transitions. The problem we deal with is: how to design the control action for each local controller which works independently, and drive the system from initial marking m0to final marking mf. IV. STRUCTURAL DECOMPOSITION OF MARKED GRAPHS In this section we adapt the decomposition methods developed in [6]. The idea is the following: given a strongly connected marked graph N, it is first split into two subnets N1and N2according to a set of places B⊆P, after that the complemented subnets (CN) are derived through adding marking structurally implicit places. Definition 4.1: Let N=hP, T, P re,P ostibe a strongly connected marked graph, B⊆Pis said to be a cut iff there exists subnets Ni=hPi, Ti,P rei,P ostii,i= 1,2, such that: (i) T1∪T2=T,T1∩T2=∅ (i) P1∪P2=P,P1∩P2=B (ii) P1=•T1∪T• 1,P2=•T2∪T• 2 where U=•B∪B•is said to be interface, which is partitioned into U1,U2, such that U1∪U2=U,Ui=Ti∩U. Example 4.1: The non-dotted part in Fig. 2 are the subnets N1,N2obtained from the marked graph in Fig. 1, which is cut by B={p5, p14}, with the interface U= {t4, t5, t11, t12}while U1={t4, t12},U2={t5, t11}. After cutting, the two subsystems N1,N2are independent, because all the constraints from the rest of the system are removed. Therefore different behaviors are introduced. The complemented subnet is obtained after adding marking structurally implicit places as approximations of other parts of the system that are missing. Definition 4.2: Let N=hP, T, P re,P osti be a strongly connected marked graph, Ni= t2 t1 t3 t4t5 t11 t12 t13 p1 p2 p3 p5p6 p14 p15 p16 p4p5,11 p11,11 (a) N1(non-dotted part) and CN1(with dotted part) t4t5t6t7t8 t9 t10 t11 t12 p5p6p7 p8 p9 p10 p11 p12 p13 p14 p12,4 p5,11 (b) N2(non-dotted part) and CN2(with dotted part) Fig. 2. Cutting of marked graph hPi, Ti,P rei,P ostiibe the subnets associated with a cut B. The complemented subnet CNiis obtained from Niby copying transitions in Ujand adding the marking structurally implicit places with respect to the paths P(te, ts) in Nj,te, ts∈Uj,i, j = 1,2, i 6=j. The set of places being added to Niis denoted by IPi. In Fig. 2, the complemented subnet CN 1is obtained after copying U2={t5, t11}and adding IP1={p511, p11 11}to N1, while CN 2is obtained after copying U1={t4, t12}and adding IP2={p12 4}to N2. Notice that cut Band interface Uare shared in both subnets. In order to calculate the initial marking of pesthat makes it implicit, we have to find out the path from teto tssuch that (3) is satisfied. There are some efficient algorithms which can be used, e.g., the algorithm of Floyd-Warshall [1] with a computation complexity of O(|T|3), where |T|is the number of transitions. Sometimes for a complex system, only one cut is not sufficient, because the complemented subsets are still difficult to be handled. Therefore, the above decomposition process need to be executed in multiple hierarchical levels. Fig. 3 presents the complemented subnets obtained after cutting CN2in Fig. 2(b) one more time, with B={p6, p12, p13}. After this two level cutting, the original system is decomposed into three: CN 1,CN 21 and CN 22. It should be noticed that the order of cutting is not important, if the net in Fig. 1 is first cut by B1={p6, p12, p13}, then by B2={p5, p14}, the exactly same subnets are obtained. V. DISTRIBUTED CONTROL OF LARGE SCALE SYSTEMS The distributed structure of a large scale system is obtained using the the decomposition method presented in section IV. In this section we will show that the ON-OFF controller t4t5t6 t10 t11 t12 p5p6 p12 p13 p14 p12,4 p6,10 (a) CN21 t5t6t7t8 t9 t10 t11 p6p7 p9 p10 p11 p12 p13 p11,5 p8 (b) CN22 Fig. 3. Complemented subnets: second cut from CN2 developed in [19] can be applied to each subsystem, leading to the overall final state in minimum-time. A firing count vector ~σ driving the system to mfis said to be minimal if it can not be expressed as the sum of other ones and T-semiflows [19] . An ON-OFF controller for structurally persistent ContP N is proposed in [19]: if ~σ is minimal, for any tj, simply let it ON (with control input equal to 0) before the accumulated flow of tjreaches ~σ(tj), and after that suddenly let it OFF (with control input equal to f(tj)). mfis reached in minimum time using this strategy. Because marked graphs is a subclass of structurally persistent nets, this ON-OFF strategy can be applied. In a distributed system, local controllers can only access limited resources, so the global control law (minimal firing count vector) cannot be obtained directly. In the following, it is shown how it is computed in a distributed way. In the sequel, we will use the following notations: (1) mi 0: the initial marking of CN i, directly projected from m0. For every p∈Pi,mi 0(p) = m0(p), while for every added implicit place p∈IPi,mi 0(p) = mmin 0(p). (2) mi f: the finial marking of CN i, directly projected from mf. For every p∈Pi,mi f(p) = mf(p). Every place p∈IPibelongs to different circuit in CNi, and since CN iis a strongly connected marked graph, each circuit forms a P-semiflow [15], mi f(p)can be easily computed. (3) ~σ: the minimal firing count vector driving Nfrom m0 to mf. (4) ~σi: the firing count vector of CN idirectly projected from ~σ. For every t∈Ti,~σi(t) = ~σ(t). (5) ~σi: the firing count vector driving CN ifrom mi 0to mi f. It is assumed to be minimal when there is no additional specification. A. Decomposition with One Cut The most interesting point of the decomposition approach in section IV is: if we put proper initial markings in the added marking structurally implicit places making them implicit, the projections of reachable markings and firing sequences of the original system are preserved in the complemented subnets [6], i.e., ~σican always be fired in CN iwith initial marking mi 0, and leading to mi f. In the framework of continuous net system, this is also true, and the exactly same proof can be constructed. Definition 5.1: Firing count vectors ~σ1and ~σ2are said to be compatible if ~σ1(t) = ~σ2(t),∀t∈U. Definition 5.2: Let ~σ1and ~σ2be compatible firing count vectors. Operator ⊕:hR|T1| ≥0,R|T2| ≥0i → R|T1∪T2| ≥0is defined to be the merge, such that, ~σ12 =~σ1⊕~σ2,∀t∈Ti,~σ12(t) = ~σi(t),i= 1,2. Example 5.1: Let us consider the marked graph in Fig. 1 and its complemented subnets obtained using cut B= {p5, p14}, and interface U={t4, t5, t11, t12}in Fig. 2. Table I shows their initial, final markings and the firing count vectors. The initial markings of the added marking structurally implicit places are computed from (3), while their finial markings are m1 f(p511) = 2.1,m1 f(p11 11) = 1, and m2 f(p12 4) = 1.5. We can notice that the firing count vector of CNiprojected from ~σ may be not minimal, e.g., in CN 1, the minimal vector is ~σ1= [1.1 1.7 0.9 0.5 0.1 0 1 1.5]T, while the projection ~σ1=~σ1+0.6·1. For sure ~σ1is fireable in CN 1since 1is the T-semiflow. TABLE I MARKINGS AND FIRING COUNT VECTORS Pm0m1 0m2 0T~σ ~σ1~σ2 (mf) (m1 f) (m2 f) (~σ1) (~σ2) p11(0.4) 1(0.4) t11.7 1.7(1.1) p20(0.2) 0(0.2) t22.3 2.3(1.7) p30(1.2) 0(1.2) t31.5 1.5(0.9) p40(0.4) 0(0.4) t41.1 1.1(0.5) 1.1(1.1) p50(0.4) 0(0.4) 0(0.4) t50.7 0.7(0.1) 0.7(0.7) p60(0.2) 0(0.2) t60.5 0.5(0.5) p71(0.5) 1(0.5) t71 1 (1 ) p80(0.4) 0(0.4) t80.6 0.6(0.6) p91(0.6) 1(0.6) t90.5 0.5(0.5) p10 0(0.1) 0(0.1) t10 0 0 (0 ) p11 0(0.5) 0(0.5) t11 0.6 0.6(0) 0.6(0.6) p12 1(0.4) 1(0.4) t12 1.6 1.6(1) 1.6(1.6) p13 0(0.6) 0(0.6) t13 2.1 2.1(1.5) p14 1(0) 1(0) 1(0) p15 1(0.5) 1(0.5) p16 0(0.4) 0(0.4) p5,11 2(2.1) p11,11 1(1) p12,41(1.5) Until now the time has been ignored. If all the transition are controllable, a marking mis reachable in the timed model, it is also reachable in the untimed one; while if a marking mis reachable in the untimed model, then it is asymptotically reachable in the timed one [12]. Therefore, similar results can be easily extended to ContP N . In particular, the projections of firing count vectors and reachable markings of the original system are preserved in the complemented subnets. In the following parts, we assume the system is live. If the minimal firing count vectors of CN1and CN2are compatible, we will prove the merged vector is firable in N. In the case they are not compatible, like ~σ1and ~σ2in Ex. 5.1 (because ∀t∈U, ~σ1(t)6=~σ2(t)), a T-semiflow can be added to make them compatible. Finally, the merged vector obtained is actually equal to ~σ. Proposition 5.1: Let hN,m0ibe a live marked graph, with cut Band corresponding interface U. Let ~σibe the firing count vector driving CNifrom mi 0to mi f,i= 1,2. If ~σ1,~σ2are compatible, then there exists a firing sequence σ12 with ~σ12 =~σ1⊕~σ2that can be fired in Nmfis reached. Proof: Since ~σ1and ~σ2are compatible, all the common transitions (t∈U) have the same firing counts. On the other side Bare the common places of CN 1and CN 2and •B∪ B•=U, therefore, m0+C·~σ12 =m0+C·(~σ1⊕~σ2) = mf Because the system is a live marked graph, there always exists a sequence σ12 can be fired. Property 5.1: Let hN,m0ibe a live marked graph, with cut Band corresponding interface U. There exists k≥0, such that ~σ = (k·1+~σi)⊕~σj,i, j = 1,2, i 6=j. Proof: Since ~σiis a fireable vector in CN ireaching mi f, and ~σiis the corresponding minimal firing count vector, considering CNiis live marked graph with the unit vector as the unique T-semiflow, we have ~σi=~σi+αi·1,αi≥ 0, i = 1,2, without loss of generality, assume α1≤α2. In particular, for any t∈U,~σi(t) = ~σi(t) + αi, because ~σ1(t) = ~σ2(t) = ~σ(t),~σ1(t)−~σ2(t) = α2−α1=k≥0. Therefore ~σ1and ~σ2+k·1are compatible, according to Proposition 5.1 ~σ12 = (k·1+~σ2)⊕~σ1is fireable in CN and mfis reached. Since ~σ1,~σ2are minimal, ~σ12 is also minimal. Because the minimal firing count vector is unique in live marked graph [19], ~σ12 =~σ. Example 5.2: In Ex. 5.1, ~σ1and ~σ2are not compatible, with difference k= 0.6(i.e., ∀t∈U, ~σ2(t)−~σ1(t) = 0.6). Clearly, after adding 0.6·1to ~σ1, they can be merged, and ~σ is obtained, i.e., ~σ = (~σ1+ 0.6·1)⊕~σ2. Notice that in the example, ~σ1is different from the direct projection from ~σ, while ~σ2is equal to ~σ2. In fact, if ~σ = (k·1+~σi)⊕~σj, then ~σ(t) = ~σj(t), t ∈Tj. B. Decomposition with Hierarchical Cut Let us consider the case when the system is decomposed hierarchically. When cutting a net into two parts CN1,CN2, and suppose ~σ = (k1·1+~σ1)⊕~σ2, then ~σ(t) = ~σ2(t), t ∈ T2. If cutting CN 2one more time into CN 21 and CN 22, and suppose ~σ2= (k2·1+~σ21)⊕~σ22 , then ~σ2(t) = ~σ22(t),∀t∈ T22. Therefore we have ~σ(t) = ~σ22(t),∀t∈T22. The same result can be obtained when CN 22 is cut again, hence it can be concluded: there always exists at least one complemented subnet CNi, such that ~σ(t) = ~σi(t),∀t∈Ti, and CN iis said to be critical. Two complemented subnets are neighbors if they share a cut. Because every time we split one net into two, each subnets has at least one neighbor. We will prove it is possible to make pairs of minimal firing vectors of neighbors to be compatible and obtain ~σ after merging all of them. Proposition 5.2: Let hN,m0ibe a live marked graph that is decomposed into nsubnets. Assuming CN q,1≤q≤n is a critical complemented subnet, then there exist xi, i = 1,2, ..., n such that: ~σ = n M i=1 (~σi+xi·1)(4) and if i=q, xi= 0, else xi≥0. Proof: Since all the complemented subnets are still live marked graphs, ~σi+xi·1is also fireable in CNi. For any two neighbor subnets CNi,CNj,xi, xj≥0can be found such that ~σi+xi·1and ~σj+xj·1are compatible. According to Proposition 5.1, (~σi+xi·1)⊕(~σj+xj·1)is fireable in the net composed by CN iand CN j. Therefore after merging all the firing count vectors, ~σ′=Ln i=1(~σi+xi·1)is obtained, which can be fired in N, and reach the final marking. If every xi>0,~σ′is not a minimal firing count vector, then certain amount of T-semiflow can be subtracted from ~σ′ until ~σ =~σ′. Since CNqis critical, xq= 0. Let us observe that it is possible to have more than one critical subnet, but considering there is unique minimal firing count vector in a live marked graph, given any one of the critical subnets, the same ~σ is constructed. Example 5.3: Let’s examine the marked graph in Fig. 1 with the initial and final markings as listed in Table. I. After cutting with B1={p5, p14}and B2={p6, p12, p13}, we get three complemented subnets CN1(Fig. 2(a)), CN 21,CN 22 (Fig. 3). CN 1and CN 21 are neighbors sharing cutting B1, CN 21 and CN 22 are neighbors sharing B2. In Table II is the minimal firing count vectors for reaching corresponding final markings. It is obtained: ~σ = (~σ1+ 0.6·1)⊕~σ2⊕~σ3 Here CN 21,CN 22 are critical subnets. The rest of this section devotes to design an effective algorithm to search a critical subnet, and calculating corresponding xito generate ~σ. In order to make it more understandable, let us construct a graph G=hV, W ito depict the relations among complemented subnets. Each node v∈Vrepresents a subnet, there are arcs between viand vjif the corresponding subnets CNi and CN jare neighbors. The weight of the arc from vito vjis w(vi, vj) = ~σi(t)−~σj(t), t ∈U, negative weight is also allowed here. So in the corresponding graph G(Fig. 4) the weight w(v2, v1) = 0.6,w(v1, v2) = −0.6, while TABLE II MINIMAL FIRING COUNT VECTORS T~σ(N)~σ1(CN 1)~σ2(CN21)~σ3(CN 22) t11.7 1.1 t22.3 1.7 t31.5 0.9 t41.1 0.5 1.1 t50.7 0.1 0.7 0.7 t60.5 0.5 0.5 t71 1 t80.6 0.6 t90.5 0.5 t10 0 0 0 t11 0.6 0 0.6 0.6 t12 1.6 1 1.6 t13 2.1 1.5 v3 v2 v1 - 0.6 0.6 0 0 Fig. 4. The graph G=hV, W iconstructed from the three complemented subnets in Ex. 5.3 w(v2, v3) = w(v3, v2) = 0. Denote W(vi, vj)the sum of the weights on the simple path from vito vj. Since a cut splits a net into two subnets, in graph Gthere only exists one directed simple path from nodes vito vj (also from vj, vi), and obviously W(vi, vj) = −W(vj, vi). It can be observed that, the sum of weight in the path hvi, vjireflects the relative difference of ~σito ~σj. In Ex. 5.3, the relative difference of v3to v2is w(v3, v2) = 0, while the one of v3to v1is w(v3, v2) + w(v2, v1) = 0.6. Obviously we have ~σ = (~σ1+ 0.6·1)⊕(~σ2+ 0 ·1)⊕~σ3. Actually, the non negative value xiin (4) is equal to W(vq, vi). Property 5.2: If for any node vi∈V,W(vq, vi)≥0, then CNqis a critical subnet. Proof: If W(vq, vi)≥0, then let xi=W(vq, vi),~σ can be constructed. Therefore xq=W(vq, vq) = 0,CNqis critical. Algorithm 1 shows how to search a critial subnet based on the graph constructed. In the beginning all the nodes are labeled as new, then every time a new labeled node, denoted by viis chosen, the relative differences from vito others nodes vj,W(vi, vj)is calculated (if it is not done before). If it is negative then viis not critical and labeled as old. If it is positive then vjis not critical because W(vj, vi) must be negative, and we don’t need to check vjin the future. When a node with all relative differences non-negative is found, or there is only one node left which is labeled as new, the program finishes. When calculating the sum of weights, of course the intermediate value that has been calculated before should be reused. In the worst case, the computing complexity is O(n(n−1) 2), where nis the number of complemented subnets. Algorithm 1 Search a critical subnet Input: G=hV, W i Output: A node vq∈V 1: Label all the nodes in Vas new; 2: while more than one node in Vis labeled as new do 3: Choose a node vifrom Vwhich is labeled as new; 4: for j = 1 to n do 5: if W(j, i)has not been calculated then 6: calculate W(i, j); 7: if W(i, j)>0then 8: label vjas old; 9: else if W(i, j)<0then 10: label vias old; 11: break; 12: end if 13: end if 14: end for 15: if j=nand viis labeled as new then 16: return vi; 17: end if 18: end while 19: return The last node in Vthat is labeled as new We will assume there is a supervisory controller in our system structure, whose work is to search a critical subnet, and send the relative difference xito the local controller of CN i. The local controller receives this value then updates the local control law. Algorithm 2, 3 are for supervisory controller, local controller respectively. Algorithm 2 Supervisory Controller Input: ~σi Output: x 1: Construct the graph G=hV, W i; 2: Find out a critical subnet CN qusing Algorithm 1; 3: Compute x(i): the relative difference of CNqto CN i; 4: Send x(i)to subnet CNi,i= 1,2, ..., n; VI. CASE STUDY Let us consider the ContP N system in Fig. 5 which models a manufacturing system with three types of product lines which are assembled for one final product. The system is cut into four subsystems through the buffer places (B1= {p1, p12},B2={p13, p23},B3={p24, p38}) of each product line, as shown in Fig. 6, where p8,31,p27,31,p1,7, p9,15 and p16,24 are the added marking structurally implicit places. Algorithm 3 Local Controller i Input: CNi,mi 0,mi f Output: ~σi 1: Calculate the minimal firing count ~σito reach mi f; 2: Send ~σito the supervisory controller; 3: Receive x(i)from the supervisory controller; 4: Update ~σito ~σi+x(i)·1; 5: Apply ON-OFF control; 3 4 3 5 p1p2p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 p20 p21 p22 p23 p24 p25 p26 p27 p28 p29 p30 p31 p32 p33 p34 p35 p36 p37 p38 p39 p40 p41 p42 p43 p44 p45 p46 p47 p48 p49 p50 t1t2 t3t4t5t6t7 t8 t9t10 t11 t13 t14 t15 t12 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t27 t28 t29 t30 t31 t32 Fig. 5. A manufacturing system model Assuming the initial and desired final marking are listed in Table III. The corresponding minimal firing count vector are easy to calculate, shown in Table IV. TABLE III INITIAL AND FINAL MARKINGS CN 1CN 2CN 3CN 4 Pm0Pm0Pm0Pm0 (mf) (mf) (mf) (mf) p13(0.6) p13 4(1.9) p24 3(0.3) p13(0.6) p20(0.4) p14 0(0.3) p25 0(0.2) p12 0(0.4) p30(0.8) p15 0(0.9) p26 0(0.7) p13 4(1.9) p41(0.2) p16 1(0.1) p27 2(0.5) p23 0(0.3) p52(0.5) p17 2(0.5) p28 0(0.8) p24 3(0.3) p60(0.7) p18 0(0.6) p29 0(0.9) p38 0(0.2) p70(0.8) p19 0(0.9) p30 1(0.1) p39 0(0.6) p81(0.2) p20 2(0.5) p31 0(0.6) p40 1(0.8) p90(0.7) p21 0(0.6) p32 2(0.5) p41 0(0.2) p10 2(0.5) p22 0(0.3) p33 0(0.9) p42 0(0.2) p11 0(0.4) p23 0(0.3) p34 0(0.6) p43 0(0.4) p12 0(0.4) p35 1(0.1) p44 0(0.8) p36 2(0.5) p45 1(0.2) p37 0(0.2) p46 0(1.0) p38 0(0.2) p47 2(1.0) p48 5(0.4) p49 3(1.5) p50 0(1.5) p8,31 6(4.2) p8,31 6(4.2) p27,31 5(2.6) p1,70(3.8) p9,15 0(3.6) p16,24 0(4.9) Based on Table. IV, graph G(Fig. 7) is constructed, in which CN 4is neighbor to all the other subnets with weight w(v4, v1) = w(v4, v2) = 2.8,w(v4, v3) = 2.2. If applying Algorithm 1, CN 4is selected. The relative differences of CN4to all the other subnets can be computed, which in this case is very straightforward: x1=x2= 2.8,x3= 2.2. Therefor the minimal firing count vector is generated as: ~σ = (~σ1+ 2.8·1)⊕(~σ2+ 2.8·1)⊕ (~σ3+ 2.2·1)⊕~σ4. Then, for instance, in order to control the transitions in CN 1, the ON-OFF can be applied with control law ~σ′ 1=~σ1+ 2.8·1, i.e., transition tj∈T1is ON when the accumulated flow of tjis less than ~σ′ 1(tj), else tjis 6 3 p1p2p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 t1t2 t3t4t5t6t7 t31 t8 p8,31 (a) CN 1 4 p13 p14 p15 p16 p18 p19 p21 p22 p23 t9t10 t11 t13 t14 t15 t12 t8 t31 p8,31 6 (b) CN 2 5 3 p24 p25 p26 p28 p29 p30 p31 p33 p34 p35 p37 p38 t16 t17 t18 t19 t20 t21 t22 t23 t24 t27 t31 p27,31 (c) CN 3 5 p12 p23 p39 p40 p41 p42 t8 t25 t26 p38 p43 p44 p45 p46 p47 p48 p49 p50 t27 t28 t29 t30 t31 t32 p1t1 p13 t9 t7 t15 p24 t16 t24 p1,7 p9,15 p16,24 (d) CN 4 Fig. 6. Complemented subnets from the system model in Fig. 5, with cut B1={p1, p12},B2={p13 , p23 },B3={p24 , p38 } v3 v2 v1 -2.2 2.2 v4 2.8 -2.8 -2.8 2.8 Fig. 7. The graph constructed from Table. IV OFF. The global final marking is reached in 13.24 time units, which is minimal time as what has been proved in [19]. VII. CONCLUSIONS Distributed control could be a solutions of controlling systems that are too complex to handle with centralized controller or the deployments of systems are physically distributed. This work focus on distributed control of large scale systems that are modeled with timed continuous Petri nets, aiming to drive the system from initial marking to desired final marking. The model is first decomposed into subnets with sets of places, then making structurally implicit TABLE IV MINIMAL FIRING COUNT VECTORS CN 1CN 2CN 3CN 4 T~σ1T~σ2T~σ3T~σ4 t14.2t80t16 5.1t17 t23.8t93.9t17 4.9t73.2 t33t10 3.6t18 4.2t82.8 t42.3t11 2.7t19 3.4t96.7 t51.5t12 2.1t20 2.5t15 3.1 t60.8t13 1.2t21 1.9t16 7.3 t70.4t14 0.6t22 1t24 2.4 t80t15 0.3t23 0.4t25 2.2 t31 1.8t31 1.8t24 0.2t26 2.4 t27 0t27 2.2 t31 2.4t28 1.8 t29 1 t30 0 t31 4.6 t32 1.5 places are introduced to obtain complemented subnets and control laws can be computed in a distributed way. After that, ON-OFF control is applied in each subnet, and final marking is reached in minimum time. Since the obtained subnets depend on the selection of cuts, an improper cut may lead to subnets with big size which are still difficult to handle. Therefore a qualified automatic cutting algorithm is worth to be investigated. In principle, a proper cut should generate subnets with similar size and the corresponding set of interface transitions should be small. Another future work will be applying this control method to more general nets structures, for example structurally persistent nets, where the decomposition method and approximation strategy should be reconsidered. REFERENCES [1] A. V Aho, J. D Ullman, and J. E Hopcroft. Data Structures and Algorithms. Addison Wesley, 1983. [2] A. Amrah, N. Zerhouni, and A. El Moudni. On the control of manufacturing lines modelled by controlled continuous Petri nets. Journal of Systems Science, 29(2):127–137, 1998. [3] H. Apaydin-Ozkan, J. Julvez, C. Mahulea, and M. Silva. A Control Method for Timed Distributed Continuous Petri nets. In 2010 American Control Conference, Baltimore, USA, June 2010. to appear. [4] F. Balduzzi, A. Giua, and C. Seatzu. Hybrid Control of Production Systems with Local Optimization. In Proc. of the 7th IEEE Int. Conf. on Emerging Technologies and Factory Automation, pages 1531–1540, Barcelona, Spain, October 1999. [5] J. Campos, G. Chiola, J. M. Colom, and M. Silva. Properties and Performance Bounds for Timed Marked Graphs. IEEE Transactions on Circuits and Systems I Fundamental Theory and Applications, 39(5):386–401, 1992. [6] J. Campos, J.M. Colom, H. Jungnitz, and M. Silva. Approximate Throughput Computation of Stochastic Marked Graphs. Springer, 1995. [7] R. David and H.Alla. Autonomous and timed continuous Petri nets. Springer, Berlin, 2010. [8] X. Guan and L. E. Holloway. Control of Distributed Discrete Event Systems Modeled as Petri Nets. In Proceedings of the American Control Conference, pages 2342–2347, Albuquerque, New Mexico, June 1997. [9] L. E. Holloway, B. H. Krogh, and A. Giua. A Survey of Petri Net Methods for Controlled Discrete Event Systems. Discrete Event Dynamic Systems, 7(2):151–190, 1997. [10] J. J´ ulvez, L. Recalde, and M. Silva. On reachability in autonomous continuous Petri net systems. In G. Goos, J. Hartmanis, and J. van Leeuwen, editors, Applications and Theory of Petri Nets 2003, volume 2679, pages 221–240, Eindhoven, The Netherlands, June 2003. Springer Berlin / Heidelberg. [11] P. Krishnan. Distributed timed automata. In WDS’99, Workshop on Distributed Systems (A satellite workshop to FCT’99), volume 28 of Electronic Notes in Theoretical Computer Science, pages 5 – 21, 2000. [12] C. Mahulea, A. Ramirez, L. Recalde, and M.Silva. Steady state control reference and token conservation laws in continuous petri net systems. IEEE Transactions on Automation Science and Engineering, 5(2):307– 320, April 2008. [13] C. Mahulea, L. Recalde, and M. Silva. Basic Server Semantics and Performance Monotonicity of Continuous Petri Nets. Discrete Event Dynamic Systems: Theory and Applications, 19(2):189 – 212, June 2009. [14] R. P. Moreno, D. Tardioli, and J.l.V. Salcedo. Distributed Implementation of Discrete Event Control Systems based on Petri nets. In ISIE08: IEEE International Symposium on Industrial Electronics, pages 1738– 1745, June 2008. [15] T. Murata. Petri nets: properties, analysis and applications. Proceedings of the IEEE, 77 No:4:541–580, 1989. [16] M. Silva. Las Redes de Petri en La Autom´ atica y la Inform´ atica. Editorial AC, Madrid, 1985. [17] M. Silva and L. Recalde. On fluidification of Petri net models: from discrete to hybrid and continuous models. Annual Reviews in Control, 28(2):253–266, 2004. [18] M. Silva, E. Teruel, and J.M. Colom. Linear algebraic and linear programming techniques for the analysis of P/T net systems. LCNS, 1:309–373, 1998. [19] L. Wang, C. Mahulea, J. J´ ulvez, and M. Silva. Minimum-time Control for Structurally Persistent Continuous Petri Nets. In 49th IEEE Conference on Decision and Control, Atlanta, Georgia USA, December 2010. to appear. [20] G. Yasuda. Design and implementation of Petri net based distributed control architecture for robotic manufacturing systems. In MICAI’07: Proceedings of the artificial intelligence 6th Mexican international conference on Advances in artificial intelligence, pages 1151–1161, Berlin, Heidelberg, 2007. Springer-Verlag.