Repositorio Institucional de Documentos

2013 57 Liewei Wang On Minimum-time Control of Continuous Petri nets: Centralized and Decentralized Perspectives Departamento Informática e Ingeniería de Sistemas Director/es Silva Suárez, Manuel Mahulea, Cristian Florentín Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Liewei Wang ON MINIMUM-TIME CONTROL OF CONTINUOUS PETRI NETS: CENTRALIZED AND DECENTRALIZED PERSPECTIVES Director/es Informática e Ingeniería de Sistemas Silva Suárez, Manuel Mahuelea Cristian, Florentín Tesis Doctoral Autor 2013 Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA Departamento Director/es Director/es Tesis Doctoral Autor Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es UNIVERSIDAD DE ZARAGOZA On Minimum-time Control of Continuous Petri nets: Centralized and Decentralized Perspectives Liewei WANG Ph.D. Thesis Advisor: Manuel Silva Su´arez and Cristian Mahulea Departamento de Inform´atica e Ingenier´ıa de Sistemas Centro Polit´ecnico Superior Universidad de Zaragoza May 2013 Resumen Muchos sistemas artificales, como los sistemas de manufactura, de log´ıstica, de telecomunicaciones o de tr´afico, pueden ser vistos “de manera natural” como Sistemas Din´amicos de Eventos Discretos (DEDS). Desafortunadamente, cuando tienen grandes poblaciones, estos sistemas pueden sufrir del cl´asico problema de la explosi´on de estados. Con la intenci´on de evitar este problema, se pueden aplicar t´ecnicas de fluidificaci´on, obteniendo una relajaci´on fluida del modelo original discreto. Las redes de Petri continuas (CPNs) son una aproximaci´on fluida de las redes de Petri discretas, un conocido formalismo para los DEDS. Una ventaja clave del empleo de las CPNs es que, a menudo, llevan a una substancial reduccin del coste computacional. Esta tesis se centra en el control de Redes de Petri continuas temporizadas (TCPNs), donde las transiciones tienen una interpretaci´on temporal asociada. Se asume que los sistemas siguen una sem´antica de servidores infinitos (velocidad variable) y que las acciones de control aplicables son la disminuci´on de la velocidad del disparo de las transiciones. Se consideran dos interesantes problemas de control en esta tesis: 1)control del marcado objetivo, donde el objetivo es conducir el sistema (tan r´apido como sea posible) desde un estado inicial a un estado final deseado, y es similar al problema de control set-point para cualquier sistema de estado continuo; 2)control del flujo ´optimo, donde el objetivo es conducir el sistema a un flujo ´optimo sin conocimiento a priori del estado final. En particular, estamos interesados en alcanzar el flujo m´aximo tan r´apido como sea posible, lo cual suele ser deseable en la mayor´ıa de sistemas prcticos. El problema de control del marcado objetivo se considera desde las perspectivas centralizada y descentralizada. Proponemos varios controladores centralizados en tiempo m´ınimo, y todos ellos est´an basados en una estrategia ON/OFF. Para algunas subclases, como las redes Choice-Free (CF), se garantiza la evoluci´on en tiempo m´ınimo; mientras que para redes generales, los controladores propuestos son heur´ısticos. Respecto del problema de control descentralizado, proponemos en primer lugar un controlador descentralizado en tiempo m´ınimo para redes CF. Para redes generales, proponemos una aproximaci´on distribuida del m´etodo Model Predictive Control (MPC); sin embargo en este m´etodo no se considera evoluci´on en tiempo m´ınimo. El problema de control de flujo ´optimo (en nuestro caso, flujo m´aximo) en tiempo m´ınimo se considera para redes CF. Proponemos un algoritmo heur´ıstico en el que calculamos los “mejores” firing count vectors que llevan al sistema al flujo i m´aximo, y aplicamos una estrategia de disparo ON/OFF. Tambi´en demostramos que, debido a que las redes CF son persistentes, podemos reducir el tiempo que tarda en alcanzar el flujo m´aximo con algunos disparos adicionales. Los m´etodos de control propuestos se han implementado e integrado en una herramienta para Redes de Petri h´ıbridas basada en Matlab, llamada SimHPN. Abstract Many man-made systems, such as manufacturing, logistics, telecommunication or traffic systems, can be “naturally” viewed as Discrete Event Dynamic Systems (DEDS). Nevertheless, in the case of large populations they may suffer from the classical state explosion problem. In order to overcome this problem, fluidization can be applied, obtaining the fluid relaxation of the original discrete model. Continuous Petri nets (CPNs) are a fluid approximation of discrete Petri nets (PNs), a well known formalism for DEDS. One key benefit of using CPNs is that, most frequently, it leads to a substantial reduction in the computational costs. In this thesis we focus on the control of timed continuous Petri nets (TCPNs), in which time interpretations are associated to transitions. We assume that net systems are under infinite server semantics (variable speed) and control actions are applied to slow down the firing of transitions. We consider two interesting control problems in this thesis: 1) target marking control, where the objective is to drive the system (as fast as possible) from an initial state to a desired final state, and it is similar to the set-point control problem in a general continuous-state system; 2) optimal flow control, in which the objective is to drive the system to an optimal flow, without a priori knowledge of a specific final state. In particular, we are interested in reaching as fast as possible the maximal flow, what is frequently desirable in practical systems. The target marking control problem is considered in both centralized and decentralized settings. We propose several minimum-time centralized controllers and all of them are based on an ON/OFF strategy. For some subclasses like Choice-Free (CF) nets, minimum-time evolution is guaranteed; for general nets, the proposed controllers are heuristics. Regarding the decentralized control, we first propose a minimum-time decentralized controller for CF nets. Then, for general nets, we propose a distributed Model Predictive Control (MPC) approach; however, in this method, minimum-time evolution is not considered. The minimum-time optimal flow (in our case, the maximal flow) control problem is considered for CF nets. We propose a heuristic algorithm, in which we compute the “best” firing count vectors bringing the system to the maximal flow and an ON/OFF firing strategy is applied. We also show that because of the persistency of CF nets, we can further reduce the time spent to reach the maximal flow by means of some additional firings. The proposed control methods are implemented and integrated into a Matlab based toolbox for hybrid PN systems, called, SimHPN. iii iv Contents 1 Introduction 1 2 Continuous Petri nets: Basic Concepts and Notations 7 2.1 (Discrete) Petri nets and the state explosion problem . . . . . . . . . 8 2.2 Autonomous (untimed) continuous Petri nets . . . . . . . . . . . . . 9 2.2.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 Petri nets subclasses . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.3 Basic structural concepts . . . . . . . . . . . . . . . . . . . . 11 2.2.4 Reachability and lim-reachability . . . . . . . . . . . . . . . . 12 2.2.5 Boundedness . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2.6 Liveness and deadlock-freeness . . . . . . . . . . . . . . . . . 14 2.2.7 Implicit places and structurally implicit places . . . . . . . . 15 2.3 Timed continuous Petri nets . . . . . . . . . . . . . . . . . . . . . . . 16 2.3.1 Conceptual framework and server semantics . . . . . . . . . . 16 2.3.2 Timed models versus untimed models . . . . . . . . . . . . . 18 2.3.3 Performance bounds under infinite server semantics . . . . . 19 2.3.4 Parametric optimization under infinite server semantics . . . 20 2.3.5 Approximation to the discrete systems . . . . . . . . . . . . . 21 2.4 An example: a kanban-like manufacturing system . . . . . . . . . . . 24 3 Control of Continuous Petri nets 31 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.1 Controlling the systems . . . . . . . . . . . . . . . . . . . . . 32 3.1.2 Target marking control problem . . . . . . . . . . . . . . . . 32 3.1.3 Optimal flow control problem . . . . . . . . . . . . . . . . . . 34 3.2 Computing the initial and desired final states . . . . . . . . . . . . . 34 3.2.1 About m0............................. 34 3.2.2 About the desired/final state . . . . . . . . . . . . . . . . . . 35 3.3 Controllability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Previous centralized control methods . . . . . . . . . . . . . . . . . . 38 3.4.1 Initial comparisons . . . . . . . . . . . . . . . . . . . . . . . . 42 3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 v Chapter 1. Introduction minimum-time. We first propose an ON/OFF controller for Choice-Free (CF) net systems (Section 4.2) and we prove that it ensures a minimum-time time evolution. The idea is rather simple: let all the transitions fire as fast as possible until their upper bounds, given by the minimal firing count vector (that can be computed in polynomial time), are reached; then simply block them. Nevertheless, this standard ON/OFF strategy cannot be applied to general net systems because convergence to the final state is not guaranteed; some illustrative examples are given in Section 4.3. Several extensions (ON/OFF+, B-ON/OFF and MPC-ON/OFF) are proposed in Section 4.4, adding more adequate strategies to solve the conflicts that appear in general net systems; all the extended methods are heuristics for the minimumtime control. A main advantage of the proposed methods is the low computational complexity; meanwhile, reasonable time spent for reaching the final state can be obtained. The distributed physical deployment of a large scale system often makes it impossible to implement a centralized controller, considering the high communication costs, time delays, etc. In the context of target marking control problem of TCPNs, few contributions have considered the decentralized setting. For example, [4] considered continuous models composed by several subsystems that communicate through buffers (modelled by places). This method assumes that all the subsystems and the global one should be mono-T-semiflow. In Chapter 5 we propose a decentralized control method for CF nets. We assume a large scale system modelled by TCPNs that can be cut through a set of buffer places, obtaining disconnected subsystems. However, these disconnected subsystems may exhibit different behaviors (firing sequences) to the original system. To overcome this problem, we propose several reduction rules to obtain abstractions of the missing parts of subsystems. The abstractions are used to construct the complemented subsystems that preserve the behaviors of the original system. Then, local control laws are computed separately in subsystems. Finally, we present a simple algorithm to coordinate the local control laws that may be not globally admissible. Because the considered nets are CF, we can implement the ON/OFF controller independently and drive each subsystem to its final state in minimum-time. For a general net system, the previous decentralized control methods may be no longer applicable: the method proposed in Chapter 5 is only for CF nets; the approach proposed in [4] requires (sub-)systems to be mono-T-semiflow. In Chapter 6 we propose an approach based on Distributed Model Predictive Control (DMPC). We first present a centralized MPC controller, in which the stability—a key issue in MPC based approaches—is ensured by forcing the state evolution inside an interior convex subnet of the reachability space. Recall that in another (centralized) MPC control approach for TCPNs proposed in [64], the states are constrained to be on a straight line trajectory from the initial state to the final one; however, for our method this is not mandatory. Later, we apply the proposed MPC controller to a distributed setting. Similarly to the previous methods, we assume a (large scale) TCPN that is cut into subsystems through sets of buffer places. Then we focus on driving all the subsystems to their final states and keeping all the buffer places in legal non4 negative states. In the proposed distributed MPC algorithm, each local controller can access informations (states and structures) of its local subsystem and the buffers connecting to it; no global coordinator is required, and communications among local controllers only occur inside neighborhoods, in which the data transmitted is very low. However, minimum-time evolution is not considered in this method. In Chapter 7 we are interested in reaching the maximal flow of TCPNs in minimum-time. As we have already mentioned, the main challenge of this problem is the fact that we usually cannot uniquely determine a final state with the maximal flow and obviously, the time varies significantly on which one is chosen. Even for Marked Graphs (MG, a subclass of CF nets), the problem becomes complicated when minimum-time evolution is considered, in particular, non-monotonicity appears with respect to the firing count vectors that drive the system to the maximal flow. We propose a heuristic algorithm for CF nets. The idea is to compute the “best” firing counter vector (in terms of the time spent on the trajectory) driving the system to the maximal flow, according to an estimation of the number of time steps based on the current state and flow at each time step; then an ON/OFF firing strategy is applied. Moreover, because of the persistency of CF nets, we can further reduce the time by employing some additional firings. The main contributions of this thesis can be briefly listed as the follows: •A simple and efficient minimum-time controller for the target marking control problem of CF net systems (Chapter 4, the primary results are published in [104]). •Several heuristic minimum-time control methods for the target marking control problem of general net systems (Chapter 4, the primary results are published in [106]). •A decentralized minimum-time controller for the target marking control problem of CF net systems (Chapter 5, the primary results are published in [105, 103]). •A distributed MPC approach for the target marking control problem of general net systems (Chapter 6, the primary results are in [107] ) •Heuristic methods for the minimum-time (maximal) flow control problem of CF nets (Chapter 7, the primary results are published in [108]) •The proposed control methods are implemented and integrated into a Matlab based toolbox for hybrid PN systems, called, SimHPN [48]. The organization of the thesis is as follows: In Chapter 2 we briefly recall the basic concepts and important technical results of continuous PNs; in Chapter 3 more details about the control of continuous PNs, which is the main topic of the thesis, are introduced. In Chapter 4 we propose centralized control methods for the target marking control problem, with the objective of minimizing the time spent 5 Chapter 1. Introduction on the trajectory. Some proposed methods are heuristics and all of them are based on the ON/OFF strategy. Chapter 5 and 6 study decentralized control methods for the target marking control problem: in Chapter 5 we propose a decentralized minimum-time controller for CF net systems; in Chapter 6, we propose a distributed MPC approach for general net systems. Chapter 7 focuses on the (minimum-time) optimal flow control problem, and heuristic algorithms are proposed for CF nets. In Chapter 8 we carry out several case studies to illustrate the proposed (target marking) control methods: the first three examples focus on the centralized control methods and the last one considers the distributed control. Some final remarks are in Chapter 9. 6 Chapter 2 Continuous Petri nets: Basic Concepts and Notations In this chapter, we introduce some basic definitions, concepts and techniques about continuous Petri nets, both for the autonomous (untimed fully non-deterministic) model and the timed model. Without time interpretation, the autonomous model can be used to analyze some properties like boundedness, deadlock-freeness, liveness, etc. Notice that, as a “coarse” model, some important properties of the original discrete model may be lost after fluidization. Therefore, during the presentation of the technical results related to continuous Petri nets, we will compare with those related to the discrete ones, trying to clarify the “bridges” and “gaps” between them. Timed models are often used in performance evaluation of, for example, manufacturing systems. Among mostly used firing server semantics, we focus on infinite server semantics (variable firing speed), since it usually provides better approximations to discrete systems under some general conditions. Finally, we present a case study to illustrate the concepts and techniques that have been introduced in this chapter. 7 Chapter 2. Continuous Petri nets: Basic Concepts and Notations 2.1 (Discrete) Petri nets and the state explosion problem Petri nets are a modelling paradigm with several “related” formalisms. In the sequel, we consider Place/Transition (P/T) nets, which is most usually found in the literature. PNs enjoy a bipartite structure, which is also considered in other DEDS formalisms as queueing networks or Forrester Diagrams (see [87] for a broad review). They can directly represent a production/consume logic that frequently appears in practical systems as manufacturing systems, logistics, transportation systems. In this section we introduce the basic definitions of discrete PNs, and illustrate its principal limitation—the state explosion problem. Definition 2.1.1. A Petri net (PN) system is a pair hN ,M0i, in which N= hP, T, P re,P ostiis a net structure, where: •P and T are the disjoint, finite sets of places and transitions respectively. •P re,P ost ∈N|P|×|T|are the pre and post incidence matrices. •M0∈N|P|is the initial marking (state). Let pi,i= 1,...,|P|and tj, j = 1,...,|T|denote the places and transitions. P re[pi, tj] = w1and P ost[pi, tj] = w2indicate the connections between places and transitions: if w1>0 there is a arc from pito tjwith w1as the weight; if w2>0 there is a arc from tjto p2with w2as the weight. For any v∈P∪T, the sets of its input and output nodes are denoted as •vand v•, respectively. These definitions can be naturally extended to sets of nodes. Each place can contain a non-negative real number of tokens, its marking. The distribution of tokens in places is denoted by Mand the marking of place piis represented as M[pi]. In (discrete) PNs one transition tjis enabled at marking Mif each of its input place pi∈•tjfulfills M[pi]≥P re[pi, tj]. The enabling degree of transition tjat marking Mis defined as: enab(tj,M) = min pi∈•tj M[pi] P re[pi, tj] (2.1) It gives the maximal amount that transition tjcan fire at M. Transition tjis called k-enabled under marking M, if enab(tj,M) = k. The firing of transition tj with an amount α∈N(denoted by tj(α)) leads the system to a new state M′= M0+α·C[P, tj], the evolution being denoted by Mtj(α) →M′, where C=P ost−P re is the token flow matrix (incidence matrix if Nis self-loop free) and C[P, tj] and C[pi, T] are its jth column and ith row. A marking Mthat can be reached from M0 by firing a sequence σ=t1(α1)t2(α2)..., satisfies the following state (fundamental) equation: M=M0+C·σ,M∈N|P|,σ∈N|T|(2.2) where σis called the firing count vector corresponding to firing sequence σ, such that σ[tj] is the accumulative amount that tjfires in σ. 8 2.2. Autonomous (untimed) continuous Petri nets Similar to other modelling formalisms, PNs also suffer from the state explosion problem of DEDS which makes intractable the computational complexity of the traditional state enumeration based methods. In particular, the size of the reachability set of a PN may increase exponentially with respect to the initial state. Example 2.1.2. Let consider a discrete net system given in Fig.2.1 [93, 46]. Table 2.1 shows that the size of the reachability set grows exponentially when the initial state is scaled. p1 p2 p3 p4 p5 p6 p7 t1 t2 t3 t4 t5 t6 2 22 4 3 Figure 2.1: A simple PN that models an assembly system, initial state M0=[1 0 2 3 1 0 0]T Table 2.1: The size of the reachability set of the net system in Fig.2.1 Initial state Size of the reachability set M054 2·M01,685 3·M010,354 4·M037,722 5·M0103,914 ... ... 10 ·M02,598,345 2.2 Autonomous (untimed) continuous Petri nets One classical technique used to overcome the state explosion problem is fluidization. Fluid models are obtained by removing the integrality constraint from the system. In particular, in the fluid PN models, the firing of transitions and consequently the 9 Chapter 2. Continuous Petri nets: Basic Concepts and Notations markings, are no longer restricted to the natural and they can be non-negative real numbers. The main advantage of using the fluid relaxation is that the computational issue in the original discrete model is considerably reduced, usually in a dynamical way. 2.2.1 Basic concepts Definition 2.2.1. A continuous Petri net (CPN) system is a pair hN ,m0iwhere N=hP, T, P re,P ostiis the same net structure as defined for the discrete PN. The difference is that in CPNs the firing of transitions and the markings (states) are no longer restricted to be in the naturals, but relaxed to be non-negative real numbers, so, m0∈R|P| ≥0. In CPN systems, the markings are denoted by m, distinguishing with Mfor the markings in discrete models. In CPN systems, a transition tis enabled at mif for every p∈•t,m[p]>0, i.e., every input place should be marked. Notice that, in contrast with discrete systems, it is not necessary to consider the weights of arcs to decide whether a transition is enabled or not. However, the weights of arcs are important to compute the enabling degree of a transition tjat a certain marking m, which is defined as: enab(tj,m) = min pi∈•tjm[pi] P re[pi, tj] An enabled transition tjcan fire in any real amount α, with 0 < α ≤enab(tj,m), leading to a new state m′=m+α·C[P, tj] . Similar to to discrete systems, a reachable marking from m0through a finite sequence σis included in the state (fundamental) equation: m=m0+C·σ,m,σ≥0 (2.3) 2.2.2 Petri nets subclasses The subclasses of discrete PNs that depend only on the structure of net are also applicable to the continuous PNs; in particular, we consider the following subclasses: •Marked-Graph(MG) [74]: ordinary net and ∀p∈P, |p•|=|•p|= 1. •Weighted T-system (WTS) [92]: ∀p∈P, |p•|=|•p|= 1. •Choice-Free (CF) [93]: ∀p∈P, |p•|= 1. •Join-Free (JF): ∀t∈T, |•t| ≤ 1. •Equal conflict (EQ) [94]: iff •t∩•t′6=∅ ⇒ P re[P, t] = P re[P, t′]. •Mono-T-semiflow (MTS) [19]: conservative and has a unique minimal T-semiflow whose support contains all the transitions. 10 2.2. Autonomous (untimed) continuous Petri nets 2.2.3 Basic structural concepts The support of a vector, v≥0, is kvk={vi|vi>0}, the set of positive elements of v. Right (C·x= 0) and left (y·C= 0) natural annullers of the token flow matrix are called Tand P-semiflows, respectively. A semiflow is minimal when its support is not a proper superset of the support of any other semiflow, and the greatest common divisor of its elements is one. As in discrete nets, when ∃y>0, s.t. yT·C=0, the net is said to be conservative, and when ∃x>0s.t. C·x=0, the net is said to be consistent. Given a P-semiflow y(a vector), there exist two related notions that should be differentiated: •conservation laws: a set of equations yT·m0=yT·m, which hold for an arbitrary initial marking m0and every reachable marking m=m0+C·σ, m,σ≥0. •conservative component: the P-subnet generated by the support of y. It is a part of the net that conserves its weighted token content. On the other hand, T-semiflows identify potentially cyclic behaviors in the system, i.e., if ∃x0s.t. C·x=0, and xis fireable from mthen, by the state equation, mσ →mwith σbeing a firing sequence and the corresponding firing count vector is equal to x. Example 2.2.2. For example, the PN system in Fig. 2.2(a) has a P-semiflow y=[1 1 1]T, therefore kyk={p1, p2, p3}. By the state equation, it holds yT·m0=yT·m, i.e., for any marking mreachable from a given m0,m[p1] + m[p2] + m[p3] = m0[p1]+m0[p2]+m0[p3], which are the conservation laws. For example, considering the initial marking m0= [2 0 0]Tit holds m[p1] + m[p2] + m[p3] = 2. The Psubnet generated by kykcontains all the places of the net, i.e., the whole net is a conservative component. The PN system has also a T-semiflow, x=[1 1 1]T, thus kxk={t1, t2, t3}. Therefore, if every transition fires once, the system returns to the initial marking. Two interesting structural concepts are siphons and traps. A set of places Σ is a siphon if •Σ⊆Σ•. The dual concept of of siphon, called trap, is a set of places Θ such that Θ•⊆•Θ. An important property is that an empty siphon will remain empty forever; and analogously, in discrete net systems, a marked trap cannot get emptied. Nevertheless, in continuous systems, a trap may be emptied in the limit [83]. For example, p1in Fig. 2.2(b) is a trap. But, if we consider the net as continuous, p1 can be emptied with an infinite firing sequence, see Ex. 2.2.5. For the PN in Fig. 2.2(a), Σ = {p1, p2}is a siphon since: •Σ = {t1, t3} ⊆ {t1, t2, t3}= Σ•. Considering the PN in Fig. 2.2(b), S={p1}is a trap and also a siphon, since S•={t1, t2}=•S. 11 Chapter 2. Continuous Petri nets: Basic Concepts and Notations t1 p2 p1 t3 p3 2 t2 (a) p1 p2 t1t2 22 (b) p1 p2 t1t2 3 22 223 (c) p1 p2 t1t2 2 3 (d) Figure 2.2: Some simple PN systems 2.2.4 Reachability and lim-reachability The reachability space (reachability set) of a given system hN,m0i, denoted by RS(N,m0), is the set of all markings that are reachable by a finite firing sequence: Definition 2.2.3. RS(N,m0) = {m|a finite fireable sequence σ=ta1(α1). . . tak(αk) exists such that m0 ta1(α1) →m1 ta2(α2) →m2... tak(αk) →mk=mwhere tai∈Tand αi∈R+}. An interesting property of the RS of CPNs, different from the discrete RS is that this set is convex [83]. Property 2.2.4. Let hN ,m0ibe a continuous PN system. The set RS(N,m0)is convex, i.e., if two markings m1and m2are reachable, then for any α∈[0,1], m′=α·m1+ (1 −α)·m2is also a reachable marking. 12 2.2. Autonomous (untimed) continuous Petri nets Example 2.2.5. Let us consider the system in Fig. 2.2(b). At the initial marking m0= [2 0]T, transition t1is enabled, and its enabling degree is 1. It can fire any real amount αs.t. 0< α ≤1. For example, if it fires the maximal possible amount, α= 1, the system reaches the marking m1= [1 1]T, from which both transitions (t1and t2) are enabled. From marking m1, if t1fires an amount equal to enab(t1,m1) = 1 2, the system reaches m2= [1 2 3 2]T. Firing successively transition t1an amount equal to its enabling degree, the marking of p1decreases to the half in each firing; but p1 is never emptied by a finite firing sequence. However, place p1can be emptied if we consider an infinitely long firing sequence and the marking will approach m= [0 2]T, which is said to be reachable in the limit. Notice that p1is a trap and it gets emptied in a CPN system, but only with an infinite firing sequence. The markings that are reachable with infinite long firing sequences are said to be lim-reachable, denoted by lim-RS(N,m0): Definition 2.2.6. [83] Let hN,m0ibe a continuous system. A marking m∈(R+∪ {0})|P|is lim-reachable, if a sequence of reachable markings {mi}i≥1exists such that m0 σ1 →m1 σ2 →m2···mi−1 σi →mi··· and lim i→∞ mi=m. The lim-reachable space is the set of lim-reachable markings, and will be denoted by lim-RS(N,m0). For any continuous system hN,m0i, the differences between RS(N,m0) and lim-RS(N,m0) are just in the border points of the reachability spaces. Therefore, it holds that RS(N,m0)⊆lim-RS(N,m0) and that the closure of RS(N,m0), i.e., all the points in RS(N,m0) plus the limit points of RS(N,m0), is equal to the closure of lim-RS(N,m0) [49]. Moreover, lim-RS(N,m0) is also convex. Assuming an initial marking of non-negative integers of a continuous system hN,m0i, if mis a marking that is reached by firing transitions in discrete amounts, i.e., as if the system was discrete, then mis also reachable by the system as continuous just by applying the same firing sequence. Thus RSD(N,M0)⊆RS(N,m0) where M0=m0and RSD(N,M0) is the discrete reachability space, i.e., the set of markings reachable in the corresponding discrete system. Under some common conditions, we can characterize the set lim-RS(N,m0) by using some linear inequality systems, which can be easily checked, in polynomial time: Proposition 2.2.7. [49, 83] Let hN ,m0ibe a consistent CPN system, such that each transition can fire at least once (there does not exist an empty siphon at m0). Then, the following statements are equivalent: •mis lim-reachable. • ∃σ≥0, such that m=m0+C·σ. •By·m=By·m0,m≥0, where Byis a basis of P-flows. 13 Chapter 2. Continuous Petri nets: Basic Concepts and Notations computed using the following non-linear programming problem that maximizes the flow of an arbitrary transition tj: max fss[tj] s.t. mss =m0+C·σ fss[t] = λ[t]·min pi∈•tnmss[pi] P re[pi,tj]o,∀t∈T C·fss = 0 mss,σ≥0 (2.11) where mss is the steady-state marking. Due to the minimum operator, problem (2.11) is non linear and a branch & bound algorithm was propsed in [50] to solve it. By relaxing the minimum operator to inequalities the problem is reduced to a LPP, shown in (2.12), which can be solved in polynomial time, but usually we may only obtain a non-tight upper bound, i.e., the solution may be not reachable if there exists a transition for which the flow equation is not satisfied. If the net is not MTS, similar developments can be done by adapting the equations in [23]. max fss[tj] s.t. mss =m0+C·σ fss[t]≤λ[t]·mss[p] P re[p,t],∀t∈TS,∀p∈•t fss[t] = λ[t]·mss[p] P re[p,t],∀t∈TU, p =•t C·fss =0 mss,σ≥0 (2.12) where TUis the set of transitions with unique input place, and TSthe synchronizations transitions (TU∩TS=∅,TU∪TS=T) . Once a solution of LPP (2.12) is obtained, it can be easily checked whether it is the exact value of the flow by introducing it into the problem (2.11). 2.3.4 Parametric optimization under infinite server semantics Parametric optimization considers “off line” problems in which, given the system configuration, it is optimally parameterized for the steady state. Among the problems belonging to parametric optimization, some of them are, for example, computing the optimal initial marking m0to achieve the maximal throughput in the steady state, satisfying certain constraints; or problems of minimizing certain cost function related to the initial marking; or optimizing other design parameters, like the optimal routing or the optimal firing speed, etc. A general formulation for this class of optimization problems with respect to the steady state is trying to maximize a profit function depending on the throughput (flow) vector (fss) in the steady state, the marking in the steady state (mss), and the initial marking (m0). The profit function can be represented, in linear terms, like: g·fss −w·mss −b·m0, where gis a gain vector w.r.t. the flow; wis the cost vector due to immobilization to maintain the production flow, e.g. due to the 20 2.3. Timed continuous Petri nets levels in stores; and vector brepresents depreciations or amortization of the initial investments w.r.t. m0, e.g., the size of buffers, the number of machines. Given K·m0≤das linear cost-constraints to the initial state, assume that we need to optimize the throughput of transition tjin the steady state, fss[tj], the following LPP can be written [89]: max fss[tj] s.t. mss =m0+C·σ fss[t]≤λ[t]·mss[p] P re[p,t],∀t∈TS,∀p∈•t fss[t] = λ[t]·mss[p] P re[p,t],∀t∈TU, p =•t C·fss =0 σ,m0,mss ≥0 K·m0≤d (2.13) where TUis the set of transitions with unique input place, and TSthe remaining (synchronization) transitions. If we compare LPP (2.13) with the LPP (2.12), the only difference is that now the initial state m0appears as a variable and that the linear cost-constraints associated to m0are added. In general, LPP (2.13) just provides an upper bound of the throughput of transition tj. Another parametric optimization problem concerns computing the minimal cost initial marking w.r.t. a given cost weight vector bsuch that a certain cycle time Γ = 1/fss[tj] is guaranteed. This optimization problem can be solved by means of the following LPP [89]: min b·m0 s.t. mss =m0+C·σ fss[t]≤λ[t]·mf[p] P re[p,t],∀t∈TS,∀p∈•t fss[t] = λ[t]·mf[p] P re[p,t],∀t∈TU, p =•t C·fss =0 σ,m0,mss ≥0 fss[tj]≥1/Γ (2.14) where TUis the set of transitions with unique input place, and TSthe synchronizations transitions (TU∩TS=∅,TU∪TS=T) . 2.3.5 Approximation to the discrete systems The fluid PNs are a relaxation/approximation of the original discrete model, in particular, we consider the Markovian (discrete) Petri nets (MPNs): stochastic discrete PNs with exponential delays associated to the transitions and conflicts solved by a race policy [73]. MPNs enjoy the memoryless property, and it is widely used in the performance evaluation, for example [73, 69, 8]; but the analysis of its underlying Markovian Chain may be intractable, because of the computational issue cased by 21 Chapter 2. Continuous Petri nets: Basic Concepts and Notations the state explosion problem. The approximation (steady-state as well as transient behavior) of MPNs by using TCPNs under infinite server semantics was first considered in [80]. However, in some situations the fluid approximation may not be good. Therefore it is interesting to investigate the conditions, based on which an appropriate fluid model could be obtained. Example 2.3.4. Let us still consider the net system in Fig.2.1. We simulate it by using the Markovian PN model [73] and the corresponding TCPN model under infinite server semantics. The state trajectories of both cases are illustrated in Fig. 2.4. We can see that the fluid model has a reasonable approximation of the original discrete one, and the accuracy is improved if the system is more populated. Notice that, if the initial marking is increased form m0to 10 ·m0, the size of the state space of the discrete PN model increases from 54 to more than 2.5 million—the state explosion problem appears, so the analysis based on the discrete model could be difficult. However, if we consider the fluid model, the number of variables in the system, determined by the number of places, is not changed. On the other hand, for the analysis by using the deterministic fluid model, only one round simulation is enough, which is also much cheaper than using the (stochastic) discrete model. 0 20 40 60 80 100 0 1 2 3 4 5 6 m[p6] Time TCPN Markovian PN size of discrete state space = 54 (a) Simulation results using initial state m0 0 20 40 60 80 100 0 10 20 30 40 50 60 m[p6] Time Markovian PN TCPN size of discrete state space > 2.5 ⋅ 106 (b) Simulation results using initial state 10 ·m0 Figure 2.4: Simulations: a discrete PN and its fluid model There are two main reasons that may introduce errors to the fluid models: the weights on arcs and join transitions (rendez-vous). Let Mbe the marking of the original discrete PN and mbe the one of the corresponding fluid model, TCPN. We assume that the state of fluid model approximates the one of discrete model, then we have m∼E(M), where E(M) refers to the expectation of M. Assume a JF nets, and wbe the weight on the directed arc from place pito tj. The expected enabling degree of tjin the discrete model is E(enab(tj,M)) = E(⌊M[pi]/w⌋); while in the TCPN, enab(tj,m) = m[pi]/w ∼E(M[pi])/w. Clearly, due to the operation ⌊·⌋,E(enab(tj,M)) may be different to enab(tj,m) in a non-ordinary net (w > 1). The similar problem may appear even in an ordinary net when tj is a join (|•tj|>1): E(enab(tj,M) = E(min{M[pi]}), pi∈•tjis not equal to 22 2.3. Timed continuous Petri nets enab(tj,m) = min{m[pi]} ∼ min{E(M[pi])}, pi∈•tj, because it is a common knowledge that operator min and Ecannot commute. More detailed explanations and illustrative examples about these issues can be found in [87]. It has been formally proved in [101] that for ordinary JF nets, perfect approximation of the discrete model can be obtained by using TCPNs. If a JF net is not ordinary, approximation errors may appears; however, if the net system has a unique asymptotically stable equilibrium point, the errors are ultimately bounded and the larger the average enabling degree the lower the errors. For non JF nets, if the probability that the MPN system evolves inside a unique region (in which the TCPN also evolves) is near 1, i.e., for each synchronization, it is almost always constrained by a single input place, the approximation error is also ultimately bounded and can be improved if the average enabling degree is larger. In [29], the conditions for an appropriate fuidization are investigated mainly based on the marking homothetic behaviours of the system. In particular, the relations between the original discrete model and the fluid one are established, in terms of some important logical properties as boundedness, deadlock-freeness, liveness and reversibility. Several techniques have been proposed to improve the approximation of using TCPNs. For instance, by adding white noise to the flows of transitions of the TCPN model [101], a continuous stochastic CPN (denoted by TnCPN) is obtained. Intuitively, the stochastic behavior of the MPN is better approximated, according to the following evolution (in discrete time): mk+1 =mk+C(ΛΠ(mk)mk∆τ+vk) where vkis a noise column vector, of length |T|, whose elements are of independent normally distributed random variables with zero mean and covariance matrix. An interesting issue is that, by adding the white noise according to the previous approach, the expected value and covariance of the original MPN and the resulting TnCPN coincide. Another class of techniques for improving the approximation consists in modifying the server semantics of TCPNs. For example, we may change the infinite server semantics by multiplying a marking-dependent function (m[pi]q−1/qq) to the flow of a transition tj, such that pi=•tjand P re[pi, tj] = q[87], then the flow of tjis modified to f[tj] = λj·(m[pi]/q)q. In this way, the approximation may be improved. Belonging to the same category, in [59], the firing rate is considered as piece-wise constant, depending on the regions of the current markings. It is show that the asymptotic mean marking of discrete model can be approximated by the continuous one, if the system is in non-critical regions (each join is driven by different place); in [56] the case of critical regions is considered, by means of partial homothetic initial markings but differently, the firing rate is not piece-wise constant but fixed value. More constructive method has been proposed by the same authors in [57], where the homothetic approach is used to compute a set of reference data for several firing rates and an interpolation method is applied. We can also improve the approximation by removing spurious solutions: those markings that cannot be reached in the discrete model but become (lim-)reachable after fluidization (it is an immediate result of Proposition 2.2.7). Spurious solutions may appear due to the fact that in TCPNs, marked traps are finally emptied in 23 Chapter 2. Continuous Petri nets: Basic Concepts and Notations the limit. Fortunately, this kind of spurious solutions can be cut by adding some implicit places to the system. A comprehensive discussion of this technique can be found in [87]. In this thesis, we focus on the synthesis of controllers directly based on the fluid model and we assume that the approximation of the TCPN to the underlying discrete model is appropriate. 2.4 An example: a kanban-like manufacturing system This section is devoted to illustrate some of the basic concepts and techniques about TCPNs that we have introduced in this chapter, by means of the analysis of the model of a flexible manufacturing system. The system is composed by two production lines with three machines M1, M2 and M3. The layout of the system and its production process are shown in Fig.2.5, while the PN model is depicted in Fig. 2.6. Parts of type A are processed in machine M1 and then in machine M2, with intermediate products stored in buffers B 1A and B2A. Parts of type B are first processed in M2 then in M1, with intermediate products stored in buffers B 1B and B 2B. Finally, machine M3 assembles a part A and a part B, obtaining the final product that is stored in buffer B 3 until its removal. Places Max B 1A and Max B 1B initially have only one token, so there can be at most one part of type A and one part of type B either in B 1A and B 1B, or being processed by M1 and M2. Parts A and B are moved in pallets all along the process, and there are 20 pallets of type A and 15 pallets of type B. Place Max B 3 has initially one token, so only one final product can be stored in the buffer B 3 until its removal. The initial state m0of the system is as shown in Fig. 2.6. Typical competition and cooperation relationships that often appear in manufacturing systems, are introduced by means of the movement of parts inside the system. For instance, machine M1 and machine M2 are shared for processing parts A and parts B, therefore, these activities are in mutual exclusion (mutex). Final products can be assembled only when both intermediate produces of type A and B are available (i.e., buffer B 2A and B 2B are not empty) (rendez-vous). Buffer Input A Input B In_A M1 Output Buffer Buffer Output M2 In_B M2 M1 M3 Machine 1 Machine 2 Machine 3 (a) (b) Figure 2.5: (a) Logical layout of a manufacturing system and (b), its production process 24 2.4. An example: a kanban-like manufacturing system M1_A(p2) B_1A(p3) 20 Pallets_A(p1)M2_A(p4) 15 M2_B(p8) B_1B(p9) Pallets_B(p7)M1_B(p10) B_2A(p11) B_2B(p12) M1_Idle(p5) M2_Idle(p6) M3_Idle(p13) M3_Work(p14) Max_B_3(p15) B_3(p16) S_M1_A(t1)E_M1_A(t2)S_M2_A(t3)E_M2_A(t4) S_M2_B(t5)E_M2_B(t6) S_M1_B(t7)E_M1_B(t8) S_M3(t9)E_M3(t10)Out(t11) Max_B_1A(p17) Max_B_1B(p18) Figure 2.6: The PN system that models the manufacturing system described in Fig.2.5 Let us first consider the net system in Figure 2.6 as a continuous model without any temporal interpretation (i.e., as an autonomous PN: a fully non-deterministic model). Some important properties of the autonomous PN system can be studied: conservativeness/consistency, boundedness, structurally implicit places, deadlockfreeness, liveness. Looking at the structure of the net, it can be checked that it is conservative: ∃y>0 s.t. yT·C= 0 (it has 8 elementary P-semiflows covering all the places, each one gives an elementary token conservation law (see Table 2.2)). The system is also consistent: it has a unique minimal T-semiflow x=1(C·x= 0). Given that the net is conservative and has a unique T-semiflow that covers all the transitions, the net system is mono-T-semiflow (MTS). Table 2.2: P-semiflow of the system in Fig. 2.6 P-semiflow Corresponding token conservation law y1M1 A + M1 Idle + M1 B = 1 y2Pallets B + M2 B + B1 B + M1 B + B 2B + M3 work + B3 = 15 y3M2 B + B1 B + M1 B + Max B1 B = 1 y4Pallets A + M1 A + B1 A + M2 A + B 2A + M3 work + B3 = 20 y5M1 A + B1 A + M2 A + Max B1 A = 1 y6M2 A + M2 Idle + M2 B = 1 y7Max B 3 + B 3 = 1 y8M3 Idle + M3 work = 1 25 Chapter 2. Continuous Petri nets: Basic Concepts and Notations (Structural) Boundedness: The PN is conservative, thus it is structurally bounded (i.e., bounded for any m0). The structural bound of each place can be computed from (2.4). For example, SB(p1) = 20 and SB(p2) = 1. Structurally implicit places: There exist six structurally implicit places (see Proposition 2.2.12): M1 Idle, M2 Idle, M3 Idle, Max B 3, Max B 1A and Max B 1B. The minimal initial marking of p5to make it implicit (see Proposition 2.2.13) is m0′[p5] = 2. It means that, if we keep the initial marking of other places and we have 2 or more tokens in p5, then it will no longer restrict the system. In other words, even we put more machines of type M1 in the system, the throughput cannot be improved. Analogously, the minimal initial marking of p6to become implicit is 2; for p13, is 15; for p15, is 15; for p17, is 20; and finally for p18, it is 15. Deadlock-freeness and liveness: As we have briefly recalled, there exist several methods that can be used for checking the deadlock-freeness. For instance, we can use the deadlock-trap property (DTP). In this particular ordinary net example, siphons are also traps (see Table 2.3) and they are initially marked. So, every siphon contains a marked trap, i.e., the DTP property holds. Thus the net system is deadlock-free. Moreover, the DTP property guarantees not only homothetic deadlock-freeness, but also monotonic deadlock-freeness. It means that, if the marking of any place is increased, the net system will remain deadlock-free. If a discrete system hN,M0iis homothetic DF, then it is also DF as continuous [29]. Another interesting way to approach the problem is the following: places M1Idle(p5) and M2Idle(p6) are structurally implicit, if we add enough tokens to the initial state of those places (one more token to each of them), they become implicit. Therefore both can be removed without affecting structural liveness. After the removal, the remaining PN is a strongly connected marked graph with all circuits (i.e., P-semiflows) marked. Thus, the original system is structurally live. Table 2.3: Minimal siphons of the net. They coincide with the minimal traps. Minimal siphons / minimal traps {p1, p2, p3, p4, p11, p14, p16} {p2, p3, p4, p17} {p2, p5, p10} {p4, p6, p8} {p7, p8, p9, p10, p12, p14} {p8, p9, p10, p18} {p13, p14} {p15, p16} Let us now consider the model in Fig.2.6 as a timed PN system. We assume that each transition is associated to a time delay that follows exponential distributions. In particular, the time delay vector of transitions, represented by δ, is set as following. 26 2.4. An example: a kanban-like manufacturing system The transitions that model the starting of machines (labelled by S) have time delays δ[t1] = δ[t3] = δ[t5] = δ[t7] = δ[t9] = 1 t.u.. The delays of transitions that model the endings (labelled by E) are δ[t2] = δ[t6] = 3 t.u., δ[t4] = δ[t10] = 4 t.u. and δ[t8] = 5 t.u.. The output transition has a delay δ[t11] = 1 t.u. In the corresponding TCPN model under infinite server semantics, time delays are approximated by their mean values (λ[tj] = 1/δ[tj], tj∈T), obtaining a first order (or deterministic) relaxation of the discrete case [80]. As an important part in the life-cycle of manufacturing systems, performance evaluation has been widely investigated by using time interpreted PNs, under both the framework of continuous and discrete systems, for example in [50, 69, 8]. We will focus on the steady state evaluation and transient state evaluation, using TCPNs under infinite server semantics. Steady state analysis: By solving LPP (2.12), an upper bound of the flow, equal to 0.1, is obtained (given that the net is MTS with the unique minimal T-semiflow equal to 1, all the transitions will have the same flow in the steady state). We can check that it is a solution of problem (2.11), i.e., the relaxed LPP (2.12) gives the exact upper bound of the flow! On the other hand, if we consider the problem (2.11) with min operator in the objective function, instead of max operator, i.e., computing the lower bound of the flow, the obtained flow is also 0.1. The direct consequence is that, the flow of transitions is exactly equal to 0.1 in the steady state, which is mss = [0.1 0.3 0.1 0.4 0.2 0.3 13.5 0.3 0.1 0.5 18.6 0.1 0.6 0.4 0.9 0.1 0.2 0.1]T. Transient analysis: The transient evaluation analyzes the behavior of the system, from the initial state (at time zero) until a given end time. As we have mentioned in the previous sections, TCPN models can approximate the average marking of the corresponding MPN if the MPN evolves inside a unique region (in which the TCPN also evolves), but it does not hold for this net system. In Fig.2.7 the transient state evolution of M1 Idle (p5) is shown (obtained with the initial marking shown in Fig. 2.6). The results of the MPN are obtained by 100 simulations and taking the average value at each time instant. It can be observed that, even if the general shape of curves of the TCPN and the MPN are similar, the approximation provided by the fluid model is not very accurate: in the interval from 3.5 t.u. to 4.5 t.u. the average value of M[p5] (for the MPN) is 0.40, while the average value of m[p5] (for the TCPN) is 0.22, with error of (0.40 −0.22)/0.40 = 45%. We can further improve the approximation, for example, by applying the technique proposed in [101]. Adding white noise to the flows of transitions of the TCPN model, we obtain the continuous stochastic CPN (TnCPN). In Fig.2.7, it can be clearly seen that the TnCPN model gives more accurate approximation to the original MPN: in the interval from 3.5 t.u. to 4.5 t.u., the average value of m[p5] for the TnCPN is 0.34, the error is 15% (much better than the TCPN model with error of 45%). One essential reason of the relatively inaccurate approximation of the deterministic model (Fig. 2.7) may be that the system is not truly very much populated: in m0, there is only one machine for each operation, and the size of buffers is also 27 Chapter 2. Continuous Petri nets: Basic Concepts and Notations Figure 2.7: Marking trajectory of place p5: with initial marking m0 limited to 1. In the case that the system is more populated, for example, instead of using m0, we simulate the system with initial marking equal to 50 ·m0(results shown in Fig.2.8), a very good approximation can already be obtained by using the deterministic TCPN model, even if no white noise is considered. More theoretical results about the approximation of using CPN can be found in [63]. Figure 2.8: Marking trajectory of place p5: with initial marking 50 ·m0 Last but not least, let us consider the parametric optimization problem of computing the optimal initial marking that satisfies a linear constraint K·m0≤d. Assume that because of constraints on the investment, we can have at most 5 machines in the system (m0[M1Idle] + m0[M2Idle] + m0[M3Idle]≤5), and the total size of buffers is constrained to no more than 10 (m0[Max B1A] + m0[Max B 1B] + m0[Max B3] ≤10). At the same time, the total amount of available pallets for the raw materials A and B are limited to 20 (m0[Pallets A]+ m0[Pallets B]≤20). Under these constraints and with the other places initially set to be zero, we want to compute an optimal m0, such that the throughput of transition Out (t11) in 28 2.4. An example: a kanban-like manufacturing system the steady state is maximized. An optimal m0obtained by solving LPP (2.13) is: m0[Pallets A] = 3.4, m0[Pallets B] = 3.6, m0[Max B 3] = 1.1, m0[Max B 1A] = 2.0, m0[Max B1B] = 2.3, m0[M1Idle] = 2.1, m0[M2Idle] = 1.8, m0[M1Idle] = 1.1. Using this initial marking, the maximal throughput of t11 is 0.2273. 29 Chapter 3. Control of Continuous Petri nets can maximize certain profit functions, for example, they correspond to the maximal throughput (flow) of the system. Chapter 7 is devoted to this problem, in which instead of reaching a specific final marking, we are interested in reaching the maximal flow as fast as possible (without considering the WIP cost). In TCPNs under infinite server semantics a marked place cannot be emptied in finite time (like the theoretical discharging of a capacitor in an electrical RC-circuit). Given a positive initial state m0>0, only a positive final state can be reached in finite time, thus the final state should also be an interior point in the reachability space, i.e., mf>0. 3.3 Controllability Controllability is an important property in every kind of dynamic systems. It is related to the capability of being driven in a certain desirable way and in this thesis, we consider the controllability in terms of the target marking control problem problem. More generally speaking, it is related to the classical controllability concept, according to which a system is controllable if for any two states m1,m2of the state space it is possible to transfer the system from m1to m2in finite time (see, for instance, [21]). A lot works can be found in the literature addressing the controllability of different classes of hybrid systems, for instance in [11, 33, 110]. However, in TCPNs, the control input are non-negative and state-dependently bounded, i.e., 0≤u≤ ΛΠ(m)m, therefore the complexity of the analysis of controllability increases, and the classical controllability concept cannot be applied to TCPNs in general. Few contributions about the controllability of TCPNs only focused on very limited subclass, for example, JF nets [43]. Even by assuming that the control of the system is in a region such that the constraints are not active, systems are still not controllable due to the marking conservation laws imposed by P-flows [65]. More specifically, if yis a P-flow then any reachable marking mmust fulfill yTm=yTm0, defining thus a state invariant. Nevertheless, the study of controllability “over” this invariant is particularly interesting. This set is formally defined as Class(m0) = {m∈ R|P| ≥0|BT ym=BT ym0}, where Byis a basis of P-flows, i.e., BT yC=0. For a general TCPN system, every reachable marking belongs to Class(m0) (see Proposition 2.2.7). Considering the constraints on the control input, an appropriate local controllability concept was proposed in [97]: Definition 3.3.1. The TCPN system hN,λ,m0iis controllable with bounded input (BIC)over S⊆Class(m0)if for any two markings m1,m2∈Sthere exists an input utransferring the system from m1to m2in finite or infinite time, and it is suitably bounded, i.e., 0≤u≤ΛΠ(m)m, and ∀ti∈Tnc u[ti] = 0 along the marking trajectory. 36 3.3. Controllability In the case that all the transitions in the system are controllable, the controllability of TCPNs only depends on the net structure, in particular, on the consistency. Property 3.3.2. [97] Let Σ = hN,λ,m0ibe a TCPN system in which all the transitions are controllable. Σis BIC over the interior of Class(m0)iff Nis consistent. Furthermore, the controllability is extended to the whole Class(m0)iff (additionally to consistency) there exists no empty siphon at any marking in Class(m0). Example 3.3.3. Consider for instance the TCPN of Fig. 3.2(a) and the markings m0= [2 1 1]T,m1= [1 1 2]Tand m2= [1 2.5 0.5]T. Obviously, m1and m2are both in Class(m0). The system has only one P-semiflow (involving p1,p2and p3), the marking of two places is sufficient to represent the whole state. For this system ∃σ≥0such that m1=m0+C·σ, but ∄σ≥0such that m2=m0+C·σ. So m1 is reachable but m2is not. It can be easily verified that the TCPN in Fig. 3.2(a) is not consistent, therefore according to Proposition 3.3.2 this TCPN is not controllable over Class(m0). The shadowed area in Fig.3.2(a) corresponds to the set of reachable markings. It is the convex cone defined by vectors c1,c2and c3, which represent the columns of C(here restricted to p1and p3). 1 21 t1 p2 p1t3p3 t2 m[p1] m[p3] 4 2 24 m0 m2m1 c1 c2 c3 (a) 1 21 t1 p2 p1t3p3 t2 t4 m[p1] m[p3] 4 2 24 m2m1 c3 c4 m0 c2 c1 (b) Figure 3.2: Two TCPN systems with identical P-flows and initial marking. The shadowed areas correspond to the sets of reachable markings. The net in (b) is consistent and there exists no empted siphon, therefore controllable over Class(m0). Now, consider the system of Fig. 3.2(b). In this case, m2become reachable from m0. In fact, for any marking m∈Class(m0), the vector (m−m0)is in the convex cone defined by the vectors c1to c4, which occurs due to the consistency of the net and implies that mis reachable from m0. Moreover, since the only siphon in this net, composed of {p1, p2, p3}, is always marked (at the same time it defines an initially marked conservative component), the system is BIC over Class(m0). 37 Chapter 3. Control of Continuous Petri nets If uncontrollable transitions exist, the analysis of controllability becomes more complex, and in general the systems are no longer controllable over Class(m0), even for consistent nets (see [87] for some examples). Since in the whole reachability space the system is usually uncontrollable when uncontrollable transitions exist, some contributions studied the controllability on the subsets of markings. For example, in [43], it is studied over the so called Controllability Space (CS), the set of all the controllable markings, that is characterized for Join-Free net. However, it is difficult to extend to general subclasses because its dependence on the markings. Contribution [97] focused on equilibrium markings. Marking mq∈Class(m0) is an equilibrium one if ∃uq(0 ≤uq≤ΛΠ(mq)mq) such that C(ΛΠ(mq)mq−uq) = 0. They represent the possible stationary operating points of the system. The results are interesting, considering that controllers are frequently designed in order to drive the system towards a desired stationary operating point. Although here the technical results are not detailed, this approach is supported by the following proposition: Property 3.3.4. Let hN ,λ,m0ibe a TCPN system. Consider some equilibrium sets S1,S2,..., Sjrelated to different regions R1,R2,..., Rj. If the system is BIC (in finite time) over each one and their union Sj i=1 Siis connected, the system is BIC over the union. Finally, let us mention that in the case of systems with uncontrollable transitions, the controllability may depend not only on the structure of the net, but also on the timing, more detailed explanations can be found in [87, 96]. 3.4 Previous centralized control methods Partially derived from [87], in this section we briefly summarize some control methods proposed in the literature for the target marking control problem of TCPNs. Some preliminary comparisons are presented. Notice that all the methods mentioned in this section are in the framework of centralized control, the decentralized/distributed control will be discussed in Chapter 5 and 6. Most of the control methods that can be found in the literature assume that all the transitions are controllable: Fuzzy control [36] The authors proposed a control method for a particular variable speed CPNs, in which the firing speed vjof a transition tjis given by: vj=Vjmax ·min{1, m[pj1], m[pj2], ..., m[pjn]} where pj1, pj2, ..., pjn are the input places of tjand Vjmax is the maximal firing speed of tj. It can be viewed as TCPNs under infinite server semantics with an implicit self-loop in each fluid transition. It is shown that the flow of a transition, can be represented as the output of two fuzzy rules under the Sugeno model. It was proved 38 3.4. Previous centralized control methods that if the integral of the output of each fuzzy rule converges to a finite value then the resulting global fuzzy system (that represents the controlled flow) converges as well. Moreover, upper and lower bounds of this convergence were derived. Based on that, a proportional fuzzy control was proposed. Under a sufficient condition that the desired output (the marking of a place) is smaller than the initial upstream marking, it was proven that the convergence of the fuzzy global system can be obtained. However, this is not applicable to general cases. Control for a piecewise-straight marking trajectory [44, 45, 5] This approach was firstly explored in [44] for Join-Free nets, in which the tracking control problem of a mixed ramp-step reference signal is considered. Later, this method was extended to general PNs in [45]. There, a “high and low” gain proportional controller is synthesized, while a ramp-step reference trajectory, as a sort of path-planning problem at a higher level, is computed. To illustrate this kind of approach, let us detail a simple and more heuristic synthesis procedure introduced later in [5]. Consider the line lconnecting m0and md, and the markings in the intersection of lwith the region’s borders, denoted as m1 c,m2 c, ...., mn c. Define m0 c=m0and mn+1 c=mf. Then, ∀k∈ {0,1, ..., n}compute τkby solving the linear programming problem (LPP): min τk s.t. :mk+1 c=mk c+C·x 0≤xj≤λjΠk jimin{mk c[pi],mk+1 c[pi]}τk ∀j∈ {1, ..., |T|} where i satisfies Πk ji 6=0 (3.3) where Πkis the configuration matrix corresponding to the region, to which mk cand mk+1 cbelong and Πk ji gives its element in the jth row and ith column. The control law to be applied is thus w=x/τk, when the system is between the markings mk cand mk+1 c. The time required for reaching the desired marking is given by τf=Pn k=0 τk.Feasibility and convergence to mfwere proved in [5]. In order to reach the final state faster, the trajectory is now not constrained to be straight linear, but piecewise-linear, i.e., only the states in the same region are constrained to be in a linear trajectory. The following bilinear programming problem (BPP) needs to be solved to find the intermediate states on the borders, reducing the accumulated time for reaching the final state. min τf=Pn k=0 τ(k) s.t mk+1 =mk+C·xk,,k ∈ {0,1, ..., n} (Πk−Πk+1)·mk= 0, k ∈ {1,2, ..., n} mk[pi]≤mk+1[pi],if m0[pi]≤mf[pi], pi∈P, k ∈ {0,1, ..., n} mk(pi)≥mk+1[pi],if m0[pi]≥mf[pi], pi∈P, k ∈ {0,1, ..., n} 0≤xk[tj]≤λj·Πk ji ·min{mk[pi],mk+1[pi]} · τk ∀tj∈T, where pisatisfy Πk ji 6= 0, k ={0,1, ...n} (3.4) Finally, by recursively solving similar BPPs as in (3.4), intermediate states are 39 Chapter 3. Control of Continuous Petri nets added in the interior of each region, obtaining faster trajectories, until the accumulated time can not be significantly improved respect to a user specified threshold value. Model predictive control (MPC) [64] Model predictive control (MPC) has been widely applied in the industry for controlling complex dynamic systems [17, 70]. By solving a discrete-time optimal control problem over a given horizon, an optimal open-loop control input sequence is obtained and the first one is applied. Then in the next time step, a new optimal control problem is solved based on the current state and measurement, resulting in aclose-loop control. In [64], the MPC scheme is applied to the control of TCPNs. The evolution of the timed continuous Petri net model, in discrete-time, is represented by the difference equation: mk+1 =mk+ Θ ·C·wk, subject to the constraints 0≤wk≤fkwith fkbeing the flow without control, which is equivalent to G·[wT k,mT k]T≤0, for a particular matrix G. The sampling period Θ must be chosen small enough in order to avoid spurious markings, in particular, for ensuring the positiveness of the markings. For that, the following condition is required to be fulfilled ∀p∈P:Ptj∈p•λjΘ<1. By using this representation of continuous PNs, in each time step the following optimization problem is solved: min J(mk, N) s.t. :mk+j+1 =mk+j+ Θ ·C·wk+j, j = 0, ..., N −1 (3.5a) G·wk+j mk+j≤0, j = 0, ..., N −1 (3.5b) wk+j≥0, j = 0, ..., N −1 (3.5c) where J(mk, N) may be a quadratic objective function in the form of (3.6): J(mk, N) = (mk+N−mf)T·Z·(mk+N−mf) + N−1 X j=0 [(mk+j−mf)T·Q·(mk+j−mf) (3.6) + (wk+j−wf)T·R·(wk+j−wf)] where Z,Qand Rare positive definite matrices and Nis a given time horizon, and wfis a (desired) flow in the final state. However, if the desired marking (mf) has zero components, the standard techniques used for ensuring converge in linear/hybrid systems (i.e., terminal constraints or terminal cost) cannot be applied in continuous nets [64]. Nevertheless, a particular control law is proposed to overcome this problem: the system state at time k+N is constrained to the straight line from mkto mf. Roughly, this is equivalent to add a terminal constraint in the form of: 40 3.4. Previous centralized control methods mk+N=mk+α·(mf−mk) 0≤α≤1(3.7) where αis a new decision variable. The asymptotic stability of this method is proved in [64]. An alternative MPC approach for this problem is the so-called explicit solution [12], where the set of all states that are controllable is split into polytopes. In each polytope the control command is defined as a piecewise affine function of the state. The closed-loop stability is guaranteed with this approach. On the contrary, when either the order of the system or the length of the prediction horizon are not small, the complexity of the explicit controller becomes quickly prohibitive. Furthermore, the computation of the polytopes sometimes is infeasible. Proportional control synthesis with LMI [51] The proposed control scheme consists of a set of proportional (affine) control laws, one for each region. In detail, the controlled flow is represented, in discrete time, by w(k) = Fr(m(k)−md)+R, where Ris a vector and Fris a gain matrix computed for each region (the subindex rdenotes the r−th region). In each region, the control and the marking are required to fulfill: 1. the input constraints: 0≤w(k)≤f(k), where f(k) represents the flow without control, 2. the region membership: m(k)∈ P(Gr,gr), where P(Gr,gr) = {m|Grm≤ gr}is the inequality representation of the r-th region (a polyhedral), 3. the existence of a contractive invariant set (in order to prove closed-loop stability), which is stated as: x(k)∈ P(Q,µ)→x(k+ 1) ∈ P(Q, αµ), where x(k) = (m(k)−md) is the current error, α < 1 and P(Q, αµ) = {x|Qx ≤αµ} is the contractive set (so, the absolute error is monotonicdecreasing). The methodology consists in expressing the previous conditions as sets of linear matrix inequalities (LMI), one set for each region. The solution of a LMI can be achieved in polynomial time. Furthermore, convergence to the desired marking md is guaranteed. The main drawback of this approach is that a LMI must be solved for each region, but the number of these increases exponentially w.r.t. the number of synchronizations (joins). Affine control [102] The synthesis of controllers for TCPNs can be geometrically expressed in terms of polytopes. An affine system in polytopes χis defined as: ˙x=Ax+Bu +a with restriction x∈χand u∈U, where Uis a polytope of admissible inputs. An admissible affine control law is a affine function u:χ→U, characterized by u(x) = Fx+g. The affine control is used in the synthesis of piecewise hybrid 41 Chapter 3. Control of Continuous Petri nets system in [34, 32], by decomposing the polytopes into simplices and synthesizing a proper affine control law for each of them. In [102] this method is extended to the control of TCPNs, in which global affine control laws for the complete polytopes are synthesized. The vertices of a polytope of dimension k−1 are enumerated, and it is assume that the first kvertices define a simplex of dimension k−1. Then the evaluation of the control law at the vertices and conditions for the unique equilibrium point (in close loop) are derived. It is proved that given a consistent TCPN with initial state m0>0, using this affine control technology, the system can always be driven to a desirable final state mf>0. The main drawback of this method is that the number of vertices increases exponentially respect to the number of dimensions that is determined by the number of places, therefore its computational complexity may be intractable (although it can be partially done off-line). In this work, we assume all the transitions are controllable. In the case that uncontrollable transitions exist, the control problem becomes much more complex. Few works can be found in the literatures considering partially controllable systems. For instance, in [58], a Gradient-base control based method was proposed; anther method that considered uncontrollable transitions is Pole assignment control proposed in [99], where the initial and desired markings are equilibrium states. 3.4.1 Initial comparisons The availability of many control methods for this target marking control problem of TCPNs makes difficult the selection of the most appropriate technique for a given system and purpose. In order to make an appropriate choice, several properties may be taken into account, e.g., feasibility, closed-loop stability, robustness, computational complexity (for the synthesis and during the applications), etc. Table 3.1: Qualitative characteristics of several control methods (assuming m0> 0, mf>0 and all transitions are controllable). The following abbreviations are used: min. (minimize), suff. (sufficient conditions), comput. (computational), quad. (quadratic) and poly. (polynomial). Methods Comput. issues Optimizing index Stability Fuzzy control two fuzzy rules per transition None under suff. Piecewise-straight trajectory LPPs or BPPs on |T|Heuristic Min. time Yes MPC QPPs on |T|, N Min. quad. (or linear) functions under suff. LMI A LMI for each configuration None under suff. Affine Control Expon. on |P|None Yes 42 3.4. Previous centralized control methods Table 3.1 (that partially derived from Table 4 in [87]) demonstrates some qualitative properties of different control methods (under infinite server semantics) that have been described, assuming all the transitions are controllable. All those methods are applicable to any PN structure. The fuzzy control guarantees the convergence based on some sufficient conditions that may be too “restrictive” in general cases. The MPC based approaches ensure convergence and minimize a quadratic or linear objective function, obtaining a desired state trajectory. Nevertheless, when the number of transitions grows, or a large time horizon N is considered, its complexity for solving the problem with a huge number of variables may become intractable. In such cases, the piecewise-straight trajectory method could be more appropriate. However, when the process for obtaining heuristic minimum-time evolution is considered, the computational complexity is also very high. For instance, in the method proposed in [5], a non-linear BPP problem needs to be solved once an intermediate state is introduced to reduce the time. Affine controller also guarantees the convergence to the final state, but no optimizing index is considered; on the other hand, its complexity may increase rapidly in a larger system with many places. Now let us consider some a few examples using different methods for the target marking control problem. The simulations are performed by using Matlab 8.0 on a PC with Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz, 3.24GB of RAM. This first net system we consider is shown in Fig. 3.3. Let us assume that the firing rate of every transition is equal to 1; the sampling period is Θ = 0.01. We will consider two different initial states m01= [3 3 1 3]T;m02= [2.1 2.1 0.1 2.1]T and also two different final marking: mf1= [1 4.5 1.5 3]Tand mf2= [0.1 3.6 0.6 2.1]T, respectively. It can be checked that mfican be reached from m0i,i= 1,2 with the same firing count vectors, but one element of m02is very small. We can observe later that the performance of some control methods is quite dependent on the initial marking. For this control example we have applied the approaching minimum-time controller (appro. min-time) [5], affine controller [102] and the MPC controller [64]. Different parameters of the MPC controller are used. The simulation results are shown in Table 3.2 (considering m01/mf1) and Table 3.3 (considering m02/mf2). 43 Chapter 3. Control of Continuous Petri nets t1 t2 p2 p1 t3 p4 p3 2 2 3 Figure 3.3: A simple TCPN system Table 3.2: Simulation results of reaching mf1from m01, in the net system of Fig. 3.3 (for the MPC control, the weight matrix Q=q·1|P|,R=r·1|T|) Control methods Time steps CPU time (ms) Parameters appro. min-time 176 402 affine control⋆1,639 102 MPC control 173 630 N= 1, q = 1000, r = 0.2 MPC control 185 684 N= 1, q = 1000, r = 2 MPC control 249 885 N= 1, q = 1000, r = 20 MPC control 173 1,126 N= 3, q = 1000, r = 0.2 MPC control 182 1,157 N= 3, q = 1000, r = 2 MPC control 236 1,385 N= 3, q = 1000, r = 20 MPC control 173 1,929 N= 5, q = 1000, r = 0.2 MPC control 181 2,002 N= 5, q = 1000, r = 2 MPC control 228 2,260 N= 5, q = 1000, r = 20 MPC control 173 5,099 N= 10, q = 1000, r = 0.2 MPC control 180 5,318 N= 10, q = 1000, r = 2 MPC control 219 5,816 N= 10, q = 1000, r = 20 ⋆The affine control is not designed for minimum-time control, and there may exist many optimizing parameters, but it is not clear how to choose one to minimize the time. Here, no optimizing parameter is used. We can observe in this example that in the case of reaching mf1from m01, the approaching minimum-time controller gives a number of time steps slightly larger than that of the MPC controller; but its computational cost is less. However, in the case of reaching mf2from m02(Table 3.3), the approaching minimum-time controller does not work very well. Because in this approach, between each pair 44 3.4. Previous centralized control methods Table 3.3: Simulation results of reaching mf2from m02, in the net system of Fig. 3.3 (for the MPC control, the weight matrix Q=q·1|P|,R=r·1|T|) Control methods Time steps CPU time (ms) Parameters appro. min-time 1,076 490 affine control⋆6,454 356 MPC control 490 1,833 N= 1, q = 1000, r = 0.2 MPC control 486 1,811 N= 1, q = 1000, r = 2 MPC control 517 1,880 N= 1, q = 1000, r = 20 MPC control 493 3,203 N= 3, q = 1000, r = 0.2 MPC control 492 3,193 N= 3, q = 1000, r = 2 MPC control 514 3,214 N= 3, q = 1000, r = 20 MPC control 493 5,565 N= 5, q = 1000, r = 0.2 MPC control 494 5,572 N= 5, q = 1000, r = 2 MPC control 512 5,571 N= 5, q = 1000, r = 20 MPC control 492 14,916 N= 10, q = 1000, r = 0.2 MPC control 493 14,887 N= 10, q = 1000, r = 2 MPC control 509 14,962 N= 10, q = 1000, r = 20 ⋆The affine control is not designed for minimum-time control, and there may exist many optimizing parameters, but it is not clear how to choose one to minimize the time. Here, no optimizing parameter is used. of adjacent states of the trajectory the firing speed is constant and determined by the one with smaller flow; therefore, if one of the states has very small flow (in this case, the initial one), the time spent for reaching mfcould be large. The affine controller costs more time steps to reach the final state, because it is not designed for the minimum-time control. For the MPC controller, both Tables show that a small number of time steps could be obtained by using a large weight for matrix Q and a small weight for R. We should also notice that the MPC controller is not designed for minimum-time evolution either, and using a larger time horizon Ndoes not guarantee a smaller time to reach the final state. Now let us consider a larger net system in Fig. 2.6 that we have discussed in Section 2.4. We assume a positive initial state (required by the control methods) that each of the emptied place in Fig. 2.6 has marking equal to 0.1, and for the other places we keep their markings as in Fig. 2.6. Let us assume that we want to reach a final state that obtains the maximal flow ψ= 0.13 (computed by solving a LPP similar to (3.1)), mf= [18.78 0.39 0.13 0.52 0.16 0.29 13.65 0.39 0.13 0.65 0.13 0.13 0.58 0.52 0.97 0.13 0.26 0.13]T. The simulation results are shown in Table 3.4. As we have already mentioned, in affine control the number of vertices increases exponentially with respect to the number of dimensions that is determined by the number of places; therefore its computational complexity may easily be intractable. In the PC that we do the simulation, the computational cost of the affine controller is intractable for the net system of Fig. 2.6 . In this example, the smallest number 45 Chapter 4. Centralized Control: ON/OFF Based Methods 4 p1 t1 p2 t2 p3 t4 p4 t5 2 2 p5 t3 t6 Figure 4.1: A non-CF Petri net system 0. Since C·(σ12 +α·x) = 0 and σ12 +α·x≥0, it is a T-semiflow. Therefore, there exists β > 0 such that σ12 +α·x=β·x, implying σ12 = (β−α)·x. If β−α= 0 then σ1=σ2which is impossible by assumption. If β−α > 0 then σ1=σ2+ (β−α)·x>(β−α)·x. Therefore, σ1is not a minimal firing count vector. Similarly, if β−α < 0 then σ2is not a minimal firing count vector. In the sequel, we assume strongly connected and consistent CF nets. Thus, any controller driving the system to mfmust follow the minimal firing count vector plus eventually a T-semiflow. We will prove that by using the minimal firing count and applying an ON/OFF controller,mfcan be reached in minimum-time. 4.2.2 ON/OFF controller: discrete-time case As already said in Section 3.4, by sampling the continuous-time CPN system with asampling period Θ, we obtain the discrete-time TCPN ([64]) given by: mk+1 =mk+ Θ ·C·wk 0≤wk≤fk(4.3) Here mkand wk=fk−ukare the marking and controlled flow at sampling instant k, i.e., at τ=k·Θ, while fkand ukare the uncontrolled flow and control input. It is proved in [64] that if the sampling period satisfies (4.4), the interior reachability spaces of discrete-time and continuous-time CPN systems are the same. ∀p∈P:X tj∈p• λj·Θ<1 (4.4) In the sequel, we assume that the sampling period Θ is small enough to satisfy (4.4). We first develop the ON/OFF controller based on the discrete-time model, then it is naturally extended to continuous-time settings. 52 4.2. Minimum-time controller for Choice-Free nets In a CF net system, if two transitions t1and t2are enabled at the same time, the order of firing is not important (i.e., both sequence t1t2and t2t1are fireable). Based on this observation, if there exists a transition that has not fired with the maximal amount at one moment, certain amount of its firings may be moved ahead in order to reach this maximal quantity. Example 4.2.4. Let us consider the trivial CF net system in Fig. 4.2 and assume mf= [0.2 0.5 0.3]T, the minimal firing count vector for reaching the final state is σ= [0.8 0.3 0]T. Following this vector, one firing sequence may be σ1=t1(0.5)t2(0.3)t1(0.3). It can be observed that t1is 1-enabled under m0, and the required amount that t1should fire is 0.8. Therefore, we can fire t1more than 0.5in the beginning. In particular, the final marking is also reached by the firing sequence σ2=t1(0.8)t2(0.3), for example. p3 t1t3 t2 p2 p1 Figure 4.2: A trivial CF net system with m0= [1 0 0]. The strategy of the ON/OFF controller is quite simple: every transition fires as fast as possible at any moment until the required firing count σ[tj] (mf=m0+C·σ) is reached. The control input of tjat kth sampling period is: uk[tj] =                                  0 if Θ · k−1 P i=0 wi[tj] + Θ ·fk[tj]≤σ[tj] (a) fk[tj] if Θ · k−1 P i=0 wi[tj] = σ[tj] (b) fk[tj]− σ[tj]−Θ· k−1 P i=0 wi[tj] Θ if Θ · k−1 P i=0 wi[tj]<σ[tj] and (c) Θ· k−1 P i=0 wi[tj] + Θ ·f[tj]>σ[tj] (4.5) where at k= 0, Θ · k−1 P i=0 wi[tj] = 0. Remember wk=fk−uk, (a) says that before reaching the required total firing count σ[tj], we simply let transition tjto fire free (ON), i.e. uk[tj] = 0; (b) means once σ[tj] is reached, the transition is completely stopped (OFF), i.e. uk[tj] = fk[tj]; (c) represents the last firing of tj. Algorithm 1 synthesizes the ON/OFF controller, in which w0,w1,w2,... is the sequence of control inputs at the time instants. Lemma 4.2.5. Let hN,λ,m0ibe a discrete-time continuous CF net system and mf>0be a reachable final state. Among all the controllers that drive the system to 53 Chapter 4. Centralized Control: ON/OFF Based Methods Algorithm 1 ON/OFF controller Input: hN,λ,m0i,mf,σ,Θ Output: w0,w1,w2,... 1: k= 0 2: while Θ· k−1 P i=0 wi≤σdo 3: Solve the following LP P : max 1T·wk s.t. mk+1 =mk+ Θ ·C·wk 0≤Θ·wk≤σ−Θ· k−1 P i=0 wi wk[tj]≤λj·enab(tj,mk),∀tj∈T (4.6) 4: Apply wk:mk+1 =mk+ Θ ·C·wk 5: k:= k+ 1 6: end while 7: return w0,w1,w2,... mfby firing σ, i.e., mf=m0+C·σ, the ON/OFF controller costs the minimumtime. Proof: Assume an arbitrary non ON/OFF controller G. Hence, at a sampling period kthere exists a transition tjthat is not sufficiently fired, i.e., not fired as much as possible. In other words, tjhas to fire later in a sampling period l,l > k. Let us assume, without loss of generality, that tjdoes not fire between the kth and the lth sampling periods. It is always possible to “move” some amounts of its firings from the lth sampling period to the kth one until tjbecomes sufficiently fired in k. According to the persistency property of CF nets, this move is not reducing the enabling degree of the other transitions. Iterating the procedure, all transitions can be sufficiently fired in all sampling periods and the obtained controller is an ON/OFF one. Obviously, the number of discrete-time periods required to reach the final marking after moving firings from a sampling period lto another one kwith k≤lis at least the same. Hence the number of sampling steps of the ON/OFF controller is not more than the one of controller G, i.e., the ON/OFF controller costs the minimum time. Lemma 4.2.5 only holds for CF nets. For a net system that is not CF, the ON/OFF controller may be not a minimum-time controller for a given σ, and in the worst case, the final state may not be reached, i.e., the stability is not guaranteed (see Ex. 4.3.1 for an example, in which the (reachable) final state cannot be reached by applying the ON/OFF controller using the given σ.) Lemma 4.2.6. Let hN,λ,m0ibe a discrete-time continuous CF net system, σ 54 4.2. Minimum-time controller for Choice-Free nets and σ′be firing count vectors, such that σ≤σ′and they both drive the system to mf>0, i.e., mf=m0+C·σand mf=m0+C·σ′. By using the ON/OFF controller, firing σ′costs at least the time of firing σ. Proof: If firing σ′costs less time than firing σ, there must exist at least a transition tj, such that firing σ′[tj] costs less time than firing σ[tj]. We will prove that it is not possible. Since by firing σ′and σthe same final state is reached, σ′[tj]≥σ[tj] implies that in the case of firing σ′, more tokens should be put into each of its input place pi∈•tj(with the quantity of P re[pi, tj]·(σ′[tj]−σ[tj])), and later they are all moved out (by firing tj). Remember that tjis the unique output transition of pi (the net is CF), so the time spent for moving out this quantity of tokens depends only on tj; and since this quantity of tokens have to be moved out, they do not contribute to the firing of σ[tj] (they do not make σ[tj] firing faster). Therefore, firing σ′[tj] cannot cost less time than firing σ[tj]. Lemma 4.2.6 holds also only for CF nets. Let us consider the following simple example: Example 4.2.7. Assume that in the non-CF net system in Fig. 4.3 the firing rate vector is λ=[1 0.01 1 1 1]T, the sampling period is Θ=0.1, and we want to reach a final state mf=[0 0.5 0.5 4]T.mfcan be reached, for example, by using σ= [0 0.5 0 0 0]Tor σ′=[0 0.5 0 4 4]T. Although σ≤σ′, we can verify that if we apply the ON/OFF controller using σthe final state is reached in 692 time steps; if we we apply the ON/OFF controller using σ′the final state is reached in only 673 time steps. In the case of σ, only t2fires, so the time used for the firing of σ[t2] determines the time to reach the final state. In the case of σ′, transitions t4and t5 also fire (an additional T-semiflow [0 0 0 1 1]Tis fired). By firing t4we can increase the marking of p2(at some time instants, later this increased quantity of marking is moved back to p4by firing t5), so t2fires faster; on the other hand, since the firing rate of t2is much smaller than the others, the firing of σ′[t2]still determines the total time to reach mf. Therefore, the final state is reached faster in the case of firing σ′. On the other hand, even for CF nets, given σ≤σ′,mf=m0+C·σand mf′=m0+C·σ′, if mf6=mf′, by applying the ON/OFF controller, reaching mf′with σ′may be faster than reaching mfwith σ. Example 4.2.8. Let us consider again the trivial MG (a subclass of CF) in Fig. 4.2 of Ex. 4.2.4. Now assume that m0=[1 1 0]T;λ=[10 1 1]T; and sampling period is Θ = 0.01. Given σ=[0 0.5 0]Tand σ′=[0.5 0.5 0]T(σ≤σ′), by using the ON/OFF controller, σis fired in 69 time steps ([1 0.5 0.5]Tis reached) and σ′ is fired in only 42 time steps ([0.5 1 0.5]Tis reached). Proposition 4.2.9. Let hN ,λ,m0ibe a consistent and strongly connected discretetime continuous CF net system and σ≥0be a firing count vector driving the system 55 Chapter 4. Centralized Control: ON/OFF Based Methods p1 t1 t3 1 p2 p3 t2 4 t4 t5 p4 Figure 4.3: A simple non-CF net (a state machine): by using the ON/OFF controller, firing σmay cost more time than firing σ′≥σ to mf>0, i.e., mf=m0+C·σ. The ON/OFF controller is a minimum-time controller driving the system to mfif σis the minimal firing count vector. Proof: In consistent and strongly connected CF nets, there exist a unique minimal firing count vector and a unique minimal T-semiflow x>0 [93], hence for any other firing count vector σ′6=σthat drives the system to mfwe must have σ′= σ+α·x>σ,α > 0. According to Lemma 4.2.5 and 4.2.6, the results can be derived straightforwardly. Remark 4.2.10. When the final state mfhas been reached by applying the ON/OFF controller, all the transitions are stopped. If mfis an equilibrium point, it can be maintained by using an appropriated control uk, such that C·wk= 0. 4.2.3 ON/OFF controller: continuous-time case By taking the sampling period Θ →0, the ON/OFF controller can be easily extended to the continuous time setting, the control input for transition tjat time τis given by: u(τ)[tj] = (0 if Rτ− 0w(δ)[tj] dδ < σ[tj] (ON) (a) f(τ)[tj] if Rτ− 0w(δ)[tj] dδ=σ[tj] (OFF ) (b)(4.7) where σis the minimal firing count vector and w(δ)[tj] is the controlled flow of tj at time δ;f(τ)[tj] is the uncontrolled flow at time τ. It should be noticed that for continuous timed systems under infinite server semantics, once a place is marked it will take infinite time to be emptied (like the discharging of a capacitor in an electrical RC-circuit). Therefore, if there exist places that are emptied during the trajectory to mf, the final marking is reached at the limit, i.e., in infinite time. If mf>0 and use the proposed control method, this situation does not happen. 56 4.2. Minimum-time controller for Choice-Free nets One main advantage of the ON/OFF control strategy is its low computational complexity. Given a (minimal) firing count vector (that can be computed in polynomial time), the control actions can be obtained by solving a simple LPP (also in polynomial time) in each time step. On the other hand, the minimum-time state evolution is guaranteed. Although the ON/OFF is only proposed for CF nets, we can also guarantee its convergence to the final state if the system is Join-Free (JF) and conservative. But now it cannot ensure a minimum-time evolution to mfin general. Proposition 4.2.11. Let hN ,λ,m0ibe a conservative Join-Free TCPN system and σ≥0be a firing count vector diving the system to mf>0, i.e., mf=m0+C·σ. By applying the ON/OFF controller, the system state converges to mfin finite time. Proof: We prove it by contradiction. Assume that the system reaches a state mand m6=mf. Therefore, there must exist a transition tjthat cannot reach its accumulative firing upper bound σ[tj]. Since the system is JF, tjcan fire if its unique input place piis not emptied, it implies that m[pi] = 0. For any other place p′ isuch that its output transitions fire completely the firing amounts give by σ, it holds m[p′ i]≤mf[p′ i] because the firing of every transition is upper bounded by σand mf=m0+C·σ. Therefore, for any place p∈Pit holds m[p]≤mf[p] and there exists at least one place pi∈P, such that m[pi] = 0 <mf[pi]. This contradicts the conservativeness of the net. Remark 4.2.12. Let us notice that in the standard ON/OFF controller proposed here, we do not necessarily require a positive initial marking. However, it is needed for the extended controllers for general nets that will be presented in Sections 4.4. 4.2.4 A case study Let us consider the net system in Fig. 4.4, which models a table factory system (taken from [93]). The system consists of several parts, including board maker, leg maker, assembler, painting line. Assume that in the initial marking m0[p1] = m0[p2] = m0[p3] = m0[p4] = 1, m0[p6] = m0[p8] = m0[p10] = m0[p12] = m0[p16] = m0[p19] = 0.5, and the other places are empty; in the final marking mf[p3] = mf[p17] = 0.1, mf[p4] = mf[p5] = 0.2, mf[p13] = 0.15, and all the other places with markings equal to 0.25. The corresponding minimal firing count vector σ= [0.85 0.85 1.0 0.9 0.6 0.6 0.75 0.65 0.45 0.2 0.35 0.10]T. Fig. 4.5 shows the stopping time instants of transitions when the ON/OFF controller is applied. After t9is stopped at 4.28 time units, the markings of all the places are at the final state values. 57 Chapter 4. Centralized Control: ON/OFF Based Methods 0.5 t1 p1 p2 p3 p4 0.5 0.5 0.5 0.5 0.5 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 p15 p16 p17 p18 p19 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 Other factory Board maker Old Legmaker New legmaker Assembler Painting line 2 4 2 Figure 4.4: The CF net model (weighted T-system) of a table factory system. The firing rate of every transition is equal to 1. Figure 4.5: Transitions’ stopping time instants obtained by applying the ON/OFF controller to the CF system in Fig. 4.4 Fig. 4.6 shows the marking trajectory of places p3,p13,p14 and p17. For instance, the marking of place p17 depends on transitions t5,t10 and t11, which are stopped at 2.9, 3.24 and 4.19 time units, respectively. When t11 stops, p17 also reaches its final state, at 4.19 time units. 58 4.3. Drawbacks of the ON/OFF controller for general nets Figure 4.6: Marking trajectories of applying the ON/OFF controller to the CF system in Fig. 4.4 4.3 Drawbacks of the ON/OFF controller for general nets In general net systems, multiple minimal firing count vectors may exist. Therefore it is not clear which one gives the minimum-time by using the ON/OFF controller (moreover, minimum-time may be with a non-minimal firing count vector). On the other hand, the convergence of the final state may not be ensured: in the case of non-CF nets, conflicts (|p•|>1) may appear, thus firing faster one transition may reduce the firing of another transition, and the overall time for reaching mfmay increase, being infinity in the extreme case. The following example shows a live and bounded system, in which by applying the ON/OFF strategy, the final state cannot be reached. Example 4.3.1. Assume we want to drive the system in Fig.4.7 to final state mf= [0.5 0.5 0.5 0.5 0.2 0.4 1.4]T, the firing rate of t3is 10, while the firing rates of other transitions are all set to 1. σ=[0.8 1.3 0.5 0 1 0 0]Tis a minimal firing count vector driving the system from m0(shown in the figure) to mf. By using this setting and applying the ON/OFF controller, mfcannot be reached and the system will be “blocked” in an intermediate marking m=[1 0 0.78 0.22 0 0 2]T. Notice that, this “blocking” situation is imposed by the controller. For instance, transition t7is actually enabled at m, but the control law has forbidden its firing because σ[t7] = 0. One may think that deadlock-freeness is a sufficient condition for applying the ON/OFF controller to a general net system. But we should notice that, the control laws may forbid the firings of some transitions (like in Ex.4.3.1, the firing of t7is forbidden because σ[t7] = 0), bringing the system to some “blocking” situations. 59 Chapter 4. Centralized Control: ON/OFF Based Methods p4 p1 p5 p2 p3 0.1 p6 1.9 p7 t7 t1t2t3t4 t5 t6 2 Figure 4.7: A live and bounded CPN system that the ON/OFF controller brings to a “deadlock” situation if λ3≫λ2 4.4 Extended ON/OFF based methods Because the ON/OFF controller cannot be directly applied to general TCPNs, three heuristic extensions are proposed: ON/OFF+, B-ON/OFF and MPC-ON/OFF. In all the methods the convergence to the final state is always guaranteed, although we may not obtain a minimum-time state evolution. The ON/OFF+ overcomes the problem of the standard ON/OFF controller by forcing proportional firings of conflicting transitions; B-ON/OFF is proposed to handle those bad cases of applying the ON/OFF+ controller; the MPC-ON/OFF controller has higher computational complexity, but may lead to better solutions, i.e., solutions that need less time to reach the final state. 4.4.1 ON/OFF+ controller The problem of the ON/OFF controller arises from “inappropriate” manners of solving the conflicts (e.g., in the system of Fig. 4.7, since λ3≫λ2,t3fires much faster than t2). Two transitions taand tbare in a structural conflict relation if •ta∩•tb6=∅. The coupled conflict relation is its transitive closure. For example, in the net shown in Fig. 4.7, the sets of places in coupled conflict relation are {t1},{t4},{t2, t3}and {t5, t6, t7}. In the sequel, let us denote by Tpthe set of persistent transitions (transitions that are not in any conflict relation) and Tcthe set of transitions in any coupled conflict relation, Tp∩Tc=∅, Tp∪Tc=T. In order to overcome this problem, we consider a more “fair” strategy to solve the conflicts: forcing the flows of transitions that are in coupled conflict relation to be proportional to the given firing count vector. Meanwhile, for the rest of (persistent) transitions the ON/OFF strategy is applied. The modified ON/OFF controller is shown in Algorithm 2 and we will call it ON/OFF+ controller. The procedure of the ON/OFF+ controller is similar to the one of the standard ON/OFF, except the last constraint of LPP (4.8) in the step 3 of Algorithm 2, which 60 4.4. Extended ON/OFF based methods Algorithm 2 ON/OFF+ controller Input: hN,λ,m0i,mf,σ, Θ Output: w0,w1,w2,... 1: k←0 2: while Θ· k−1 P i=0 wi6=σdo 3: Solve the following LPP: max 1T·wk s.t. mk+1 =mk+ Θ ·C·wk 0≤Θ·wk≤σ−Θ· k−1 P i=0 wi wk[tj]≤λj·enab(tj,mk),∀tj∈T mk+1 ≥0 wk[ta]·σ[tb] = wk[tb]·σ[ta] ∀ta, tb,•ta∩•tb6=∅and σ[ta]>0,σ[tb]>0 (4.8) 4: Apply wk:mk+1 ←mk+ Θ ·C·wk 5: k←k+ 1 6: end while 7: return w0,w1,w2,... means that, at any time step k, if transitions taand tbare in conflict, the following will be forced: wk[ta] wk[tb]=σ[ta] σ[tb]. Since we need positive flows (wk[tb]>0), in the sequel we assume an initial state m0>0. Also Notice that, only transitions with positive values in the corresponding firing count vector should be considered. In order to prove the convergence, we first show that by using some reduction rules, the original system with the ON/OFF+ controller is equivalent to a CF net system with a particular controller A, i.e., the same state trajectory can be obtained. Then, we prove that controller Adrives the CF net system to mf, implying that the ON/OFF+ controller also drives the original one to mf. Reduction Rule. Given a net N=hP, T, P re,P osti, let Tj={t1, t2, ..., tn} ⊆ T be a set of transitions that are in coupled conflict relation. These transitions fire proportionally according to a given firing count vector σ, i.e., for any ta, tb∈ Tj,σ[ta],σ[tb]>0, if tafires in an amount sa, simultaneously, tbfires in an amount sb, such that sa sb=σ[ta] σ[tb]. Let ¯σ=Pt∈Tjσ[t],Nis transformed to N′= hP, T′,P re′,P ost′iin the following way: (1) T′=T\Tj (2) Merge Tjto a new transition tj,T′=T′∪ {tj} (3) ∀p∈•Tj,P re′[p, tj] = P t∈p• P re[p, t]·σ[t]/¯σ 61 Chapter 4. Centralized Control: ON/OFF Based Methods the performance of Algorithm 3. In particular, we suggest using a small d, because if dis too large, the controller is not “sensitive” to the difference between “faster” and “slower” transitions, thus it is similar to applying the ON/OFF+ strategy. In the example of Section 4.4.5, we use d≤10 and reasonable results are obtained. 4.4.3 MPC-ON/OFF controller Both the ON/OFF+ and B-ON/OFF controllers are using some “greedy strategies” to fire transitions, they solve the conflict based on the flows and the required firing counts in a current time step, without a “careful looking at the future”. In this section, we combine the ON/OFF strategy with Model Predictive Control (MPC), obtaining the MPC-ON/OFF controller. MPC has been widely applied in the industry for controlling complex dynamic systems. By solving a discrete-time optimal control problem over a given time horizon, an optimal open-loop control input sequence is obtained and the first one is applied. Then at the next time step, a new optimal control problem is solved. In [64], the MPC scheme is applied to the control of TCPNs, by solving the following optimization problem (3.5) at each time step, with cost function J(mk, N) (3.6): MPC is usually used for optimizing trajectories subject to certain constraints. In our problem, the aim is to reach mfas soon as possible, i.e., minimizing the time. Although it is difficult to obtain a minimum-time control by using a MPC approach, we will consider this method for transitions in conflicts while for the others we use a similar ON/OFF strategy. We may obtain smaller number of time steps than those of the ON/OFF+ or B-ON/OFF controller, particularly with large time horizon N (even if an improvement is not guaranteed by using a larger N), what means with higher computational complexity. The MPC-ON/OFF controller is synthesized in Algorithm 4. Algorithm 4 MPC-ON/OFF controller Input: hN,λ,m0i,mf,σ, Θ, Q,R,N ǫ,ζ Output: w0,w1,w2,... 1: k←0 2: σk←σ 3: while mk6=mfdo 4: Solve problem (4.13) 5: Apply wk:mk+1 ←mk+ Θ ·C·wk 6: σk+1 ←σk−Θ·wk 7: k←k+ 1 8: end while 9: return w0,w1,w2,... 68 4.4. Extended ON/OFF based methods The problem that should be solved at each time step kis: min J(mk, N) s.t. :mk+j+1 =mk+j+ Θ ·C·wk+j, j = 0, ..., N −1 (4.13a) G·wk+j mk+j≤0, j = 0, ..., N −1 (4.13b) wk+j≥0, j = 0, ..., N −1 (4.13c) Θ· N−1 X j=0 wk+j≤σk(4.13d) mk+1 ≥1·ǫ(4.13e) 1T·wk≥ζ(4.13f) where ǫand ζare sufficient small positive numbers and σkis the remaining firing count vector that should be fired. Constraint mk+1 ≥1·ǫ(4.13e) ensures that the system only evolves inside an interior region of the reachability space; in order to include m0and mfin that region, it should hold mf≥1·ǫand m0≥1·ǫ. Constraint 1T·wk≥ζ(4.13f) forces a non-zero flow in the first predictive step. For our specific problem, we use the following assumptions: (A1) m0,mf>0. (A2) Q∈R|P|≥0 are positive definite matrices. (A3) R∈R|T| ≥0is a diagonal matrix, such that if tj∈Tp,R[j, j]>0, otherwise R[j, j] = 0. We define the cost function as: J(mk, N) = N X j=0 [(mk+j−mf)′·Q·(mk+j−mf)] −w′ k·R·wk By means of the item −w′ k·R·wkin the cost function and choosing large values for R[j, j], tj∈Tp, we try to fire the persistent transitions as fast as possible, similarly to applying the ON/OFF strategy. Now, we will prove that the asymptotic stability holds. Proposition 4.4.10. Let hN,λ,m0ibe a TCPN system with m0>0. Let mf>0 be a reachable final marking, such that mf=m0+C·σ. Assume that the system is controlled by using the MPC-ON/OFF controller shown in Algorithm 4, and assumptions (A1)–(A3) are satisfied. Then the closed-loop system is asymptotically stable. Proof: We will define a Lyapunov function and prove that it is strictly decreasing. Let V(mk) = 1T·(σ−Θ·Pk i=0 wi), where wkis the controlled flow at time step kand Θ is the sampling period. According to constraint (4.13d), the accumulative 69 Chapter 4. Centralized Control: ON/OFF Based Methods firing count is upper bounded by σ. Therefore, V(mk)≥0and V(mk)6= 0 until σ= Θ ·Pk i=0 wi, i.e., until mk=mf. Now we need to prove that V(mk) is strictly decreasing, and it is equivalent to prove that wk6= 0 until σis reached. Considering the last constraint (4.13f), we only need to prove that problem (4.13) is feasible until mfis reached. Assume that the system is at time step kwith marking mk6=mf, according to constraint (4.13e), we have mk>0. Let us denote by σ′the firing count vector that has been fired. It is clear that σ′≤σ, therefore, σ−σ′≥0 and: mf=mk+C·(σ−σ′)>0 (4.14) so mfis reachable from mk>0 [49]. Since the net is consistent, the marking of the system is able to move from mkin any direction (may be a small movement) inside the reachability space. Therefore, if ζis small enough, we can always find a solution of problem (4.13) in which mk+1 is, for example, on the straight line from mkto mf. 4.4.4 Initial Comparisons In order to have a good “guess” of selecting the most appropriate technique for a given system, several qualitative properties may be taken into account. Table 4.1 shows some qualitative characteristics of the already mentioned control methods. Apart from the methods proposed in this Chapter, another heuristics proposed in [5] for minimum-time control of TCPNs is also included in the comparison. Table 4.1: Qualitative characteristics of several control methods that all ensure the stability (assuming m0>0, mf>0). Methods Subclass Computational issues Optimizing index Approaching minimum-time [5] All A BPP for each intermediate state Heuristic Min. Time ON/OFF CF a LPP in each time step Min. time ON-OFF+ All a LPP in each time step Heuristic Min. Time B-ON/OFF All a LPP in each time step Heuristic Min. Time MPC-ON/OFF All a QPP in each time step Heuristic Min. Time The ON/OFF controller is particularly suitable for the minimum-time control of CF nets, while all the other methods can be applied to general net systems. For the ON/OFF, ON/OFF+ and B-ON/OFF controllers, in each step only a LPP 70 4.4. Extended ON/OFF based methods needs to be solved, therefore those methods have very low computational complexity. Nevertheless, for the MPC-ON/OFF controller, the number of variables also depends on the time horizon N, being computationally expensive if Nis large. The approaching minimum-time controller [5] also has high computational complexity, since bilinear programming problems (BPPs) have to be solved when intermediate states are added to the trajectory for decreasing the duration of the evolution. 4.4.5 A case study In this section, we apply different control methods to the CPN model of an assembly system using different settings. The simulations are performed on a PC with Intel(R) Core(TM)2 Quad CPU Q9400 @ 2.66GHz, 3.24GB of RAM. More case studies are in Chapter 8. The system model in Fig. 4.11 represents an assembly system. There are two kinds of input raw materials stored in p1and p2. The material A, B are first processed by Proc A1, then the obtained semi-products are further processed by Proc A2 and Proc A3. In the other processing line, material B is sequentially processed by Proc B1 and Proc B2. Then final produces are obtained after assembling all the semi-products. t1 p1 0.4 3 0.1 0.1 0.5 0.1 5 0.1 2 p2 p3p4 p5p6p7p9 p8 t2 t3t4t5 t6 t7 2 IN_A IN_B Proc_A1 Proc_A2 Proc_A3 Proc_B1 Proc_B2 Assemble Figure 4.11: The TCPN model of an assembly system. It is assumed that the firing rate of t2is 4, while for the other transitions, they are equal to 1. The simulations are performed under four different settings, in which setting s.1) and setting s.2) have different initial and final states, but the same firing count vector is used; setting s.3) uses the same initial marking as in s.1), but a different final state (therefore a different firing count vector) is considered.; the difference between setting s.3) and setting s.4) is that, for the places with markings smaller than 1 in s.3), their markings are increased by 1 in s.4), while the same firing count vectors are used in both cases. 71 Chapter 4. Centralized Control: ON/OFF Based Methods s.1) Θ = 0.01, m0= [1 2 0.4 0.5 0.1 0.1 0.1 5 0.1]T,mf= [0.6 1.8 0.7 0.2 0.2 0.5 0.3 4.7 0.4]T,σ= [0.4 0 0.2 0.5 0.3 0.1 0]T; s.2) Θ = 0.01, m0= [1 2 0.001 0.5 0.1 0.1 0.1 5 0.1]T,mf= [0.6 1.8 0.301 0.2 0.2 0.5 0.3 4.7 0.4]T,σ= [0.4 0 0.2 0.5 0.3 0.1 0]T; s.3) Θ = 0.1, m0= [1 2 0.4 0.5 0.1 0.1 0.1 5 0.1]T,mf= [0.6 1.8 0.7 0.2 0.2 0.5 0.3 3 2.1]T,σ= [2.1 1.7 1.9 2.2 2 1.8 0]T. s.4) Θ = 0.02, m0= [1 2 1.4 1.5 1.1 1.1 1.1 5 1.1]T,mf=[0.6 1.8 1.7 1.2 1.2 1.5 1.3 3 3.1]T,σ= [2.1 1.7 1.9 2.2 2 1.8 0]T. The simulation results are shown in Table A.1–A.4 in the Appendix (for the BON/OFF controller, smaller numbers of time steps are usually obtained with smaller values of d. In the case that the numbers of time steps of using the ON/OFF+ controller cannot be reduced by using the B-ON/OFF controller, the result is not sensitive to d. For the MPC-ON/OFF controller, although in some cases the numbers of time steps are not very sensitive to the weights on matrix Rand Q, we suggest to use larger weights on matrix Rand smaller weights on matrix Q; we may slightly reduce the time steps with larger N, but at the same time, the computational costs grows fast with respect to N). In Table 4.2, we summarize the smallest numbers of time steps that obtained by using different control methods, and the corresponding parameters. From the aspect of the number of time steps spent to reach the final state, the B-ON/OFF controller gives the best result in most of the cases (it is the best for setting s.1) (Table A.1) and setting s.2) (Table A.2), and close to the best in setting s.3) (Table A.3) and setting s.4) (Table A.4); usually smaller dlead to smaller numbers of time steps. The ON/OFF+ controller also gives quite small number of time steps, except in setting s.2). This is because that there are four transitions, t1,t2,t3and t4, in coupled conflict relation and in setting setting s.2), the initial marking of place p3is much smaller than those of p1and p2, therefore the flows of t3and t4are much smaller than those of t1and t2. As we have discussed in previous sections, in the case of conflicting transitions with very different flows, the overall system may be highly slowed down by applying ON/OFF+ controller. The approaching minimum-time controller does not give smaller numbers of time steps comparing with the other controllers, except in setting s.4). The reason is what we have already mentioned before: the performance (with respect to the time) of the approaching minimum-time controller highly depends on the initial state of the system, if there exist places with very small initial markings, the time to reach the final state could be large. Regarding the MPC-ON/OFF controller, the numbers of time steps are not far from the best among other control methods, even the best in setting s.3). We can also observe that, usually with larger time horizon Nwe could obtain smaller number of time steps (in setting s.2), s.3) and s.4)); but it is not guaranteed, for example the smallest time step in setting s.4) is obtained with N= 1. On the other hand, with larger weights to the matrix R(i.e., putting more 72 4.4. Extended ON/OFF based methods Table 4.2: The smallest numbers of time steps of using different control methods among different parameters (if exist), derived from Table A.1–A.4. For the MPCON/OFF controller, the weight matrix Q=q·I|P|,R[j, j] = r, ∀tj∈Tp. Control methods Time steps CPU time (ms) Parameters appro. min-time 101 847 ON/OFF+ 94 41 s.1) B-ON/OFF 91 136 d= 2 (or 1) MPC-ON/OFF 91 955 N= 1, r=1000, q= 1 (or 100, 1000) MPC-ON/OFF 91 50,784 N= 5, r= 1000, q= 1 appro. min-time 176 465 s.2) ON/OFF+ 954 410 B-ON/OFF 132 192 d= 2 (or 1) MPC-ON/OFF 145 16,240 N= 5, r= 1000, q= 1 appro. min-time 94 352 s.3) ON/OFF+ 76 34 B-ON/OFF 76 115 d=20 (or 15, 10) MPC-ON/OFF 75 52,803 N= 10, r=1000, q=1000 appro. min-time 122 2,546 s.4) ON/OFF+ 126 55 B-ON/OFF 126 195 d= 20 (or 15, 10) MPC-ON/OFF 125 90,781 N= 10, r=1000, q=1 weight on the flow of persistent transitions), we often obtain a smaller number of the time steps. From the computational costs point of view, the ON/OFF+ controller gives lowest consumed CPU time, except in setting s.2). The B-ON/OFF controller also has very low computational costs, slightly higher than that of the ON/OFF+ controller because an estimation of number of time steps should be computed. The approaching minimum-time controller usually costs more CPU time to compute the control low than the ON/OFF+ and B-ON/OFF controller, because a BPP problem needs to be solved whenever an intermediate point is added to the trajectory to improve the time. The most computationally expensive method here is the MPC-ON/OFF controller: a QPP should be solved in each time steps and with larger Nits computational costs increase fast. Notice that we have shown the results of different methods for a particular example with different settings, however, the number of time steps required for reaching the final state may depend on many variables, such as net structures, firing rates, initial/final state. More comparisons using different examples are presented in Chapter 8. 73 Chapter 4. Centralized Control: ON/OFF Based Methods 4.5 Computation of minimum-time control laws Assume that by applying one of the ON/OFF (based) controllers, we reach the final state in hsteps. For a general PN system, usually it does not give a minimumtime control law (see Ex. 4.4.5 for an example). However, after the application of the ON/OFF (based) method and reaching the final state in hsteps, one may be interested in computing (or knowing) the minimum number of time steps. This can be computed by applying Algorithm 5. The idea of the algorithm is the following: because we already know that mf can be reached in hsteps, now we verify if mfcan also be reached in k=h−1 steps, by solving LPP (4.15). If a control law is found, then we decrease kagain and check if mfcan still be reached; repeat this process until we find a ksuch that mfcannot be reached, then the minimum number of time steps to reach mfis k+1. Instead of a sequential decreasing of kwe may apply different approaches (e.g., binary search algorithms) to “search” for the minimum-time control laws. However, the problem is that the computational complexity of this kind of method may become intractable in practice when the system is large or his very large. Algorithm 5 Computation of minimum-time control laws Input: hN,λ,m0i,mf, Θ Output: w0,w1,w2,... 1: Apply one of the ON/OFF based controllers 2: W={w0,w1,w2,...,wh−1},Wlast =∅ 3: k=h 4: repeat 5: k=k−1 6: Solve the following problem: min Z =||mk−mf||1 s.t. mi+1 =mi+ Θ ·C·wi, i = 0,1, ..., k −1 wi[tj]≤λj·enab(tj,mi),∀tj∈T, i = 0, ..., k −1 wi≥0, i = 0, ..., k −1 (4.15) 7: if Z= 0 then 8: Wlast =W 9: W={w0,w1... wk−1} 10: end if 11: until Z6= 0 12: return W Remark 4.5.1. In problem 4.15, the minimization of ||mk−mf||1can be turned into a LPP by introducing a new variable vwith constraints v≥mk−mf,v≥ −(mk−mf), then solving the problem by minimizing 1T·v. 74 4.6. Conclusions 4.6 Conclusions The time spent on the trajectory and the computational complexity of control synthesis are naturally important for the targeting control problem that we address in this thesis. In this chapter we develop several controllers for TCPNs under infinite server semantics, based on the ON/OFF strategy, which frequently arises in minimum-time problem. The basic idea is to fire transitions as fast as possible until a upper bound is reached. This upper bound is specified by a given firing count vector that brings the system to its desired final state. The final state, if an equilibrium point, can be maintained by using proper control inputs. We first prove that for CF net systems, the standard ON/OFF controller ensures minimum-time evolution. For a general net system, we only obtain heuristic minimum-time by using one of the extended ON/OFF methods—additional techniques for solving conflicts are used. Low computational complexity is a main advantage of our methods. We can see from Table 4.2 that, the ON/OFF+ and B-ON/OFF controllers have much lower computational costs than the approaching minimum-time controller. By applying the proposed methods, we obtain a reasonable trade-off on quality vs computational complexity: relatively small numbers of time steps for reaching the final state and acceptable computational costs. 75 Chapter 4. Centralized Control: ON/OFF Based Methods 76 Chapter 5 Decentralized Control of CF nets: ON/OFF Based Methods In this chapter, decentralized methods for the target marking control problem of TCPNs are studied. Here, we assume nets to be Choice-Free; they are cut into disjoint subnets through a set of buffer places. Due to the disconnection of subsystems, different behaviors may appear. In order to overcome this problem, we propose two reduction rules to obtain an abstraction of the missing part of each disconnected subsystem. The abstractions are then used to complement the subsystems; in this way, the behaviors (firing sequences) of the original system are preserved. Algorithms are proposed to make an agreement among those local control laws computed separately in complemented subsystems, because they may be not globally admissible considering the states of the buffer places. After that, the minimum-time ON/OFF controller presented in Section 4 can be implemented independently in subsystems. 77 Chapter 5. Decentralized Control of CF nets: ON/OFF Based Methods to1(α4), and its projection to the reduced system S′is ς=ti1(α1)ti2(α2)tom 1(α3) to1(α4). For other transitions, since the gains of all paths between transition should be reserved according the reduction rules, consider tim 1is similar to consider ti1, putting tokens to pi1with different weights; for the same reason, consider tim 2is similar to consider ti2. If tjfires tokens are put into po1and po2at the same time just with different weights, so consider transition to1is similar to consider to2. In S, let π1={ti1,pi1,tj,po1,to1}and π2={ti2,pi2,tj,po1,to1}; In S′, let π′ 1and π′ 2be the paths corresponding to the same transitions as π1,π2, respectively, i.e., π′ 1={ti1,p1 1,to1}and π′ 2={ti2,p2 1,to1}. Let us first consider a subsequence of σ,σ1=ti1(α1)ti2(α2)tj(β)tom 1(α3), and its corresponding projection to S′,ς1=ti1(α1)ti2(α2)tom 1(α3). Obviously, σ1is fireable in Siff ς1is fireable in S′because transitions ti1,ti2and tom 1have the same input places and corresponding markings in Sand S′. In S, if tjfires with the maximal amount in σ1,to1will get the maximal enabling degree. Therefore by firing σ1, the enabling degree of to1can be maximally increased by: φ= min{α1·G(π1) + α3·w7 w11 , α2·G(π2) + α3·w7 w11 } Considering the initial marking m0, the maximal enabling degree of to1by firing of σ1is: min {G(π1)·M(π1,m0), G(π2)·M(π2,m0)}+φ In S′, the enabling degree of to1under the initial marking is equal to: min m0′[p11] g10 ,m0′[p21] g12  According to according the reduction step (4), it is equal to min g2·M(π1,m0) g10 ,g5·M(π2,m0) g12  = min{G(π1)·M(π1,m0), G(π2)·M(π2,m0)} By the firing of ς1, it is increased by the same amount φas in S, because G(πi) = G(π′ i), i= 1,2 and w7/w11 =g9/g10 =g11/g12. Therefore, if σis fireable in S,ςis for sure fireable in S′. The other direction, if ςis fireable in S′,σis fireable in Swhen the intermediate transition tjfires in the maximal amount. A similar proof can be achieved for any firing sequence following the procedure: 1) any sequence that consists of the transitions whose input places are the same in Sand S′(like ti1, ti2in Fig.5.4), is fireable in Siff its projection in S′is fireable; 2) any other transitions (like to1, to2in Fig.5.4) can get the same enabling degrees in Sand S′, when sequences in 1) fire. Remark 5.3.8. It can be observed that, each time T-RR is applied to a subnet formed by paths between Tin ∈Tand Tout ∈T, one transition t /∈Tin ∪Tout is 84 5.3. Decentralized control of CF nets removed. Therefore the repetitive application of T-RR results in a set of places between Tin and Tout but no transition. Place Reduction Rule (P-RR). Let p1, p2be two places in a continuous CF net system, such that •p1=•p2=Tin ⊆T, p1•=p2•=tout. If for any tin ∈Tin, paths πa={tin, p1, tout}and πb={tin, p2, tout}have the same gain, i.e., G(πa) = G(πb). Then, if m0[p1] P re(p1,tout)≤m0[p2] P re(p2,tout),p2can be removed, otherwise, p1can be removed. In order to apply P-RR, G(πa) = G(πb) has to be satisfied. Notice that if G(πa)6=G(πb), it implies that the system is not live or not bounded. In particular, if G(πa)> G(πb) then place p1is not bounded, otherwise the net system is not live; if G(πa)< G(πb) then place p2is not bounded, otherwise the net system is not live either. Example 5.3.9. Fig. 5.5(a) shows a CF net system in which Tin ={ti1, ti2}. In order to apply P-RR, the weights of arcs should satisfy w1 w5=w2 w6, and w3 w5= w4 w6. Assume m0[p1] w5≤m0[p2] w6, then by removing p2, the reduced system is shown in Fig. 5.5(b). ti_1 p1 to w1 p2 …... w5 w4w6 ti_2 …... w2 w3 (a) Original subsystem S to p1 ti_1 …... ti_2 w1 w5 w3 (b) Reduced subsystem S′ Figure 5.5: Place Reduction Rule (P-RR): reducing p2 Proposition 5.3.10. Let Sbe a continuous CF net system, and S′be the reduced system obtained by applying P-RR, sequence σis fireable in Sif and only if σis fireable in S′. Proof: It is easy to verify that the places being removed by applying P-RR belong to a particular type of implicit places, i.e., those places that never uniquely restrict the firing of its output transitions (see [90]). Therefore, they can be removed without affecting the behavior of the rest of the system. Example 5.3.11. Let us apply the reduction rules on subsystem S2in Fig. 5.2(a). The net system in Fig. 5.6(a) is obtained by applying P-RR to remove place p5. By applying T-RR to the path between t2and t6,p26is obtained (Fig.5.6(b)). Similarly, the application of T-RR to the path between t3and t7in Fig.5.6(b), removes t5and 85 Chapter 5. Decentralized Control of CF nets: ON/OFF Based Methods obtains p37(Fig.5.6(c)). The application of T-RR to the path between t2and t8in Fig.5.6(c), removes t6and obtains p28(Fig.5.6(d)). The application of T-RR to the path between t3and t9in Fig.5.6(d), removes t7and obtains p39(Fig.5.6(e)). Finally, only two places are left with markings m0′[p28] = 2,m0′[p39] = 1. The reduced subsystem in Fig.5.6(e) is the abstraction of S2. 2 p3 p7 p8 t2 t3 t4 t5 t8 t7t9 t6 p9 p6 2 33 2 p4 (a) applying P-RR to S2 2 p7 p8 t2 t3t5 t8 t7t9 t6 p9 2 33 2 p4 p2_6 (b) applying T-RR to (a) 2p8 t2 t3 t8 t7t9 t6 p9 2 33 2 p3_7 p2_6 (c) applying T-RR to (b) 2 t2 t3 t8 t7t9 p9 2 33 2 p3_7 p2_8 (d) applying T-RR to (c) 2 t2 t3 t8 t9 2 33 2 p3_9 p2_8 (e) applying T-RR to (d) Figure 5.6: Reduction process of S2in Fig. 5.2(a) Let us point out that if we apply the classical reduction rules proposed for discrete nets (see, for example, [13]) to the example shown in Ex. 5.3.11, the same reduced net system can be obtained. However, in this work we extend the classical reduction rules to CPNs where the markings, also the weights, are real numbers. Let us consider the following simple example: Example 5.3.12. Given the a (partial) CPN system shown in Fig. 5.7(a) and it is assumed that we want to reduce the paths between transition taand tb. By applying T-RR to remove transition t1, Fig.5.7(b) is obtained; similarly, t2can also be removed, obtaining Fig.5.7(c) which is clearly equivalent to Fig.5.7(d). Let us point out that the main limitation of applying the classical reduction rules to this example is that, in those rules for discrete nets fractional firings are not considered. For example, after the reduction, the marking of the single place left between taand tband the weights on arcs are decimal fractions, which are forbidden in discrete cases. Assume that, using T-RR and P-RR, we reduce the paths between two sets of transitions Tin and Tout. Now we will discuss the uniqueness of the fully reduced system. 86 5.3. Decentralized control of CF nets ta t2 t1 2 2 4 5 tb ta t2 2 0.5 4 5 tb 0.5 ta 0.7 4 tb 0.5 0.4 ta 0.7 4 tb 0.9 (a) (b) (c) (d) Figure 5.7: Reduction of the paths between taand tbusing T-RR: the classical reduction rules for discrete nets cannot be applied Property 5.3.13. Any arbitrary and interleaved application of T-RR and P-RR until none of them can be applied produces the same reduced system. Proof: It is first proved that the order of adjacent rules that are applied can be interchanged, obtaining the same reduced system. Otherwise stated, let Aand B be the instances of two rules, by applying AB or BA, the same system is obtained. Then we will show that any sequence of rules, leading to the fully reduced system, can be reordered. After that, the uniqueness of the reduced system can be easily proved. 1) if Aand Bare both instances of T-RR (or P-RR), it is trivial. 2) if Aand Bare instances of different rules. Without loss of generality, assume Ais an instance of T-RR, removing a transition tjand B is an instance of P-RR, removing an implicit place px. Obviously, if tj/∈•px∪px•,Aand Bare independent, so the system obtained after applying AB is equivalent to the one obtained after applying BA. Therefore, we only need to consider the two cases shown in Fig.5.8, where tjcan be removed by using T-RR, at the same time, its input or/and output places can be reduced by using P-RR. Its extension to more general structures is quite straightforward. We will show that for case (a), by applying AB and BA, the same system is obtained. The analysis to case (b) is similar. Since pxcan be removed by using P-RR, then w1/w3=w2/w4and in the initial state m0[px]/w3≥m0[p1]/w4. Let path π1={t1, px, tj, p2, t2}and π2= {t1, p1, tj, p2, t2}, then we have the weighted marking M(π1,m0)≥M(π2,m0). If first T-RR has been applied to remove tj, the system in Fig.5.9(a) is obtained. Let us first consider the obtained place paand p′ a. Without loss of generality, we should have: g1 g5=w1·w5 w3·w7=g2 g6=w2·w5 w4·w7, moreover, with the initial marking m0′[p′ a] = 87 Chapter 5. Decentralized Control of CF nets: ON/OFF Based Methods t1 px p1 w2 w3 w6 w4 tjw5 t2 w1 t3 w7 w8 p2 p3 (a) t1p1 p2 w2 w3 w6 w4 tjw5w7 w8 px p3 t2 w1t3 (b) Figure 5.8: The two cases with tj∈•px∪px• g1·M(π1,m0) and m0′[pa] = g2·M(π2,m0), therefore, m0′[p′ a] g5≥m0′[pa] g6,p′ ais implicit place. Then, it can be removed by applying P-RR. Similarly, for pband p′ b, let g3 g7=w2·w6 w4·w8,g4 g8=w1·w6 w3·w8,p′ bis also implicit and can be removed. The obtained system is shown in Fig.5.9(c). If first P-RR has been applied to remove px, the system in Fig.5.9(b) is obtained. Then by applying T-RR, tjis removed, it is clear that the same reduced system in Fig.5.9(c) is achieved. Now we know that the order of applying reduction rules is not important. Let Γ1and Γ2be two sequences of rules leading to two fully reduced systems S1and S2. It is clear that, the same number of T-RR is applied in Γ1and Γ2(because applying T-RR once, one transition between Tin and Tout is removed). From 1) and 2), we can transform the sequence Γ1to Γ′ 1by interchanging the order of adjacent rules, until all the instances of T-RR are moved ahead of instances of P-RR. Assume that by applying all the instances of T-RR, the obtained system is S′ 1. On the other hand, we can also transform the sequence Γ2to Γ′ 2by doing the same interchanging and assume that by applying all the instances of T-RR, the obtained system is S′ 2. Obviously, S′ 1and S′ 2are equivalent, and there are only places (but no transition) left between Tin and Tout. After that, the instances of P-RR are applied to reduce implicit places in S′ 1and S′ 2. If they are fully reduced, for sure the finally obtained systems are the same, i.e., S1and S2are equivalent. Therefore, the fully reduced system is unique. Remark 5.3.14. In order to obtain the fully reduced system, we need to explore the paths between transitions. Concerning the computational complexity, it is suggested that before considering to apply T-RR, we should first apply P-RR as much as possible to remove the implicit places. For example, in Ex.5.3.11, P-RR is first applied to remove the implicit place p5. 5.3.3 Complemented subsystems Definition 5.3.15. Let Sbe a continuous CF net system, and Si,i= 1,2be the subsystems obtained by cutting through places B∈P. The complemented subsystems, denoted by CSi, is obtained from Sby substituting Sj,j= 1,2,j6=iwith its abstraction. 88 5.3. Decentralized control of CF nets t1 pa' g3 g4 t2 g1g5 g8 t2 g2g6 g7 t3 pa pb pb' (a) First apply T-RR t1 p1 w2 w6 w4 tjw5 t2 t3 w7 w8 p2 p3 (b) First apply P-RR t1 t2 t3 pa pb g2 g6 g3 g7 (c) Fully reduced Figure 5.9: Reduction by applying rules in different order Let us still consider the system in Fig.5.2(a). By applying the proposed rules, the paths in S1between interface transitions t1and t10 can be reduced to a single place p10 1, obtaining the abstraction of S1. Using this abstraction to complement S2, the complemented subsystem CS2is obtained, shown in Fig.5.2(c). Similarly, the abstraction of S2can be constructed, and the complemented subsystem CS1is shown in Fig.5.2(b). Notice that, the cutting places and interface transitions are shared in both complemented subsystems. Remark 5.3.16. A direct consequence of Proposition. 5.3.7 and 5.3.10 is that the firing sequences and reachable markings of the original system are preserved in its complemented subsystems. The decomposition method can be easily extended to a large scale system that is decomposed into Ksubsystems, by given sets of cutting places. The complemented subsystems are constructed in two steps: first, each subsystem builds its abstraction (the reduced subsystem respect to its interface transitions); then, each subsystem constructs its complementing parts based on the abstractions of the rest of the system that have been built in the first step. In this way, each subsystem does not need the detailed structures and states of other parts of the system, but only their abstractions. 89 Chapter 5. Decentralized Control of CF nets: ON/OFF Based Methods 5.3.4 The control law computation A interesting property of the complemented subsystem is that their firing sequences are identical to those of the original system (Remark 5.3.16). Thus, the local control laws can be computed separately, driving all subsystems to their corresponding final states. However, local control laws may not be compatible with each other, i.e., there may exist a interface transition that does not fire with the same amount in the corresponding complemented subsystems (see Ex.5.3.17 for a example). In order to overcome this problem, a coordinator is introduced (see the control structure in Fig. 5.1). Local controllers will send limited information (the local control law and the minimal T-semiflow) to the coordinator. Algorithms are proposed to compute a globally admissible control law based on this information, without knowing the detailed structures of subsystems but only the interface transitions. Example 5.3.17. Let us consider the CF net in Ex. 5.3.2 and the two obtained complemented subsystems in Fig.5.2(b) and Fig.5.2(c). The initial and final marking m0,mfof the original system, and its corresponding minimal firing count vector σmin are shown in Table 5.1. As for the subsystems, the minimal firing count vectors σi min of CSifor reaching the corresponding final marking mi ffrom mi 0are computed separately, they are also given in Table 5.1. It can be observed that σ1 min and σ2 min are not compatible, because their interface transitions do not have the same firing counts, for instance, σ1 min[t1]6=σ2 min[t1]. Let S=hN,m0ibe the original system, with mf>0 the desired final state. It is assumed that Sis decomposed into Ksubsystems, S1to Sk. The following notations are used: (1) σmin: the minimal firing count vector driving Sto mf. (2) B(i1,i2): the buffer cutting places between Si1and Si2. (3) U(i1,i2): the interface transitions between Si1and Si2. (4) CSi=hCN i,m0ii: the complemented subsystems with corresponding final state mi f,i= 1,2, ..., K. (5) xi: the minimal T-semiflow in CN i,i= 1,2, ..., K. (6) σi min: the minimal firing count vector driving CSito mi f,i= 1,2, ..., K. According to the decomposition and reduction process, the obtained complemented CF subnets are also consistent and conservative. Therefore, the minimal T-semiflow and minimal firing count vector are unique [93, 104], i.e., xiand σi min are unique. So, any firing count vector σidriving CSito its final state can be written as follows σi=σi min +αi·xi, αi≥0 (5.1) 90 5.3. Decentralized control of CF nets Table 5.1: Markings and firing count vectors of the systems in Fig. 5.2 Pm0(mf)m01(mf1)m02(mf2)Tσmin σ1 min σ2 min p10 (0.4) 0 (0.4) 0 (0.4) t11.4 0.9 1.4 p20 (0.3) 0 (0.3) 0 (0.3) t20.55 0.3 0.55 p30 (0.3) 0 (0.3) t31 0.5 1 p40 (0.3) 0 (0.3) t40.25 0.25 p51 (1.3) 1 (1.3) t50.7 0.7 p60 (0.5) 0 (0.5) t60 0 p71 (0.3) 1 (0.3) t71.4 1.4 p81 (0.4) 1 (0.4) t81 0.5 1 p90 (0.2) 0 (0.2) t90.4 0.23 0.4 p10 0 (0.6) 0 (0.6) 0 (0.6) t10 0.8 0.3 0.8 p11 0 (0.2) 0 (0.2) t11 0.6 0.1 p12 0 (0.1) 0 (0.1) t12 0.7 0.2 p13 0 (0.1) 0 (0.1) t13 0.35 0.1 p14 0 (0.3) 0 (0.3) t14 0.5 0 p15 0 (0.1) 0 (0.1) t15 0.6 0.1 p16 0 (0.1) 0 (0.1) t16 0.25 0 p17 1 (0.1) 1 (0.1) p18 1 (0.2) 1 (0.2) p19 1 (0.1) 1 (0.1) p282 (2.1) p391 (0.8) p10 11 (0.4) Algorithm 6 is used by the coordinator controller. Non-negative value α1,α2, ..., αKare obtained by solving a simple LPP. Then these values are sent back to local controllers. It is ensured that by updating the local control law from σi min to σi min +αi·xi, the interface transitions fire in the same amounts in corresponding neghboring subsystems. Given a reachable final state mf, LPP (5.2) is feasible. Let σbe a firing count vector driving Sto mf, and denote by σi1and σi2the projections of σ, corresponding to CSi1and CSi2. By firing σi1and σi2in CSi1and CSi2, markings mfi1,mfi2 are reached. Obviously, the transitions in U(i1,i2)fire in the same amounts in σi1 and σi2, so there exist αi1and αi2, satisfying the constraints of LPP (5.2). Proposition 5.3.18. Let αibe the value obtained by using Algorithm 6 and σi= σi min +αi·xi,i= 1,2, ..., K be the local control laws of CSi. The global control law σobtained by merging all the local ones, is the (unique) minimal firing count vector driving Sto mf. Proof: It is trivial that σcan drive Sto mf. If σis not the minimal one, some amounts of T-semiflow can be subtracted, obtaining a contradiction with the 91 Chapter 5. Decentralized Control of CF nets: ON/OFF Based Methods Algorithm 6 Coordinator Input: σi min,xi,i= 1,2, .., K Output: αi,i= 1,2, .., K 1: Receive σi min and xifrom local controllers 2: Compute αiby solving LPP: min K P i=1 αi s.t. σi1 min[tj] + αi1·xi1[tj] = σi2 min[tj] + αi2·xi2[tj],∀tj∈U(i1,i2) ∀i1, i2∈ {1,2, ..., K},CSi1and CSi2are neighbors. αi≥0, i = 1,2, ..., K (5.2) 3: Send αito CSi; objective function of LPP (5.2). Notice that the minimal firing count vector is unique, implying that the solution of LPP (5.2) is also unique. Algorithm 7 is used by the local controllers. In the first step, the minimal firing count vector σi min of each subsystem CSiis computed separately by the local controller. Then, every subsystem CSisends σi min to the coordinator, together with its corresponding minimal T-semiflow (only once if the net structure does not change). After αiis received from the coordinator, the controller of CSican be implemented independently by considering σi min +αi·xi. In particular, the minimum-time ON-OFF controller (presented in Chapter 3) is used. Algorithm 7 Local Controller i Input: CN i,mi 0,mi f Output: σi 1: Compute σi min the drives the system to mi f; 2: Compute the minimal T-semiflow xi; 3: Send σi min and xito the coordinator; 4: Receive αifrom the coordinator; 5: Update σi←σi min +αi·xi; 6: Apply the ON-OFF controller; Since only limited information (the local control laws and the minimal T-semiflows) are required by the coordinator, very low communication costs are obtained (two vectors σi∈R|Ti|and xi∈R|Ti|for each subsystem Si). When the agreement is obtained, all the subsystems work independently. 92 5.3. Decentralized control of CF nets 5.3.5 A case study In order to illustrate the developed approach, let us consider the CF net in Fig.5.10. It is adapted from the model of a simple manufacturing line that makes tables [81]. It consists of three work stations: WS 1 and WS 2 and WS 3. Two types of raw materials A and B are processed by WS 1 and WS 2 respectively. The obtained semi-products are deposited in buffers and will be finally assembled in WS 3 to make the final products. Table 5.2 gives the interpretations of the model. We will apply to this system the proposed decentralized control method. 10 5 10 2 22 2 22 2 2 Load S_M1_A1 E_M1_A1 S_M2_A1 E_M2_A1 S_M1_B E_M1_B S_M2_B E_M2_B S_M1_C E_M1_C S_M2_C E_M2_C Load Unload 5Load Unload Blk A1_Rdy A2_Rdy S_M1_A2 E_M1_A2 S_M2_A2 E_M2_A2 A_Raw B_Raw A_Finished B_Finished B_Rdy M1_B M2_B Max_M1_A1 Max_M2_A1 Max_M1_A2 Max_M2_A2 Max_M1_B Max_M2_B Max_M2_C Max_M1_C M1_A1 M2_A1 M2_A2 M1_A2 B_A1 B_A3 C_Rdy M1_C M2_C B_C2 Max_C 2 3 B_C1 Max_B WS_1 WS_2 WS_3 p1p2 p3 p4 p5 p6 p7 p8p9 p10 p11 p12 p13 p14 p15 p16 p17 p19 p22 p23 p24 p25 p26 p27 p30 p31 p32 p33 t1 t2t3t4t5t6 t7t8t9t10 t11 t12 t13 t15 t18 t19 t20 t21 p34 Unload B_A2 B_A4 Unload B_B1 p18 p20 p21 p28 p29 t16 t14 t17 t22 t23 Final p35 t24 Figure 5.10: The TCPN model of a manufacturing system with three work stations. The original system is cut into three subsystems CS1to CS3corresponding to work stations WS 1 to WS 3. The buffer places are B(1,3) ={p30, p31},B(2,3) = {p32, p33}and the interface transition are U(1,3) ={t1, t6, t11, t18, t23,},U(2,3) = {t12, t17, t18, t23}. It is assumed that in the initial state both types of materials have quantities equal to 10, while two machines are available for any processing, production lines in WS 2 and WS 3 have maximal capabilities equal to 5. The firing rates are: λ8=λ10 = 1/2, λ15 =λ16 = 1/3, λ20 =λ22 = 1/4 and for other transitions, all equal to 1. Under this setting, the maximal throughput of transition EM2 C (t22, which models the machine that produces the final product) in the steady state is 0.33 ([87]). The complemented subsystems are shown in Fig. 5.11, the final states of subsystems and their corresponding minimal firing count vectors are shown in Table 5.3. In this specific example, the minimal T-semiflows of subsystems are unit vectors 93 Chapter 6. Distributed MPC Control of General nets Therefore, after each time step, the marking of every place should only move closer towards its final one or remain in the same marking (given by constraints (6.1)). The method proposed here is a generalization of the MPC controller introduced in [64], where linear state trajectories are considered. Comparing with the heuristic minimum-time method proposed in [5], our method is also less constrained on the trajectory, but it is not designed for the minimum-time control. The MPC controller is given in Algorithm 8: Algorithm 8 A centralized MPC controller Input: hN,m0i,mf,wf,Z,Q Output: w0,w1,w2,... 1: k←0; 2: while mk6=mfdo 3: Solve problem (6.2); 4: Apply wk:mk+1 ←mk+ Θ ·C·wk; 5: k←k+ 1; 6: end while 7: return w0,w1,w2,...; min J(mk, N) s.t. :mk+j+1 =mk+j+ Θ ·C·wk+j, j = 0, ..., N −1 (6.2a) G·wk+j mk+j≤0, j = 0, ..., N −1 (6.2b) wk+j≥0, j = 0, ..., N −1 (6.2c) mf[pi]≥mk+j+1[pi]≥mk+j[pi],if mf[pi]≥m0[pi],(6.2d) j= 0, ..., N −1 mf[pi]≤mk+j+1[pi]≤mk+j[pi],if mf[pi]≤m0[pi],(6.2e) j= 0, ..., N −1 where Gis a particular matrix deduced from the net structure and (6.2b) gives the (upper bound) constraint on firing flows to guarantee the non-negativeness of markings [64]. According to [83], the reachability space of CPN systems is a convex set. The convex subset of the reachability space R(N,mk,mf) corresponding to mkand mf, inside which the following system states evolve, is generated by using constraints (6.2d) and (6.2e). The cost function J(mk, N) may be a linear or quadratic. For the target marking 100 6.2. A centralized MPC controller control problem addressed here, J(mk, N) has the quadratic form: J(mk, N) =(mk+N−mf)′·Z·(mk+N−mf) (6.3) + N−1 X j=0 [(mk+j−mf)′·Q·(mk+j−mf) where weighting matrix Z,Q∈R|P|are positive definite. Example 6.2.1. Let us consider the consistent and conservative CPN (a simple strongly connected state machine) shown in Fig.6.2(a). Since there exists only one P-semiflow in the net (the corresponding token conservation law: m[p1] + m[p2] + m[p3] = 4), the markings of two places are sufficient to represent the whole reachability space, R(N,m0)(see Fig. 6.2(b)). Let mf=[1 2.5 0.5]T. The subset of its reachability space, R(N,mk,mf), generated by constraints (6.2d) and (6.2e), is also shown (mk=m0). 1.5 20.5 t1 p2 p1t3p3 t2 t4 (a) m[p1] m[p3] 4 2 24 mf m0 R(N, m0,mf) R(N, m0) (b) Figure 6.2: (a) A consistent and conservative CPN (a simple state machine); (b) the reachability space R(N,m0) and the subset R(N,m0,mf), mf=[1 2.5 0.5]T Proposition 6.2.2. Let hN,λ,m0ibe a consistent TCPN system with m0>0, and let mf>0be a reachable final marking. By applying the MPC controller given in Algorithm 8, the closed-loop system is asymptotically stable. Proof: We prove the statement in two steps: 1) we prove that the problem (6.2) is feasible; 2) we define a quadratic Lyapunov function and prove that it is strictly decreasing. 1) Since the system is deterministic, i.e., noise free, it is clear that at any time step kwith marking mk, one solution of problem (6.2) could be {mk+j+1 =mk,wk+j=0}, j = 0,1, ..., N −1 101 Chapter 6. Distributed MPC Control of General nets So problem (6.2) is feasible. 2) Let V(mk) = (mk−mf)T·Z·(mk−mf), where Zis the weight matrix in (6.2). It is clear that V(mk)≥0, and for any mk6=mf,V(mk)6= 0. Let mk−mf=∆mk, according to constraints (6.2d) and (6.2e) of problem (6.2), ∀pi∈P,|∆mk[pi]| ≥ |∆mk+1[pi]|. Therefore, V(mk)≥V(mk+1). Now we will show that V(mk)> V (mk+1) until mk=mf, i.e., until the system is already in the desired final state. Because the marking of each place can only move closer to its final value or stay in the same value, it is equivalent to prove that mk6=mk+1 until mk=mf. Assume that at time step k,mk6=mfand mk=mk+1, i.e., at the first predictive step, the system stays at mkwith flow wk=α·x(where α≥0 and xis a T-semiflow). Then, a solution of problem (6.2), Υ1, gives a sequence of predictive states as follows: mk α·x −→ mk+1 (= mk)→mk+2 ···mk+N−1→mk+N Obviously, instead of staying in mkat the first predictive step (mk+1 =mk), we may have another solution Υ2by starting moving to mk+2 at the first predictive step, and following the same sequence of states as in Υ1, then staying in mk+Nat the last predictive step: mk→mk+2 →mk+3 ···mk+N α·x −→ mk+N The values of cost function corresponding to Υ1and Υ2are: J1=∆mT k+N·Z·∆mk+N+∆mT k·Q·∆mk(6.4) + N−1 X j=1 ∆mT k+j·Q·∆mk+j J2=∆mT k+N·Z·∆mk+N+∆mT k·Q·∆mk(6.5) + N X j=2 ∆mT k+j·Q·∆mk+j Therefore, the following can be obtained: J2−J1=∆mT k+N·Q·∆mk+N−∆mT k+1 ·Q·∆mk+1 =∆mT k+N·Q·∆mk+N−∆mT k·Q·∆mk According to the constraints (6.2d) and (6.2e), if mk6=mf, we must have mk+N6=mkand ∀pi∈P,|∆mk[pi]| ≥ |∆mk+N[pi]|. Otherwise, the system should stay in mkat every predictive step, but obviously this cannot be an optimal solution: since the net is consistent, mk>0 (inside R(N,m0,mf)) and all transitions are 102 6.3. Application to Distributed MPC control controllable, the state marking can move in any direction [97]; in particular, it is possible to move towards mf, hence it is possible to decrease the distance to the desired marking in one step. Therefore, J2−J1<0, i.e., Υ2is a better solution than Υ1, implying that if mk6=mf, by applying the MPC controller given in Algorithm 8 the system always starts moving towards mffrom the first predictive step. So V(mk)> V (mk+1) until mk=mf. Example 6.2.3. Let us still consider the net system shown in Fig 6.2(a) with the final state mf=[1 2.5 0.5]T. Assume that the firing rates of all the transitions are equal to 0.1and the sampling period Θ=0.1. By applying the MPC controller shown in Algorithm 8 (with Q=I,Z= 1000 ·I, N = 5), the obtained marking trajectory of places p1and p3is illustrated in Fig. 6.3 (in continuous line), and the close-loop cost is 99793. We also apply to the system the MPC controller proposed in [64] (with Q=I,Z= 1000 ·I,R=0), in which the state trajectory follows a straight line from m0to mf(in dotted line), and the close-loop cost is equal to 114220 that is larger than by using the method proposed here. Figure 6.3: Marking trajectory of the net system in Fig. 6.2(a) by applying: the MPC controller proposed in [64] (dotted line) and the MPC controller shown in Algorithm 8 (continuous line) 6.3 Application to Distributed MPC control Let us consider now a (large scale) PN system that is composed of a set of subsystems denoted by K. Those subsystems Sl=hN l,m0li ∈ Kare connected with places modelling buffers denoted by B. The transitions connecting with buffer places are said to be interface transitions. Let Pl,Tlbe the sets of places and transitions of subsystem Sl. The partition of the system is described as follows: •TSl∈KPl=∅, (SSl∈KPl)∪B=P; 103 Chapter 6. Distributed MPC Control of General nets •TSl∈KTl=∅,SSl∈KTl=T; •for any place pi∈B,•pi∩Pl6=∅ ⇒ •pi⊆Pland pi•∩Pl6=∅ ⇒ pi•⊆Pl, i.e., buffer places are input and output private. In the sequel, the following notations are used: •B(l,k)={pi∈B|•pi⊆Sl, pi•⊆Sk}is the set of output buffers of Sland input buffers of Sk; •B(·,l)=SSk∈KB(k,l)and B(l,·)=SSk∈KB(l,k); •Cl∈N|Pl|×|Tl|is the flow matrix of subsystem Sl. In the distributed setting, each subsystem is controlled independently by the MPC controller given in Algorithm 8. Therefore the states of each subsystem Sl will be interior points (inside R(Nl,m0l,mfl). However, one key issue we need to consider is that the markings of buffer places may be keeping decreased and converging to zero if the same control laws are applied (in TCPNs under infinite server semantics, once a place is marked it takes infinite to empty it). Since we consider the control in finite time, in the sequel, if mk[pi]≤ǫ1with ǫ1a small positive value, we assume that under the actual control law the marking of the buffer place piis converging to zero. When some buffer places with their markings smaller than ǫ1, subsystems may “stop”, because the required flows to move towards the final states may be constrained by these buffer places. We will design a particular strategy to put more tokens to these places with their markings converging to zero. 6.3.1 Two subsystems For clarity, let us first consider the system composed of only two subsystems. Later, the control method is directly extended to the case of multiple subsystems. t1 S1S2 t2 t3 t4 t5 t6 p1 p2 p3 B Figure 6.4: A distributed CPN composed of two subsystems 104 6.3. Application to Distributed MPC control Fig. 6.4 shows the interface transitions and buffer places of a CPN that is composed of two subsystems S1and S2, we have B(1,2) =B(1,·)={p1},B(2,1) = B(2,·)={p2, p3}. Let us denote by m01and m02the initial states (markings) of subsystems S1 and S2, while the desired final states are denoted by mf1and mf2. The initial and final states of the global system, including the buffer places, are m0and mf. Instead of a global central controller, each subsystem will have its own local MPC controller. A local controller has only information about the structure and state of its corresponding subsystem, as well as the connected buffers places. The problem we address here is to drive the subsystems S1and S2to their desired final states. We use the following assumptions: (A1) The global system is consistent (therefore, each subsystem is also consistent). (A2) The initial state of the global system m0>0 (including the buffer places); mf>0 is a given reachable final state of the global system, and mf1,mf2>0 are the corresponding final states of subsystems (observe that we do not require liveness or deadlock-freeness). (A3) In the untimed (autonomous) model, subsets of buffer places never define a siphon that can be emptied. Notice that although in assumption (A2) we assume a given final state of the global system, we are only focusing on driving subsystems to their corresponding final states. Regarding the buffer places, we simply ensure that they are always in legal (non-negative) states. Assumption (A3) can be checked in the following way. Let us define PreΣand PostΣas |P| × |T|sized matrices for a given net system hN,m0isuch that: •PreΣ[p, t] = |t•|if Pre[p, t]>0, PreΣ[p, t] = 0 otherwise •PostΣ[p, t] = 1 if Post[p, t]>0, PostΣ[p, t] = 0 otherwise. Equations {yT·CΣ≤0,y≥0}where CΣ=PostΣ−PreΣdefine a generator of siphons (Σ is a siphon iff ∃y≥0such that Σ = kyk,yT·CΣ≤0) [28, 87]. Hence, the following system: •m=m0+C·σ,m,σ≥0,{state equation} •yT·CΣ≤0,y≥0,{siphon generator} •yT·m= 0,{empty siphon at m}(6.6) has no solution iff the continuous net system has no emptied siphon. We only need to solve problem (6.6) off-line considering the part of system composed of the buffer places and interface transitions, denoted by S′: because every firing sequence that can fire in the original system Scan also fire in S′and, normally S′has much smaller 105 Chapter 6. Distributed MPC Control of General nets size than the whole system. Nevertheless, in some particular cases, it may be not necessary to solve problem (6.6). For example, given a EQ net, we can easily check its consistency and conservativeness, then by applying the rank theorems we can verify the liveness the boundedness in polynomial time. If the net system is live and bounded, then we can directly conclude that there exists no emptied siphon. It is clearly that the buffer places may constrain the flows of the interface transitions. Thus, the following additional constraint to problem (6.2) should be added for each subsystem Sl: wl k[t]≤λ[t]·mk[pi] P re[pi, t],∀t∈pi•, pi∈B(·,l)(6.7) where wl k[t] is the flow of transition tand mk[pi] is the marking of buffer place pi at time step k. Then, for each subsystem Sl, the modified problem that should be solved at every time step kis: min J(ml k, N) (6.8a) s.t. :ml k+j+1 =ml k+j+ Θ ·Cl·wl k+j, j = 0, ..., N −1 (6.8b) Gl·wl k+j ml k+j≤0, j = 0, ..., N −1 (6.8c) wl k+j≥0, j = 0, ..., N −1 (6.8d) mfl[pi]≥ml k+j+1[pi]≥ml k+j[pi],if mfl[pi]≥m0l[pi],(6.8e) j= 0, ..., N −1 mfl[pi]≤ml k+j+1[pi]≤ml k+j[pi],if mfl[pi]≤m0l[pi],(6.8f) j= 0, ..., N −1 wl k[t]≤λ[t]·mk[pi] P rel[pi, t],∀t∈pi•, pi∈B(·,l)(6.8g) If all the (input) buffer places of subsystem Slare marked, according to Proposition 6.2.2, problem (6.8) is also feasible, because we can always fire a small wl k≥0 such that constraint (6.8g) is not active. Moreover, if at every time step kall of its input buffer places are marked, using the same reasoning as in Proposition 6.2.2, we will have ml k6=ml k+1, so V(ml k)> V (ml k+1); therefore, the subsystem keeps evolving until the final state is reached. Nevertheless, if the markings of some of the input buffer places of a subsystem Sl are converging to zero (with their markings smaller than ǫ1), Slmay “stop” in certain state before reaching mfl. In this case, Slhas to wait on the current state until its neighboring subsystem puts more tokens into these buffer places. At the same time, some T-semiflows might be fired in Sl, putting more tokens into its output buffer places; since these output buffer places of Slare inputs buffer places of its neighboring subsystem, consequently this will help the evolution of its neighboring 106 6.3. Application to Distributed MPC control subsystem to the final state. Therefore, when Sl“stops” evolving we will use another cost function, denoted by H(ml k): H(ml k) = X ∀tj∈•pi,pi∈B(l,·),mk[pi]≤ǫ1 −wl k[tj] (6.9) where mk[pi] is the marking of buffer place piat time step k. By minimizing H(ml k), we try to put more tokens into its output buffer places pi,mk[pi]≤ǫ1(if there exist) and it is equivalent to maximizing their input transition flows; but meanwhile, it may also try to empty its input buffer places. Therefore, in order to keep certain amounts of tokens inside a marked input buffer place pi, the following constrains are added: Θ·X tj∈pi• wl k[tj]·P re[pi, tj]≤α·mk[pi],∀pi∈B(·,l)(6.10) where 0 ≤α < 1. It mean that by one step, the marking of a marked buffer place pican be maximally decreased to (1 −α)·mk[pi]. When cost function H(ml k) is applied, we fix the time horizon N= 1, then problem (6.8) is modified to (6.11): min H(ml k) (6.11a) s.t. :ml k+1 =ml k+ Θ ·Cl·wl k(6.11b) Gl·wl k ml k≤0 (6.11c) wl k≥0 (6.11d) mfl[pi]≥ml k+1[pi]≥ml k[pi],if mfl[pi]≥m0l[pi] (6.11e) mfl[pi]≤ml k+1[pi]≤ml k[pi],if mfl[pi]≤m0l[pi] (6.11f) wl k[t]≤λ[t]·ml k[pi] P rel[pi, t],∀t∈pi•, pi∈B(·,l)(6.11g) Θ·X tj∈pi• wl k[tj]·P re[pi, tj]≤α·mk[pi],∀pi∈B(·,l)(6.11h) The procedure of the distributed MPC controller consists of solving problem (6.8) and/or problem (6.11) in each subsystem Slat any time step: if the final state mflhas already been reached, problem (6.11) is solved, trying to put more tokens to its output buffers with their markings converging to zero (remember that Slstays in mflbecause of constraints (6.11e) and (6.11f)); otherwise, problem (6.8) is first solved and, if subsystem Slis able to evolve towards its final state (still inside the convex R(Nl,ml 0,ml f)), the first predictive control law is applied; if by solving (6.8) the system stops in mk, then problem (6.11) is solved. Because one subsystem may reach the final state faster than the other, each subsystem should communicate to its neighbors when its final state has been reached. This procedure repeats until the 107 Chapter 6. Distributed MPC Control of General nets final states of both subsystems have been reached. The local controller of subsystem Slis given in Algorithm 9. Algorithm 9 Distributed MPC control: algorithm for subsystem Sl Input: Sl,Z,Q,mfl,α Output: wl 0,wl 1,wl 2,... 1: k←0; 2: while ∃Si,mi k6=mfi,i= 1,2do 3: if ml k=mflthen 4: Solve problem (6.11) 5: else 6: Solve problem (6.8) 7: if ml k=ml k+1 then 8: Solve problem (6.11) 9: end if 10: end if 11: Apply wl k:ml k+1 ←ml k+ Θ ·Cl·wl k 12: Update the states of buffers 13: k←k+ 1 14: end while 15: return wl 0,wl 1,wl 2,... Remark 6.3.1. As we have already mentioned, in TCPNs under infinite server semantics it will take infinite time to empty a marked place, therefore the initially marked buffer places cannot totally get emptied in finite time and thus the subsystem will not be totally stopped. Hence, in the implementation of Algorithm 9 we approximate condition “ml k=ml k+1” (implying that Slstops in ml k)by using “(ml k−ml k+1)T·(ml k−ml k+1)≤ǫ2”, where ǫ2is a small positive value. Proposition 6.3.2. Let S=hN,λ,m0ibe TCPN system composed of two subsystems Sl=hNl,λl,m0li,l= 1,2. If assumptions (A1) to (A3) are satisfied, by applying Algorithm 9, each subsystem Slconverges to its corresponding final state mflin finite time. Proof: If all the buffer places are marked, according to Proposition 6.2.2 we can find a solution of problem (6.8) such that the obtained state of the next step ml k+1 6=ml k, then V(ml k+1)< V (ml k), i.e., subsystem Slevolves towards mfl. If a subsystem “stops” in a state ml k6=ml f, it is because some buffer places pi are converging to zero (mk[pi]≤ǫ1). We will prove that by using the proposed algorithm, these buffer places can get marked, and the subsystem will keep evolving towards the final state. Without loss of generality, assume that subsystem S1has stopped in a state before reaching mf1, then problem (6.11) should be solved in S1. Consider now 108 6.3. Application to Distributed MPC control subsystem S2, there are two cases: (i) S2is able to keep evolving towards mf2by solving problem (6.8); (ii) S2also stops in a state before reaching mf2. In case (i) the final state of S2will be reached in finite time, then problem (6.11) should be solved; in case (ii), problem (6.11) should also be solved according to the algorithm. Therefore, we need to prove that by solving (6.11) in both subsystems, these buffer places with their marking converging to zero, will get marked. Assume that by applying Algorithm 9 the system has “stopped” at mk, then problem (6.11) should be solved in both subsystems. According to assumption (A3), there exists no empty siphon composed of buffer places. If we consider each subsystem independently, its states are forced to be inside the closed interior convex subset R(Nl,ml 0,ml f), so both subsystems have positive markings. Therefore, there exists no empty siphon in the (global) system. On the other hand, since the net is consistent, the system is possible to move in any direction [97]. In particular, because mf>0 is reachable from mk, there must exist a global flow such that at the next step some buffer places pi,mk[pi]≤ǫget marked. Now let us consider the subsystems. Clearly, a place can only get tokens by means of firing its input transitions. Therefore, by solving problem (6.11) in which we try to maximize the input transition flows of buffer places piwith mk[pi]≤ǫ, some of these places will get marked. Hence, once both subsystems solve problem (6.11) and the obtained control laws are applied, at least one of these buffer place will be marked. At the same time, because of constrains (6.11h) (with 0 ≤α < 1), for any already marked buffer place pj, its marking can be maximally decreased to (1 −α)·mk[pj]>0. By repeating this process, more buffer places with markings converging to zero will be marked (until all of them are marked, if necessary); for any already marked buffer places pj, its marking can be maximally decreased to (1 −α)n·mk[pj], where nis the (bounded) number of buffer places. By choosing an appropriated αand a small enough positive number ǫ1<(1 −α)n·mk[pj], it means that all the buffer places are marked. After that, both subsystems can keep evolving towards the final state by solving problem (6.8). 6.3.2 Multiple subsystems Algorithm 9 can be directly applied to the distributed control of a system composed of multiple subsystems and the convergence to the final states could be proved using a similar argument as in Proposition 6.3.2. Let us point out that, one subsystem may have multiple neighbors, hence have multiple sets of buffer places and interface transitions; and those related constraints (in problem (6.8) and (6.11)) should be applied to all of them. On the other hand, let us address the ending condition of Algorithm 9 (step 2). As we have already mentioned, one subsystem may reach its final state faster than the others. However, the algorithm (executed in each subsystem) finishes only if all the subsystems have reached their final states. The reason is very clear: one subsystem that has already been in its final state may still need to put more tokens to its output buffer places (by firing some T-semiflows), which are required 109 Chapter 7. Minimum-time Flow Control of CF nets Figure 7.2: The time steps required to reach different steady-states with the maximal flow by applying the ON/OFF controller to the MG shown in Fig.7.1: nonmonotonicity appears with respect to the corresponding firing count vectors m1 m2 m3 m4 m5 m6 m7 m8 m9 m10 m11 0 200 400 600 800 1000 Time steps to reach markings Markings The difference between σ1and σ2, for example, is that in σ2transition t2fires more than in σ1. Therefore, p3receives more tokens and t5may fire faster (its flow is increased). In the cases of σ1to σ9, transition t5is the one that fires “slowest”, i.e., the one that requires more time steps to fire the given firing amount. Therefore by increasing the flow of t5, the overall number of time steps is decreased. On the other hand, if t2fires too much, as in σ10 and σ11,t2becomes the one that requires more time steps, so the overall time steps starts to increase. 7.3 A heuristic algorithm for CF nets In a (strongly connected and consistent) CF net there exists a unique minimal Tsemiflow xand its support contains all the transitions [93]. Therfore, if ψjis the maximal flow of transition tj(the optimal solution of LPP (7.1)), then the maximal flow of every transition can be deduced (because ψis a steady-state flow, C·ψ= 0 and ψ=α·x,α > 0). Moreover, the minimal required marking of a place pito ensure the maximal flow can be easily determined by the firing rate of its unique output transition and weight on the arc: Definition 7.3.1. Let hN ,λ,m0ibe a CF system, xbe the minimal T-semiflow and ψjbe the optimal flow of transition tj. Then, µis said to be the minimal required marking for the optimal flow 1, if: µ[pi] = (ψj/λ[t]) ·(x[t]/x[tj]) ·P re[pi, t],∀pi∈P, {t}=pi•(7.3) 1It is a marking vector that may not be reachable. 116 7.3. A heuristic algorithm for CF nets An immediate consequence of Definition 7.3.1 is the following: given m≥µ, the uncontrolled flow of any transition tjcorresponding to msatisfies f[tj]≥ψj. Therefore, if all the transitions are controllable, there exists 0 ≤u≤f, such that the controlled flow w[tj] = ψj. In other words, for any reachable marking m,m∈ M iff m≥µ. Thus, the Minimum-time Flow Control problem of CF nets is equivalent to reaching a marking m≥µin minimum-time. Moreover, a firing count vector σ that leads to a steady state mss with the maximal flow is a solution of the following equations: mss =m0+C·σ mss ≥µ σ≥0 (7.4) As we have discussed in Chatper 4, the ON/OFF controller is a minimum-time controller of CF nets assuming a given firing count vector. However, the firing count vector satisfying (7.4) is not unique in general. Therefore, we need to compute the best one, i.e., the one that leads to the maximal flow in minimum-time by applying the ON/OFF controller. According to the ON/OFF strategy, every transition fires as fast as possible, until each one completes its required amount given by the corresponding firing count vector. Therefore, the overall time is determined by the “slowest” transition, i.e., the one that costs most time steps to fire its given amount. Since the firing speed is variable in TCPN under infinite server semantics, depending on the state evolution, we will consider an estimation of the number of time steps (something similar to the concept we have used in the B-ON/OFF controller (see Section 4.4.2)). Let us assume that the current marking at time step kis mkand let σkbe a firing count vector that should be fired to reach a state in M. Then Sk[tj] = ⌈σk[tj] λj·enab(mk,tj)·Θ⌉can be viewed as an estimation of the number of time steps that transition tjneeds to fire (it is an estimation because it is assumed a constant speed for tj). Given transitions taand tb, if Sk[ta]>Sk[tb], then it would be said that tais “slower” than tb. Notice that Skdoes not give neither a lower nor an upper bound because mkchanges dynamically. In the heuristics we propose, at each time step kwe minimize the number of time steps of the slowest transition, i.e., to minimize the infinity norm of Sk,||Sk||∞= max{|Sk[tj]|}, tj∈T. The minimization of ||Sk||∞can be done by solving the following LPP, in which a new variable dis introduced: min d s.t. mss =mk+C·σk mss ≥µ d≥σk[t]/(λ[t]·enab(mk, t)·Θ),∀t∈T σk≥0 (7.5) where mkis a the current marking at time step k. 117 Chapter 7. Minimum-time Flow Control of CF nets The control progress is given in Algorithm 10, which is a close-loop control and at each time step we recompute the “best” firing count vector σkaccording to the current state. Then, σkis fired by applying the ON/OFF strategy, obtaining a heuristics for the Minimum-time Flow Control. Since the stability of applying the ON/OFF controller to CF nets has been proved, the convergence of Algorithm 10 can be easily obtained. Algorithm 10 An algorithm of Minimum-time Flow Control problem for CF nets Input: hN,λ,m0i,tj, Θ Output: sequence of controlled flows: w0,w1, ..., wk 1: compute ψjby solving LPP (7.1); 2: compute µthat satisfies (7.3); 3: k←0; 4: while not (mk≥µ)do 5: compute σkby solving LPP (7.5); 6: compute the controlled flow wkcorresponding to the ON/OFF strategy; 7: update state: mk+1 ←mk+ Θ ·C·wk; 8: k←k+ 1; 9: end while 10: compute the steady state controlled flow wk, such that: C·wk= 0,wk[tj] = ψj; 11: Return w0,w1, ..., wk; Algorithm 10 can be further improved, considering the persistency property of CF nets: the (additional) firing of one transition does not disable the firing of the others [93]; however, it may increase the flow of the other transitions (as in the net system in Fig.7.1, additional firings of t2increased the flow of t5). Based on this observation and because our problem is to drive the system to a marking m∈ M, i.e., m≥µ, for any transition t, if at time step kall of its input place pi∈•tsatisfy mk[pi]>µ[pi], we can fire twithout increasing the time to reach M. So, in the improved algorithm we distinguish the following two cases: (1) for any transition twith σk[t] = 0, we consider the markings of the input places of t: if for any pi∈•t,mk[pi]>µ[pi], then tis fired as fast as possible; else, tis blocked; (2) for any transition twith σk[t]>0 the ON/OFF strategy is applied. The strategy of case (1) can only decrease the time for reaching a marking in M, but not increase. This is because we would fire tonly if all of its input places already have more-than-enough markings to obtain the maximal flow; at the same time this firing will not “slow down”, but may “speed up”, the firing of others. This improved process is given in Algorithm 11. Proposition 7.3.2. Let hN ,λ,m0ibe a CF net system. By applying Algorithm 11, the system converges to a steady-state m∈ M that maximizes the flow. 118 7.3. A heuristic algorithm for CF nets Algorithm 11 Improved algorithm of Minimum-time Flow Control problem for CF nets Input: hN,λ,m0i,tj, Θ Output: sequence of controlled flows: w0,w1, ..., wk 1: compute ψjby solving LPP (7.1); 2: compute µthat satisfies (7.3); 3: k←0; 4: compute σkby solving LPP (7.5); 5: while not (mk≥µ)do 6: for all t∈Tdo 7: if σk[t]>0then 8: compute the controlled flow wk[t] corresponding to the ON/OFF strategy; 9: else if mk[pi]>µ[pi] for any pi∈•tthen 10: wk[t]←λ[t]·enab(mk, t); 11: else 12: wk[t]←0; 13: end if 14: end for 15: update state: mk+1 ←mk+ Θ ·C·wk; 16: k←k+ 1; 17: end while 18: compute the steady state controlled flow wk, such that: C·wk= 0,wk[tj] = ψj; 19: Return w0,w1, ..., wk; Proof: Since Nis a CF net, the additional firings (for a transition twith σk[t] = 0) do not disable the firing of σkthat drives the system to a state m∈ M. On the other hand, for any place piwith m[pi]≤µ[pi], we do not decrease its marking, therefore the algorithm will converge to a marking m′≥µbelonging to M. Algorithm 11 is still a heuristics for minimum-time. One clear reason is that we try to look for the “best” firing count vector (in terms of spending less time on firing it) based on an approximation of the time steps that is obtained from the current state and flow; nevertheless, the risk of choosing a very “bad” one is somehow reduced because after each time step we recompute it based on the actual state. Another possible reasons is that only local information is considered. By means of some firings, the time spent for reaching a marking in Mmay be decreased. But, in the case concerning a transition twith σk[t] = 0, it is allowed to fire tagain only if its input places have tokens more than those in µ. However, this strategy may not be the optimal in some situations, even for MGs (a simple subclass of CF nets, see the net in Fig. 7.5 for a example). 119 Chapter 7. Minimum-time Flow Control of CF nets 7.4 Examples Let us consider the CF net system in Fig.7.3, assuming Θ = 0.01. The unique minimal T-semiflow of the net is x=[1111122111]T. Figure 7.3: A CF net system with the maximal flow ψ9= 1 , firing rate vector λ= [0.25 1/6 0.05 0.25 1/6 0.1 0.5 0.05 1/30 1/30]T 200 100 100 10 200 200 10 2 2 2 p1p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 t1t2 t3 t4t5 t6 t7 t8 t9 t10 Assume that we want to maximize the flow of transition t9, by solving LPP (7.1) with tj=t9, it is obtained ψj= 1. From (7.3), the corresponding minimal required marking is µ= [4 6 4 20 40 4 6 4 4 40 40 30 30]T. However, the solution of LPP (7.4) is not unique. For instance, σ1= [34 28 0 6 0 0 100 30 0 0]Tand σ11 = [6 0 0 34 28 0 100 30 0 0]Tare both solutions of LPP (7.4), reaching optimal-flow steady states m1= [166 6 4 128 40 194 6 100 4 40 40 30 30]Tand m11 = [194 6 4 100 40 166 6 128 4 40 40 30 30]T. Similarly to the example of the MG in Fig.7.1, we also consider 9 more intermediate points on the straight line from m1to m11 and the maximal flow can be obtained from all of them. The time steps required for reaching mi, i= 1,2, ..., 11, by using the ON/OFF controller, the results of applying Algorithm 10 and Algorithm 11, are illustrated in Fig.7.4. As shown in Fig. 7.4, by applying Algorithm 10 we can obtain the maximal flow in 1895 time steps, which is the same as using the ON/OFF controller to drive the system to m6. However, we should remember that we do not know a priori that driving the system to m6will cost less time than to other markings mi, i= 1,2, ..., 11, i6= 6. By applying Algorithm 11, the time to reach the maximal flow is further reduced to 1641 time steps. Although Algorithm 11 can highly reduce the time spent for reaching a marking in M, the minimum-time is not guaranteed in general, even for MGs. Let us consider a MG shown in Fig.7.5, assuming that the firing rate vector λ= [1 1 1 1 1/3 1 1]T and Θ = 0.01. The maximal flow is ψ= 1 (obtained by solving LPP (7.1)) and the corresponding minimal required marking is µ= [1 1 1 3 3 1 1 1]T. By using Algorithm 10, we can reach the maximal flow in 138 time steps. By Algorithm 11, we can reduce the number of time steps to 102, reaching steady-state m= [5.64 2.941 120 7.5. Conclusions Figure 7.4: Comparison of time steps for reaching the maximal of the CF system in Fig.7.3 m1 m2 m3 m4 m5 m6 m7 m8 m9 m10m11 0 500 1000 1500 2000 2500 3000 3500 Time steps to reach markings Marking (a) time steps required to reach different steadystates with the maximal flow by applying the ON/OFF control Algorithm 10 Algorithm 11 0 500 1000 1500 2000 2500 3000 3500 Time steps Algorithms (b) time steps required to reach the maximal flow by applying the proposed algorithms 2.609 3 3 1 3.587 7.323]Tand the corresponding firing count vector σ= [9.09 3.55 1.609 3 0 0.2 6.413]T. Nevertheless, it is still not the minimum-time for reaching the maximal flow: by firing σ′= [8.942 3.437 1.598 3 0 0.2 6.34]Tusing the ON/OFF strategy, we reach another maximal flow steady-state m′= [5.605 2.84 2.598 3 3 1 3.66 7.398]Tin only 100 time steps. 7.5 Conclusions In this chapter we discuss Minimum-time (Optimal) Flow Control problems for CF net systems. The main difference from the target marking control problem (at the same time the main difficulty of solving it) is that, in general we cannot uniquely determine a steady state with the given optimal flow (in our case the maximal flow), and actually, they belong to a convex region. Then, two issues arise: which steady state with maximal flow can be reached fastest? and which control method should 121 Chapter 7. Minimum-time Flow Control of CF nets Figure 7.5: A MG example where Algorithm 11 does not give the minimum-time to the maximal flow t1 p2p3 p4 p5p6 p7 p8 t2t3 t4 t5 t6 t7 0.1 p1 1 4 1.22.8 10 10 be applied? We have already known that the ON/OFF controller is a minimum-time controller assuming a given firing count vector, and here we first focus on how to choose the “best” one. We propose a heuristic algorithm for CF nets, in which we compute and update at each time step the “best” firing count vector according to an estimation of the number of time steps for firing. We also show that by means of some additional firings (because of the persistency of CF nets, the firing of one transition will reduce the enabling degrees of other transitions, but may increase their flows), the time to reach the maximal flow can be further reduced. Concerning the computational complexity, in each time step we solve a LPP, therefore, in polynomial time. 122 Chapter 8 Simulations and Comparisons The control methods proposed in this thesis have been implemented and integrated to SimHPN, a Matlab toolbox for hybrid PNs [48]. In this chapter we carry out several case studies using the SimHPN toolbox for control laws computation and for simulations. In the first three case studies we focus on the centralized control methods and the last one illustrates the distributed control. 123 Chapter 8. Simulations and Comparisons 8.1 Implementation: SimHPN The control methods proposed in this thesis are implemented and integrated into a Matlab embedded toolbox for hybrid Petri nets, called SimHPN. It provides a collection of tools for simulation, analysis and synthesis of dynamical systems that are modelled by continuous, discrete and hybrid PNs. Different firing server semantics are supported for both continuous and discrete transitions, as infinite server semantics and product server semantics. Moreover, deterministic delays with single server semantics are also available for discrete transitions. Besides of simulation options, SimHPN also offers some useful tools such as computing the structural elements (P/T-semiflows), performance bounds, optimal steady-state control; the optimal observability and diagnosis of continuous models. Both the data related to the model description, i.e., the net structures, markings, timing parameters etc., and the output results can be exported to the Matlab workspace and then used for further analysis. Figure 8.1: The main Graphical User Interface of SimHPN The main GUI (Graphical User Interface) of the toolbox is shown in Fig. 8.1. The model description, i.e., P re,P ost,λand m0, can be imported from other PN editors such as Pmeditor or TimeNet [53], or from a .mat file; alternatively, users can also directly input the parameters through the edit boxes. 124 8.1. Implementation: SimHPN Figure 8.2: The pop-up window corresponding to the MPC-ON/OFF controller Regarding the control of TCPNs, we can choose the menu “continuous” from the Menu Bar, then in the pop-up sub-menus, users can select an appropriate controller, both centralized or distributed are available. For the target marking control, the desired final state mfand other parameters (if exist) can be input through edit boxes. For instance, by selecting the MPC-ON/OFF controller from the centralized method, a window as in Fig. 8.2 appears. In the case that distributed control is selected, users need to provide the number of subsystems. Then, a window shown in Fig. 8.3 appears, in which the definition of subsystems should be inputted: for each subsystem, its buffer places and interface transitions should be given. In the corresponding edit box, the first line should be a row vector composed of the index of buffer places, and the second line should be a row vector composed of the index of interface transitions. For example, Fig. 8.3 gives the input parameters related to the example of three subsystems shown in Fig. 6.5. Users can also choose the minimum-time flow control for CF nets, in which we automatically compute the maximal flow of the system and give a heuristic minimum-time control for reaching the flow. The toolbox is available at http://webdiis.unizar.es/GISED/?q=tool/simhpn, and more technical details can be found in [48]. In the sequel, we consider several examples from flexible manufacturing systems and Automatic Guided Vehicle Systems (AGVS). We simulate those centralized control methods and compare the results (time steps and CPU time) by using the first 3 examples. Apart from the methods proposed in this thesis, another heuristics 125 Chapter 8. Simulations and Comparisons can decrease the customer waiting time, accepting a high work in process. The interpretations of the places and transitions in the PN model are explained in Table 8.2. 10 10 10 5 5 55 5 5 5 5 2 5 8 2 2 2 2 inA(p1) M1A(p2) B1A(p3) M1(p33) M3(p35) M3A(p4)B3A(p5) M2(p34) M4(p36) M5(p37) MaxB1A(p23)MaxB3A(p24) M2B(p9) B2B(p10) M1B(p11)B1B(p12) inB(p8) MaxB2B(p25) MaxB1B(p26) inC(p13) M3C(p14)B3C(p15) M1C(p16)B1C(p17) MaxB3C(p27) MaxB1C(p28) M4AB(p6) B4AB(p7) MaxB4AB(p29) M4C(p18)B4C(p19) MaxB4C(p20) M5F(p21) B5F(p22) MaxB5F(p30) Wait(p32)Cus(p31) t1t2t4 t3 t5 t6t7t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 OK(t19) t20 Figure 8.8: The PN model of an assembly system with five machines Table 8.2: The interpretation of the PN model in Fig. 8.8 Place Interpretation Transition Interpretation inX input of part X t1, t8, t12 M1 starts working My machine y t2, t9, t13 M1 finises MyX machine y is working on part X t6M2 starts working M5F machine 5 is working on the final product t7M2 finishes ByX buffer of part X in My t3,t10 M3 starts working B5F buffer of the final product in M5 t4,t11 M3 finishes MaxByX maximal size of buffer ByX t5,t14 M4 starts working MaxB5F maximal size of buffer B5F t15,t16 M4 finishes Cus customers t17 M5 starts working Wait waiting orders t18 M3 finishes t19 final product delivers t20 customer order arrives ⋆X = A, B, C and y = 1, 2, 3, 4. 132 8.3. Case study 2: centralized control of an assembly line We assume that the input of each part initially has 10 pieces; each machine can handle 2 pieces at the same time; buffer sizes are limited to 5; and initially 8 customers are considered. The corresponding initial marking m0is shown in Fig. 8.8, in which the empty places are assumed to have initial markings equal to 0.1. Similarly to the first example, we also assume that every transition has an average delay time, denoted by δ: the stating time delays of all machines are equal to 0.02 time units, i.e., δ[t1] = δ[t3] = δ[t5] = δ[t6] = δ[t8] = δ[t10] = δ[t12] = δ[t14] = δ[t17] = 0.02; the working process of machine M1 takes 0.2 time units, i.e., δ[t2] = δ[t9] = δ[t13] = 0.2; for machines M3 and M4, 0.4 time units, i.e., δ[t4] = δ[t11] = δ[t15] = δ[t16] = 0.4; machines M2, M5 work slower, it takes 0.8 time units, i.e., δ[t7] =δ[t18] = 0.8; the delay time of customer orders is 0.8; and the final products are delivered with delay of 0.1 time units, i.e., δ[t19] = 0.1. We consider reaching a final state with the flow of transition t19 (modelling the delivering of final products) maximized, and now we will also consider the work in process (WIP) cost in the profit function. We assume a fixed residence cost, equal to 50, for per piece of (semi-) products in the buffers; for machines M1, M4, the operation cost is 150; for machines M2, M5, the cost is 100; and for machine M3, the cost is 120. For per piece of final products, we assume an income of 1000. Then the following LPP can be written: max J= 1000 ·wf[t19]−l·mf s.t. mf=m0+C·σ C·wf=0 wf[t] = λ[t]·mf[pi] P re[pi,t]−v[pi, t], ∀pi∈•t, v[pi, t]≥0 wf,σ,mf≥0 (8.2) where Jis the profit function and l[3] = l[5] = l[10] = l[12] = l[15] = l[17] = l[7] = l[19] = l[22] = 50, l[2] = l[11] = l[16] = l[6] = l[18] = 150, l[4] = l[14] = 120, l[9] = l[21] = 100, for other places pi,l[i] = 0. By solving LPP (8.2), a desired final state is mf= [5.78 0.5122 0.05122 1.024 0.05122 1.024 0.05122 4.756 2.049 0.05122 0.5122 0.05122 5.78 1.024 0.05122 0.5122 0.05122 1.024 0.05122 4.124 2.049 0.2561 4.637 4.124 3.1 4.637 4.124 4.637 4.124 4.844 7.844 0.2561 0.7634 0.05122 0.1512 0.1512 0.05122]T, with maximal flow wf[t19] = 2.561. Table A.7 shows the simulation results by using different control methods. In this case, the B-ON/OFF controller again gives the smallest number of time steps (131), which is much smaller than that of the ON/OFF+ controller (249) and that of the approaching minimum-time controller (300). By using the MPCON/OFF controller with N= 5, the same number of time steps as that of the B-ON/OFF controller can be obtained, but its computational cost (284,859ms) is about 600 times larger than that of the B-ON/OFF. 133 Chapter 8. Simulations and Comparisons 8.4 Case study 3: centralized control of a manufacturing system In the third example (taken from [60]), we consider a flexible manufacturing system with four types of machines M1 to M4, and three type of robots R1 to R3. Three type of products P1 to P3 can be produced in this system. Fig. 8.9 represents its production process. The PN model of this system is shown in Fig.8.10, and the final products are finished in transition t14, t20, t6respectively. P1 : I1 R2 M2 O1 R2 P2 : I2 R3 M4 M3 R2 O2 R1 P3 : I3 M3 M4 R2 M1 M2 R2 O3 R1 R1 R3 R3 Figure 8.9: The production process of a flexible manufacturing system 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 10 0.1 0.1 3 3 3 57 t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 p1 I1/O1 p2 p3 p4 p5 p6 p7 p8 p9 p10 p11 p12 p13 p14 I2/O2 p15 p16 p17 p18 p19 p20 R1 p21 R2 p22 R3 p23 M1 p24 M2 p25 M3 p26 M4 I3/O3 Figure 8.10: The PN model of a flexible manufacturing system Assume that the initial state m0(p1) = 5, m0(p5) = 10, m0(p14) = 7, m0(p20) = 134 8.5. Discussions of case study 1–3 m0(p21) = m0(p22) = 3, m0(p23) = m0(p24) = m0(p25) = m0(p26) = 1 and the initial marking of the rest of places is equal to 0.1, the firing rate of transitions is defined as λ=[1/3 1/2 1/2 1/2 1/2 1 1/2 1/2 1/2 1/2 1/4 1/2 1/2 1 1/2 1/2 1/2 1/2 1/2 1/4]Tand sampling period be Θ = 0.03. Let us assume that the objective function of the system is defined as: 3 ·wf[t6] + 5 ·wf[t14] + 4 ·wf[t20], where wf is the flow in a steady state. Then following LPP can be written: max J= 3 ·wf[t6] + 5 ·wf[t14] + 4 ·wf[t20] s.t. mf=m0+C·σ C·wf=0 wf[t] = λ[t]·mf[pi] P re[pi,t]−v[pi, t], ∀pi∈•t, v[pi, t]≥0 wf,σ,mf≥0 (8.3) By solving LPP (8.3), a desired final state (maximizing the profit function) can be computed: mf= [3.4; 1.3; 0.4; 0.2; 7.6; 0.4; 0.4; 0.4; 0.4; 0.4; 0.4; 0.4; 0.4; 3.1; 0.8; 0.4; 0.4; 0.4; 2.4; 2; 0.8; 0.4; 0.7; 0.4; 0.4; 0.4] and the maximal profit is J= 3. The simulation results by using different control methods are shown in Table A.8. In this example, the approaching minimum-time controller gives the smallest number of time steps (279), which is about 10% smaller than that of the other control methods. However, the CPU time required for computing the control law (60,691ms) is about 200 times as large as that of the ON/OFF+ controller and 50 times as large as that of the B-ON/OFF controller. 8.5 Discussions of case study 1–3 In Table 8.3, we summarize the smallest numbers of time steps that obtained by using different control methods, and the corresponding parameters, according to the simulation results shown in Table A.5–A.8. From the simulation results, we can make some initial conclusions (that are consistent with those in Section 4.4.5): Regarding the numbers of time steps: •The B-ON/OFF controller gives the smallest number of time steps in most of the cases (except for case study 3). Usually smaller numbers of time steps are obtained by using smaller values of d, as shown in Table A.5 and Table A.7. A small value of dimplies that the “slower” transitions in a conflict will keep blocked until their flows get very “balanced” with the “faster” ones; then the proportional firing strategy (used in the ON/OFF+ controller) is applied to fire the “slower” transitions, and this strategy is more suitable when conflicting transitions have very similar flows, therefore a smaller value of dmay give better results. If dis very large, the B-ON/OFF controller is not sensitive to the difference of flows among conflicting transitions, and it is similar to apply the ON/OFF+ directly. However, in the case that the B-ON/OFF controller cannot improve the result of the ON/OFF+ controller 135 Chapter 8. Simulations and Comparisons Table 8.3: The smallest numbers of time steps of using different control methods among different parameters (if exist), derived from Table A.5–A.8. For the MPCON/OFF controller, the weight matrix Q=q·I|P|,R[j, j] = r, ∀tj∈Tp. Cases Control methods Time steps CPU time Parameters appro. min-time 311 88,505 Case 1 ON/OFF+ 457 275 B-ON/OFF 209 426 d= 2 MPC-ON/OFF 219 102,622 N= 5, r= 1000, q=1 (or 100, 1000) appro. min-time 316 55,608 Case 1 ON/OFF+ 223 108 (variant) B-ON/OFF 223 419 d= 20 (or 15, 10, 5, 2) MPC-ON/OFF 228 5,018 N= 1, r=1000, q=1 MPC-ON/OFF 228 99,749 N= 5, r= 1000, q=1 (or 100, 1000) appro. min-time 300 138,826 Case 2 ON/OFF+ 249 213 B-ON/OFF 131 475 d= 10 (or 5, 2, 1) MPC-ON/OFF 131 284,859 N= 5, r=1000, q=100 appro. min-time 279 60,691 Case 3 ON/OFF+ 301 271 B-ON/OFF 301 1,157 d= 20 (or 15, 10, 5, 2, 1) MPC-ON/OFF 310 443,439 N= 5, r= 1000, q=1 (or 100, 1000) (when conflicting transitions have similar flows), the numbers of time steps are not sensitive to the values of d, as shown in Table A.6 and Table A.8. •The ON/OFF+ controller usually gives quite small numbers of time steps (as shown in Table A.6 and Table A.8), except when the flows of conflicting transitions are very different. For example, in the original system in case study 1 (Fig. 8.5, Table A.5), the flows of t4and t9are much smaller than the ones of t1and t6; those four transitions are in a coupled conflict, therefore if we fire them proportionally by using the ON/OFF+ strategy the result is not good, costing 457 time steps, more than the double of the B-ON/OFF controller, to reach mf. On the other hand, we can see that in the variant system in cast study 1 (Fig. 8.6, Table A.6), it gives the smallest number of time steps (as the B-ON/OFF controller) and its computational cost is the lowest. It is because the fact that in the variant system, transitions t4,t9and transitions t1,t6are now in different sets of coupled conflict. •Most probably, the approaching minimum-time controller may not work very well when there exist some places with very small initial markings (as in case study 1 and 2, Table A.5–A.7). The reason may be what have mentioned before: in this approach the flow between two adjacent states is determined 136 8.6. Case study 4: distributed control of an AGV System by the one with the smaller flow, so if some states have very small flows (for example the initial state), it may take long time to reach the final state. •The numbers of time steps obtained by using the MPC-ON/OFF controller are not far from the best among other control methods, even the best (as the B-ON/OFF controller) in case 2 (shown in Table A.7). Usually, its required numbers of time steps can be decreased but using a larger time horizon N, but the improvement is not very significant (less than 0.5% in case 1, 3% in case 3 and 10% in case 2, but the computational costs increase more than 20 times). However, we can also observe that even with a small N, we may already obtain a reasonable number of time steps (as in case 1, Table A.5 and Table A.6). On the other hands, in these examples the number of time steps is not very sensitive to the weights on the matrix Rand Q. Regarding the computational costs: •The ON/OFF+ controller is the computationally cheapest one in all these three case studies. •The B-ON/OFF controller costs slightly higher CPU time than the ON/OFF+ controller (less than 5 times higher), because an estimation of number of time steps should be computed at each time step. But, it is still very efficient. •We can see that in those three cases, the approaching minimum-time controller costs more than hundred times the CPU time than that of the ON/OFF+ and B-ON/OFF controller, because it needs to solve a non-linear problem whenever an intermediate state is inserted on the trajectory to reduce the time. •In these examples, the computational cost of MPC-ON/OFF controller is not higher than the approaching minimum-time controller when a small Nis used; but it always costs more CPU time than the ON/OFF+ and B-ON/OFF controller. On the other hand, the computational cost grows fast with respect to N. From our simulation, the required CPU time for computing the control law increases more than 20 times, when Nincreases from 1 to 5. (We should also notice that, the increasing speed of the computational costs with respect to Nmay also depend on the size and structure of the considered net systems.) 8.6 Case study 4: distributed control of an AGV System In this case study we consider a model of Automatic Guided Vehicle Systems(AGVS). The system describes a manufacturing factory floor that consists of four workstations: WS 1 to 4 and three AGVS areas: AGVS 1 to 3. Each workstation handles some parts of the system that are first stored in the buffers, then moved from one workstation to another through the AGVS areas. The system can be naturally viewed 137 Chapter 8. Simulations and Comparisons as 7 subsystem connected by those buffers, each workstation or AGVS area as a subsystem. The PN model of the system is presented in Fig. 8.11, in which the buffers are modelled as places. The input and output buffer places of each subsystem are: for subsystem S1,B(·,1) ={p1},B(1,·)={p9, p10}; for subsystem S2, B(·,2) ={p9, p10},B(2,·)={p16, p24}; for subsystem S3,B(·,3) ={p16},B(3,·)={p30}; for subsystem S4,B(·,4) ={p24},B(4,·)={p27}; for subsystem S5,B(·,5) ={p30, p27}, B(5,·)={p33, p36}; for subsystem S6,B(·,6) ={p33, p36},B(6,·)={p45}; for subsystem S7,B(·,7) ={p45},B(7,·)={p1}. 3 p1 t1 p2 p3 p4 p5 p6 p7p8 t2 t3 t4 t5 t6 p9p10 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 t7 t8 t9 t10 t11 t12 t13 t14 t15 t16 t17 t18 t19 t20 t21 t22 t23 t24 t25 t26 t26 t27 t28 t29 t30 t31 t31 t32 t33 t34 WS 1 (S1) AGVS 1 (S2) WS 2 (S3) WS 3 (S4) AGVS 2 (S5) WS 4 (S6) AGVS 3 (S7) 10 4 88 3 8 5 3 6 6 22 3 5 5 8 3 3 3 Figure 8.11: The PN model of an AGVS composed by 7 subsystems We assume that in the initial state there are certain raw materials or parts in the input buffer places of each workstation, in particular, m0[p1] = 10; m0[p16] = 8; m0[p24] = 5; m0[p33] = m0[p36] = 5. In each workstation there exist some (shared) machines, modelled by places, which have the initial markings as the following: m0[p6] = 4; m0[p21] = 3; m0[p28] = m0[p29] = 2; m0[p42] = m0[p43] = 3. There also exist limitations for the parts that can be accepted by the workstations: m0[p7] = m0[p8] = 8; m0[p22] = m0[p23] = 6; m0[p44] = 8. We assume that in each AGVS area, there maximally have 3 available vehicles, i.e., 138 8.6. Case study 4: distributed control of an AGV System m0[p15] = m0[p37] = m0[p48] = 3. For the other places in model, we assume their initial markings equal to 0.1 ensuring positiveness of the initial state required by the control method. Similarly to the previous examples, we assume final states of subsystems given in Table 8.4 such that the maximal flow may be obtained. The final states of buffer places are: mf[p1] = 4.23; mf[p9] = 0.14; mf[p10] = 0.27; mf[p16] = 4.80; mf[p24] = 3.60; mf[p27] = 0.14; mf[p30] = 0.14; mf[p33] = 1.57; mf[p36] = 3.00; mf[p45] = 0.41. We assume that the average delay times of transitions are set to the values shown in Table 8.5 and the sampling period Θ = 0.05. Table 8.4: The final states of subsystems S1S2S3S4S5S6S7 p20.68 p11 0.40 p17 0.54 p25 0.68 p31 0.40 p38 1.08 p46 1.22 p30.54 p12 0.14 p18 0.81 p26 0.54 p32 0.14 p39 0.54 p47 0.40 p41.36 p13 0.81 p19 0.68 p28 1.42 p34 0.40 p40 1.08 p48 1.57 p52.17 p14 0.27 p20 0.81 p29 1.56 p35 0.14 p41 0.54 p62.17 p21 1.98 p37 2.32 p42 1.57 p76.98 p22 4.85 p43 2.02 p84.68 p23 4.71 p44 5.15 Table 8.5: The average delay times of transitions S1S2S3S4S5S6S7 t10.4 t70.1 t13 0.3 t18 0.4 t21 0.1 t27 0.4 t32 0.1 t20.5 t80.3 t14 0.4 t19 0.5 t22 0.3 t28 0.8 t33 0.3 t30.4 t90.1 t15 0.5 t20 0.4 t23 0.1 t29 0.4 t34 0.1 t40.8 t10 0.1 t16 0.5 t24 0.1 t30 0.8 t50.5 t11 0.3 t17 0.6 t25 0.3 t31 0.4 t60.8 t12 0.1 t26 0.1 The problem we handle here is to drive all the subsystems to their final states by using distributed control methods. Clearly, the net is not CF, so the approach proposed in Chapter 5 is not applicable; on the other hand, subsystems are not mono-T-semiflow (for example, subsystem S1has two minimal T-semiflows), so we cannot apply the method proposed in [4] either. Hence, here we will apply the distributed MPC controller presented in Chapter 6. In Fig. 8.12 and Fig. 8.13, for each subsystem Slwe show the quadratic distance of states ml k(at any time step k) to the final state mfl, defined as (ml k−mfl)T·(ml k−mfl), l= 1 to 7, by using the centralized MPC controller given in Algorithm 8 and the distributed MPC controller given in Algorithm 9. Since subsystems may not reach their final states at the same time, Fig. 8.13(d) shows the different time instants of reaching the final states by using the centralized and distributed MPC. The results are obtained by 139 Chapter 8. Simulations and Comparisons using N= 3, Q=I,Z= 1000 ·I. For other parameters in distributed MPC, we use α= 0.5, ǫ1= 0.1, ǫ2= 10−6. (a) S1(b) S2 (c) S3(d) S4 Figure 8.12: The quadratic distance of ml kto the final state mfl,l= 1,2,3,4 It can be observed that all the subsystems reach their final states in finite time by using both the centralized and distributed methods. From Fig. 8.13(d) we can see that, the last subsystem that reaches its final state is S7, requiring 38 time steps by using the centralized MPC and 51 time steps by using the distributed MPC. However, let us notice that not all the subsystems reach their final states slower by using the distributed MPC. For instance, the distributed MPC controller requires 9 time steps for subsystem S4to reach mf4, smaller than the 14 time steps of using the centralized MPC. On the other hand, Fig. 8.15(a) shows that by using the distributed MPC, the CPU time consumed for computing the control laws (the sum of the CPU time consumed in all the subsystems) is much smaller than by using the centralized MPC, and the reason is clear: the computational complexity of MPC based approaches may grow very quickly on the size of net systems. We should point out that, in both centralized and distributed MPC approaches, from each time step kthe state evolutions of subsystems are constrained to be inside the subset convex R(N,mk,mf) (generated by constrains (6.2d) and (6.2e)) of the reachability space. 140 8.6. Case study 4: distributed control of an AGV System (a) S5(b) S6 (c) S7(d) Time instants Figure 8.13: (a)-(c) the quadratic distance of ml kto the final state mfl,l= 5,6,7; (d) the time instants of subsystems reaching to mfl,l= 1 to 7 Therefore we can see that the states converge to the final ones monotonically. However, in the distributed method the markings of buffers are not controlled as in the centralized method, thus have more “freedom”. Therefore we may not be able to conclude which one is better in general, just considering the time spent on the trajectories. Fig. 8.14 shows the state evolutions of buffer places (we take p1,p16 and p45 as examples). We can observe that the markings of buffer places may reach different values: by using the centralized MPC the final markings specified in mfare reached; but by using the distributed MPC, the markings of buffer places may reach some different (non-negative) values since here we only consider the convergence to the final states of subsystems. By using the distributed MPC the marking trajectory of buffer places, e.g., p45 in Fig. 8.14(b), is no longer monotone. For instance, after 31 time steps, the marking of p45 oscillates around the value of 0.1. This is because subsystem S6reaches its final state at 30 time steps (see Fig. 8.13(d)), then optimization problem (6.11) should be solved in S6and it tries to put more tokens to its (unique) output buffer place p45 when its marking mk[p45]≤ǫ1= 0.1 (see cost function (6.9) and Remark 6.3.1); at the same time, subsystem S7needs to consume 141