Global Petri Net Modeling of Hybrid Systems and Fault Analysis By Mohammad Rezai B . E . Electrical and Electronics Engineering, B h a r a t h i d a s a n University, Tiruchirapalli, India, 1987 M . S c . E n g . Electrical E n g i n e e r i n g , University of N e w Brunswick, Fredericton, 1990 A THESIS S U B M I T T E D IN PARTIAL F U L F I L L M E N T T H E R E Q U I R E M E N T FOR T H E D E G R E E O F D O C T O R O F PHILOSOPHY in T H E F A C U L T Y O F G R A D U A T E STUDIES (DEPARTMENT O F E L E C T R I C A L ENGINEERING) W e accept this thesis a s conforming / t O y t h e , required standard T H E UNIVERSITY O F BRITISH COLUMBIA 1996 © M o h a m m a d R e z a i , 1996 OF In presenting this degree at the thesis in University of partial fulfilment of of department this thesis for or by his or scholarly purposes may be her representatives. permission. Department The University of British Columbia Vancouver, Canada DE-6 (2/88) for an advanced Library shall make it agree that permission for extensive It publication of this thesis for financial gain shall not Date requirements British Columbia, I agree that the freely available for reference and study. I further copying the is granted by the understood that head of copying my or be allowed without my written Abstract In this dissertation, a new methodology for the modeling and analysis of hybrid systems is presented. Hybrid systems are those which have both event-driven (asynchronous) and time-driven (synchronous) elements. This new methodology is based on an extension of the Petri net (PN) theory. Petri nets have proven themselves to be an excellent modeling tool for discrete-event systems and computer architectures. This new extension of Petri nets, which is called a Global Petri Net (GPN), provides a means for extending these capabilities to discrete-time systems. Although, many extensions of PNs have been developed over the years, the G P N methodology is the first one to perform the modeling, analysis, and simulation of discrete-event and discrete-time dynamic systems in a unified PN framework. The G P N is formally defined, and the structural and behavioral differences between PNs and GPNs are presented. The derivation of GPNs from the basic P N , and derivation of the G P N dynamic equations are also given. Next, two modeling examples are provided. These two examples show that the G P N formalism can be used to model hybrid systems in various application areas. Analysis techniques, which can be used to investigate the system properties, are developed. These analysis techniques are based on the construction of the system reachability tree and linear algebraic equations. The properties which are analyzed by these techniques include controllability, boundedness, stability, and conservation. Theorems and proofs of these properties are stated and proven. An example of a distributed hybrid system is modeled at various levels of abstraction. This system consists of a hydraulic control system and its interfaces with a bus-based communication system. At the highest level, the system is modeled as a discrete-event system. At the lowest level, where the details of the hydraulic control system are modeled, a hybrid model is used. The nets at all levels are simulated and analyzed by the global Petri net simulation and analysis tool (GPNSAT), written specifically for this research. ii Various system level faults for a hydraulic control system are modeled and simulated. For each fault type, the simulation shows how various system outputs are affected. At each level of abstraction, the hybrid system is simulated and analyzed for various properties, such as stability, boundedness, controllability, conservativeness, and liveness. Analysis methods developed for GPNs provide distinct fault signatures for each of the system fault types. These fault signatures can be used to distinguish successfully each fault in a detection and recognition scheme. The major contribution of this thesis is the extension of Petri nets to encompass hybrid systems. This new modeling approach can be applied to a variety of systems in application areas such as, manufacturing, multimedia, production, digital, and communication systems. This extension also enables one to examine the impact of faults in either part of the system (synchronous or asynchronous) and the effect that fault would have on the other parts of the system. These effects can be analyzed or simulated either at design time or run-time. iii Contents Abstract ii List of Tables ix List of Figures x List of Definitions xiv List of Symbols and Abbreviations xv Acknowledgments xvii Dedications xviii Chapter I Introduction . . . 1 1.1 P r o b l e m Definition a n d R e s e a r c h Motivation 1 1.2 R e a l - T i m e Control S y s t e m s 2 1.3 Hybrid S y s t e m s 3 1.4 Dissertation Contributions 7 1.5 Dissertation Layout 8 Chapter II Petri Net Modeling of the Systems 10 11.1 Petri Net Definition 10 11.2 Petri Net G r a p h 12 11.3 Petri net D y n a m i c s 12 11.4 A n E x a m p l e of a P N 13 11.5 W h y Petri N e t s ? 14 11.6 A s s i g n i n g Time to Petri Nets 16 11.7 R e v i e w of S o m e Relevant Petri nets : ... 17 11.7.1 Fault Detection by Petri N e t s : 17 11.7.2 Digital Control S y s t e m s : 17 11.7.3 Petri Nets a s Discrete Controllers: 18 iv 11.7.4 Failure Modeling and A n a l y s i s in a Material Handling System: 18 11.7.5 C o n t i n u o u s Petri N e t s : 18 11.7.6 Hybrid Petri N e t s : Chapter III . 19 Global Petri Nets: Definitions and Examples . . . . . . . . 21 .111.1 T i m e d Petri Net Definition 22 111.2 G l o b a l Petri Net Definition 22 111.3 G P N Graph .23 111.4 G P N Dynamics . 24 111.5 A n E x a m p l e of a G P N 25 111.6 Derivation of the G P N from C o n v e n t i o n a l P N 28 111.7 Derivation of G P N D y n a m i c s Equation 29 111.8 C o m p a r i s o n of the P N a n d the G P N M o d e l i n g 111.9 P l a c e a n d Transition T y p e s in G P N 37 111.9.1 Transition T y p e s : 37 111.9.2 Place Types: 111.10 III.10.1 . . . . . . . . . 34 . 39 A d v a n t a g e s of Modeling with the G P N . . . . 40 Hybrid M o d e l i n g ; Water Tank Flow Control E x a m p l e : . . . . . 40 G P N M o d e l i n g of a Six-Transistor X O R G a t e 43 111.11.1 M O S Transistor: 43 111.11.2 G P N Modeling with M O S Transistors: 46 111.11.3 Simulation C o n c l u s i o n s 49 111.11 V Chapter IV G P N Properties and Analysis Methods 50 G P N Modeling Issues 51 IV. 1.1 Hybrid Transition Matrix: 51 IV.1.2 A S u b - c l a s s of G P N s (When A is a Diagonal Matrix): 53 IV.1 IV.2 Condition for G P N Modelability . . . 55 IV.2.1 An Example: 57 IV.2.2 Modelability Condition for the S y n c h r o n o u s Part of G P N s : . . 58 IV.3 G P N Hierarchy 58 IV.4 Analysis Methods 59 IV.4.1 Reachability T r e e : . . . . 59 IV.4.2 Linear A l g e b r a i c M e t h o d : 65 Controllability 67 IV.5.1 Controllability (When A is an Identity Matrix): 67 IV.5.2 Controllability of Time-variant S y s t e m s : 68 Conservation 69 IV.6.1 C o n s e r v a t i o n of G P N s with Diagonal A Matrix: 70 IV.6.2 C o n s e r v a t i o n of any G i v e n G P N : 70 IV.7 B o u n d e d n e s s and Stability 71 IV.8 Liveness 74 IV.9 Safeness : 75 IV. 10 Reachability . : IV.5 IV.6 . 75 vi Chapter V Global Petri Net Simulation and Analysis Tool (GPNSAT) . 76 V.1 Modeling P r o c e d u r e 76 V.2 G P N S A T Top V i e w Structure 77 V. 3 G P N S A T Substructures 78 V.3.1 H u m a n Interface: V.3.2 Net Utilities: V.3.3 Simulators: V . 3.4 A n a l y s i s Tools: Chapter VI VI. 1 -. . 78 79 . . 82 83 Modeling and Analysis of a Hydraulic Control System . . 85 Overall S y s t e m Structure: Level 0 85 Petri Net A n a l y s i s of the M o d e l at L e v e l 0: 91 VI.2 A M o r e Detailed M o d e l of the Overall S y s t e m : Level 1 . . . . 94 VI.3 A Hydraulic Control S y s t e m 96 VI.4 G P N M o d e l of the Hydraulic S y s t e m : L e v e l 2 99 VI.5 G P N A n a l y s i s of the Hydraulic S y s t e m 103 VI.5.1 Linear A l g e b r a i c A n a l y s i s : 103 VI. 5.2 Reachability Tree A n a l y s i s : 105 Simulation and A n a l y s i s P e r f o r m a n c e 106 Fault Modeling and Analysis by G P N 108 VI. 1.1 VI. 6 Chapter VII VII. 1 S y s t e m Level Faults VII.2 Hydraulic S y s t e m Faults 110 S e n s o r Faults M o d e l : 111 VII. 2.1 .108 vii VII.3 Fault S c e n a r i o s : Simulation a n d A n a l y s i s 113 VII.3.1 S e n s o r O n e G a i n C h a n g e Fault Simulation: 113 VII.3.2 S e n s o r O n e G a i n C h a n g e Fault A n a l y s i s : 114 VII.3.3 S e n s o r Two G a i n C h a n g e Fault Simulation a n d A n a l y s i s : , 1 1 7 VII.3.4 S e n s o r s B i a s Faults Simulation a n d A n a l y s i s : . . 119 Other Fault T y p e s 121 Vll.4.1 Actuator Faults M o d e l i n g : 121 VII.4.2 Actuator Faults Simulation a n d A n a l y s i s : 122 VII.4.3 Disturbances a n d S y s t e m P a r a m e t e r C h a n g e s : 124 Fault Conditions M o d e l e d by a G P N 125 C o n c l u s i o n s and Future Work 127 Future W o r k 129 Bibliography 131 Appendix A Modeling of Logic Gates by G P N s 141 VII.4 VII.5 Chapter VIII VIM.I Chapter IX A.1 Inverter G a t e 141 A.2 A N D Gate A.3 N A N D Gate 142 A.4 N O R Gate 142 A.5 O R Gate 143 .142 Appendix B Derivation of the Hybrid Transition Matrix 144 Appendix C Diagonal A Matrix Transformation 147 Appendix D The Hybrid System Global Petri Net Parameters 155 Appendix E Fault Detection, Identification and Reconfiguration (FDIR) Scheme 157 viii List of Tables Table 111.1 Structural Differences between the P N a n d the G P N Table III.2 Simulation R e s u l t s of the G P N R e p r e s e n t i n g an X O R G a t e . . 47 Table VI.3 R o o t s of H k + I Matrices F o r m e d by the Firing of Various Hybrid T r a n s i t i o n s . . Table VII.4 34 105 S e n s o r O n e G a i n C h a n g e Faults a n d Their A n a l y s i s Results 117 Table VII.5 S e n s o r Two G a i n Faults and Their A n a l y s i s R e s u l t s 119 Table VII.6 S e n s o r B i a s Faults and Their A n a l y s i s R e s u l t s . 121 Table VII.7 Actuators Faults and Their A n a l y s i s R e s u l t s Table A . 8 T h e Truth Table for Various Digital Logic G a t e s ix . . . . . . . . 124 141 List of Figures Figure 1.1 A Typical R e a l - T i m e Control S y s t e m 3 Figure 1.2 S y s t e m Classification a n d T h e s i s S c o p e 7 Figure II.3 A S i m p l e E x a m p l e of a Petri Net Modeling a Printing Process 13 Figure III.4 A n E x a m p l e of a S i m p l e G P N 25 Figure III.5 A G e n e r a l G P N with all P o s s i b l e A r c s 31 Figure III.6 Various Transition T y p e s in the G P N . 38 Figure III.7 Various P l a c e T y p e s in the G P N Figure III.8 (a) A S i m p l e Flow control S y s t e m , (b) T h e G P N M o d e l of (a). . 41 Figure 111.9 P l a c e Markings V e r s u s Time Plots for the Flow Control Example. .40 . 42 Figure 111.10 n M O S a n d p M O S Transistor S y m b o l s . . . 43 Figure 111.11 Hybrid G P N M o d e l of a n n M O S Transistor 44 Figure 111.12 Simulation Plots of Different Voltages in a n A n a l o g G P N M o d e l of a n n M O S Transistor Figure 111.13 T h e Six-Transistor X O R G a t e Figure 111.14 Plots of the Input and Output S i g n a l s of the Hybrid M o d e l of the X O R G a t e 46 47 48 Figure 111.15 H S P I C E Simulation R e s u l t s of the Six-transistor X O R G a t e . . 4 9 Figure IV. 16 Hybrid Transitions Figure IV.17 Two E x a m p l e s of Nets not A l l o w e d by Diagonal A 51 Restriction Figure IV. 18 54 T w o E x a m p l e s of Nets A l l o w e d by Diagonal A Matrix Restriction Figure IV. 19 55 A n Algorithm for Constructing G P N a n d P N Reachability Trees 61 X Figure IV.20 E x a m p l e s of a G P N u s e d for Construction of G P N R T s . (a) A G P N with only A s y n c h r o n o u s Transitions, (b) A G P N with a n Extra S y n c h r o n o u s Transition 63 Figure IV.21 Reachability Tree of the G P N G i v e n in Figure IV.20(a) 64 Figure IV.22 Reachability Tree of the G P N G i v e n in Figure IV.20(b) 65 Figure V . 2 3 Modeling P r o c e d u r e U s e d for Translation of S y s t e m Specifications into a C o m p l e t e Net M o d e l . Figure V . 2 4 77 T h e Overall Structure of the G P N Simulation a n d A n a l y s i s Tool ( G P N S A T ) Figure VI.25 78 B l o c k Diagram of a Hydraulic Control S y s t e m H a r d w a r e Structure. .'.. 86 Figure VI.26 Block Diagram of a Distributed S y s t e m at Level 0. 87 Figure VI.27 Petri Net M o d e l of the S y s t e m s h o w n in Figure VI.26 88 Figure VI.28 Simulation R e s u l t s of the P N M o d e l G i v e n in Figure VI.27. (a) P l a c e pi Marking, (b) P l a c e p 2 Marking, (d) P l a c e p A Figure VI.29 M a r k i n g , (c) P l a c e p 3 Marking 90 Simulation R e s u l t s of the P N M o d e l G i v e n in Figure VI.27 w h e n the N u m b e r of B u s C h a n n e l s is Increased to Two. (a) P l a c e pi Marking, (b) P l a c e p 2 M a r k i n g , (c) P l a c e p 3 Marking. (d) P l a c e PA Marking 91 Figure VI.30 T h e Reachability Tree of the Petri Net S h o w n in Figure VI.27 . 92 Figure VI.31 A M o r e Detailed M o d e l of the Overall S y s t e m : L e v e l 1. Figure VI.32 A Petri Net M o d e l of the Distributed S y s t e m G i v e n in Figure ... 94 VL'31 .95 Figure VI.33 S c h e m a t i c D i a g r a m of a Two-stage Hydraulic Valve S y s t e m . 97 Figure VI.34 Block Diagram Representation of the Plant and the Controller C o r r e s p o n d i n g to Transitions U a n d t xi 6 in Figure VI.32 98 Figure VI.35 G l o b a l Petri Net M o d e l of the Plant S h o w n in Figure VI.34. Figure VI.36 G l o b a l Petri Net M o d e l of the Controller S h o w n in Figure . 99 VI.34 Figure VI.37 100 C o m p a r i s o n of Simulation Results of the C o m p l e t e S y s t e m by the G P N M o d e l and a Conventional Control S y s t e m Simulator, (a) Plant Output P l a c e d in Figure VI.35, (b) Control Input P l a c e V in Figure VI.36, (c) Plant Output e X, 0 (d) Control Input V 101 e Figure VI.-38 Result of the Simulation of the C o m p l e t e S y s t e m by the G P N M o d e l (a) Plant Output Validity P l a c e Control Input Validity P l a c e p Figure VII.39 1 0 in Figure VI.32, (b) P 5 in Figure VI.32 102 Simulation Results of the Hybrid S y s t e m w h e n the B u s A c c e s s e s are not Met. (a) Hydraulic S y s t e m Output (Place X 0 Marking), (b) Control Input (Place V e D e s i r e d Input Validity (Place p ) 2 S u b s y s t e m (Place P 7 Marking), (c) Marking, (d) "All Other" ) Marking. 110 Figure VII.40 A S e n s o r Fault M o d e l 111 Figure VI 1.41 A S e n s o r Fault M o d e l a s a M o r e Detailed Representation of S e n s o r Transition Figure VII.42 112 Simulation Plots of the First S e n s o r G a i n Faults, a-b) S e n s o r Cut off.t?/ = 1. c-d) S e n s o r G a i n C h a n g e to G f = -0.5. e-f) S e n s o r G a i n C h a n g e to Gf = - 1 . g-h) S e n s o r G a i n C h a n g e to G f Figure VII.43 = -1.5 115 Simulation Plots of the S e c o n d S e n s o r G a i n Faults, a-b) S e n s o r Cut off, Gf — 1. c-d) S e n s o r G a i n C h a n g e to G f = -4. e-f) S e n s o r G a i n C h a n g e to Gf = - 7 . Xll . 118 Figure VII.44 Simulation Plots of the S e n s o r s B i a s Faults, a-b) S e n s o r B i a s of "10,(1 = 10. c-d) S e n s o r B i a s of 100, d = 100 Figure VII.45 A n Actuator Fault M o d e l Figure VII.46 Simulation Plots of the Actuator Faults, a-b) Actuator 120 122 C u t o f f C / = 1. c-d) Actuator G a i n C h a n g e to G f Actuator G a i n C h a n g e to G f = -0.2. = -1.2. e-f) 123 Figure A . 4 7 T h e Inverter G a t e M o d e l e d by a G P N 141 Figure A . 4 8 T h e A N D G a t e M o d e l e d by a G P N 142 Figure A . 4 9 T h e N A N D G a t e M o d e l e d by a G P N 142 Figure A . 5 0 T h e O R G a t e M o d e l e d by a G P N 143 Figure C.51 A T w o - P l a c e , Two-Transition G P N with All P o s s i b l e A r c s Figure E.52 The FDIR S c h e m e Block Diagram xiii . 147 158 List of Definitions Definition 2.1 Petri Net Section II. 1 Definition 2.2 Enabled Transition Section II.3 Definition 3.1 Timed Petri Net Section i n Definition 3.2 Global Petri Net Section IH.2 Definition 3.3 Diagonalizing Function Section IH.7 Definition 3.4 One Function Section III.7 Definition 3.5 PN Incidence Matrix (N Matrix) Section JJL7 Definition 3.6 P N Transition Firing Vector Section IH.7 Definition 3.7 G P N Transition Firing Matrix Section IH.7 Definition 3.8 G P N Dynamic Equation Section IH.8 Definition 3.9 : P N Dynamic Equation Section IIJ.8 Definition 3.10 : Synchronous Transition Section IH.9 Definition 3.11 : Asynchronous Transition Section IH.9 Definition 3.12 : Real Place Section IH.9 Definition 3.13 : Integer Place Section IH.9 Definition 4.1 : Hybrid Transition Section IV.1 xiv List of Symbols and Abbreviations Symbol Definition A Synchronous Arc Weight Matrix Connecting Places to Transitions, Standard Control Matrix B Synchronous Arc Weight Matrix Connecting Transitions to Places, Standard Control Matrix DEDS Discrete Event Dynamic System Diag Diagonalizing Function Fk G P N Transition Firing Matrix at Instant k fk P N Transition Firing Vector at Instant k FDIR Fault Detection, Identification and Reconfiguration FTP File Transfer Protocol GPN G lobar Petri GPNRT Global Petri Net Reachability Tree GPNSAT Global Petri Net Simulation and Analysis Tool H(k),H Hybrid Matrix at Time Instant k HI Human Interface HMP Health Monitoring Process I Identity Matrix k Time Instant, Sapmling Instant 1. Number of Places k N e t - M(k),M Marking at Time Instant k M(0) Initial Marking N . Incidence Matrix n Number of Transitions One One Function k XV Symbol Definition P = {Pl,P2, • • • , P m } . Places Pi Input Place Po Output Place PN Petri Net PNRT Petri Net Reachability Tree RT Reachability Tree T — {ti, ^2,t } Transitions TPN Timed Petri Net n Transition Times u Input Vector w,pi Asynchronous A r c Weight Matrix Connecting Places to Transitions Witp Asynchronous A r c Weight Matrix Connecting Transitions to Places X State Vector Y A n Abrbitrary Vector, Output Vector z z Transform u Infinity Element in a Reachability Tree xvi Acknowledgments My first and foremost thanks go to my supervisors, Professor Mabo R. Ito and Professor Peter D. Lawrence, for their guidance and insight. They remained my source of inspiration and faith in this work. Their support and assistance are gratefully appreciated. I wish to acknowledge my Ph.D. supervisory committee members, Dr. Andre lyanov and Dr. Jeffrey Joyce, who provided me with the most needed help since the start of this research. I also hope to thank Dr. D. Cherchas for acting as the chair of the examining committee and conducting the defence. I am also heavily indebted to my external examiner, Dr. K . Valavanis, and members of my examining committee, Drs. A . Mackworth, M . Davies and G. Bond. I would like to thank them all for their excellent comments and suggestions. Next, I would like to sincerely thank our EE secretaries, Leslie Nichols and Doris Metcalf, who always looked after all the forms and office work. And finally I should thank my friends in the E E department and high performance computing lab, especially Kendra Cooper for proofreading my thesis draft, and my Iranian friends at U B C who provided the "home away from home" feeling for my family. xvii Dedications To my wonderful wife Fereshteh, whose support, understanding and encouragements made it all possible. And To our sweet daughter, Raumina who has made our lives so much more fun, purposeful, and motivated. xviii Chapter I Introduction In this dissertation, a new methodology for the modeling of hybrid systems is developed. Hybrid systems are defined as systems which have both time- and event-driven parts. Such systems can be found in many application areas, such as manufacturing [1], real-time control systems [2], communication [3], robotics, and production [4]. This modeling technique can also be used for the modeling and simulation of faults in these systems [5]. The system is modeled by a new extension of Petri nets which can replicate the system at various levels of abstraction. This analytical and redundant model can be used to detect and recognize faults. This chapter is an overview of the preliminary notions, concepts, and definitions which are required in the presentation of these research findings. It starts by defining the problem and stating the research objectives. Then the primary application area, the control of realtime systems, is described. Hybrid systems are also defined, and their characteristics are discussed. The chapter ends by enumerating the dissertation contributions and presenting the dissertation layout. 1.1. Problem Definition and Research Motivation Control and system scientists have mainly considered systems whose states change with time. Such systems are referred to as time-driven systems. But with the advent of computers and digital devices, we are faced more and more with systems whose dynamics change with events [6]. These events, which are either internal to the systems or are due to the environment, result in discontinuous states. The state trajectories of such systems are. made up of these changes. Such systems are referred to as discrete-event or event-driven systems. Modeling, simulation, and analysis of any practical system (with a computer and communication parts), has to consider both the time-driven and event-driven sub-systems. Systems which comprise both these sub-systems are called hybrid systems. Event-driven systems have been modeled by many methods, such as Petri nets [7], state machines [8], 1 /. Introduction 2 finite state Markov chains, queueing networks, and Statecharts. On the other hand, control system theory has dealt with the modeling, design, and simulation of time-driven systems. In this thesis, a new methodology and technique is developed and presented which can study hybrid systems using a single modeling tool. This methodology can be applied to any system which is to be modeled and studied as a hybrid system. The study of faults in dynamic systems is a very good example for application of hybrid system modeling [9]. Faults are considered events which change the dynamic (time-driven) behavior of the systems. Modeling fault-prone systems as hybrid systems will allow one to study and predict the effects of faults on overall system behavior [10]. In this way these faults can be detected and recognized by schemes developed for this purpose. The modeling methodology, which is presented in this thesis, can be applied to any type of hybrid systems. This is shown through a series of examples. One example, which is dealt with quite thoroughly in Chapter i n , is modeling of a digital X O R gates composed of MOS transistors. These transistors are modeled at both the analog and digital (switch) levels. However, our primary target area is modeling and analysis of real-time control systems which is described next. 1.2. Real-Time Control Systems Real-time controllers are used increasingly in various facets of life, ranging from home appliances to large and complex systems for industrial and military applications. Real-time means that the correctness of the computation, or the decision, depends not only on the logical correctness, but also on the time at which the result is produced [11]. It should be noted that a fast computation does not guarantee real-time correctness since it may not be completed at the appropriate time [12]. Typical real-time control systems consist of an object or controlled environment connected to a control system (computer) via sensors and actuators (Figure 1.1). Sensors accept data at regular periods or are event-driven [13]. The / . Introduction 3 sensor inputs are used, along with the control strategy, to calculate the control inputs. These control inputs are applied to the system through the actuators. Sensors Control System (Computer) Status ^ . Target System Command Actuators ^ Figure 1.1 A Typical Real-Time Control System. 1.3. Hybrid Systems Since the advent of computers, and their widespread use in everyday life, a new class of systems has emerged called hybrid systems. The prime characteristic of hybrid systems is that they incorporate both continuous components, usually called plants, and also digital components such as digital computers, sensors and actuators controlled by programs. These programs are designed to select, control and supervise the behavior of the continuous parts. The control program reads the sensor data, sampled at discrete times, computes the next control law and imposes it on the plant. The challenge is to develop methodologies which, given a performance specification and system description, extract control programs which will force the plants to meet their performance specifications. This objective cannot be met with any of the traditional modeling and analysis methodologies, which are aimed specifically at either of the continuous-time or discrete-event systems [14]. ' The modeling and analysis of hybrid systems is a complex task which has slowly been gaining attention. Examples of hybrid systems include robots, multimedia applications, communication networks, and supervisory control systems. The motivation for studying hybrid systems is to extend the scope of system theory to handle these examples. The ability to model such systems will provide a means for their control and performance evaluation. / . Introduction 4 The computer and its interfaces in all systems can be characterized as discrete-event dynamic systems (DEDS) [15]. The state of DEDS changes only when an event occurs. It is assumed that nothing important occurs between two successive events. The dynamics of the system are the result of complex interactions of various conditions and events in it [16]. Examples of an event are the pressing of a floor button in an elevator, arrival of a part in a manufacturing system, or failure of a computing system [17]. Another class of systems commonly encountered are those whose dynamics depend on time, referred to as time-driven systems. These systems (continuous time, discrete-time, and sampled-data) have been studied under traditional control system theory. In these systems, the maps from output measurements to control inputs are continuous. Time-driven systems are characterized by differential or difference equations and have been studied in much greater detail compared to DEDS. There has been an increasing interest in the study of hybrid systems which has resulted in many approaches to their modeling and analysis. A good starting point for the study of these works are [18, 19, 20]. In the following some of these works are reviewed. Modeling and analysis of hybrid systems by Petri nets are reviewed at the end of next chapter after PNs are formally defined. Hybrid systems are inherently concurrent and reactive [21]. A hybrid modeling methodology should incorporate techniques for specifying real-time constraints. Hybrid systems are mostly modeled as interacting networks of automata, possibly with infinite number of states, and input and output letters [22]. A n automaton consists of sets of states, input symbols, output symbols, transition functions and initial conditions. Timed automata are defined as those which accept timed input strings [23]. This modeling is used for control of intelligent space vehicles [22]. The main problem with this approach is that it dichotomizes the system into symbolic (discrete) and non-symbolic (continuous) parts. As a result an interface is needed to convert continuous-time signals into sequence of symbols and vice versa. The complexity of the interface determines the ability to model and analyze various systems. /. Introduction 5 The interface given in [22] is quite simple and works only for constant plant inputs. More complex interfaces complicate the analysis of the overall system. Another approach is to model the hybrid systems as products of nonlinear control and finite state automata [24]. According to this view, the automaton switches between the control systems, and that the switching is a function of the discrete input symbols or letters that it receives. The plant state-space is divided into regions (modes). For example, an aircraft control system may have climbing, descending and level flight modes. To go from one mode to a desired one needs a look-up table for suitable control [18]. The mode switching is quite ad hoc since even for simple continuous plants, the identification of possible behaviors is mathematically a very complex task. Moreover, identifying the effects of the proposed mode switching scheme is even more complicated. The stumbling block for the implementation of this scheme is the need for high speed database retrieval in real-time applications. Manna and Pnueli use an extended version of discrete transition systems (itself an extended version of Statecharts), called phase transition systems to specify hybrid systems [25, 26]. Two types of semantics are considered. Super dense semantics is based on hybrid traces, and sampling computations sample the continuous behavior of a hybrid system at countably many observation points. The first one provides a more accurate description of the behavior whereas, the latter semantics is easier for verification. A compromise can be achieved by considering important events. Determination of important events is system dependent and requires a through knowledge of the system behavior which is very difficult for any moderately-complex system. The verification is based on an extension of temporal logic approach which has proven useful for the formal analysis of discrete systems. Their method uses sampled computation and important events together with an inductive proof rule to verify properties of hybrid systems [21]. • Constraint nets are developed as an algebraic computation model of general dynamic systems [27, 28, 29]. The plants, control structure and environment are modeled in a single on-line framework under multiple levels of abstractions. The system requirements / . Introduction 6 are specified by temporal logic and timed V-automata. Extended linear temporal logic is used to represent temporal properties such as safety, liveness and real-time response. Timed V-automata are developed by defining timed states from V-automata and are used to represent any formula in real-time temporal logic. Model checking and stability analysis are used for behavior verification. The constraint nets approach falls short in analyzing the system properties such as controllability and observability. Such properties may possibly be specified and analyzed at the requirement specification stage but the current work does not address them explicitly. Another limitation is that this method cannot specify uncertainties using probabilistic and stochastic system behavior. As a general observation it is worth nothing that there seems to be a gap between the hybrid system modeling approaches attempted by the computer science and the control system research communities. The language used and the problem statement are very different even though they are aimed at modeling and analyzing the same systems. There is an urgent need for methods which can close this gap and pose the problem in a manner and structure which is understandable by both communities. The methodology developed in this thesis is an important step in this direction. Figure 1.2, which is adapted from [30], shows the scope of our research and its domain as a part of system theory classification. Our research is concerned with a restricted class of hybrid systems. They include the systems that can be modeled by the grey ovals in this classification. The term hybrid system in this thesis refers to the class of dynamic, time-invariant, discrete-time systems which are either event- or time-driven. Continuoustime systems which can be discretized (for example, by sampling) can also fall within this domain. / . Introduction 7 (^Systems ( Static •) ( Dyna m i c Time-Varying ) Q Time-lnvariantJ) (^Continuous-Time_) ^Di$Cfete--Tirne^. Time- Driven ") (^Even-Driven^) Figure 1.2 System Classification and Thesis Scope. 1.4. Dissertation C o n t r i b u t i o n s The main contributions of this dissertation are the development of a method for the modeling and analysis of hybrid systems within the Petri Net framework and an examination of their fault-modeling and detection issues. These contributions can be listed as follows: 1. Development of a new methodology for modeling hybrid systems, based on a new extension of Petri net formalism. This extension, called global Petri net, can be used to model both discrete-time and discrete-event systems (Chapter III). 2. Definition and derivation of GPN dynamic equations (Chapter III). 3. Development of a set of analysis tools for checking the properties of systems modeled by GPNs. These tools examine the net properties, such as boundedness, stability, conservation, and controllability (Chapter IV). A sub-class of GPNs is also developed and defined, which can ease the analysis burden. 4. Development of a simulation and analysis package called GPNSAT. This package can model, simulate, and analyze any given hybrid system (Chapter V ) . 5. Application of the methodology developed to a hybrid system consisting of a hydraulic control system, its input-output interfaces, and a communication system. This system is simulated and analyzed for the relevant properties (Chapter VI). 6. Application of the above principles in modeling faults in a hybrid system. These fault models are simulated and analyzed by the G P N methodology (Chapter VII). /. Introduction 8 1.5. Dissertation Layout This dissertation comprises eight chapters. The present chapter was devoted to problem specification and research motivation. The second chapter provides the fundamental definitions related to the modeling of discrete-event systems by Petri nets (PNs). We define the P N structure and dynamics. These definitions are essential for following the rest of this thesis' notations and concepts. The reasons for choosing this platform, to solve the problem at hand, are given and its power and shortcomings are also described. A brief survey of some of the PN-related research in modeling control systems and fault analysis is provided at the end of this chapter. Chapter III formally defines global Petri nets. Derivation of the G P N from conventional P N and derivation of the G P N dynamic equations are also given. At the end of this chapter some modeling examples are included. These examples are used to show the ease and power of modeling with the G P N , and are chosen from different areas of application. Chapter IV is devoted to the investigation of G P N properties and analysis methods. First, some modeling issues, which will be useful in the later analysis, are discussed. The G P N modelability conditions are derived next. It is shown what sort of systems can be modeled with this net. Then, the GPNs hierarchy is discussed. The analysis methods used for GPNs are explained in the final two sections. The application of analysis methods in finding the net properties such as controllability, reachability, boundedness, and stability are also explained. Chapter V describes the tool which has been developed to assist in the modeling, simulation, and analysis of hybrid and discrete-event systems. This tool is called the "Global Petri Net Simulation and Analysis Tool (GPNS AT)". Some of its salient features are presented and use of the tool is described. In Chapter VI, application of the G P N in the modeling and analysis of a complete realtime hybrid control system is demonstrated. This system includes a hydraulic control system with its interfaces with the other parts of the system. The system is modeled as a distributed /. Introduction 9 computing system, with nodes dedicated to various tasks such as control, actuation, and operation. Chapter VII is dedicated to fault modeling, simulation, and analysis by global Petri nets. The system, described in the previous chapter, is used to model and analyze faults in a hybrid system. The chapter starts with system level faults (bottlenecks) and then models and analyzes hydraulic system faults. Conclusions are given in the last chapter. The scope and limitations of the G P N modeling and simulation are discussed. This chapter also includes some recommendations for future research directions. Chapter II Petri Net Modeling of the Systems Petri net (PN) theory [31, 32] was developed by Carl Petri [33] in 1962, primarily as an abstract and formal representation of information flow. Over the years it has turned into one of the most powerful tools for the modeling of systems exhibiting concurrency and synchronization characteristics. Petri nets in their various forms have been used to model and analyze systems in different application areas such as manufacturing [34—36], real-time processing [37, 38], computer architecture [39, 40], dynamic control [41, 42], supervisory control [43-45], material handling [46, 47], and robotics [48]. In this chapter we start by providing the basic Petri net concepts and definitions which are essential for following the rest of this thesis. We then present an outline of the reasons for choosing the Petri net as our modeling tool. At the end of this chapter, a survey of the works related to modeling of real-time control systems by Petri nets is given. This survey also includes the works which use PNs for fault detection and identification. 11.1. Petri Net Definition The Petri net is a directed graph consisting of two types of nodes, called places and transitions. Weighted and directed arcs connect places to transitions, or vice versa. Any given system is modeled as sets of conditions and events. Places represent conditions, and transitions represent events. Each transition has a set of input and output places which represent the pre-conditions and post-conditions of the transition. The state of a net is modeled by the presence or absence of a token in the places. The number of tokens in a place is also referred to as the marking of the place. The initial marking represents the initial condition or the initial state of the net. The state of the net is changed by the firing of transitions, which models the events taking place. A n event can happen only when its pre-conditions are satisfied and is represented by an enabled transition. The firing of a 10 //. Petri Net Modeling of the Systems 11 transition changes the marking of its input and output places, modeling a change in its preand post-conditions. We now formally define a Petri net. Definition 2.1. Petri Net: [31, 32] A Petri net (PN) is a five tuple structure defined as PN = (HI) (P,T,W W ,M(0)), pU tp where P — {pi,P2, •••,Pi} is finite set of places, and / > 0. a T = {h,t2, ...,t } is a finite set of transitions, and n > 0 (any arbitrary place is n represented as p, and any arbitrary transition as t). There are two weight functions, W t and W , which attach a positive integer weight p ip to each arc of the net connecting places to transitions (pt) and transitions to places (tp), respectively. The initial marking is represented by M(Q) = [mi(0) m (0) . . . m/(0)] 2 and is a function from the set of places to the non-negative integers ( superscript T in this thesis always refers to transpose of a matrix). The marking at any arbitrary. time instant k is represented as M(k) = [mi(fc) m,2(k) ... mi(k)] and sometimes is referred to as the number of tokens in each place. The other formal Petri net definition which is widely used [31, 49] defines P N as: PN = {P,T,I,O,M(0)) (H.2) where P, T, M(0) are the same as defined in Definition 2.1. I is an input mapping P x T —> {0,1} (input incidence application [49]) corresponding to the set of directed arcs from P to T. These arcs are called input arcs. O is an output mapping T x P ^ { 0 , l } (output incidence application [49]) corresponding to the set of directed arcs from T to P. These arcs are called output arcs. The conversion between these two forms of definition is straightforward and is governed by the following equations. //. Petri Net Modeling of the Systems 12 w =[w ], pt where W Vtij = I(Pi,Tj) and W= ijPi = 0(Tj,Pi). (H.4) [W ], tp where W (n.3) Pitj tjpi W t and Wt are called input and output incidence matrices. p p 11.2. Petri Net G r a p h The graphical representation is one of the attractive features of Petri nets. It allows a precise and easily understood display of the formal theory. Places and, transitions are represented by circles and bars, respectively. Arcs are shown by arrows, and tokens by small dots inside the places. Arc weights are represented by numbers placed close to the arcs. Absence of a number indicates a weight equal to one. 11.3. Petri net D y n a m i c s The state of a net is represented by the number of tokens in each place. The movement of tokens between places describes the dynamics of the net, and is accomplished by firing of the enabled transitions. Let *x and x' be called the preset and postset of x, where x is either a place or a transition. Definition 2.2. Enabled Transition: [31, 32] Places P l and p are called input and output 0 places of transition t if they belong to the sets't and t*, respectively: Then, transition t G T is called enabled under a marking M(k) of a P N iff Vpj € ' t : M (k) Pi > W (p ,t). pt t An enabled transition can be fired which yields a new marking, given by M (k + 1) = M (k) - Wpt( ,t) forall e't, (H.5) M (k + 1) = M (k) for all p € f , (E.6) Pi Pi Po Po Pi + W (t, ) tp M (k + 1) = M (k) p p Po Pi 0 otherwise. (JJ.7) //. Petri Net Modeling of the Systems 13 II.4. A n E x a m p l e of a P N The following example is meant to illustrate the above concepts and definitions. Figure II.3 shows a Petri net which models a printing process. There are five places rep- resenting various conditions, such as paper availability and printer queue, as defined by P = {pi,p2,P3,P4,P5} = { Paper Available, Printer Queue, Printer Idle, Printing, Print Ready}. There are also three transitions, given as T = { i i , ^ , ^ } = ( Print Request Ar- rives, Start Printing, Finish Printing}. Printing can start when there is enough paper, a print request, and an idle printer. Paper Available Finish Printing Q Print Request Arrives Print Ready Figure n.3 A Simple Example of a Petri Net Modeling a Printing Process. Arc weight matrices are written as: 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 Witp Each element of the arc weight matrices, W pt 0 0 0 1 0 0 0 0 0 1 0 0 1 0 1 and W , represents an arc connecting a place ip to a transition or vice versa, respectively. For example W t(l,2) p — 1 indicates that there is an arc connecting place p\ to transition ti with an arc weight equal to one. The initial marking, with reference to the figure, is written as: Af(0) = [ 3 1 1 0 0 //. Petri Net Modeling of the Systems 14 which indicates that there are three units of paper, one print request, and an idle printer. Under this condition, the transition representing "start printing" is enabled. This transition fires by removing a token from each of its input places (paper available, printer queue, and printer idle). It then adds a token to its output transition, showing that printing is taking place. The place marking vector then becomes: M ( l ) = [2 0 0 1 0] . T The printing completion is modeled by the firing of transition £3. This transition removes a token from the place which is modeling the printing job (J04) and adds a token to the print ready place (ps). This state is presented by the following marking: M(2)=.[2 0 1 0 1] . T • The next printing job starts once there is a new request in the printer queue, represented by a token in the place P2. 11.5. W h y Petri N e t s ? Many modeling and analysis methods, such as dataflow graphs [50, 51], higraph and statechart [52, 53], state machine design, constraint modeling [54, 29, 28], and structured design have been used to model and design various computing systems. methods has found success in the design of a particular type of system. Each of these However, if we compare the P N modeling with each of the above methods, it offers one or more of the following advantages over these methods. These advantages are listed to justify our selection of this method: 1. The model can represent concurrency and synchronization, which are integral parts of any computer system. 2. Both hardware and software can be represented by this model. 3. P N models can be developed and analyzed for various abstraction levels from system level transactions down to the circuit logic level [39, 55]. As noted in [56], a hierarchical //. Petri Net Modeling of the Systems 15 description is not only desirable, but is essential since it is impossible to describe any real system with a sufficient degree of detail in a single model. 4. There have been already many methods developed to analyze the Petri net model [57, 58]. Some of these methods are marking tree, reachability, liveness, boundedness, and invariance analysis [59, 60]. 5. There is already a well-established interest in the P N theory which can benefit our model development efforts. There are many commercial P N tools which can be useful for modeling, analysis, and simulation of the model [61, 62]. There are at least two World Wide Web and FTP sites which provide the latest information on Petri nets and the latest tools [63, 64] available. 6. PNs are very easy to understand and work with, due to their graphical and precise representation scheme. 7. With the addition of temporal and stochastic specifications, the P N provides a structured framework for system simulation and performance evaluation. 8. PNs can be used in the various steps of system development and operation, such as requirement definition, design, testing, simulation and, on-line replication. There are, however, some drawbacks to and trade-offs in using Petri nets which have to be considered. These are the following: 1. Only discrete-event (asynchronous) systems can be modeled with the basic Petri nets. In most real-time control systems, we encounter many elements which have to be modeled as time-driven systems. 2. Even though the basic Petri net has a mix of simplicity and power of expression for essential interactions, it needs further capabilities to be able to model the complexities of actual systems [56]. Moreover, useful extensions for real-time applications are still limited. 3. Modeling, analysis and simulation of a PN is very expensive and requires a large amount of processing power and time. //. 4. Petri Net Modeling of the Systems 16 Some of the analysis methods are restricted to subclasses of PNs. This issue is addressed in Chapter IV on G P N analysis methods. Our extension of the Petri net theory, which will be formally presented in the next chapter, is meant to address some of these shortcomings. Here we would like to point out the folio wings: 1. Hierarchical modeling and distributed detection ease the processing burden and allow more detailed modeling only when it is needed. 2. A new extension to the existing P N is presented which will greatly increase its modeling capabilities and ease of modeling for real-time systems. 3. This new extension has the capability of modeling hybrid systems with both discretetime and event elements. 11.6. A s s i g n i n g T i m e to Petri Nets There are two approaches for adding temporal specifications to the basic PN. A stochastic PN (SPN) [65] is obtained by associating exponentially-distributed firing times to the transitions. Stochastic models are well-suited to performance evaluation but are not suitable for the modeling of real-time systems. In real-time systems, we are concerned with the worst case timing requirements because the system receives input from uncontrollable environments and not meeting the timing requirements may have catastrophic results. Thus, SPNs cannot be satisfactorily used for modeling real-time systems. The other method for temporal specification is to assign time to transitions or, alternatively, to places [66, 48]. In the first extension, time is associated with each of the transitions of the original model. With this model, transition firing is no longer an instantaneous event as defined in the original P N model. Another extension associates a delay to each place in the classical net. It has been shown that assigning time to a transition or a place are equivalent, and any one of them can be transformed to the other one [67]. //. Petri Net Modeling of the Systems 17 The two most important extensions are time P N and timed P N (TPN). The time P N extension [68] defines and associates an interval [t in,t ], m max with each transition, which represents the minimum and maximum time during which an enabled transition should fire. Timed PNs are formed simply by associating a transition firing time to each transition [66]. II.7. R e v i e w of S o m e Relevant Petri nets In this section we review some of the prominent research in Petri net modeling which has been aimed at modeling dynamic systems and/or fault detection and identification. We will briefly describe some of their salient features and discuss their advantages and shortcomings. The interested readers are referred [69-75] for further information about these issues. 11.7.1. Fault Detection by Petri Nets: Petri nets have been used to model a pressurized water reactor's cooling loop [76]. This model is used to detect faults such as leaks in vessels or temperature drifts in the sensors. This method is suitable for detecting failures with very long time constants. Fault detection is performed by checking whether the number of tokens in the places representing the cooler loop remains constant (conservativeness property). The actual, number of tokens per place is compared with the initial token content of the total process. The method presented is applicable only to systems which have physical conservation qualities. In addition, this method can only detect fault as no attempt is made at recognizing its cause. In other words, it cannot localize the fault. 11.7.2. Digital Control Systems: The main purpose of this work [77] is to describe a programmer workbench. A workbench is a package which helps with the creation of a program, in which the code to be tested runs, together with a comprehensive diagnostic utility. A Petri net model is used to define how the utilities of the workbench and the different parts of the control system exchange data. Places and transitions represent data storage (mailboxes) and functions, respectively. Tokens are used to show if a place has all the expected data. This method does not model time-driven processes but instead represents them as a set of conditions and discrete-events. //. Petri Net Modeling of the. Systems II.7.3. Petri Nets as Discrete Controllers: 18 This paper [78] presents an approach to the specification, modeling, and analysis of discrete manufacturing systems. Petri nets have been used for controller specification and implementation. The control computer uses a P N model of the controlled system, using the marking of the net, to determine control actions. In generating a P N model, state values in the systems specification are mapped into distinct P N places. For example, state X , with the possible state values a, b, c, and d, would be mapped onto four P N places. This.sort of modelling can be used only for systems which have a limited number of states with just a few discrete values. Otherwise, the net size can explode even for small examples. The reduced reachability graphs are used which permit efficient evaluation of the state behavior of the system sub-components. n.7.4. Failure Modeling and Analysis in a Material Handling System: Petri nets are used for modeling, simulation, and analysis of failures in a material handling system [47]. A new extension of Petri nets is used called Extended P N (EPN). Six types of places, such as action, sink, and switch are used to model different conditions which arise in the system [46]. Failures considered in the system include both hard failures (in conveyer belts, camera, or the robots), and soft failures (due to transient faults). Reachability graphs are used to analyze safeness, liveness and reversibility properties. H.7.5. Continuous Petri Nets: The markings in an ordinary Petri net have either a binary or an integer value. A binary marking represents the validity of a condition whereas, an integer marking may signify the number of clients in a queue or the number of parts in a resource. The continuous Petri net is a model in which the number of marks in the places are positive real numbers [79,49]. The inspiration for, having real number markings comes from research in production systems in which the number of parts is modeled by real numbers. In this model each mark is cut into infinitely smaller pieces. A transition is enabled if all of its input places have a marking greater than zero (in conventional Petri nets, the markings //. Petri Net Modeling of the Systems 19 should be greater than or equal to one). A quantity TJ of transition Tj can be fired with 0 < Tj < min(M(p ),..., a M(p(,)), where (M(p ),..., a M(p )) is the set of input places of b Tj. Then, TJ is known as a firing quantity. In each transition firing, this quantity is subtracted and added to the input places and output places of the firing transition, respectively. The difference between a discrete P N and a continuous P N is not a structural difference, since they differ only in their markings. Therefore, all structural properties which hold true for the former are true for the latter as well. Timed continuous Petri nets are formed by assigning a firing speed to each transition. A transition can start firing when it is enabled. Firing frequency or speed is taken to be the inverse of transition delay defined as transition time for the timed Petri nets. Once a transition fires, tokens are transferred according to the firing speed of the transitions. In this way, the marking of a net changes continuously instead of in discrete steps, as in Petri nets. There are two approximations in calculating the firing speeds associated with each transition. The resulting models, corresponding to these approximations, are called constant speed continuous Petri nets (CCPN), and variable speed continuous Petri nets (VCPN) [49,80]. The main problem with this methodology is that the variable speed is dependent upon the markings of the net. Computation of the firing speed for transitions with variable speed becomes very expensive. In addition, construction of evolution graphs, which are used instead of the reachability trees, is more complicated. In these graphs one needs to include the firing speed of each transition. These speeds keep changing with changes in the markings. Finally, determination of enabled transitions, even in the case of CCPN, is not as straightforward as for simple PNs and this determination needs a complex algorithm to be implemented. II.7.6. Hybrid Petri Nets: Hybrid Petri nets have been defined by the same group of researchers who have developed the continuous P N [80,41,49]. A hybrid P N is composed of both discrete P N places and transitions (D-places and D-transitions) and continuous PN places and transitions (C-places and C-transitions). Markings and arc weights of the continuous parts can take any positive real number value, just as with continuous PNs. //. Petri Net Modeling of the Systems 20 There are a few issues which should be addressed in evaluating the hybrid Petri net methodology. The first two of these issues have to do with the approximations which are made in modeling different processes. The first approximation is with regard to the markings. Each mark is divided into smaller pieces called tokens. For this approximation to approach the continuous space that it is intended for, the token size should be infinitely small. Since this division cannot be by infinity, any division is in fact a discretization but probably at smaller granularity. The second issue to consider here is that the continuous process or firing is just an approximation of a discrete event [80], and is not a time-driven process. A transition cannot fire if its input conditions are not satisfied (if there is no token in its input places), clearly indicating that it is event-driven and not time-driven. In a hybrid P N , "continuous" really means breaking down a discrete-event which, for example, takes two seconds to occur into a large number of small instances of time. If we define hybrid systems as those which have both event-driven and time-driven processes [15], then hybrid PNs would be a misnomer, since in fact all transitions in a hybrid P N are event-driven. The last issue is the limitations in terms of the markings which can be represented by this method. Since the marking is limited to positive real values only, we cannot have any negative markings. The developers of this method have not felt the necessity of having negative markings since their prime application area is the modeling of production systems. In these systems, positive real numbers would suffice for modeling resources, queues, and parts. But when one considers other application areas such as modeling of dynamic and control systems, the necessity for markings with negative values becomes evident. Chapter Ml Global Petri Nets: Definitions and Examples This chapter describes various features and attributes of a new extension of Petri nets called the G P N (Global Petri Net). We start with our formal definitions of timed Petri nets [66] and the G P N and then describe the G P N operation, using an example. The derivation of the G P N from a conventional P N and the derivation of the G P N dynamic equations are given in the next two sections. A comparison of the P N and G P N modeling is also presented and discussed. Next, various place and transition types allowed in the G P N formalism are described. The final section provides two modeling examples to demonstrate G P N modeling capabilities. There are many extensions suggested by various researchers which are meant to increase the modeling power of PNs. These extensions usually are aimed at a particular application or area of interest and lack a generality which could benefit other classes of applications. Moreover, any increase in modeling power is accompanied by a decrease in the analytical power of the net [31]. In this section, we introduce our extensions to the original P N and call the resulting net a Global Petri Net (GPN). The global Petri net is developed to furnish a new methodology for modeling real-time control systems. This modeling tool has the advantage of preserving many of the P N analysis capabilities, as shown in the next chapter. The Global Petri net (GPN) is a concise extension of the original Petri nets which enables one to model more complex systems. This new extension is developed for modeling hybrid systems which have both time-driven and event-driven parts. The G P N is very general and facilitates the modeling of any kind of digital system, including the digitized versions of analog plants and computer hardware and software. This class of systems covers a large area of applications, including systems in real-time control, robotics, and manufacturing. 21 ///. Global Petri Nets: Definitions and Examples 22 Since the concept of time is essential in the definition of the G P N , we first present our method of adding temporal specifications to the original Petri net which was defined in the previous chapter. 111-1 _ T i m e d Petri Net Definition In the present modeling methodology, we associate time with transitions. This approach is very close to the way time is represented in actual real-time control systems. Definition 3.1. Timed Petri Net (TPN): Timed Petri net (TPN) can be defined formally as TPN — (PN, TT), (EI.12) where PN is as defined in Equation (II. 1), and TT is an n-vector of 0 < tt < oo transition times specified in k sampling times. Each transition, t , takes tt n n sample periods to complete. This time corresponds to the maximum time a transition would take to complete in an actual system, without causing any fault or noticeable performance degradation. A transition fires as soon as all its pre-conditions are met and takes a maximum of tt sampling time to finish. The firing starts by removing tokens from the firing transition's.input places. The transition in this time period is busy and therefore cannot be fired unless the previous firing has ended. Firing ends by updating all of its output.places. III.2. G l o b a l Petri Net Definition Places in a G P N correspond to system parameters, variables, or states. The system dynamics can be observed by looking at the places, which collectively describe the state which, the system is in. Transitions represent processes or operation of various components. A process can be as simple as an addition operation of two numbers, or as complex as an entire system structure. Tokens are the major source of departure of the G P N from the original P N . Tokens.in the original Petri net have.a binary value and therefore result in markings that can have ///. Global Petri Nets: Definitions and Examples 23 only positive integer values. In the global Petri net, markings can take any real number value, including negative values. The positive integer restriction on tokens limits the type of systems which can be modeled. The token in this case can only represent the validity of certain conditions (for example presence and number of parts in a manufacturing system). The inclusion of markings with any real number value enables us to model any state even those which take negative values. Another major deviation from the conventional P N is the types of arcs which are allowed under G P N formalism. There are two types of arcs in a G P N . Event-driven or asynchronous arcs (whose weights are assigned by arc weight matrices W and W ) pi ip are the same as those defined for the Petri net models (Equation II. 1). In addition, there are the synchronous (time-driven) arcs, which are represented by A and B matrices. When A and B matrices have all zero elements, a G P N reduces to a P N . Definition 3.2. Global Petri Net (GPN) : G P N is a triple structure defined as: GPN = (TPN, A,B) , (HI. 13) where TPN P, T, W t, p Wt p = (P,T,W ,W ,M(0),TT) pt . tp and T T are the same as those defined for the T P N (Equation 111.12). M ( 0 ) is an m-vector of initial markings of real numbers, A is an / x n matrix of real value arc weights drawn from places to transitions, and B is an n x I matrix of real value arc weights drawn from transitions to places. III.3. G P N G r a p h The G P N graph is very similar to the P N graph. The only difference is that tokens are represented as numbers instead of dots inside the places. Synchronous arcs with arc ///. Global Petri Nets: Definitions and Examples 24 weights A and B are shown by double arrow arcs. The transition time is scribed beside the transitions. The default value for transition time is one sampling period and may be omitted from the graph,and the definition. III.4. G P N Dynamics In a G P N , firing is an execution of a transition by which the value of one or more markings in the corresponding places are changed. State evolution or dynamics of the net are represented by changes in the marking. Every transition can have both input event (asynchronous) arcs, whose arc weights are given by W pi and time (synchronous) arcs, with arc weights given by the A matrix. A transition which has no input event arc always is enabled, and fires according to its transition time, or in other words, it will fire as soon as it is not busy. Let sets of all input and output places of a transition t, be denoted as 't and f, respectively. Each individual place belonging to one of these sets can be written as p l and p , respectively. Transitions which have input asynchronous arcs must meet the P N 0 firing condition, which is Vp;. G *t : M (k) > W (pi,t). pi pt .* Firing of the transition t results in the following changes in the current state (marking) of input places of the transition t: M (k + l) = M (k)-A{pi,t)M {k)-W ( ,t) Pi Pi Pi pt forallpie't. Pi (EL 14) M (k) and M (k + 1) represent before and after firing markings of input place pi. A(pi,t) Pl Pi and W t(pi,t) represent elements of the arc weight matrices A and W , connecting place i p pt P and transition t. For transition output places, the change in marking can be represented as: M P o i k + 1) = M (k) + B(t,p )M (k) + W {t,p ) Po 0 Pt tp 0 for all p 0 G f and P l G't . (in. 15) Places, which do not belong to either of transition input or output places, are not affected by the firing; therefore, we can write: M (k + 1) = M (k) p p for all p 0 {%f} . (111.16) ///. Global Petri Nets: Definitions and Examples 25 These concepts are illustrated through an example in the next section. The equations for the system dynamics are derived in Section III.7 of this chapter. Modeling advantages and the G P N capabilities are explored more fully through some other examples at the end of this chapter. III.5. An Example of a GPN In this section we present a simple example to show the dynamics of a G P N . Figure III.4 shows a net with three places and three transitions. 3 Figure m.4 An Example of a Simple GPN. Net parameters, as defined in Equation (III. 13), can be written from the figure as: ///. Global Petri Nets: Definitions and Examples P = {Pl,P2,Ps} T = {h,t ,t } 0 0 0 W = 0 0 3 1 0 0 0 2 1 0 A = 0 0 0 B = 0 0 0 0 0 2 3 pt 0 0 0 0 0 0 0 0 1 0 3 - 4 0 0 0 Cm. 17) -io.r mi(0) m (0) m (d) M(0) = 26 2.0 17.8 2 3 This example has three different types of transitions. £ is a synchronous transition since 2 it has no asynchronous input arcs. This transition does not have a pre-condition for its firing and fires instantly when it completes the previous firing. i is an asynchronous transition and 3 fires only when its pre-condition is satisfied, that is when its input place marking is greater than the arc weight connecting them. The arc weight (W (2, 3)), in this case, is equal to pt three. t\ is a hybrid transition since it has both types of input arcs. A complete discussion of the G P N arc types is given in Section III.9. Now we can go through a series of firing to show how the state of the net changes due to the firing of various transitions. At time instant k = 0, the initial marking is M(0) =-[Mi(0) [—10.1 2.0 M (0) 2 M (0)] 3 T = 17.8] . Under this marking, transitions t\ and t are enabled. t\ is enabled 2 since M ( 0 ) = 17.8, which is greater than 14^(3,1) = 1. £ is a synchronous transition 3 2 so it is always enabled. Transition i is not enabled since the marking of place p = 2.0 3 2 is smaller than the arc connecting this place to transition t . The sets of input and output 3 places for these enabled transitions can be written as: •*2 = {pi}, The firing of transitions t\ and t 2 f = 2 {p }. 2 (m.i8) results in changes in their input place (pi and p ) 3 markings. By substituting appropriately from Equation (111.18) in Equation (111.14), we have ///. Global Petri Nets: Definitions and Examples the following: 27 . M i ( l ) = M!(0) - A(l, l ) M i ( O ) - ,4(1,2)71^(0) M3(1) = M ( 0 ) - W p t ( 3 , l ) . (EI.19) 3 Changes in the output places' ( p and ^3) markings due to these transitions firing can be 2 found by substituting the arc weights and initial makings, in Equation (HI. 15): M ( l ) = M ( 0 ) + 5(2,2)Mi(0) 2 2 M ( l ) = M (0) + £ ( l i 3 ) M i ( 0 ) , 3 3 (EI.20) The overall effect of the firing of transitions t\ and £ can be written,by combining Equations 2 (EI.19) and (EI.20). Mi(l) = MJCO) - l)Mi(O) - A(l,2)7^(0) M ( 1 ) = M ( 0 ) + B(2,2)M (0) 2 2 1 (EI.21) M ( l ) = M ( 0 ) + 5 ( 1 , 3 ) 7 ^ ( 0 ) - W (3,1) . 3 3 pt The new markings can be obtained by substituting the net parameters (Equation IE. 17) in the above equations. M i ( l ) = -10.1 - 2(—10.1) - 1(-10.1) = 20.2 M ( l ) = 2 - 4( —10.1) = 42.4 2 M ( l ) = 17.8 + 3(—10.1) 3 1 = -13.5 or M ( l ) = [20.2 42.4 -13.5] -. T (EI.22) With this new marking transition, £3 becomes enabled, but t\ gets disabled since the marking of pz is negative. The sets of input and output places for the enabled transitions ///. Global Petri Nets: Definitions and Examples 28 ti and h can be written as: n '*2 = { P 1 } , * 5 = {P2>, *h = {pi}, = {p }. (m.23) 3 The firing of transitions t and £3 results in a new marking: 2 Mi(2) = M i ( l ) - A ( , l , 2 ) M i ( l ) = 20.2 - 20.2.= 0 M ( 2 ) = M ( l ) + B ( 2 , 2 ) M i ( l ) - W {2,3) = 42.2 + (-4)20.2 - 3 2 2 pt 41.6 M3(2) = M ( 1 ) + Wip(3,3) = -13.5 + 1 = -12.5 3 or -41.6 -12.5] T M(2) = [0 (EI.24) Under this new marking, only transition ti is enabled. However, its firing cannot change any of the markings since marking of its input place pi, at the present time instant is zero. III.6. Derivation of the G P N from Conventional PN In this section we show how the G P N structure can be derived from the conventional Petri nets. Rewriting the equation for Petri net dynamics, Equation (1X5): M (k + 1) = M (k) - W ( ,t) Pt Pi pt for all Pl P l (EI.25) G *t . At time instants k = 0 , 1 , 2 , . . . ,k, while the transition is enabled, we have M (l) = M (0)- . W ( ,t) Pi Pi pt for all Pl M (2) = M (l) - W { ,t) =M (0) Pi Pt pt Pi Pi P i e't .. - 2 x W ( ,t), pt Pi M {k) = M (k - 1) - W (pi,t) = M (0) - k x.W t( ,t) Pi Pt pt Pi p Pi . (m.26) Rewriting the counterpart equation of G P N dynamics (only the synchronous elements), equation (EI. 14), and substituting for time instant k=l, we get ///. Global Petri Nets: Definitions and Examples 29 M {k-+l) = M (k)-A( ,t)M (k) Pi Pi Pi -forallpiE't, Pi M (l) = M (0) - A(pi,t)M (0) . Pi Pi Pi (HI.27) Comparing equations (111.26) and (111.27), if we choose Wp (t,pi) t = —- , (m.28) and run the net for k time samples, we get the same result as if we had run the equivalent G P N for only one sample time. This is one of the reasons it is more concise to model the dynamics of a complex system by a G P N . Similarly.if we compare equations (U.6) and (111.15), we need to choose , EMpm, Wtr(t Po)= (m .29) and run the P N for k time samples, to get the equivalent G P N . III.7. Derivation of G P N D y n a m i c s E q u a t i o n In this section we develop the equations which govern the dynamics of a G P N . This derivation is carried out for a general example and is extended for any given net. In the following derivation we need to define two functions. These two functions are used in the equations which describe G P N dynamics equations. Their importance and usefulness become clear later, when they are used in the derivation. Definition 3.3. Diagonalizing (DiagQ) Function: This function adds the elements of a matrix row and puts the result in the diagonal element of that row. It is denoted by Diag(). ///. Global Petri Nets: Definitions and Examples 30 The following shows its operation: // 0 = On 012 021 022 031 032 011+012 Diag{Q) = 0 0 th en 0 0 0 021 + 022 0 '31 (DX30) + 032 Definition 3.4. One{) Function: This function replaces all non-zero elements of a matrix with one. Zero elements remain the same. This function is written as One(). The following is an example of its use: 2.1 0 th en -3 1 "2.1 0' "1 0' One(S) = One 1 1 -3 1 ) If S = (TJJ.31) The following is a general form of a two-place, two-transition net with all possible arcs among them included. Double and single arrow arcs represent time-driven (synchronous) and event-driven arcs, respectively. ///. Global Petri Nets: Definitions and Examples 31 A(1,1) A(1,2) A(2,1) A(2,2) Figure HI.5 A General GPN with all Possible Arcs Net parameters for this example are written as T = {t t } P = {P1,P2} Wpt = Wpt(l,l) W (l,2) W {2,l) W {2,2) pt pt W = pt A(l,2) -4(2,2) A = h B = 5(1,1] 73(2,1] tp 2 ~W {l,l W (l,2) W {2,l) W {2,2) tp tp ip tp 5(1,2) 5(2,2) Mi(0) M (0) M(0) = 2 Definition 3.5. Petri Net Incidence Matrix N: N is called the Petri net incidence matrix and is defined as T N = W<tp W = pt W {l, 1) - Wpt(l, 1) W (2,1) - W p ( l , 2) [W {l,2) - Wp*(2,l) Wi (2,2) - Wpt(2,2) tp tp tp p t ///. Global Petri Nets: Definitions and Examples 32 Definition 3.6. Petri Net Transition Firing Vector: In a Petri net, the firing of various transitions is represented by a firing vector with a size equal to the number of transitions. Every element of the vector corresponds to a transition. A non-zero entry in the vector shows the number of firings of the respective transition. For example, fk = ^ indicates that at time instant k, transition one is fired twice, whereas transition two is not fired at all. Definition 3.7. Global Petri Net Transition Firing Matrix: In a GPN, the firing sequence is shown both by a vector and a matrix. The firing sequence vector, fk, is used for the asynchronous part of the net. Fk which is used for the synchronous part, is a square matrix of size n (number of transitions). This matrix is diagonal, and each element of the main diagonal corresponds to a transition. The relation between the firing sequence vector and the G P N firing matrix is F k In this thesis we use both Diag(fk) = (EI.34) Diag(fk). and Fk interchangeably to refer to the firing sequence matrix. For the G P N in Figure IH.5, assuming transition t\ is enabled, the transition firing vector at time instant k = 0 will be fo = ^ ' . This transition firing will change the net marking to 0 M (l) = M (0)-A(l,l)Mi(0) 1 1 +B(1, l)Mi(O) + B{\, 1)M (0) - W {l, 1) + W (l, 1) , 2 pt tp M ( l ) = M ( 0 ) - A(2,1)M (0) 2 2 +5(l,2)Mi(0) + 2 fl(l,2)M (0) - W (2,l) + W (l,2) , 2 pt tp Or M(l) MM) Mi(0) M (0)_ 0 2 5(1,1) + 5(1,2) 5(1,1) 5(1,2) 'Mi(O) M (0) 2 0 ^(2,1: + M (0) M (0) t 2 W (l,l)-W (l,l) W {l,2)-W {2,\) tp tp pt pt (LTI.35) ///. Global Petri Nets: Definitions and Examples 33 Using the Diag{) and One() functions, we can write the following: 0 -4(1,1) = Diag | A(2,l) -4(2,1 A ( l , l ) ,A(1,2) Y = Diag(Af -4(2,1) A(2,2) 0 -4(1,1 0 = Diag 5(1,1) 5(1,2) 0 5(1,1) 5(1,2) 'i i r i "1 0" 5(1,1) 1 0 5(2,1) "1 0" 5(1,1) 0 0 5(2,1) 5(1,2) 5(2,2) 5(l,2) 5(2,2). T n n T = [One(A)Diag(f )B] J (JH.36) 0 We can also write the following expression for the asynchronous part of the net: W (l,l)-W (l,l) W (l,2)-W (2,l)\ W (l, 1) - W {l, 1) W (2,1) - W {l, 2) "1" . W ( l , 2 ) - W (2,l) W (2,2) - W^(2,2) 0 tp pt tp tp pt tp (HI. 37) pt tp pt pt Nfo . tp Substituting from expressions (JJI.36) and (UI.37) in equation (UI.35), we get M{\) = M(0) - Diag{Af )M(0) + [One{A)Diag{f )B] M{0) + Nf . T 0 0 0 (HI.38) Now, H = (-Diag{Af ) + [One{A)Diag{f )B] 0 0 0 T (HI.39) is called the hybrid transition matrix (H matrix for short). This matrix is defined formally in the next chapter. Substituting for the H matrix, we get M ( l ) = M(0) + H M{0) + Nf . 0 Q For any time instant k we can write M(k + 1) = M(k) + H M(k) + Nf , k where H is written as k k (HI.41) ///. Global Petri Nets: Definitions and Examples H = (-Diag(Af ) k 34 + [One{A)Diag{f )B] ) T k k (11X42) or H = (-Diag(AF ) k k + [One{A)F B] ) . T k (111.43) III.8. C o m p a r i s o n of the P N a n d the G P N M o d e l i n g In this section we elaborate some of the structural and behavioral differences between the P N and the G P N modeling. Table III. 1 summarizes the major modeling and structural differences between the PN and the GPN. It shows what their elements are and what they represent. PN/GPN Element GPN Representation Place (P) Condition Transition (T) Event, Change of State Arcs ( W s , A , B) Relation Token, Marking (M) ' Condition Validity, State Variable Table 111.1 Graphical Representation (GPN) o 1 —' • PN Representation Condition Event Relation Condition Validity Graphical Representation (PN) o 1 • I * *\ Structural Differences between the PN and the GPN. To demonstrate the G P N and the P N behaviorial differences, we start by looking at the dynamics of each net. ///. Global Petri Nets: Definitions and Examples 35 Definition 3.8. GPN Dynamic Equation: The G P N dynamics, according to equation (111.41), can be defined by M(k + 1) = M(k) + H M(k) + N.f k k . (111.44) If Both A and B matrices are zero, that is if there are no synchronous arcs, then H = ( - D ( 0 . / ) + [0(0).Z)(/o).0] ) = 0 . T k 0 (m.45) If Equation 111.45 is substituted in Equation III.44, the P N dynamic equation can be found. Definition 3.9. PN Dynamic Equation: is given as M(k + 1) = M(k) + N.f k . (111.46) As can be seen from equations (111.46) and (111.44), P N and G P N have different dynamics. In a PN, a new marking is an addition of the old marking and the token movement; in other words, it is an additive type of net. On the other hand for a GPN, a new marking in addition, has a term which is a multiplication of the previous marking. This part can be called the multiplicative one. A GPN, therefore, is a more generalized version of a conventional P N . A Petri net is suitable for modeling discrete-event systems, whereas a G P N is geared towards modeling both discrete-time and discrete-event systems. G P N modeling gives us a tool which can be used to model and analyze a complete real-time system. Another difference in the operation of the two nets is the way a change in the firing sequence affects the marking. Let us write the marking changes for a P N due to two transition firings /o and f\. M ( l ) = M(0) + N.f 0 M(2) =M(l) , + N.h . ///. Global Petri Nets: Definitions and Examples 36 Substituting for M ( l ) in M(2), we get M(2) = M(0) + /vXfo + /i). If we change the order of the firings (first f\ and then /n), we get M(1) = M(0) + N.f , 1 M{2) = M(l) + N.f . 0 Then the final state is M(2) = M(0) + N(f 1 + f ). 0 In the above case, irrespective of which transition firing (/o or /i) we go through first, the final state M(2) will be the same (assuming that the order of transition firing does not change the enabling of transitions). The reason for this equality is that N(fo+'fi) = N(f f ). 1+ 0 Now we look at similar marking changes for a G P N : Af(l) = Af(0) + H M(0) + N.fo 0 M(2) = M(l) + HiM(l) + /V./i . Substituting for M(l) in the equation for M(2), we get M(2) = M(0) + / / M ( 0 ) + # i M ( l ) + 7V(/i + /o) . 0 (HI.53) If we change the order of transition firing, we get a different marking, M(2) = M(0) + //iM(0) + 5 M ( 1 ) + N(f 0 which is not the same as the one in the previous firing order. 0 + /,)•, (HI.54) ///. Global Petri Nets: Definitions and Examples 37 In a Petri net, it does not matter in what order transitions are fired unless they change the set of enabled transitions. In the above example, if we had fired Transition two before Transition one, we would still get the same result. In general, future states of a P N depend on its structure, initial condition, and the number of times each transition fires. For a GPN, however, the future states not only depend on the initial condition and structure of the net, but also on the order that transitions are fired. III.9. P l a c e a n d T r a n s i t i o n T y p e s in G P N Any place in a G P N is either of real or integer type, depending on the type of arcs connected to it. Any transition, however, can be either of synchronous or asynchronous type. Hybrid places and transitions are also defined to be of one of these types. The type of a transition or a place depends on the type of arcs which are connected to them. These types easily can be determined by examining arc weight matrices A , B , W t, and Wt . p HL9.1. Transition Types: p Any transition in a G P N is of either synchronous or asyn- chronous type, depending on its input arcs. Definition 3.10. Synchronous Transition: A transition is synchronous if it has no input asynchronous arc; that is, transition tj is synchronous if all members of column j of weight, matrix W pi are zero. This type of transition has no input pre-condition. It fires as soon as its previous firing is completed and remains busy for a period equal to the transition time associated with it. Definition 3.11. Asynchronous Transition: A transition is asynchronous if it has at least one asynchronous input arc; that is, transition tj is asynchronous if at least one member of column j of weight matrix W pt is non-zero. A n asynchronous transition fires only when its input conditions are satisfied. It remains busy for a period equal to the transition time associated with it. ///. Global Petri Nets: Definitions and Examples 38 Figure III.6 shows all the possible configurations which a transition can have, and the resulting types. In row (a), all transitions are of the synchronous type since there are no asynchronous input arcs. The types of output arcs have no effect on the types of transitions as can be seen in the Figure in.6. Rows (b) and (c) show only asynchronous transitions; since all the transitions have at least one input asynchronous arc. Hybrid transitions such as those in row (c), also can be classified according to this rule. Items (b.l) and (b.3) are labelled as 'Not Defined', since it is not possible to have synchronous output arcs without having synchronous input arcs. Row (d) shows transitions with no input arcs. Items (d.l) and (d.3) are labelled as 'Not Defined' for the same reason that was stated for (b.l) and (b.3). However, (d.4) is also 'Not Defined' since it is an isolated transition. Finally, (d.2) is a synchronous transition since it has no input condition and fires in regular intervals determined by its transition time. (a. 1) Synchronous (a.2) Synchronous (a.3) Synchronous (a.4) Synchronous (b.1) Not Defined (b.2) Asynchronous (b.3) Not Defined (b.4) Asynchronous (c. 1) Asynchronous (c.2) Asynchronous (c.3) Asynchronous (c.4) Asynchronous (d.1) Not Defined (d.2) Synchronous (d.3) Not Defined (d.4) Not Defined Figure III.6 Various Transition Types in the GPN. ///. Global Petri Nets: Definitions and Examples IIL9.2. Place Types: 39 Places in GPNs are of either the real or the integer types. Their types also depend on the type of arcs which are connected to them. Definition 3.12. Real Place: A place is real if it is connected to at least one synchronous input or output transition; that is, place p; is real if at least one member of row i of weight matrix A or i column of weight matrix B is non-zero. A real place gets updated every time one of its input of output synchronous transitions fires. The marking of a real place can have . any real value between minus infinity and plus infinity, unless a bound is specified. Definition 3.13. Integer Place: A place is of the integer type if there is no synchronous transition connected to it; that is, place pi is integer if all members of row i of weight matrix A or i column of weight matrix B are zeros. The marking of an integer place can take only positive integer values. Figure IH.7 shows all possible configurations of a place and its resulting type. Both input and output places, for each case, are drawn to show how they are affected by the type of transitions they are connected to. Places Pi in Figure III.7(a.4) and Pi in (b.4) are 'Not Defined', since they are isolated places which are not permitted either by P N or G P N definitions. The rest of the classifications are quite easy to figure out and are done according to the rules defined above. ///. Global Petri Nets: Definitions and Examples (b.1) (b.2) • 40 (b-3) (b.4) F= Integer fj integer Fj Integer F> Integer P Real p | P Real P Not Defined 2 Figure m.7 n t e g er 2 2 Various Place Types in the GPN. 111.10. A d v a n t a g e s of M o d e l i n g with the G P N In this section and the next we explore the G P N modeling capabilities and advantages through a series of examples. These examples are simple enough for illustration purposes but demonstrate the feature being discussed. The modeling of a simple flow control system is illustrated by the example in this section. The second example, in the next section shows how a six-transistor X O R gate can be modeled by a GPN. This section starts with modeling of nMOS and pMOS transistors. The modeling and simulation of X O R gates are performed by adding up these transistor models to form a larger GPN. m.10.1. Hybrid Modeling; Water Tank Flow Control Example: The following exam- ple often is used to show a simple hybrid system [30, 81]. Figure 111.8(a) shows a simple water tank with a closed loop flow control. The height of the water in the tank at any instant is represented by h. The water level is increased due to the flow into the tank, until the desired height H is reached. At this point water raises the float sufficiently to block the flow. ///. Global Petri Nets: Definitions and Examples T 41 H h (a) -(b) Figure ni.8 (a) A Simple Flow control System, (b) The GPN Model of (a). This system can be represented by the following relation: M * + i) = (?<5 +/ (EI.55) [ h[k) else where f is the height increase due to the constant flow into the tank when the valve is open. While h is smaller than H , its value gets increased by f. This system can be modeled by a G P N as shown in Figure 111.8(b). This net has three places and four transitions. The net parameters can be written as: P = {H,Dtff,h} r 0 0 0 A = 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 Witp 0 0 o 0 B = 1 0 0 0 1 -1 0 0 0 0 0 0 1 / 0 0 0 1 0 0 (ni.56) A l l transitions except t are synchronous and fire at all instants. Place Diff represents the 3 difference between H and h. Transition £3 fires when place Diff =H — h marking is greater than zero, or h < H. Depending on this condition the dynamics of the system changes. When h < H or Diff > 0, all transitions fire and we get the following system equations: ///. Global Petri Nets: Definitions and Examples 42 H(k + 1) = H(k) + H(k) - H(k) = H(k) Diff(k + 1) = Diff(k) - Diff(k) + H(k) - h(k) + 1 - 1 = H(k) - h{k) (111.57) h(k + 1) = h(k) + h(k) - h(k) + f = h(k) +' / . When h exceeds H , the Diff place marking becomes negative, and transition £3 is no longer enabled; therefore, only transitions t\,t2, and £4 fire. The resulting dynamics equation then becomes: H(k + 1) = H(k) + H(k)'-H(k) = H(k) Diff(k + 1) = Diff(k) - Diff(k) + H(k) - h(k) = H(k) - h{k) (111.58) h(k + 1) = h(k) + h(k) - h(k) = h(k) . .' Figure III.9 shows how the place markings change. The desired input ' H ' , the error signal 'Diff', and the height of the water 'h' are plotted by ' * ' , ' ' — ' , and '+' signs, respectively. The desired input H is set at 20. The water is added at two units per sampling time (f=2) until the error signal becomes zero and stops the flow. Time Figure III.9 Place Markings Versus Time Plots for the Flow Control Example. ///. Global Petri Nets: Definitions and Examples 43 111.11. G P N M o d e l i n g of a S i x - T r a n s i s t o r X O R G a t e In this section we will show how a six-transistor X O R gate can be modeled by a GPN. Modeling of various logic gates by GPNs are described in Appendix A . Here, we will first show the modeling and simulation of a single MOS transistor. We will then proceed to model and simulate an X O R gate composed of six of these transistors. The results of the. simulation are compared with those obtained by conventional V L S I analog simulation by HSPICE program. 11.1. M O S Transistor: The Metal Oxide Semiconductor (MOS) transistor has four ter- minals, called gate, drain, source, and substrate (body) [82]. The gate controls the flow of charge between the source and the drain. The fourth terminal, the body, cannot be used for performing useful logic and is not considered here. There are two types of MOS transistors: nMOS and pMOS. Figure III. 10 shows the symbols for these types. D D S S a) nMOS b) p M O S Figure III. 10 nMOS and pMOS Transistor Symbols. Hybrid Model of M O S Transistors: The hybrid model of an nMOS transistor is shown in Figure III. 11. There are five places in this net, representing the voltages at the three terminals and two voltage differences. The voltages at gate {VQ) and source (Vs) act as the input places, and the drain voltage (Vp) acts as the output place. In addition to these, the two internal places determine how the differences in the voltage levels of the terminal voltages control the output voltage. ///. Global Petri Nets: Definitions and Examples 44 A l l transitions in this net, except transition £3, are synchronous and fire in all sample periods no matter what their input place markings are. Transition £3 is asynchronous and is controlled by the gate-to-source voltage, V , which is defined as gs V (k + 1) = V (k) - V (k) + I . gs G s Transition £ 3 is enabled when V is greater than 1, that is when VG is larger than Vs. gs The drain-to-source voltage is computed as V (k + l) = V (k)-V (k) ds s D . -1 F g iu r e HI. 11 H y b d r i G P N M o d e l of an n M O S T r a n s s io tr . Figure in. 12 shows the simulation results for a set of inputs. The source voltage Vs (place P2 marking) was assumed to be at five volts throughout the simulation. The markings of the remaining four places are shown as plots III.12(a)-(d). Gate voltage VQ is at zero volt initially, which keeps the transistor off. VG is then changed to seven volts, which causes the transistor to conduct. Plot III. 12(d) shows the drain voltage (YD). We have marked three regions in this plot, which mark the three stages that the transistor model goes through. Thefirstregion is called ///. Global Petri Nets: Definitions and Examples 45 the "non-conducting" region, which corresponds to the case when the gate voltage is not large enough to turn the transistor on. In this region, transition £4 does not fire, and therefore the drain voltage (Vn) remains at zero volts. The second region corresponds to the behavior which can be approximately described as Ohmic. In this region the drain voltage increases until it almost equals the source voltage. In this region, transition £4 fires, and the drain voltage (V/j) starts increasing to the level set by the source voltage Vs. The rate of this increase can be controlled by the arc weight r, which connects transition £4 to place Vp, according to the following equation: V (k + 1) = V (k) + V (k) - V (k) + rV (k) D D D D d3 or V (k + l) = V (k) + rV {k) . D D d3 The last part is called the "saturation region", and it corresponds to a situation where the voltages stabilize at their final values. This happens when the drain voltage nearly equals the source voltage. In this region transition £4 is still enabled and firing, but it has no effect on the drain voltage. This is due to the reason that, the source-to-drain voltage difference, modeled by place V<i , is nearly equal to zero. s ///. Global Petri Nets: Definitions and Examples 8i 46 (b) Gate to Source Voltage (P3 Marking) 4i • 1 (a) Gate Voltage (P1 Marking) • • • 2 6 o 4 2 10 , . 20 30 Time Sample 1 40 . -6' 0 ' 10 • 20 ' 30 Time Sample (c) Drain to Source Voltage (P4 Marking) (d) Drain Voltage (P5 Marking) c o 'cn c 0) / c o CO DC cn c o // / / / -condi o ° cn a> oc o Figure ni.12 10 20 30 Time Sample 40 0 c o to c o z 0 1 40 Re 0 aturati 1 I Ohmi 0 -4 10 20 30 Time Sample 40 Simulation Plots of Different Voltages in an Analog GPN Model of an nMOS Transistor. m.11.2. G P N Modeling with M O S Transistors: In this section we will use the G P N models for the MOS transistors, developed in the previous sections, to model and simulate an X O R gate. Figure III. 13 shows a six-transistor X O R gate; The first two transistors on the left, P i and N\, form an inverter which inverts the B input. The other four transistors work together to provide the logical operation needed for the X O R gate. ///. Global Petri Nets: Definitions and Examples 47 Figure III. 13 The Six-Transistor XOR Gate. A six-transistor X O R gate at the hybrid level can be built by connecting six hybrid MOS transistor models, which were developed in Section 11.1. This was done by replacing the transistors in Figure 111.13 with their hybrid models, shown in Figure IE. 11. The modeling and simulation was carried out, and the results are summarized in Table IE.2. The model was checked for a set of A and B inputs. The output entries show the final values of these signals before new inputs are introduced. The output of the inverter and the X O R gate are exactly as expected. A B B 0 0 5 0 0 5 0 5 5 0 5 5 5 5 0 0 Table ni.2 Simulation Results of the GPN Representing an XOR Gate. A@B ///. Global Petri Nets: Definitions and Examples 48 Figure in. 14 shows the plots for the input and output signals of the XOR model. Each plot shows how the signals change before settling at their steady state value. The input signals cover a range of all possible inputs. The output of the XOR gate, shown in plot 111.14(d) takes a few samples before reaching its final steady state value. The XOR output is formed by addition of the outputs of the four transistors on the fight hand side of Figure in. 13 (transistors Pi, P$, N , and 7V ). After 2 3 every change in the inputs A, and B, each of these transistors should produce its final output, before the X O R output can reach its final value. (b) Input B (a) Input A 100 200 Time Sample 100 200 Time Sample 300 300 (d) Output AffiB (c) Output! 7 100 200 Time Sample 300 0- 100 200 Time Sample 300 Figure 111.14 Plots of the Input and Output Signals of the Hybrid Model of the XOR Gate. Figure 111.15 show the results of the simulation of the same gate by HSPICE program. The simulation is performed at analog level and using the same schematic circuit diagram as shown in Figure in. 13. The inputs and outputs are shown as four separate plots and are as marked in Figure III. 15. ///. Global Petri Nets: Definitions and Examples 5.( 49 /A I rt H JjJ I I I I I 5.0 l_l L_J I I IB J 4-L I I 0.0 ij£ 0 I LU I I I I I I I L J I L B-- -HJ-- I l j l I I I l l \\ h l I L J LJ I I L_J L /inv B 5.0. n n rj r* a 0 ———H i i i I i i 1 i I I i i r il 1 1 o /xor A B 5.0, i ii 1 •• i i I I II 1 1$ 1 1 1 1 h 1 i ft i i i i h i r u 1 r 0.0 L 0.00 J I I / !/ I L_j I I 100. I I I I 11 Hi I i 200. x10" -3 300. time Figure III. 15 HSPICE Simulation Results of the Six-transistor XOR Gate III.11.3. Simulation Conclusions In this section a modeling example by a. G P N was presented. This example was chosen from an area (analog circuit simulation), quite different from the main focus of the thesis which is modeling and simulation of real time control systems. This example also illustrates how both digital and analog behavior can be modeled by GPNs. The simulation results and their comparison with a conventional simulation method (HSPICE) show the accuracy and correctness of modeling and simulation by GPNs. Chapter IV GPN Properties and Analysis Methods One of the main advantages of using a global Petri net for modeling systems is that the resulting model can be analyzed to find the system properties. The uniqueness of GPN analysis methods are in their ability to investigate the properties such as controllability and stability of hybrid systems. The controllability and stability, and other properties of discreteevent systems are analyzed by ordinary Petri net models. But, the extension of these analysis methods to hybrid systems is what sets G P N apart. Some of the original Petri net analysis techniques can be extended for G P N modeling. In this chapter, we investigate some of the important G P N properties and then develop the necessary tools to analyze them. Modeling any actual system requires a large net with many places and transitions. This results in a large incidence and hybrid transition matrices which may be computationally difficult to check for G P N properties such as liveness and reachability. One way to handle such problems is by synthesis of GPNs. The basic idea is to start with a simple G P N which coarsely represents the system to be modeled, but is simple to analyze. Then more places and transitions are added to capture more modeling details. The additions are carried out in such a manner to preserve the properties which are proven for the more coarse models. In this thesis, we have not dealt with G P N synthesis explicitly, but the developments in Chapter VI are carried out in the top-down synthesis approach just described. We start this chapter by discussing some of the modeling issues which are useful in later analysis. We continue with a discussion of the modelability of a given system by a GPN. We show what types of systems can be modeled with this net, and derive the condition for it. Then, hierarchy of GPNs is discussed. In the final two sections, analysis methods used for the G P N are introduced, and their application in finding system properties such as controllability, reachability, and stability is presented. 50 IV . GPN Properties and Analysis Methods 51 IV.1. G P N M o d e l i n g I s s u e s To put modeling by a GPN in a proper perspective, we first need to discuss the following modeling issues. Then, we will introduce a sub-class of GPNs which will ease the G P N analysis. IV.1.1. Hybrid Transition Matrix: The next state of a G P N at any given instant k is determined by its dynamic equation, derived in the previous chapter (Equation in.41) as M{k + 1) = M(k) + H M{k) + Nf k k , (TV.62) where H is called the hybrid transition matrix, and is written (Equation 111.42) as k (IV.63) As can be seen from Equation (IV.63), corresponding to each transition sequence vector fk we get a different H k matrix. This is true only for transition sequence vectors which include a hybrid transition. To explain and prove this property, we first have to define a hybrid transition. Definition 4.1 Hybrid Transition: A hybrid transition is one which has both asynchronous and synchronous type input arcs (at least one of each). Firing of a hybrid transition affects the H matrix. A hybrid transition is by definition an asynchronous transition, since its firing depends on its input place marking. Hybrid transitions do not fire in every sampling period. Of the transitions shown in Figure 111.6, only four can be called hybrid transitions. Figure IV. 16 Hybrid Transitions. IV . GPN Properties and Analysis Methods 52 Now let any given transition be classified either as a pure synchronous, a pure asynchronous, or a hybrid transition. Corresponding to each transition, is an element in the transition firing vector. If n is the total number of transitions, then n =n +n ps where n , n ps pa pa +n , (IV.64) h and nh, represent the number of pure synchronous, pure asynchronous, and hybrid transitions, respectively. Thereom 4.1 : The number of different H matrices possible for a given G P N is equal to { 0 if 1 if n — 0 and S i f n n n^ = 0 > 1 and n/ = 0 ps 2 " Proof : rip t h (IV.65) > \ . The proof is intuitive but can be explained as below: 1.. When both n ps and nh are zero, it means we have only pure asynchronous transitions and our net reduces to a timed Petri net. In this case, we simply have no H matrix. 2. When there is at least one pure synchronous transition and no hybrid transition, all these pure synchronous transitions fire simultaneously and in every clock cycle, which gives us a single H matrix. 3. When there is one or more hybrid transitions, we get a different H matrix based on what combination of these transitions is fired. For example, for a net with two hybrid transitions; nh = 2, there will be 2 nh = 2 = 4 different H matrices. These correspond 2 to the cases where no hybrid transition fires, one of the two hybrid transitions fires and, when both fire simultaneously. In this case, the number of pure synchronous transitions does not matter since their firing coincides with one of the above 4 cases. Having different H matrices and consequently different dynamic equations is one of the strong points of modeling by a GPN. This allows a single model to represent many different dynamics of a system which are switched by events (firing of transitions). IV . GPN Properties and Analysis Methods 53 IV.1.2. A Sub-class of GPNs (When A is a Diagonal Matrix): A n increase in the mod- eling power of a Petri net extension always is accompanied by a decrease in its analytical or decision power. Peterson in [31] states that "This has resulted in the development of sub-classes of PNs with reasonable structural restrictions which will increase the decision power of the restricted net models while not overly restricting the modeling power". Some of these sub-classes mentioned in the literature are state machines, marked graphs, and simple PNs [41]. One of the restrictions in the case of a G P N is with regard to the A matrix. A is the matrix of synchronous arc weights connecting places to transitions. If we consider the expression for the hybrid matrix H = -Diag{A.F ) + [One(A).F .B} T K k K , (IV.66) when matrix A is a diagonal matrix, it means that there are equal number of transitions and places and there is just one synchronous arc connecting each place to a transition. In that case (One(A)) reduces to an identity matrix, and Equation (IV.66) reduces to H + [F .B] , = —A.F + 5 if, = -A.F K k H k K T k T since F is diagonal, k H =(B -A)F . (IV.67) T K k As can be seen in Equation (IV.67), we can take the firing sequence matrix F out of the k H matrix expression. This is a great help in the analysis of the G P N , as will be seen later. This sub-class of GPNs will have the following restriction: |P*| = | T | = 1. (IV.68) That is, the set of output transitions of every place and the set of input places of every transition have exactly one member. Figure IV. 17 shows a couple of cases which are not IV . GPN Properties and Analysis Methods 54 allowed under this formulation. In Figure IV. 17(a), P* — {^1,^2} and theref ore \p'\ — 2 . (IV.69) This is a violation of the restriction given in Equation (IV.68). In Figure IV. 17(b), *£i = {j0i,P2/ and therefore |*£i| = 2 . (IV.70) This is another example of a violation of the restriction given in Equation (IV.68). (a) (b) Figure IV.17 Two Examples of Nets not Allowed by Diagonal A Restriction. The restriction, imposed to insure that the A matrix becomes diagonal, seems to curtail our ability to model any sort of conflicts. But we should point out that this restriction applies only to the synchronous arcs. For example in Figure IV. 17(a), we can have an asynchronous arc instead of each of the synchronous arcs and not violate the restriction. In that case, we have modeled a conflict between £1 and t . 2 The above restriction does not affect our ability to model synchronization, since we can have \'P\ = \T*\=n . (IV.71) Figure IV. 18 shows two examples of nets which model synchronization and are allowed under the above restriction. IV . GPN Properties and Analysis Methods 55 Figure IV.18 Two Examples of Nets Allowed by Diagonal A Matrix Restriction. We have developed a procedure which converts GPNs with non-diagonal A matrices to GPNs which have diagonal A matrices. Appendix C illustrates this procedure through a general two-place, two-transition GPN. Originally, a G P N is considered which has a nondiagonal A matrix with all non-zero elements. Then, the G P N is transformed to one with a diagonal A matrix. The transformed G P N parameters (A, B,W t,Wt ) are obtained in p p terms of the first G P N parameters. The resulting nets in all cases are larger than the original ones since either the number of places or transitions are increased to make these numbers equal. But, the reduction in analysis complexities very well justifies the conversion especially for analyzing system properties such as controllability and conservation which are analyzed by linear algebraic methods. This should become evident in later parts of this chapter when the analysis methods for GPNs with both diagonal and non-diagonal A matrices are described. IV.2. C o n d i t i o n for G P N Modelability Modelability of any given system by a G P N is defined as the condition which allows the system to be represented by the G P N parameters (a set of places, a set of transitions, appropriate weight matrices and a marking vector). As it was shown in Chapter III and Appendix A , many different types of systems can be modeled by GPNs. These include logic gates and functions, certain types of non-linearities (such as saturation and deadbands), analog and digital electronic devices, and dynamic control systems. The only limitation is to be able to specify the system behavior in terms of a set of states and a set of equations relating IV . GPN Properties and Analysis Methods 56 those states. These equations are formed into a set of state-space matrices. These relations (matrices) can be time-variant even though only time-invariants ones are considered in this thesis. Any such systems is modeled by one of the following two methods. First, for the synchronous part of the system, if the system dynamics are given in the form of a set of state space matrices, we can write the equivalent H matrix and subsequently set up the net by determining its A and B matrices. Then we have to find out how events affect these states and accordingly set up W pt and W tp matrices. Alternately, if the system is described by a set of relations among its parameters in terms of parallel operations or precedences, we can write the net arc weight matrices and then find the H and N matrices. Here, we show the condition for finding the synchronous part of the H matrix by the first method, through an example. The second method is straightforward since we already have the required matrices. Dynamics of G P N is described by M(k + 1) = M(k) + H M{k) + k Nf . k (IV.72) Since we are concerned only with the synchronous part of the system, we assume the N matrix is null. A l l time-invariant linear systems that can be represented by state space can also be represented by the above equation. H matrix is defined as (IV.73) To construct the net we need to find the number of places and transitions and establish matrices A and B. The number of places is fixed by the dimension of the H matrix. In the simplest form, if we model the system such that it has an equal number of places and transitions, and let A and F be our identity matrices, then: Diag(A.F) = Diag(I.I) = I , IV . GPN Properties and Analysis Methods 57 and [One(A).F.B] = [One(I).I.BY = B 1 (TV.74) If we substitute from Equation (IV.74) in Equation (IV.73), we will have (IV.75) H = B - I. Equation (IV.75) above, gives the sufficient condition for any given H to have a representation by a GPN. In many cases we can find a smaller net, that is a net with fewer transitions, which can represent the H matrix. The following example illustrates this point. IV.2.1. A n Example: Let a given system and its corresponding H matrix be '1 0 3 1 "mi (A + 1)" _m (k + 1) _ 2 _m (A;) _ 2 c,r 0 0" 3 0 H (IV.76) Now as shown above, if we take A=I and F=I, then B T = H +J B = 1 0 3 1 1 3 0 1 This results in a net with two places and two transitions. This net also can be represented by a smaller net with only 2 places and one transition. In that case we have A and B = [1 3 ] The H matrix for the second net is exactly the same as the first one. IV . GPN Properties and Analysis Methods 58 IV.2.2. Modelability Condition for the Synchronous Part of GPNs: In this section we would like to show the general condition by which we can find a set of A and B matrices to model a given equation, where A is not necessarily an identity matrix. Assuming that every transition in a net fires exactly once (there are no hybrid transitions), we can write the state equations as M(k + 1) = M(k) + HM(k) where (TV .19) # = ( - 0 + $) e = Diag(A) and $ = [One(A).B] .' T Every H matrix member can be calculated as Hij = —Oij + <f>i j : n H t>J n = - ] T ( A A O + Yl 0(A ).B N=l n H ltJ = N=l Hi 0(Aj ).B iN Nti JtN N>l for i = j (IY.80) for i± j , where n is the number of equations and N is an arbitrary variable. According to the above we have p equations corresponding to H matrix members, and (p x t) unknowns corresponding 2 to A matrix and (p x t) corresponding to B matrix. Therefore, as long as the number of transitions is smaller than half the number of places, we have more equations than unknowns and can be assured of finding appropriate A and B matrices. This is only the sufficient condition for modelability of a given matrix. In most cases finding A and B matrices is much easier than solving these equations. IV.3. G P N H i e r a r c h y In modeling any system with a high degree of complexity, we need to model it at various levels of abstraction since it reduces the analysis burden. A G P N can model different systems at various degrees of abstraction. IV . GPN Properties and Analysis Methods 59 A G P N can be used for two purposes. In its general form it can model a dynamic system, with changes in its dynamics represented by a switching matrix which is event-driven. This switching takes place by the firing of enabled transitions, and it is modeled by firing sequence matrix F. In the special case when F is an identity matrix, the dynamics of the net are fixed. This special case can be used to model a dynamic plant in parts of or in its entirety. The dynamics of a G P N are such that every place is a function of one or more of the other places including itself. In building a model, the number of places is in direct proportion to the number of parameters which should be monitored in the system. When a place is not an input place, it can be written as a function of other places. That way we can reduce the number of places. Any general system can be represented by a net with an equal number of transitions and places: That is, for modeling any system we need a maximum of / places and / transitions. Now, if we eliminate a place by writing it as a function of other places, then we get fewer places as well as. fewer transitions, and consequently a smaller net. The advantage of modeling with the G P N is that we can do all the hierarchical reduction from the H matrix and then translate the final result into a G P N model. IV.4. A n a l y s i s M e t h o d s The two main approaches to the analysis of a Petri net are reachability tree and linear algebraic methods. The first method is based on constructing the set of all reachable markings of the net. This analysis method is only useful for small nets since the reachability tree size explodes rapidly with an increase in the state space size. The linear algebraic method does not involve this problem but may be restricted to only a sub-class of nets [83, 84]. These two methods are described in the following sections. It is shown how they can be applied to analyze a given G P N . IV.4.1. Reachability Tree: The First analysis method is based on constructing a complete reachability tree (RT) or a subset of all reachable states. The tree found by this method IV . GPN Properties and Analysis Methods 60 depends on the initial marking of the net, therefore, this method is considered a behaviorial analysis technique rather than a structural one. By looking at an RT we can discover many of the modeled system properties, such as boundedness, conservativeness, and liveness. These properties will be defined formally in the next section. Use of the RT method for system analysis is explored in the chapter on systems analysis. The main advantage of RT analysis is that it can be used for any system, unlike the linear algebraic method, which might be restricted to a sub-class of nets. It should be noted that a combination of these two methods is necessary for a complete analysis. The main' problem with the RT method is that the size of an RT can become very large for any non-trivial system. The construction of an RT starts with assignment of the initial marking as the root node of the tree and then finds the other nodes by firing each enabled transition. Arcs represent the transition firings and show how a node is reached from other nodes. Each new state is either a middle node or a terminal node. A terminal node can be either an " O L D " or a " D E A D E N D " type. A tree is complete when all the branches end with a terminal node. Next, we present an algorithm for the construction of the G P N reachability tree (GPNRT) and then follow it with an illustrative example. Algorithm for Construction of a G P N R T An algorithm for the construction of G P N reachability trees (GPNRT) has been developed and is given in Figure IV. 19. This algorithm is based on a standard algorithm which is used for constructing Petri net reachability trees (PNRT), as in [85, 31, 49]. IV . GPN Properties and Analysis Methods 61 Figure IV. 19 An Algorithm for Constructing GPN and PN Reachability Trees. 1. Start with the initial marking M(0) as the root node and label it " N E W " . 2. While there is a " N E W " node left, do the following: 2.a. Select a " N E W " node and call it marking M . 2.b. If M is identical to a marking already processed, then tag M " O L D " and go back to step 2.a. For real places, if the marking is close enough to a marking already processed, it is marked "OLD". 2.c. Check i f any transition is enabled under marking M ; i f not, label it " D E A D E N D " and go back to step 2.a. (Note: Synchronous transitions are by definition always enabled.) 2.d. While there are enabled transitions at M , do the following for each enabled transition t-[,t ,...,t and all of the synchronous transitions 2 n 2.d.i.Obtain the marking M ' that results from firing asynchronous at M : asynchronous transition t\, t ,t 2 n and all of the synchronous transitions at M . 2.d.ii.On the path from the root to M , i f there exists a marking M " such that M'(p) > M"(p) for each real Integer place and M ' is not equal to M " , then replace M'(p) by u for each place such that M'{p) > M"(p). 2.d.iii.On the path from the root to M , if there exists a marking M " such that M'(p) > M"{p) for some real places while the sign (+/-) of all other place markings in M ' and M " remain the same, then replace M'(p) by u> for each real place such that M ' ( p ) > M"(p). 2.d.iv.On the path from the root to M if there exists a marking M " such that M'{p) < M"(p) for some real places while the sign (+/-) of all other place markings in M ' and M " remain the same, then replace M'(p) by — u> for each synchronous place such that M'(p) < M"(p). 2.d.v.Introduce M ' as a node and draw an arc with label t form M to M ' and tag M ' " N E W " . 2.d.vi.END 2.e. E N D 3. END IV . GPN Properties and Analysis Methods 62 The modifications to the basic algorithm are presented in boldface. Description of this algorithm is given by highlighting the main differences between this algorithm and the one for the PNRT. 1. We have two types of places in a GPN. Integer places have markings which only take positive integer values and real places which can have real number markings. In the latter case we can have an infinite number of possible states which may differ from each other only by the slightest margin. To limit the number of states that a GPNRT can have, we have introduced a closeness criterion for deciding if a marking is an " O L D " node or not. By this measure, if a marking is within a threshold from an " O L D " node, it is taken to be the same one. This is implemented as step 2.b. in Figure IV. 19. The closeness measure is to be decided by the system designer since it may vary for different systems and depends on the magnitude of the variable that any particular marking represents. A threshold which is too small will increase the size of the RT, whereas a large one may result in missing some important dynamics in the way markings evolve. For markings modeled in this thesis, the threshold was taken to be anywhere from 0.1 to 0.01. 2. There are also two types (synchronous and asynchronous) of transitions in a G P N . Synchronous transitions always are enabled, and fire according to their transition time. In this GPNRT implementation, we have assumed that the transition time for all transitions is the same and is equal to one sampling period. Therefore, all synchronous transitions fire simultaneously and at all sampling periods. Asynchronous transitions are enabled once their input conditions are satisfied. Starting from the root node, we fire one of the asynchronous transitions along with all the synchronous ones to get to the next state. When there are no enabled asynchronous transitions, only synchronous ones are fired. Further, when there are no synchronous ones in the system, that node is marked " D E A D END". This step is implemented as step 2.c. in Figure IV. 19. 3. A n RT can become infinite if the markings are unbounded. To keep the tree finite, a special character u is used which has the following properties. For any constant C, IV . GPN Properties and Analysis Methods 63 LO ± C — LO, LO > C, LO > 'to. A place marking in a P N becomes an LO when its value is increased by a transition firing, while all others remain the same or increase due to the same firing. The reasoning behind this is that the firing of such a transition can repeat an infinite number of times and increase the marking of the output place to infinity. This is possible since none of the markings is decreased which would disable this transition. This step is implemented as step 2.d.ii. Markings of a G P N , unlike those of a P N , can take negative values. Therefore, a place marking can go out of bound both in the negative and positive directions. In this algorithm, we mark the possibility of crossing a negative bound by — LO. An LO or —LO appear in a real place marking, according to the rules shown in steps 2.d.iii. and 2.d.iv. G P N Reachability Tree Examples: Figure IV.20(a) shows a G P N with four places and two transitions. Both transitions are asynchronous since their firing depends on the availability of tokens in place p\. Figure IV.20(b) shows another net which is almost the same as the one in Figure IV.20(a), with the exception of an extra synchronous transition t . We will use 3 these two nets to illustrate how their RTs differ due to this extra transition. The reachability trees for these two nets (a) and (b) are shown as Figures IV.21 and IV.22, respectively. These RTs are found by the algorithm described earlier. P P ? (a) 4 P 4 P 2 l 3 (b) Figure IV.20 Examples of a GPN used for Construction of GPNRTs. (a) A GPN with only Asynchronous Transitions, (b) A GPN with an Extra Synchronous Transition. IV . GPN Properties and Analysis Methods 64 We start by describing the tree found for net which is shown in Figure IV.21(a). The initial making of the net is M ( l ) = [1 0 1 node of the tree . This node is written as (1 0] , which is shown as the main (root) 0 1 0). Under this marking condition, both t\ and t are enabled. Firing of transition t\ results in node (1 2 1 1 0). This firing increases the second place marking while keeping all others the same. According to standard PNRT, with this condition we should get an infinity character, UJ, in the place p marking. 2 But since p is a synchronous place we should apply the GPNRT rule instead. By this rule, 2 we do not get an u> since we have a change in the sign of the other place markings (a change from "0" to positive " 1 " ). Firing transition t 2 from the root results in marking (0 0 0.5 1 ). This node is a " D E A D E N D " since no transition can be fired form this marking as is shown in Figure IV.21. Starting from node ( 1 1 1 0), we can fire both transitions. The firing t 2 in another " D E A D E N D " node in (0 (1 to 1 0 0.5 results 1 ). Fifing of transition t\ gives us node 0). The infinity term w, in place p , indicates that this place is unbounded and 2 can increase infinitely under the same firing condition. Firing transition £i from node (1 this node is marked " O L D " . u 1 . 0 ) does not produce a new node, and therefore Transition t 2 gets us another " D E A D E N D " node. completes the GPNRT for this net. ROOT DEAD END Figure IV.21 Reachability Tree of the GPN Given in Figure IV.20(a). This IV . GPN Properties and Analysis Methods 65 Next we construct the GPNRT for the net given in Figure IV.20(b). The only difference between this net and the previous one (Figure IV.20(a)) is an extra synchronous transition £3. This transition has no firing condition and fires every sample period, along with any other asynchronous transition which might be enabled and firing. Therefore, as can be seen in Figure IV.22, all arcs have £ as one of the transitions being fired. This extra transition 3 produces some extra nodes. A n interesting observation is that there is no " D E A D E N D " node since transition t fire can under any condition. A l l the extra nodes.in this RT are 3 produced due to this fact. ROOT OLD Figure TV.22 Reachability Tree of the GPN Given in Figure IV.20(b). A program was written which computes all the nodes of a given GPN and produces a complete reachability tree. This program will be described in Chapter V . IV.4.2. Linear Algebraic Method: The linear algebraic method is based on an analysis of the dynamic equations of a given net [86]. By checking whether these equations satisfy certain conditions, we can find out about the modeled system properties. Due to the difficulty of the analysis, these properties might be restricted to certain classes of nets as will be shown in the following sections. The dynamic equations for a PN are given as M{k + l) = M{k) + Nf k IV . GPN Properties and Analysis Methods 66 M(k + 2) = M(k + l) + Nf k+1 = M(k) + N[f + f ] k U k+1 f=[fk + ---+Jn], M(k + n) = M{k) + Nf . " (IV.81) By analyzing equation (IV.81) we can prove certain properties for a given P N . These properties are given in the next section. The dynamic equations of GPNs which are used for the matrix equation analysis method are -given below. M(k + 1) = M(k) + H M(k) + Nf , k k M(k + 2) = M(k) + H M{k) + H M(k k + l) + k+1 M(k + n) = M(k) + Nf , k+1 Hk+j^Mik + j - l ) + Nf. (TV.82) i=i Equation (IV.82) represents the dynamic equation, which can be used in this analysis method. If we consider the GPNs with a diagonal A matrix, we can substitute H =(B -A)F T K K in Equation (IV.82) and get • M(k + 1) = M(k) + ( 5 T - A)F M(k) M(k + 2) = M(k)+ [B T + (B -A)F M(k T k+1 + Nf K - k A^F M(k) + l) + Nf K k+i , , IV . GPN Properties and Analysis M(k + n) = M{k) + (B Methods T 67 -A)J2 Fk+j^Mik + j - 1) + Nf . (IV.84) The linear algebraic method does not depend upon the initial marking of the net and only takes into account the structure of the net. Many of the system properties can be proven by this method and are described in the following sections. These two methods (linear algebraic and reachability tree), can be applied in the analysis of GPNs to investigate the modeled system properties. In the following section, we will examine each of these properties in detail and show how they can be investigated by any of these two methods. IV.5. Controllability The Controllability of a control system is defined as an answer to the question "Is it possible to steer a system from a given initial state to an arbitrary state in a finite time period?" [87]. A Petri net is said to be completely controllable if any marking is reachable from any other marking [85]. Controllability of GPNs is defined as follows: given an initial marking M(k), is it possible to reach any desired marking M(k+n), with the given H matrix, in a finite sample time n? IV.5.1. Controllability (When A is an Identity Matrix): As we have shown, to be able to take the firing matrix out of the.H matrix, we need to transform the A into a diagonal matrix. When this transformation is made, we get time-invariant matrices, which are easier to analyze. In such a case, for a G P N we have M(k+-l) = M(k) + H M(k) + k (IV. 85) Nf '. k When matrix A is diagonal, Equation (IV.85) can be written as M(k + 1) = M(k) + (B T - A)F M{k) + Nf k k (IV.86) IV . GPN Properties and Analysis where H , F , and f k k k Methods 68 are H and F matrices, and f vector at time instant k, respectively. Assuming initial marking M(0), and substituting k = 0,1, 2 , . . . , we get M ( l ) = M(0) + [B - A)FoM(0) + yv/o , T M(2) = M(0) + [B T - A ) F o M ( O ) + Nf + (B T Q M(3) = M(0) + ( # + ^B -A^F M{l) 1 0 0 + Nf2. + ^B -A^F M(2) T 1 , - A ) F M(0) + Nf R + Nf T - A ) ^ M ( 1 ) + Nf, 2 (TV. 87) In the same manner, for k = re, we have ii M(n) = M(0) + [B T n - A) F j - j Af (j - 1) + JV i=i . i=i If we take the initial marking M(0) to the other side, we get M(n)-M(0) K-iM(n-l) B 1 -AY-.-'-AB 1 -A)\N\---\N F M(0) 0 (IV.89) In- fo Then, the controllability condition is that the Rank (B T - Ay.---\[B T - IV.5.2. Controllability of Time-variant Systems: Ay.N\---\N = n. (IV.90) When A is taken to be any given matrix (without restriction of being a diagonal matrix), then our H matrix becomes time-variant of the following general form: M(k + 1) = M(k) + H M(k) + Nf k k IV . GPN Properties and Analysis Methods 69 The controllability matrix of such a system is given as [88] [P ,P,,...,P ^] 0 , n where Po = [H k N]\ (IV.92) and P = -P, + P (k + l). l+l t IV.6. C o n s e r v a t i o n When the total token count in a set of P N places remains constant, those places are called conservative. This property is useful in modeling resource allocation in a system. By showing that the number of tokens in a set of places remains constant, we are assured that no resource is created or destroyed. This property can also be used for systems with some conservation properties, for example, conservation of energy assuming no losses. A G P N is said to be conservative if, starting from an initial marking M(k) and for all reachable markings, Y,M {k)= Y,M (k + l). Pi Pi P.EP , (IV.93) P.EP Equation IV.93 is the condition for strict conservation, which rarely holds for systems. A more general form can be written as M^ Y +1 where M i k+ = MlY , (IV.94) = M(k + 1) and M = M(k) are the markings at instants k + 1 and k k, respectively. Y is an arbitrary m-dimensional vector. The weak conservation condition checks the weighted sum of the markings. We first derive the conservation condition for GPNs which have a diagonal A matrix, and later for any given G P N . IV ; GPN Properties and Analysis Methods 70 IV.6.1. Conservation of GPNs with Diagonal A Matrix: From the definition of the dy- namics of a G P N with a diagonal A matrix, we have M = M+ k+1 - A ) FM (B T k k + Nf k k . (IV.95) Transposing both sides and multiplying by a vector Y yields Ml Y = M Y + M F {B T +1 J k - A) T k k T Y + ft' N Y T . Now the condition for conservativeness of a given net can be derived as B - A) Y T = 0, T and NY (IV.97) = 0, T which gives us Mk+iY = I M • Y Vector Y is called a P-invariant, and its properties are discussed in the literature [49]. Theorem 4.1. Conservation Condition (When A is diagonal): A G P N with a diagonal A matrix is said to be (partially) conservative if there exists an arbitrary positive weighting integer y(p) for every (some) place p, such that M^^Y — M Y k (B T - A) Y = 0 IV.6.2. Conservation of any Given G P N : and NY = constant and = 0. T (IV.99) Any given G P N can be written as a series of nets with different H matrices. The conservation property should be ascertained for each of the H matrices. Let the dynamics of a net be given as M k+l = M + HM+ k k k Nf k . (IV. 100) Now depending on the firing condition of the net we get different H matrices, which can be written as H\,Hi,—,Hj. Then the condition for conservativeness of such a net will be NY T = 0 and (IV. 101) H?Y - 0, HjY = 0,and HjY = 0. IV . GPN Properties and Analysis Methods 71 Theorem 4.2. Conservation Condition (Any GPN): A Hj, H ,Hj 2 GPN with H matrices is said to be (partially) conservative if there exists an arbitrary positive weighting integer y(p) for every (some) place p, such that NY T Y = M^Y = constant and = 0 and (IV. 102) HjY = 0, HTY = 0 , a n d HJY = 0 . The conservation property can also be analyzed by the R-tree method. For this we have to inspect the tree and see if the conservation condition holds for each node of the tree. Obviously a set of places with an infinity sign to in one of them cannot be conservative. IV.7. B o u n d e d n e s s a n d Stability Boundedness of an event-driven system and stability of a time-driven system are very similar concepts. Boundedness examines whether one or more of the system states can grow beyond a limit or bound. Stability of a system checks whether for given bounded inputs to the system, its outputs would continue to remain bounded ( Bounded Input Bounded Output, BIBO). These properties are the most important characteristics of any given system. A place in a PN is called I-bounded if the marking of that place cannot exceed a positive integer number I. A P N is bounded if all its places are bounded. Boundedness of a G P N is defined in the same manner. A place in a G P N is called R-bounded if the marking of that place cannot exceed a real number R. A GPN is bounded if all its places are bounded. Since marking in a G P N can have both negative and positive values, we will have both negative and positive bounds. We start this section by showing how the boundedness of a P N is determined by the linear algebraic method. We then show why this method is not sufficient to determine G P N boundedness and present our analysis method. Theorem 4.2. P N Boundedness Condition: [85] A given P N is bounded if there exists a vector Y such that 3Y > 0 and NY T < 0. (IV. 103) IV . GPN Properties and Analysis Methods 72 Proof: [85] The equation for P N dynamics can be written as M =M k+1 k + Nf (IV. 104) . k If we take the transpose of each matrix and multiply both sides by Y , we get Mi^Y = MiY Since M and f are both positive, then k + fiN Y 1 NY becomes negative. Therefore, we can write T k (IV. 105) . Ml Y<MlY . +l (IV. 106) The bound on each individual place marking can be written as (IV. 107) In a GPN, however, not all the places are of P N types and can have both negative and positive markings. Stability or boundedness of a G P N depends on both its synchronous and asynchronous parts. Either proof of stability of the H matrix or boundedness of synchronous places alone does not prove the overall system stability and boundedness. Theorem 4.3. G P N Boundedness and Stability Condition: Any given G P N is both bounded and stable if there exists a vector Y such that 3Y > 0 and N Y <0 (IV. 108) 1 and all roots of its characteristic equations, given by the eigenvalues of [zl — H(z) — I], lie inside the unit circle. Proof: The dynamic equation of a G P N is M(k + 1) = M(k) + H M(k) + Nf k , k (IV. 109) M(k + l) = (H .+ I)M{k) + Nf k If we write the z-transform for this equation, we get k . IV . GPN Properties and Analysis Methods 73 zM(z) = \H{z) + I)M(z) + Nf{z) , .. (IV. 110) M(z) = [zi - H(z) - I}~ Nf(z) . l The stability of this net then depends upon where the poles of the system or the roots of the system characteristic equation, given by the eigenvalues of [zi — H(z) — I], fall. Places with eigenvalues of less than one (whose corresponding poles are within the unit circle) are stable and bounded no matter what the N matrix is. Places with eigenvalues greater than one are unstable and consequently unbounded. Places with their poles on the unit circle are critically stable, and their stability and boundedness depend on the TV matrix. L e m m a 4.3.1. Boundedness a n d Stability Conditions of C r i t i c a l l y Stable Places: Any place with its corresponding H matrix row or column equal to a zero vector has an eigenvalue equal to one. Such places are critically stable can become unbounded if their corresponding elements in vector N Y are not less than or equal to zero. T Proof: The dynamic equations governing the changes in the place markings are given by the folio wings: zM(z) = .(H(z) + I)M(z)'+ Nf(z) M(z) = [zl - H{z)- I]~ Nf{z) . l The change in a place marking is a function of the corresponding H matrix elements and the previous markings. The following equation shows the H matrix in terms of the net IV . GPN Properties and Analysis Methods 74 parameters A , B , and F matrices. Derivation of this expression is given in Appendix B. H = -Diag(Af) + [One(A)Diag(f)B] = T - n E j-1 ijfj ft n n + E 0ijfj ji j-1 n E o jfjbji b T,oijfjbj2 n ~ E n E j=l n E j=l n ... 2 n (hjfj + E o jfjb 2 ... j2 y.Otjfjb j2 n Oljfjbjl E n 0 ••• 2j/j j/ & oijfjbj! - E n ljfj a + E 0 /i/i jn i=i The change in place p marking is governed by the i th z A l l the elements in the i th & (iv. 112) row of the H matrix at that instant. row of the H matrix can become zeros, either because of weight matrices A and B, or the transition firing matrix F. In this case the characteristic root (poles of the system) due to that place will be of the form (z-1). That is, the pole falls on the unit circle. If the whole of the H matrix becomes a null matrix, then zM(z) = M{z) + Nf(z) (IV. 113) M{z) = [zI-I\- Nf{z). l This is the dynamic equation of the P N . In this case the stability problem becomes a boundedness problem and is dealt with the same way we deal with the PNs. Boundedness also can be analyzed by reachability tree analysis. Presence of an infinity symbol in a place marking indicates that that place is unbounded. IV.8. L i v e n e s s Another problem which is of interest in resource allocation is avoidance of deadlock [89, 90]. A deadlock in a Petri net is defined as a transition or a set of transitions which cannot fire [85]. A transition is potentially fireable if, starting from an initial marking, there is a reachable marking in which that transition is fireable. A net is called live if all transitions in that net are potentially fireable. In a G P N , all pure synchronous transitions (those which have no pre-conditions for the firing), are live all the time since they can continue firing no matter what marking their input IV . GPN Properties and Analysis Methods 75 places have. However we can have a situation where the fired transition does not change the markings. For example when the input place marking is zero, the transition firing can go on, but the input and output place markings are not altered by the firing. Therefore in liveness analysis of the GPNs, we consider only the synchronous transitions which can become unabled due to their input place markings. The liveness of a net depends on its initial marking and that is why it is analyzed by the reachability tree method. The reachability tree analysis only proves the liveness of a net for a given initial marking. Structural liveness, in general, is difficult to show and only certain classes (such as free-choice and marked graph nets) can be handled [91] by linear algebraic methods. IV.9. S a f e n e s s Safeness is a special case of the boundedness property. In the Petri net theory, a safe place can have only zero or one token at a time or is 1-bounded. This way a place can be represented by a flip-flop. This property can be used in fault detection to check if a place has erroneously acquired more than one token when it was meant to be a safe one. This property can be defined only for the asynchronous global Petri net places and not for its synchronous ones. The way to check for this property is the same as the one for checking the boundedness except that the bound is taken to be equal to 1. IV.10. Reachability Reachability is the most basic problem of a Petri net analysis. A marking is reachable if there exists a sequence of transition firing which, starting at the initial marking, results in that marking. The reachability problem is analyzed both by reachability tree and matrixequation methods. Reachability of a set of places also can be analyzed and is referred to as sub-marking reachability. Chapter V Global Petri Net Simulation and Analysis Tool (GPNSAT) In this chapter some of the main issues regarding the development and use of a tool for simulation and analysis of hybrid systems are discussed. We start by showing how a net structure can be prepared from other types of information known about the system. We then continue by describing the tool structure and its various functions. V.1. Modeling Procedure Figure V.23 shows the G P N model development procedure. It shows how various system specifications can be translated into G P N parameters. Any system to be modeled can be specified as a set of events and conditions, state space representation, transfer function, or a set of logical statements or simultaneous equations. The modeling procedure changes these specifications into a set of G P N model parameters, such as number of places, transitions, and arc weight matrices. This gives us a number of small G P N models which, when combined by the G P N engine, can represent the complete system. The G P N engine is used for model simulation and analysis. At first we show a top view of the tool structure and then describe its various parts. 76 V . Global Petri Net Simulation and Analysis Tool (GPNSAT) 77 Transfer Function Set of Events and Conditions State Space Logical Statements Simultaneous Equations Modeling Procedure G P N Parameters P , T , A , B , . . GPN Models GPN Models GPN Engine Simulation t Analysis Figure V.23 Modeling Procedure Used for Translation of System Specifications into a Complete Net Model. V.2. G P N S A T T o p View Structure The G P N simulation and analysis tool (GPNSAT) consists of many parts, as shown in Figure V.24. Rounded boxes represent different modules written for performing simulation and analysis of Petri and global Petri nets. The four main parts are the human interface, net utilities, simulators, and analysis tools. A l l of these programs have been written in M A T L A B [92]. The M A T L A B package is very suitable for our purposes since many of the required matrix manipulation routines are already provided. Moreover, routines written in the M A T L A B programming language or C can be used to provide a structured environment for program development. V. Global Petri Net Simulation and Analysis Tool (GPNSAT) 78 At the heart of the GPNSAT is a human interface which takes the input parameters and passes them onto various programs as desired by the user. Inputs can be entered interactively through a keyboard or via an already composed file. Outputs are displayed both graphically and numerically, Input/output devices in Figure V.24 are represented by grey boxes. Input from File input from Keyboard Human Interface Display Simulators PN ) [ GPN Figure V.24 The Overall Structure of the GPN Simulation and Analysis Tool (GPNSAT). V.3. G P N S A T S u b s t r u c t u r e s In this section we describe some of the programs which have been written to model, simulate, and analyze various systems by the GPN formalism. Some important implementations issues are discussed, and the trade-offs are explained. V.3.1. Human Interface: parameters. This module is used for interacting with the user to obtain net The user has two options for inputting the net parameters. S/he can do it interactively by answering a series of questions, or ask the program to access the required information, which is stored in a file. This module can also import directly the parameters from the net integrator described later on. Once the parameters are input, the human interface checks to make sure that there are no inconsistencies in the data. These inconsistencies could be the result of entering arc weight V . Global Petri Net Simulation and Analysis Tool (GPNSAT) 79 matrices with inappropriate sizes, forgetting to enter initial markings, or simply a violation of the PN/GPN rules as given by the PN/GPN formal definitions. The user is informed of any input inconsistencies which are detected by the HI, and is asked to check and re-enter the parameters. V.3.2. Net Utilities: The net utilities module consists of a set of programs used for defining nets. A routine called type checker is used to determine what the types of different transitions and places are. The net integration module takes smaller nets as its input and puts them into a large net, which can then be used for simulation or analysis. In the following we describe each of these routines. Type Checker: Types of places and transitions play an important role in the simulation of GPNs. Depending on what the types are, different firing rules are applied. The types of places or transitions can be defined by the user, and then there will not be any need to use this routine. But if the types are not known or need verification, this routine can check them. Definitions of types of G P N places and transitions were given in Section in.9. These definitions and the algorithm based on them, which determines these types from given arc weight matrices, are used in this routine. Net Integration: As mentioned in Section V . l , modeling with GPN can be carried out by constructing a series of small nets representing various parts of the complete system. These smaller nets can then be juxtaposed to form a complete picture of the total system. The advantage of this kind of modeling is that smaller nets can be analyzed individually and their properties proved before being integrated into the system. Another advantage is that we can modularize the modeling and analysis processes. It this way a module can be used in many parts of the system and, if the need arises, it can be replaced by a new one. Let two smaller nets be defined as: GPN = ( P i , r i , W X p t l , W t p i , Ai,£i,Mi(0)) V. Global Petri Net Simulation and Analysis Tool (GPNSAT) 80 and GPN = 2 (P ,T ,W ,W ,A ,B ,M (0)), 2 2 pt2 tp2 2 2 2 with their places given as P\ = {Pl,P2,---,Pl,Pl+i,---,Pl+c} and P2 = {pi,Pl i,...,Pl ,Pl+c+l,---,Pc+l>}+ +c That is, GPN\ has I + c places, out of which the last c places are the same one as those of net GPN . 2 Net GPN 2 has c + l' places, with first c places same as those of GPN\. The transitions of the two nets are given as T\ = {ti,t , ...,t ,t i,t , 2 n T = {t ,t i, 2 n That is, GPN\ and GPN 2 n+ ...,t i} and n+2 n+( ...,t i,t i i,i^+w'}- n+ n+( n+( + have n + d and n + d transitions, respectively. Out of these transitions, they share d transitions. The transitions are numbered such that the first n + d transitions belong to GPN\, and the last d + n transitions belong to GPN . 2 The weight matrices for these two nets have the following dimensions: GPN X Matrix w Ph GPN 2 A 2 w pi2 Size I + cx n+ d I + cXn+ d c + l' c+l' d + n' X d + n' X Matrix Br B 2 w tP2 Size n+d xI + c n+ d xI + c d + n' x c + l d + n' x c + l' These two nets can be combined to form a larger net. This resulting net has a smaller number of places and transitions than the two nets put together, since we can eliminate the V. Global Petri Net Simulation and Analysis Tool (GPNSAT) 81 redundant transitions and places which are common to both nets. The new net, called GPN, has the following structure: GPN = (P, T, W , W ,A, B, M(0)), pt tp where P = {Pl, P2, • • •, Pl, Pl+1, • • •, Pl+c T = {ty, t , 2 t , t -|_i,t n n n+( ,Pl+ +l,—,Pl+c+l'}, c [, £ „ ( i , +c ...,t [ i}. + 1l+( +n The dimensions of the combined net weight matrices are: GPN Matrix A Wpt Size l + c + l'xn + d+n' l + c + l'xn + d+n Matrix B Wtp 1 Size n + d + n'xl + c + l n + d + n'xl + c + l'. 1 The A and B matrices, given A-[,B\,A2, and B2 can be written as: U 'u t +d ^71 + 1 til 0 0 0 Ai 0 0 0 0 0 0 A, Pl Pl+1 A n+d+n' n Pi P2 0 0 0 0 oo0 0 A2 .0 Pl+c+V Pl A 2 Pl+c Pl+c+1 • • • Pl+c+V B 0 0 0 Pl Pl+1 P2 2 Ai Ai Pl+c Pl+c+1 A x B, B t +d t +d+i 0 n 0 0 0 0 0 0 0 B 2 B 5i n 0 x 0 0 0 .0 0 0 B B t11+d+n' The W t and Wt matrices also can be formed in a similar fashion. 2 p v 2 V. Global Petri Net Simulation and Analysis Tool (GPNSAT) V.3.3. Simulators: 82 Simulation modules simulate many different types of PNs and GPNs. Both timed and untimed versions of these nets are simulated. The first version of this simulator was written for ordinary PNs. Later, timing specifications were added, which enabled modeling of timed Petri nets (TPN). The human interface, based on the net parameters, can decide which one of the simulators is needed. It then can call the appropriate simulator to perform the simulation. Petri Net Simulator: The P N simulator can model any discrete-event system. After getting the net parameters form the human interface routine, it can run the simulation for a specified number of sample periods. At the end of the simulation run, the results are presented graphically by plots of the variations in token counts of each place. The simulator consists of many smaller routines, with each performing a specific task. For example, one routine is used to decide which transition should be fired next when there are more than one enabled transitions. This selection can be decided by a random order assignment or can be prioritized. In the latter case, some transitions have a higher priority and are fired first. The simulator program is a loop which runs for the number of time instants specified by the user. In each pass, the first thing to do is to find the transitions which are enabled. This is done by applying the P N enabling rules. Once all enabled transitions are determined, one of these transitions is selected to be the next one to be fired. The transitions are fired by subtracting tokens, specified by the arc weights connecting them to their input places, from the input places markings. Once the firing is done in this way, a flag is set to mark the transition busy for the time specified by its transition time. Then the pass is continued by checking whether any more transitions are still enabled, taking into account the token movements after the first firing in that run. This is continued until there are no more enabled transitions left. Then the present pass ends and a new one starts by checking whether any transition has finished V . Global Petri Net Simulation and Analysis Tool (GPNSAT) 83 its firing. Completion of a transition firing is completed by adding tokens to output places of the transition. In the untimed version of this simulator, no time is specified for transitions. The firings in this case are atomic actions, and additions and subtractions of tokens are done simultaneously. Other details of the simulation are the same as for the timed version. Global Petri Net Simulator: The G P N simulator was written based on the P N simulator. Its major difference is its capability in simulating synchronous and hybrid nets. The G P N simulation program also consists of many smaller modules. Some of these modules are the same as the ones in the PN simulator, but some are written specifically for G P N simulation. Two routines new to this simulator are ones which implement functions OneQ and Diag{), defined in the G P N dynamic equations. These functions are necessary in every simulation pass to find the system H matrix. Like the P N simulator, every simulation pass starts by deciding which asynchronous transitions to fire next. After firing the first enabled transition, the process continues until all enabled transitions are found. The synchronous transitions are fired once in every pass, unless they are busy completing their earlier firing. V.3.4. Analysis Tools: Another important part of the GPNSAT is its analysis tools. This part also can be invoked by the human interface upon the user's request. The analysis tools module is dedicated to analyzing the given nets. Both reachability tree and linear algebraic analysis methods are available. These programs can check a variety of net properties such as boundedness, stability, and controllability. Depending upon which property one wants, one or both of the analysis methods are used. Reachability Tree Analysis: The module for reachability tree construction is based on the algorithm developed in Figure IV. 19. This algorithm can be used for construction of both PN and G P N reachability trees, using two different routines. The programs closely follow V . Global Petri Net Simulation and Analysis Tool (GPNSAT) 84 the steps enumerated in the algorithm. In MATLAB, a number called Inf is used to denote an arbitrarily large number. This value is used in defining the infinity (LO) nodes of the tree. The RT program continues generating new nodes until all the branches of the tree are processed. At the end, each node is defined as one of the two types, DEAD END or OLD. Once the RT is constructed, we can check for different net properties, such as boundedness, liveness, and conservation. Linear Algebraic Analysis: The other analysis tool is based on the linear algebraic method. This method finds all possible H matrices for a given net by firing different combinations of hybrid transitions. These H matrices, along with the system incidence matrix N, form the basis for the analysis. This method finds the boundedness property by checking if the inequalities formed by 3Y > 0 and hold true. NY T <0 The stability of the system is checked by finding whether the roots of [zl — H(z) — 1} fall within or outside the unit circle. Chapter VI Modeling and Analysis of a Hydraulic Control System In this chapter we demonstrate how our extension of the Petri net theory, developed in the previous chapters, can be used to model and analyze a complete real-time hybrid control system. We also w i l l show how this system is simulated and analyzed by the G P N S A T package. We have chosen a real-time hydraulic control system, which is a very good example of a hybrid system. This system has many interacting parts with stringent fault detection and identification requirements. One of the advantages of using a Petri net is the ability to model a system at various levels of abstraction. This advantage becomes quite evident in the following presentation. We have modeled the system as a distributed computing system with nodes dedicated to various tasks, such as control, monitoring, and supervision. A t the highest level, the system interactions are modeled by a conventional Petri net as an asynchronous system. Later in this chapter, parts of the system are modeled at a more detailed level as hybrid subsystems. VI.1. Overall S y s t e m Structure: L e v e l 0 Figure VI.25 shows a block diagram representation of the hardware structure of a hydraulic machine control system [93]. This structure was used for the dynamic simulation and control of teleoperated hydraulic manipulators [94]. The system consists of a controller, a computing node ( C P U and memory), and a controlled subsystem, which is an excavator. There are also many sensors and actuators which are used for detection and application of outputs and control inputs, respectively. A l l of the subsystems are connected to a system bus which also can be replaced with a communication channel when the system is implemented in a teleoperated mode. 85 V M E Bus System Controller A/D CPU & Memory Joysticks D/A R/D Servo-Valves Resolvers Pressure Transducers Excavator Hydraulics _ - • - Operator Figure VI.25 Block Diagram of a Hydraulic Control System Hardware Structure.[93] Structure i VI. Modeling and Analysis of a Hydraulic Control System 87 Figure V-I.26 shows a generalized and simpler representation of the previous block diagram. It shows a number of subsystems connected to and sharing a common system bus. We assume that the bus is the critical resource, which should be shared by the subsystems, and that its performance and utilization could affect the whole system. Any other part of the system, such as C P U or memory, could also be treated and studied as a resource. But in this study we consider only the bus. The subsystems are numbered one through N , of which the first two and the last one are shown in Figure VI.26. Each subsystem can access and take hold of the bus and use it for its transactions, while the others wait for its release. At this level, the system can be modeled as an asynchronous system. We are not interested in the internal functions of each subsystem and model only the bus utilization. System Bus Subsystem One Subsystem Two • • • Subsystem N Figure VI.26 Block Diagram of a Distributed System at Level 0. The above system is modeled by a Petri net, as shown in Figure VI.27. There are four places representing the three subsystems and the system bus as places p\ — p±, respectively. Arrival of a token in one of the first three places indicates that that particular subsystem has a task to perform and needs to access the system bus. Transitions t\ —h represent the arrival of tasks at subsystems one through three, respectively. These transitions represent external events and fire due to external conditions not modeled within this system. Transitions t± —1§ represent the system bus accesses by subsystems p\ — p$, respectively. VI. Modeling and Analysis of a Hydraulic Control System 88 Subsystem *i One System Bus Subsystem h Two Subsystem N t 6 Figure VI.27 Petri Net Model of the System shown in Figure VI.26. Net parameters for this example are defined as P = {Pl,P2,P3,P4} w,pt 0 0 0 0 0 0 0 0 0 0 0 0 T= 1 0 0 0 1 0 0 0 1 1 1 1 {ti,<2,*3,*4,*5,*6} Wit P "1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0" 0 0 1 1 1 (VI. 126) M(0) = [ 1 0 0 1 TT=[5 10 15 2 4 6]. P and T are the sets of places and transitions, respectively. The W pt and W ip matrices give the weight of the arcs connecting places to transitions, and vice versa, respectively. For example, Wpt (1,4) = 1 indicates that place p\ is connected to transition weight is 1. M(0) = [1 0 0 1] by an arc whose is the initial marking or the marking at time instant zero. It indicates that initially there is one token in places \ and p±, and none in other P places. This is illustrated in Figure VI.27 by the presence and absence of dots (tokens) in the circles representing the respective places. TT is the transition time vector, which associates a time with each transition firing. TT(4) = 2 indicates that transition £4 takes 2 sampling periods to complete (each system bus access by subsystem one lasts 2 sampling periods). The net in Figure VI.26 was simulated by the simulation package described in the previous chapter. Figure VI.28 shows the results of a simulation run. Plots (a) through VI. Modeling and Analysis of a Hydraulic Control System 89 (d) are the token count at places p\ — p±, respectively. Subsystems one through three get a new token, at the rate defined by their input transition firing time. For example, place p\ receives a token every five sample periods as a result of the firing of its input transition t\. Subsystems two and three receive a new token every 10 and 15 sample periods, as determined by their input transition firing time. Ideally, each token should be consumed by the place output transitions before a new one arrives. That is, each subsystem should have a chance to access the bus frequently enough to avoid a pile-up of tokens at the place representing it. The token arrival time and bus access time for this example were selected so that the pile up situation, happens. As can be seen in plots (a) and (b), token counts (marking) at places p\ and p get larger as time goes on. This is more severe in the first subsystem since 2 it gets updated more often. On the other hand place 753 marking, shown as plot (c), never exceeds one, indicating that the bus can keep up with the new token arrivals at this place. The marking at place p± is given as plot (d). This plot shows how the bus switches between idle and busy states. The bus utilization for this case is around 92%. This could be around 100% if it were not for the initial idle time in the beginning, when none of the subsystems needed the bus. The bus utilization and accumulation of tokens in subsystems can be used to decide when a faster bus is needed. VI. Modeling and Analysis of a Hydraulic Control System (a) Place p1: Representing Subsys. One 0 50 Time Sample 90 (b) Place p2: Representing Subsys. Two 100 0 50 Time Sample 100 Figure VI.28 Simulation Results of the PN Model Given in Figure VI.27. (a) Place pi Marking, (b) Place p Marking, (c) Place p3 Marking, (d) Place pi Marking. 2 In the current example all subsystems were taken to have the same access priority. We can easily simulate many different operation scenarios to study the effect of having a faster bus, more than one bus, less frequent token arrivals, and various priority policies amongst the subsystems. A l l these are done simply by changing one or more of the initial settings for the net. For example, let us increase the number of bus channels from one to two by rp setting the initial marking to M(0) = [1 0 0 2] . In this case, the bus can easily meet the transaction demands by the three subsystems. Figure VI.29 shows the plots of the same parameters as those already shown in Figure VI.28. As can be seen, all the bus accesses by the three subsystems are going through in time, and no pile-up of tokens takes place. VI. Modeling and Analysis of a Hydraulic Control System (a) Place p1: Representing Subsys. One 1.51 • 91 (b) Place p2: Representing Subsys. Two 1.51 1 § o O • 1 50 100 1 c CD ° 0.5 0 Time Sample (c) Place p3: Representing Subsys. N 1.5i i • 1 50 100 Time Sample (d) Place p4: Representing System Bus 2rn-n-ni—in i in n 1 mi n n—rrr-n 1 o o c 0 Time Sample 100 Time Sampt Figure VI.29 Simulation Results of the PN Model Given in Figure VI.27 when the Number of Bus Channels is Increased to Two. (a) Place p\ Marking, (b) Place p 2 Marking, (c) Place p Marking, (d) Place p\ Marking. VI.1.1. Petri Net Analysis of the Model at Level 0: 3 We can use the given Petri net to analyze the system model for the various properties which were described earlier. Reachability Tree Analysis: We start the analysis by constructing the reachability tree for the previous example. We use the RT construction tool described in Chapter V to obtain the reachability tree shown in Figure VI.30. VI. Modeling and Analysis of a Hydraulic Control System 92 ROOT (co,co,co,1) OLD Figure VI.30 The Reachability Tree of the Petri Net Shown in Figure VI.27 Figure VI.30 can be used to investigate many of the modeled system properties. These are as follows: 1. Boundedness: The appearance of the infinity symbol to indicates the possibility of unboundedness in a particular place. With reference to the tree, we conclude that the first three places, representing the subsystems, are unbounded. As we saw in the simulation results, this situation can happen when the subsystems cannot access the bus before the next token arrives. Place four, representing the system bus, is safe since its marking never exceeds one. We also constructed the RT for the case where there are two bus channels available. The only difference was in the number of tokens in place p± since it can now have some nodes with two tokens. A l l other markings remained the same. This shows that, with the current structure, the number of bus channels does not eliminate the possibility of a subsystem going unbounded. 2. Liveness: Another interesting fact deduced from the above analysis is the absence of deadlocks, since none of the nodes are marked " D E A D END". This and the fact that the fourth place marking never exceeds one, indicates the mutually exclusive use of the bus by subsystems without getting into a deadlock situation. 3. Conservation: Neither the complete net nor any set of its places is conservative, as the appearance of the UJ symbol in the places' marking indicates. VI. 4. Modeling and Analysis of a Hydraulic Control System Reachability: 93 As the RT shows, only those states in which place four has one token are reachable. A l l other places may reach any marking, starting from the given initial marking. Linear Algebraic Analysis: Other properties of the net can be investigated by the linear algebraic method. The incidence matrix for this net can be written as N = W\tpT "10 0 - 1 0 0 0 1 0 0 - 1 0 0 0 1 0 0 -1 0 0 0 0 0 0 pi (VI. 127) For this net to be bounded, given that Y is an arbitrary positive vector, the following inequalities should hold: NY T "1 0 0 = -1 0 0 0 1 0 0 -1 0 0 0 1 0 0 -1 0" 0 ~yi' 0 2/2 0 23 / 0 J/4. 0 "0" 0 < 0 0 0 0 (VI. 128) These inequalities can be written as 2/i<0 2/2 <0 23 / < 0 (VI. 129) -yi<0 -2/2 -2/3 <0 < 0. Since the first three above inequalities contradict the original assumption of Y being positive, we conclude that the net is not bounded. In fact, this is the same result obtained by the RT analysis. Controllability of the net can be checked by the rank of the incidence matrix N . Since VI. Modeling and Analysis of a Hydraulic Control System rant k[N I 94 =3 (VI. 130) is less than the number of places m=4, this net is not controllable. This is due to the fact that place four, which represents the system bus, cannot be made to have any arbitrary number of tokens. VI.2. A More Detailed Model of the Overall System: Level 1 In the previous section we showed how a distributed computing system can be modeled and analyzed at its highest level as an asynchronous system by a Petri net. In this section we present the modeling of this system at a more detailed level of abstraction. Figure VI.31 shows part of the distributed system, consisting of three subsystems. The first two subsystems represent the field and computing subsystems, which are physically separate and communicate through the system bus. To enable study of the effects of all other subsystems, we have lumped everything else together into a subsystem called ' A l l Other Subsystems'. The field unit consists of the plant and its input-output interfaces with the world, such as sensors and actuators. System Bus Actual Output Desired Input Sensors Control Input Desired Input Control Input Actual Output Actuators *• Controller All Other Subsystems Plant Field Subsystem Desired Input Computing Subsystem Figure VI.31 A More Detailed Model of the Overall System: Level 1. VI. Modeling and Analysis of a Hydraulic Control System 95 This system at this level can be modeled by another Petri net, as shown in Figure VI.32. This net provides a more detailed description of the system under study by modeling the internal structure of each subsystem. All Other Subsystems t-t — I — Field Subsystem Figure VI.32 A Petri Net Model of the Distributed System Given in Figure VI.31. Places : User Input P7 : All Other Subsys. ti : Sensor Output Ps Desired Input P3 : Control Input Ps ••Actual Output h Pi Actuator Output Pio : Controller Output U h Pb •'Plant Output Pn System Bus p : Sensor Output Pl P2 Transitions U ser Sensor Actuator Plant Sensor U : Controller t Bus Access Bus Access u Bus Access tio: Bus Access 7 6 The above net is still a conventional Petri net and does not have any of the G P N nodes. In a system represented by an event-driven model, we only know when an event starts and ends and have no idea what happens in between. For example when both places ps and ^9 have a token (both the desired input and the actual output are present), the controller routine VI. Modeling and Analysis of a Hydraulic Control System 96 can run which is modeled by the firing of transition t§. The next information available to us is when this process is completed. The completion is modeled by the arrival of a token at place PIQ. We have no idea what happens while the event is in progress. The other information which is missing in the discrete-event model is the actual (quantitative) value of each signal. For example, all we know is that the control input is generated and available (a condition). But we have no information as to what its value is. In order to see the dynamics of the system in between events, we can model the process as a time-dependent element by a GPN. In Figure VI.32, transitions £4 and t$ represent the plant and the controller, respectively. These transitions are shown as boxes instead of bars. Each of these transitions can be modeled by a G P N with both synchronous and asynchronous elements. VI.3. A Hydraulic Control System The parts of the system that we have chosen to model are the field and computing (controller) subsystems (Figure VI.31). The resulting model at this level is a global Petri net which represents a hybrid system consisting of both time and event-driven parts. The G P N modeling methodology used in this example can be applied to other hybrid systems, including those in flexible manufacturing systems, process control, robotics, and communication systems. The system shown in Figure VI.33 is a two-stage electro-hydraulic valve along with its control circuitry [95, 96]. It consists of a pilot spool valve whose movement varies the differential pressure acting at the ends of the main spool. The output flow rate from the main spool is used to drive the piston, which is provided with a feedback loop. VI. Modeling and Analysis of a Hydraulic Control System 97 Figure VI.33 Schematic Diagram of a Two-stage Hydraulic Valve System [95] By deriving the relevant equations which describe the hydraulic system (Figure VI.33), we can draw the block diagram shown in Figure VI.34. It is a second order system with feedback. A l l the parameters in the block diagram correspond to those in the schematic diagram represented in Figure VI.33. We derived the transfer function for the block diagram in Figure VI.34 as X —- = V- • 2A Ar K K K K\K\P a r CVI 132) s C2 I fA ° K K[y/J£ K m v ~ir~ — r f p C I 1 V ' ' ' The above transfer function can be written in the state space form described by the following equations: X(s) Y(s) AX{s) + BU(s) = CX{s) . (VI. 133) VI. Modeling and Analysis of a Hydraulic Control System 98 Field Subsystem X K K A X X V • R MPg/2 1/A m —=t X K;VP /2 —*• J s l/A 0 R J Controller Subsystem Figure VI.34 Block Diagram Representation of the Plant and the Controller Corresponding to Transitions < and t 4 X and X 0 in Figure VI.32. 6 which are output and main valve displacements, respectively, are selected m as the system states. We have also selected the outputs to be the same as these two states. The control input (V ) is the difference of the reference input (Vi) and the feedback from e the system (X ). 0 X(s) = xi(s) ~X (s)~ = x { )y 0 X2{s) m 'Xo(s)' Y(s) = X (s)_ (VI. 134) s s) = V (s e m With this structure, we will have the following state space matrices in terms of the system variables: A = 0 0 0 B = '1 0' C = 0 1 0 (VI. 135) The controller was designed by varying the feedback gains to attain a fast tracking of the system reference inputs and a small steady state error. The control input can be written as VI. Modeling and Analysis of a Hydraulic Control System U(s) = V (s) = Vi(s) - KpY^s) - K Y {s), e f 2 99 (VI.136) where V is the reference input, and K and Kf are the feedback gains. l p The system was converted from continuous to discrete-time by assuming a zero-order hold on the inputs and a sample time equal to 0.02 seconds. The discretized system in state space form can be written as X(k + 1) = AX(k) + BU(k), (VI. 137) Y(k) = CX(k), where X , Y and U represent the same states, outputs, and inputs, respectively. The system parameters (A, B and C matrices) for the discrete model are A "0 2.5' 0 0 B= ' 0 ' 0.1 C = '1 0" 0 1 (VI. 138) VI.4. G P N Model of the Hydraulic System: Level 2 In this section we present the G P N model of the hydraulic system and then show how it can be integrated into the model developed at level 1. As a general procedure, we should represent each of the inputs, outputs and system states as distinct places. The relation among these states or places is modeled by transitions and arcs connecting them. Figures VI.35 and VI.36 represent the G P N models for the plant and the controller respectively. Figure VI.35 Global Petri Net Model of the Plant Shown in Figure VI.34. The a and b in the above figure are given as VI. Modeling and Analysis of a Hydraulic Control System 100 (VI. 139) Figure VI.36 Global Petri Net Model of the Controller Shown in Figure VI.34. The complete hybrid system consists of the net in Figure VI.32 with transitions t and 4 t$ replaced by their equivalent GPNs (shown in Figures VI.35 and VI.36). The system at this level was simulated by the GPNSAT (Global Petri Net Simulation and Analysis Tool) package . Figures VI.37(a) and (b) show the plant output and the control input, respectively, as simulated by the G P N model. These are the states modeled by places V and Y\ in Figure e VI.35. We would have obtained the same results if we had simulated the system as a conventional control system without any of the distributed communications (system bus). The results of the simulation by a conventional control system simulation program (MATLAB), in continuous-time, are shown in Figures VI.37(c) and (d) for comparison. The plant was discretized at 0.02 second (50 Hz) as mentioned in the previous section. In each sample period, which takes 0.02 seconds, the outputs are sensed and control inputs are applied exactly once. The transition time of the system bus is chosen to be one third of the plant sampling time, i.e. 0.02/3 = 0.0067 second. The reason for this selection is that the VI. Modeling and Analysis of a Hydraulic Control System 101 bus has to be accessed at least three times during each plant sampling period. These accesses are by two output sensors (twice) and by the actuator input (once). In this way, the speed of the communication (bus access) is three times that of the plant sampling time. That is, transitions £4 and t$ take three times as long to fire as do transitions £7 — £10. The G P N simulation was run for 100 sampling periods (each equal to one transition sampling time). Because of the reason just explained, the results that we get after 100 transition sampling periods (100 x 0.02/3 = .66 second of real time operation) of simulation by the G P N model is the same as those obtained after 33 sampling periods (33 x 0.02 = .66 second of real time operation) of simulation by the M A T L A B program. a) Plant Output (GPN Simulation) 50 (b) Control Input (GPN Simulation) 100 Time Sample 50 100" Time Sample (c) Plant Output (Continuous-time Simulation) (d) Control Input (Continuous-time Simulation) 200 A 150 to £ 100 A E 50 10 20 Time Sample 30 40 0 V 10 20 Time Sample 30 40 Figure VI.37 Comparison of Simulation Results of the Complete System by the.GPN Model and a Conventional Control System Simulator, (a) Plant Output PlaceXo in Figure VI.35, (b) Control Input Place V in Figure VI.36, (c) Plant Output X , (d) Control Input V . e 0 e Figure VI.38 shows the token count for places ps and pio. A token in place ^5 indicates that the plant output has been read from the plant. A token in place pw shows that the VI. Modeling and Analysis of a Hydraulic Control System 102 control input is computed by the controller and can be used to access the system bus to pass the value to. the plant.. The token count for the first 100 samples is plotted here. As can be seen in Figure VI.38, there is a regular access at almost every third time sample. The token count becomes one when a new value of the control input is calculated, and drops to zero once it is transferred by the system bus. It should be mentioned that these places are of the asynchronous type, and their synchronous behavior shows that the system is working as expected. As a result, the bus accesses are going through very regularly and exactly at every third sample. In the next chapter we show what happens when there are timing faults and all the bus accesses cannot get through. (a) Plant Output Validity Marking (Place 5) 0.8 Is 0.6 h 8 0.2 0 I 10 20 Li 30 40 50 60 Time Sample 70 . 80 90 100 80 90 100 (b) Control Input Validity Marking (Place 10) 1 0.8 1 0.6h o 0.2 0 10 20 30 40 50 60 Time Sample 70 Figure VI.38 Result of the Simulation of the Complete System by the GPN Model (a) Plant Output Validity Place p in Figure VI.32, (b) Control Input Validity Place p 5 10 in Figure VI.32. VI. Modeling and Analysis of a Hydraulic Control System 103 VI.5. G P N A n a l y s i s of the H y d r a u l i c S y s t e m In this section, the complete G P N model is analyzed in order to check the properties of the hydraulic control system. A complete analysis requires both the RT and linear algebraic methods. VI.5.1. Linear Algebraic Analysis: The complete system is modeled by a net consisting of the Petri net represented in Figure VI.32 and global Petri nets in Figures VI.35 and VI.36. The complete system G P N diagram and its parameters, such as weight matrices, are given in Appendix D. For this system to be both stable and bounded, we need to have a bounded incidence matrix N and stable H matrices. We first look at the boundedness property. The system incidence matrix N = Wj — W p can be written as pt "1 - 1 0 0 0 0 0 0 0 0 0 0 0 0 0" 0 1 0 0 0 0 0 -1 0 0 0 o 0 0 0 0 0 -1 0 0 0 0 0 1 0 0 0 0 0 0 0 0. 4 -1 0 -1 0 0 0 0 -1 -1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 o. -1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 -1 0 0 0 -1 0 -1 0 4- 0 0 -1 0 0 0 0 0 0 -1 0 -1 4 0 0 0 -1 -1 0 0 0 0 0 0 0 0 1 0 0 -1 0 0 0 0 0 0 0 0 0 0 0 0 ' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. N is bounded iff, for an arbitrary vector Y > 0, the inequalities resulting from N Y T true. If we substitute N from above into N Y < 0 we get the following set of inequalities: T yi 2/5 - 2/4 - 2/8 2/6 < 0 - 2/5 < 0 - t/ < 0 2/2 2/9 < 0 < 0 - ys - 2/9 < 0 . 4?/9 -2/4 <0 J/6 4i/ 8 < 0 hold 2/1 2 ' 2/10 - 4j/ 4 2/4 2/3 j/3 < 0 2/8 - 2/9 - yio < 0 •< 0 VI. Modeling and Analysis of a Hydraulic Control System 104 The above set of inequalities was run through the analysis tools of GPNSAT and could not be satisfied. As an example, the first inequality y\ < 0 is clearly against the condition of Y being a positive vector and indicates that the first place is unbounded. We therefore, conclude that the net is unbounded. There are all together four hybrid transitions (n^ = 4), in the net. These transitions are 241 in Figure VI.35, and and 264 in Figure VI.36. According to Theorem 4.1 in U\,te2, Chapter IV, we will have 2 " = 2 = 16 H matrices. These matrices correspond to when h 4 one or more of these hybrid transitions fire. 261 262 ^64 Location of Roots of H+I Matrix not on the Unit Circle 0 0 0 0 None 1 0 0 0 0 0 1 0 0 -0.2 1 1 0 0 -0.1+0.7i, -0.l-0.7i 0 0 1 0 0 1 0 1 0 0,0 0 1 1 0 -0.2,0 1 1 1 0 -0.1+0.7i, -0.l-0.7i, 0 0 o 0 1 None 1 0 0 1 0 0 1 0 1 -0.2 1 1 0 1 -0.1+0.7i, -0.1-0.7i 0 0 1 1 0 1 0 1 1 2 4 ] Table VI.3 . Roots of Hk + I Matrices Formed by the Firing of Various Hybrid Transitions. 0,0 (Continued) . . . . VI. Modeling and Analysis of a Hydraulic Control System 105 0 1 1 1 -0.2,0 1 1 1 1 -0.1+0.7i, -0.l-0.7i, 0 Table VI.3 Roots of Hk + I Matrices Formed by the Firing of Various Hybrid Transitions. For this system to be stable at all times, the roots of all characteristic equations formed by firing different hybrid transitions should have roots inside the unit circle. That is the eigenvalues of the various Hk + I matrices should be less than one: M(k + 1) = M{k) + H M(k) + Nf k k (VI. 142) M(fc + l ) = (H + I)M(k) + Nfk . k Table VI.3 shows the location of the roots for all system H matrices, found by firing of various transitions. The first four columns show which of the four hybrid transitions are fired. The fifth column shows the location of the roots corresponding to those firings. For example in the first row, no transition is fired. This is the case when none of the hybrid transitions is able to fire. A l l roots of the H+I matrix in this case lie on the unit circle. The last row corresponds to the case where all transitions are fired and the system is working under normal or fault-free conditions. In this case, all roots are on the unit circle except three, which are located inside. This shows that all places are stable. A l l rows in between the first and last rows represent cases where one or more transitions are not fired. They correspond to the situation in which one or more of the system level data transmission is not transferred. For example in row 15, transition £41 has not fired, which, shows the case in which the control input is not applied to the plant. A cursory look at the roots presented in the table reveals that the system is stable under all firing conditions. That is, no matter what hybrid transition fails to fire, the hydraulic system will remain stable. VI.5.2. Reachability Tree Analysis: The reachability tree of this net was constructed by the GPNSAT package. The tree is quite large since there are about 15 places, each having VI. Modeling and Analysis of a Hydraulic Control System 106 many different possible markings. Therefore, the tree cannot be drawn here, but, the results of the RT inspection can be summarized as follows: 1. Boundedness: The infinity symbol w appears in places p\, P2, and ps, indicating that these places can become unbounded. Unboundedness of place p\ is due to the transition which reads the operator's input. If these inputs are not processed fast enough, the place may go unbounded. Places p 2 and ps can also become unbounded due to the same reason (non-processing of input data). 2. Liveness: As with the higher level representation of the system, there are no deadlocks detected (there were no nodes labeled " D E A D END"). 3. Conservation: The complete net is not conservative, due to the presence of infinite nodes. There might however be some subset of bounded places which are conservative. 4. Reachability: The RT showed that the only reachable states are those in which place pu (which represents the system bus) has one token. VI.6. S i m u l a t i o n a n d A n a l y s i s P e r f o r m a n c e A l l the simulation and analysis works were performed by GPNSAT (GPN simulation and analysis tool) which was described in the previous chapter. A l l routines in GPNSAT are written as M A T L A B [92] m-files. The net (at level-2) has 15 places and 15 transitions. The simulation of this net for 200 transition sampling periods takes about 115 seconds, running on a SUN SPARC 5 workstation. 200 transition sampling periods represent 200 x 0.02/3 = 1.33 second of real time operation. The simulation of the net at levels zero and one take significantly less time since they have fewer places and transitions. The time complexity of the simulation program is 0(p x t) where p and t are the number of places and transitions respectively. The linear algebraic analysis takes almost no time and produces virtually instantaneous results. The construction of the reachability tree for this net (at level-2) takes more than VI. Modeling and Analysis of a Hydraulic Control System 107 two hours time since over 500,000 different states are to be constructed and checked for various properties. Chapter VII Fault Modeling and Analysis by GPN This chapter is dedicated to fault modeling, simulation, and analysis by global Petri nets. We only consider off-line analysis of faults and no attempt is made to use the G P N methodology for on-line detection and identification of faults. A fault detection, identification, and reconfiguration scheme is proposed in Appendix E. The scheme is based on recognition of fault conditions by comparing the actual system outputs with those simulated by a G P N based simulator. We shall use the system described in the previous chapter in order to show how faults in a hybrid system can be modeled and analyzed. We start with system level faults (bottlenecks) and see how they affect the system. We then get into how hydraulic system faults can be represented. VII.1. S y s t e m L e v e l Faults One of the most important factors in the design and operation of distributed discreteevent and hybrid systems is the utilization of critical resources. These resources become the system bottlenecks, and their management poses a serious challenge [97]. As described in the previous chapter, the bus in our hybrid system is modeled as a resource used by various subsystems. In the simulation results shown there, we had assumed that the subsystem marked " A l l Other" was dormant and did not need to access the bus (Figure VI.32). In that case, the bus was capable of meeting the demands. This manifested itself in all bus accesses going through on time and as per request [98]. To show how the system would behave if the system bus accesses did not go through, we simulated the system with some extra load. This is done by assigning a token to the initial marking of the place representing the " A l l Other" subsystem. When we do this, the system bus has to serve this client as well; and therefore, it cannot keep up with all the bus transactions which are requested. 108 VII. Fault Modeling and Analysis by GPN 109 The results of this simulation are plotted in Figure VII.39. The first two plots show the plant output and the control input. There is a noticeable difference in the plots when compared with the previous simulation results (Figure VI.37). Even though the system does not become unstable, the plant output takes a longer time to reach its desired value. The cause of this can be found in plot (c), which shows the token count at place p . This place 2 represents the validity of the data which the desired input sensor (e.g. input joystick) reads. When the system bus is able to meet all demands, there will a regular bus access by this place. That means the marking can never exceed one, since the token is consumed before the next one arrives. But in the present simulation run, the bus access demands are not met. That is why we see two and even three tokens in placep2Plot VII.39(d) shows the token count at place p-j. This place represents the "all Other" subsystem. We have chosen the arc weights so that one token is deposited in this place after every bus access. As is seen from the final token count at this place, there have been over thirty bus accesses by this subsystem. This represents the extra load on the bus, which has caused the difference in the hydraulic system behavior. VII. Fault Modeling and Analysis by GPN 110 (a) Plant Output 0 (b) Control Input 50 Time Sample 100 0 50 Time Sample 100 Figure VII.39 Simulation Results of the Hybrid System when the Bus Accesses are not Met. (a) Hydraulic System Output (Place X Marking), (b) Control Input (Place V Marking), (c) 0 e Desired Input Validity (Place p ) Marking, (d) "All Other" Subsystem (Place p ) Marking. 2 7 VII.2. H y d r a u l i c S y s t e m Faults In this section we consider how different faults in the hydraulic system can be modeled by a G P N . In the later sections we take up the simulation and analysis of these faults. The faults considered are as follows: 1. Sensor faults 2. Actuator faults 3. Disturbances 4. System parameter changes. These faults in the G P N model can be represented as events which happen asynchronously [99, 100]. Each fault condition is explicitly modeled by a place. Presence of a token in that VII. Fault Modeling and Analysis by GPN 111 place indicates a potential fault. The fault occurs when the transition enabled by that fault place is enabled. In the following section we present the sensor fault modeling in detail and then apply the same technique to other fault types. VH.2.1. Sensor Faults Model: Let a sensor be modeled as a simple gain as described by the following equation [101]: (VH143) Y (k+.l) = G Y(k), 3 where Y(k), Y (k) , and G s s represent plant outputs (which are the sensor inputs), sensor s outputs, and sensor gain, respectively [102]. We consider two types of faults and represent them with the following equation: Y (k + 1) = Y (k) - hGfY{k) + f G Y(k) s s 2 s + hd - f Y (k) , 4 s (VH.144) where Gf and d are a faulty gain change and a faulty bias, respectively. When all four transitions fire (/i = f 2 = = ft = 1), we will have Y (k + 1) = (G -G )Y(k) s s f + d. This system can be modeled with the global Petri net shown as Figure VII.40. Is" 4s Figure VII.40 A Sensor Fault Model. (VII. 145) VII. Fault Modeling and Analysis by GPN 112 The G P N parameters can be written as I>={F .Y.Y .I).<} S pi A= ; 0 1 0 0 S "1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0" 0 0 0 Witp B M(k)=.[F (k) -Y(k) s 0 0 0 0 Y (k) 0 0 0 0 0 0 0 0 s 0 0 0' 0 0 0 0 d 0 0 0 0 - G 0 G 0 0 0 0 0 D (k)]. (VH.146) f s a The above net can be used instead of the transitions representing sensors as shown in Figure VII.41. The sensor transitions in the net representing the hybrid system are transitions ti and £5 (Figure VI.32). Places ps and pe here are the same places as in Figure VI.32. These two asynchronous places indicate whether the plant output (sensor input) and sensor output data are valid. The box representing transition t models the sensor which is itself a 2 smaller net; it was represented earlier, in Figure VII.40. Figure VII.41 A Sensor Fault Model as a More Detailed Representation of Sensor Transition. VII. Fault Modeling and Analysis by GPN 113 VII.3. Fault S c e n a r i o s : S i m u l a t i o n a n d A n a l y s i s Fault simulation can be carried out by the G P N Simulation and Analysis Tool (GPNSAT). The net, modeling the system, is simulated as before. A fault is activated once the place which represents it gets a token. For example, in Figure VII.41, a gain change fault is introduced when place F gets a token. The presence of a token in this place enables transition s t\ . s The firing of this transition effectively changes the sensor gain from a no fault value of-C? 5 to a faulty value, (C? — Gf). s The sensor bias fault is activated by the presence of a token in place D . The firing of s transition t^ , which is enabled by this place, adds a bias to the eventual sensor output. The s effects of these changes are reflected in the system simulation. To give an illustration of the simulation results, let us start with the gain change faults in the first sensor. This sensor reads X and feeds it back to the controller. We introduced the 0 fault with various gain values, Gf. The results are plotted in Figure VII.42. The simulation is run for the normal (no fault) system for 100 samples. This is sufficient for the system to reach the desired output and settle at its steady state values. At this point, faults are introduced by placing a token in the appropriate places. VII.3.1. Sensor One Gain Change Fault Simulation: the hydraulic system output y\ — X 0 Figures VII.42 (a) and (b) show and control input U = V when there is a break in e the feedback ]oop. This can be modeled by having (C7 — Gf) = 0 o r C 7 = G / = l . The S s value of G in the proceeding simulation runs is always taken to be one. Gain changes are s achieved by changing Gf. As can be seen from the simulation results, the effect of this fault is to introduce a steady state error in the output. The reason for this can be seen in the analysis of these faults later on. The next two plots in Figures VII.42 (c) and (d) represent the plant output, X and control 0 input, V , when Gf = —0.5. This makes the faulty sensor gain [G — Gf) = 1 — (—0.5) = e s VII. Fault Modeling and Analysis by GPN 114 1.5. The steady state effect of this fault is similar to the previous one with final steady state error of a different value. The transient behavior of this fault, however is, quite different. The third fault introduced is a change of sensor gain to 2. This can be done by having Gf = —1. This fault causes an oscillatory type of behavior as can be seen in the plots in Figures VII.42 (e) and (f). The final fault in this series is a change of gain to 2.5 by setting Gf = —1.5. This fault makes the system unstable. The plant output and control input plotted in Figures VII.42 (g) and (h) keep increasing until they go out of bound. VII.3.2. Sensor One Gain Change Fault Analysis: An analysis of the net representing the faulty system reveals many of the its properties. The most important property is the stability of the whole system or its parameters. This can be analyzed by the linear algebraic method developed in the earlier chapters. VII. Fault Modeling and Analysis by GPN 115 200 (b) Control Input o>150 H g c5 2 100 50 0 50 200 100 150 Time Sample 200 (d) Control Input o>150 c o to 100 CD °- 50 100 150 Time Sample 50 0 0 200 50 200 100 150 Time Sample 200 (f) Control Input CO 150 100 CD o ra °- 50 100 150 Time Sample 50 200 50 100 150 Time Sample 200 2000 -400 50 100 Time Sample 150 200 0 50 100 150 200 Time Sample Figure VII.42 Simulation Plots of the First Sensor Gain Faults, a-b) Sensor Cut off,G/ = 1 • c-d) Sensor Gain Change to Gf = —0.5. e-f) Sensor Gain Change to Gf = —1. g-h) Sensor Gain Change to Gf = —1.5. Table VII.4 summarizes the type of faults introduced, the roots of their characteristic VII. Fault Modeling and Analysis by GPN 116 equations found by checking the H matrices, and the effect of these faults. The first row shows the situation for the non-faulty system. As mentioned earlier, the two roots of the hydraulic system lie at —0.1 + 0.7i and —0.1 — 0.7i. These roots are within the unit circle, which is why the system remains stable. We observe this behavior in all of the simulation plots in Figure VII.42, up to the 100th sample. The gain change faults which do not force these roots out of the unit circle (row 2 and 3) of Table VII.4, have no effect on the system stability. Therefore, they only cause a steady state error, as seen in the simulation results. The gain change fault of Gf = —1 (4th row), which makes the fault sensor gain of two, causes the roots to fall right on the unit circle. This makes the system behave in an oscillatory manner (critically stable), which is also evident in Figures VII.42 (e) and (f). The faults in the next two rows are the ones which make the system unstable (any sensor gain greater than two). Again, this is because the roots found by an analysis of the H matrix fall outside the unit circle. This is the kind of system behavior depicted in Figures VII.42 (g) and (h). Fault Type First Sensor Overall Gain Roots Condition No Fault G =0 1 -0.1+0.7i -0.l-0.7i Stable, No Error Sensor cut off Gf=l 0 0, -0.2 Stable, Steady State Error G =-0.5 1.5 -0.1+0.8602i -0.1-0.8602i Stable, Steady State Error 2 -0.1+0.995i -0.1-0.995i Oscillatory f f G =-l f Table VII.4 Sensor One Gain Change Faults and Their Analysis Results. (Continued) . . . VII. Fault Modeling and Analysis by GPN 117 G/=-1.05 2.05 -0.1+1.0075i -0.1-1.0075i Unstable G =-1.5 2.5 -0.1+1.11361 0.1-1.1136i Unstable f : Table VI1.4 Sensor One Gain Change Faults and Their Analysis Results. VII.3.3. Sensor Two Gain Change Fault Simulation and Analysis: Figure VII.43 and Table VII.5 summarize the simulation and analysis results of faults caused by a change in gain of the second sensor. The results and conclusions of their analyses are similar to those for the first sensor. For the second sensor, any gain fault of Gf = —6.5 (overall sensor gain of 7.5), causes the system to become oscillatory. Any gain larger than that makes the system unstable. VII. Fault Modeling and Analysis by GPN 118 a) Plant Output (b) Control Input 200 50 100 150 Time Sample 0 200 50 (c) Plant Output arki 200 40 c»150 I* (5 S 100 30 CD O 20 CO D_ 0) O JW— JS °- 10 0 50 100 150 Time Sample e) Plant Output 50 100 150 Time Sample Jlr"— 50 200 50 x 1o 4000 -4000 200 (d) Control Input 50 CD C 100 150 Time Sample 200 100 150 Time Sample 0 4 50 C o n t r o ' ' P n 200 ut 100 150 Time Sample 200 Figure VII.43 Simulation Plots of the Second Sensor Gain Faults, a-b) Sensor Cut off, Gf = 1. c-d) Sensor Gain Change to Gf = —4. e-f) Sensor Gain Change to G s = —7. An interesting observation in comparing the results of the two sensors analyses is that gain changes produce different roots and, consequently, different transient behavior. This difference can be a basis for the recognition of anticipated faults by different sensors in a VII. Fault Modeling and Analysis by GPN 119 fault diagnostic procedures capable of capturing these distinguishing parameters. Fault Type Second Sensor Overall Gain Roots Condition No Fault G =0 1 -0.1+0.7i -0.l-0.7i Stable, No Error Sensor cut off C7/=l 0 0+0.7i 0-0.71 Stable, Steady State Error 'G/=-4 5 -0.5+0.5i -0.5-0.5i Stable, Steady State Error G =-6.5 7.5 -1, -0.5 Oscillatory G =-6.55 7.55 -1.0196, -0.4904 Unstable G =-1 8 -1.1742, -0.4258 Unstable f f f f Table VII.5 Sensor Two Gain Faults and Their Analysis Results. VII.3.4. Sensors Bias Faults Simulation and Analysis: The last set of sensor faults we consider include the disturbances which act as biases on the sensor output. In this particular system, since the outputs of the system sensors are added up by the control routine, the bias on each sensor has a similar effect and cannot be distinguished. In fact, all bias faults act as changes in the reference input. The simulation results for two bias values are plotted in Figure VII.44. As can be seen, no matter what the amount of the bias is, the bias faults only introduce a steady state error. The reason for this can be found by referring to Table VII.6. VII. Fault Modeling and Analysis by GPN 120 a) Plant Output (b) Control Input 200 50 100 150 Time Sample 200 50 (c) Plant Output 100 150 Time Sample 200 (d) Control Input 200 50 100 150 Time Sample 200 50 100 150 Time Sample 200 Figure VII.44 Simulation Plots of the Sensors Bias Faults, a-b) Sensor Bias of I0,d =10. c-d) Sensor Bias of 100, d = 100. These faults or any other bias faults do not change the H matrix, since they are modeled by the asynchronous places and transitions. Therefore, the bias faults do not affect the dynamics of the system, such as the roots of the H matrix. A stable system can absorb these kind of faults or load changes and stay stable. Fault Type Roots Condition No Fault -0.1+0.7i -0.1-0.7i Stable, No Error Table VTJ.6 Sensor Bias Faults and Their Analysis Results. (Continued) . . . VII. Fault Modeling and Analysis by GPN 121 d=10 -0.1+0.71 -0.1-0.7i Stable, Steady State Error d=100 -0.1+0.7i -0.1-0.7i Stable, Steady State Error Table VII.6 Sensor Bias Faults and Their Analysis Results. VII.4. Other Fault T y p e s In this section we move to other types of hydraulic system faults. These faults, like the sensor faults modeled earlier, are common in all types of control systems. Here we briefly describe how these faults can be modeled. The same type of fault analysis that was carried out for sensor faults can be applied to these fault types as well. VH.4.1. Actuator Faults Modeling: As the first step, for analysis of actuator faults, we need to model the actuators used in our system. Then these models which take the form of GPNs, can be integrated into the system GPN. In general and in its simplest form, actuators can be modeled as a gain which is described by the following equation: U (k + l) = G U(k), a a (VE.147) where U(k) is the control input which is computed by the control subsystem and sent to the actuator; U (k) is the actuator output which is applied to the plant to control it; and G a a is the actuator gain when there is no fault. The actuation process takes a finite amount of time (eg., one sampling period). For this type of actuator we can consider two types of faults: a gain change fault and a bias fault. These faults can be modeled by the global Petri net shown in Fin Figure VII.45. VII. Fault Modeling and Analysis by GPN 122 Figure VII.45 An Actuator Fault Model. The operation of this net can be represented by the following equation: U {k + 1) = U {k) - fiG U(k) a a f + f G U{k) +'j d - UU (k), 2 a 3 a '; (VH.148) where Gf and d are a faulty gain change and a faulty bias, respectively. Gain change and bias faults are activated when asynchronous transitions t\ a all four transitions fire ( / i = f 2 and ti , respectively fire. When a — fo — JA — 1), we will have U (k+l) a = (G -Gf)U(k) a VII.4.2. Actuator Faults Simulation and Analysis: + d. . (VII.149) The G P N model developed for the actuator can be integrated into the main net which represents the overall system. This can be done by replacing the transition which models the actuator (transition of Figure VI.32) by the net in Figure VII.45. This was done for the system we have been modeling in this thesis. This system was simulated, and various faults were introduced. Figure VII.46 shows the plot of three such fault cases. The first two plots (Figures VII.46 (a) and (b)) represent the case when the actuator's connection to the rest of the system is broken. The next case represent an actuator gain change, which does not cause instability in the system, since the roots of the system VII. Fault Modeling and Analysis by GPN 123 characteristic equations remain within the unit circle as can be seen in Table VII.7. The final two plots (Figures VII.46 (e) and (f)) show a gain change fault of Gf — —1.2. This fault makes the overall system unstable, as any actuator gain of greater than two would. (a) Plant Output (b) Control Input 200 o)150 • 100 o ra °- 50 CD 50 100 150 Time Sample 200 (c) Plant Output 50 100 150 Time Sample 100 150 Time Sample 50 100 150 Time Sample 200 (d) Control Input 200 (e) Plant Output 50 0 .L.—/ 50 100 150 Time Sample 200 (f) Control Input 200 50 100 150 Time Sample 200 Figure VII.46 Simulation Plots of the Actuator Faults, a-b) Actuator CutoffG/ = 1. c-d) Actuator Gain Change to Gj = —0.2. e-f) Actuator Gain Change to Gf = -1.2. VII. Fault Modeling and Analysis by GPN 124 Table VII.7 below summarizes some of the analysis results for the actuator faults. It shows what the effects of various actuator gain changes are, and what gains make the system unstable. These results are found by analyzing the faulty system H matrix. Fault Type Actuator Overall Gain Roots Condition No Fault G =0 1 -0.1+0.7i -0.1-0.7i Stable, No Error G =-02 1.2 -0.12+0.7652i -0.12-0.7652i Stable, Steady State Error G =-l 2 -0.2+0.9798i 0.2-0.9798i Oscillatory G =-\2 2.2 -0.22+1.0255i -0.22-1.02555i Unstable Actuator Cut off G =0 0 No Roots Stable, no output f f f f f Table VII.7 Actuators Faults and Their Analysis Results. Vn.4.3. Disturbances and System Parameter Changes: Other types of faults in control system (such as the hydraulic system under study) which are commonly considered are system disturbances, and parameter changes. Disturbances could be due to change in the load, and can be modeled in exactly the same way as was done with sensor bias faults. They can be taken to originate from asynchronous places. System parameter changes are reflected in changes in system state space matrices, (A, B , C, and D). These changes are usually very slow acting and occur gradually and over a long period of time. The cause of these can be a change in the environment, such as temperature or pressure. These changes can be modeled by changing the G P N model. The same type of analysis can be applied to the modified models. VII. Fault Modeling and Analysis by GPN 125 VII.5. Fault C o n d i t i o n s M o d e l e d by a G P N In this final section we list some of the fault conditions which can be manifested in a G P N model. Simulation and analysis of these faults is the first step in detection and identification of them [99, 100]. The detection of faults can be accomplished by comparing the fault (actual) signals with the modeled (estimated) signals. The difference is called the fault residual and is used to detect a fault when it crosses certain threshold. The identification of faults can be done by analyzing the frequency characteristic of the fault residuals (poles and zeros of the signal) [99, 100]. The analysis techniques developed in this dissertation can help in analyzing the system for these fault conditions. A fault detection, identification, and reconfiguration scheme is proposed in Appendix E. This scheme is based on recognition of fault conditions by comparing the actual system outputs with those simulated by a G P N based simulator. 1. Boundedness: One of the main symptoms of any control system going unstable is that some of the system parameters go beyond a bound or threshold. By analyzing that if a system is capable of going or has gone out of bound, we can detect many of the faults. 2. Reachability: This property is useful in investigating if a faulty state is reachable with the given state of the system. By knowing that a faulty state is reachable, we can be ready to check for it when the system is actually running. 3. Controllability: Given a marking which corresponds to a faulty state, is it always possible to steer the system to a safe state in a finite number of samples? This question can be answered by the controllability property. This analysis can be used in recovering from faults and reconfiguring the system. 4. Liveness: Another important issue in the design of a fault-tolerant system is avoidance of deadlock states. Liveness property shows whether a system is capable of getting into a deadlock state from a given initial marking or not. 5. Conservation: This property can check if the total token content of a set of places should remain constant. When this holds for a non-faulty system, any violation of this VII. Fault Modeling and Analysis by GPN 126 property is a symptom of a fault in the system. There are many examples of such properties in physical systems such as preservation of energy, and the amount of oil or coolant in a motor. 6. Timing Faults: Another set of faults which are very essential in our analysis are timing faults. These faults can be due to a delay in the system, or a breakdown. In many systems, tokens in a particular place should be consumed before a new token arrives. Accumulation of tokens is a symptom of a timing fault. Chapter VIII Conclusions and Future Work The main objective of this research was to develop a new methodology for the modeling, simulation, and analysis of hybrid systems. Petri nets have proven to be an extremely useful tool for modeling and analyzing discrete-event systems. Linear control system theory has solved many of the problems in the control and identification of dynamic and time-driven systems. Our new modeling methodology, which is called a global Petri net (GPN), successfully combines the capabilities of these two powerful tools into a single tool. Although, many additions have been made to the P N theory and practice over the years (including Continuous and Hybrid PNs), this is the first work, to the best of our knowledge, that allows modeling, simulation, and analysis of discrete-event and discrete-time dynamic systems to be performed within a unified PN framework. Conventional Petri nets can model only discrete-event (asynchronous) systems. In a system represented by an event-driven model, we know only when an event starts and ends, and have no idea what happens in between events. The other information which is missing in a discrete-event model is the actual (quantitative) value of each signal. A l l we know is that a signal is generated and available (a condition), but, we have no information about what its value is. To be able to see the dynamics of the system in between events, we must model the process as a time-dependent element in a GPN. The G P N is very general and facilitates modeling of any kind of digital system, including the digitized versions of analog plants, computer hardware and software, and human interactions. We formally defined the G P N and showed the structural and behavioral differences between the PN and G P N formalisms. Derivation of the G P N from the basic P N and the derivation of the G P N dynamic equations were also given. The resulting structure was very similar to both the Petri net and the state space representation of dynamic systems. This similarity makes it more appealing and intuitive for both Petri net and control communities. 127 VIII. Conclusions and Future Work 128 We have also included a few examples, which were used to illustrate the scope of modeling by the G P N . These examples showed how various type of hybrid systems can be modeled by GPN. One example specifically dealt with modeling and simulation of logical gates at both analog and switch levels. These examples showed how easy and intuitive it was to model with the G P N . We also discussed the structural and behavioral differences between the P N and the G P N models. One of the main differences is in the way markings are presented. Tokens in the conventional P N can only take binary values, resulting in positive integer markings. But in the G P N formulation, markings can have any real number value. The other important difference is the type of arcs which are allowed. There are two types of arcs allowed in the G P N structure. The first one, which is the same as the arcs in the P N model, is called the asynchronous arc. These arcs set the condition for the firing of transitions. The second type, which is exclusive to the GPN, is called the synchronous arc. These arcs do not impose any conditions on the transitions to which they are connected. These two major differences enable the G P N to model hybrid systems. We have developed some techniques for analyzing the systems modeled by the GPN. These techniques are based either on the construction of a reachability tree or on linear algebra. The properties which can be analyzed by these methods are controllability, boundedness, stability, liveness, and conservation. Theorems regarding proof of these properties are stated and proven. Some of these properties are defined for a sub-class of GPNs to ease the analysis burden. This sub-class is defined in the thesis, and the reasons for reduction in the required analyses are explained. We have developed a theorem which enables us to find the number of hybrid transition matrices for a given net. We have also discussed some other modeling issues such as the G P N modelability and hierarchy. To assist us in our research, a tool called GPNSAT (Global Petri Net Simulation and Analysis Tool) was developed. The tool's structure and its salient features are described in the thesis. The GPNSAT package was used for all of our P N and G P N modeling, simulation, VIII. Conclusions and Future Work 129 and analysis. A distributed hybrid system was modeled by the G P N methodology. This system consisted of a hydraulic control system, along with its various parts, such as sensors, actuators, controller, and the communication links. The modeling was carried out at different levels of abstraction. At the highest level the system was modeled as a discrete-event system. At the lowest level, where we modeled the details of a hydraulic control system, a hybrid model was used. At each level the system was simulated and analyzed by the GPNSAT. Fault modeling and analysis for the hybrid system also was performed. Various system level faults were modeled for a hydraulic control system, its sensors, and its actuators. These faults in the G P N model are represented as events which happen asynchronously. Each fault condition is explicitly modeled by a place. Presence of a token in that place indicates a potential fault. The fault happens when the transition enabled by that fault gets fired. The analysis of these faults by the G P N analysis methods showed that these faults can be distinguished from each other successfully in a GPN-based detection and recognition scheme. The G P N analysis method can be used in model-based schemes for fault detection and recognition. These schemes monitor the operation, detect faults, and initiate the recovery process by comparing the system's actual outputs with the outputs estimated by the use of the system model. We have shown that there exists a single tool which can be used to model both the plant and the computer controlling it. In this fashion, a single detection scheme is sufficient to monitor the entire system and diagnose various forms of faults. VIII.1. Future W o r k There are many different routes that the present research can lead to. One can pursue this work in applying these theories to other real-life examples such as multimedia, manufacturing processes, robotics, and work cell scheduling. Another direction is to work in developing more analysis techniques or refining the ones presented in this dissertation. Here, we provide some pointers to the future directions. VIII. Conclusions and Future Work 130 The main limitation of modeling and analysis by GPNs is the growth in the number of states (places) when the system complexity increases. This specially becomes onerous in simulation and reachability tree analysis algorithms. This growth also limits the applicability of this method for on-line detection and identification of faults. Due to this reason only off-line fault analysis was attempted in this thesis. This shortcoming can be overcome when higher speed processors and more efficient algorithms are used. Some system properties such as liveness and reachability were analyzed only by reachability tree method. There is still a need for developmental of techniques based on linear algebraic methods to deal with these properties. One assumption made in developing the analysis methods was that the transition time of all synchronous transitions is the same. However, the G P N simulation program allows the specification of different transitions times. The analysis of hybrid systems with different synchronous transition times would be a very useful and interesting undertaking. In the construction of reachability trees, we have not specified the transition time. The next version of RTs can take this into consideration. This might reduce the size of the tree, since some of the states may not be reachable when the transitions are timed. On the implementation side, we do not have a graphical editor for the GPNSAT. There are many P N editors in shareware. These editors can be modified to accept G P N parameters as well. Another area to develop is to optimize the programs written for the GPNSAT. This can help reduce the running time and memory requirements of these programs. Bibliography [1] R. Williams, B. Benhabib, and K . Smith, " A Hybrid Supervisory Control System for Flexible Manufacturing Workcells," in Proc. of IEEE International Conf. on Robotics and Automation, pp. 2551-2556, 1994. [2] J. A . Stiver and P. Antsaklis, "Modeling and Analysis of Hybrid Control Systems," in Proc. of the 31st Conf. on Decision and Control, Tuscon, Arizona, pp. 3748-3751, 1992. [3] M . Marsen, G. Balbo, and G. Bruno, "TOPNET: A Tool for the Visual Simulation of Communication Networks," IEEE Journal on Selected Areas in Communications, vol. 8, no. 9, pp. 1735-1747, 1990. [4] R. Valette, M . Courvoisier, and D. Mayeux, Control of Flexible Production Systems and Petri Nets, pp. 266-27. in Application and Theory of Petri Nets, Selected Papers from the 3rd European Workshop, Springer-Verlag, 1983. [5] R. J. Abbott, "Resourceful Systems for Fault Tolerance, Reliability and Safety," ACM Computing Surveys, vol. 22, no. 1, pp. 35-68, 1990. [6] M . D. Lemmon and P. Antsaklis, "Event Identification in Hybrid Control Systems," in Proc. of the 32nd Conf. on Decision and Control, San Antonio, Texas, pp. 2323-2328, 1993. [7] P. Peleties and R. DeCarlo, "Analysis of a Hybrid System Using Symbolic Dynamics and Petri Nets," Automatica, vol. 30, no. 9, pp. 1421-1427, 1994. [8] P. Zave, " A n Operational Approach to Requirements Specification for Embedded Systems," IEEE Trans, on Software Engg., vol. 8, no. 3, pp. 250-269, 1982. [9] J. R. Connet, E. J. Pasternak, and B. D. Wagner, "Software Defenses in Real-Time Control Systems," in Proc. of the Fault Tolerant Computing Symposium FTCS-2, pp. 94-99, 1972. 131 IX. Bibliography 132 [10] R. Doraiswami, M . Kaye, and M . . Rezai, "Detection and Identification of Sensor, Actuator and Excessive Load Faults," Proc. of Canadian Conf. on Elect, and Comp. Engg., Montreal, 1989. [11] J. H . Lala, R. E. Harper, and L . S. Alger, " A Design Approach for Ultrareliable RealTime Systems," IEEE Computer Magazine, pp. 12-22, May 1991. [12] G. Bruno, A . Castella, G. Macario, and M . P. Pescarmona, "Scheduling Hard Real Time Systems Using High-Level Petri Nets," Application and Theory of Petri Nets 1992, Lecture Notes in Computer Science, Springer-Verlag, vol. 616, pp. 93-112, 1992. [13] H . Kopetz and W. Merker, "The Architecture of M A R S , " in Proc. of Fault Tolerant Computing Symposium FTCS-15, pp. 274-279, 1985. [14] C. Cao, "Supervisory Control of a Class of Hybrid Dynamic Systems," in Proc. of 1993 IEEE Midwest Symposium on Circuits and Systems, pp. 967-970, 1993. [15] Y . Ho, "Performance Evaluation and Perturbation Analysis of Discrete Dynamic Systems," IEEE Trans, on Automatic Control, vol. 32, no. 7, pp. 563-572, 1987. [16] M . Heymann, "Concurrency and Discrete Event Control," IEEE Control Systems Magazine, pp. 103-112, June 1990. [17] A . Ichikawa and K . Hiraishi, "Analysis and Control of Discrete Event Systems Represented by Petri Nets," Discrete Event Systems: Models and Applications, 11ASA Conf, Sopron, Hungry, Lecture Notes in Control and Inf. Systems, Springer-Verlag, pp. 115-134, 1987. [18] R. L . Grossman, A. Nerode, A. P. Ravn, and H. Rischel(Eds.), Hybrid Systems. SpringerVerlag, New York, 1993. [19] P. Antsaklis(Eds.), Hybrid Systems II, Lecture Notes in Computer Science, Vol. 999. Springer-Verlag, New York, 1995. [20] R. Alur, T. A . Henzinger, and E. D. Sontag(Eds.), Hybrid Systems III: Verification and Control, Lecture Notes in Computer Science, Vol. 1066. Springer-Verlag, New York, IX. Bibliography 133 1996. [21] Z. Manna and A . Pnueli, "Verifying Hybrid Systems," in Hybrid Systems, Lecture Notes in Computer Science, Springer-Verlag, vol. 736, pp. 4-35, 1993. [22] P. Antsaklis, A . Stiver, and M . Lemmon, "Hybrid Systems Modeling and Autonomous Control Systems," in Hybrid Systems, Lecture Notes in Computer Science, SpringerVerlag, vol. 736, pp. 366-391, 1993. [23] R. Alur and D. Dill, "The Theory of Timed Automata," in Real-Time: Theory and Practice, Lecture Notes in Computer Sc., Springer-Verlag, vol. 600, pp. 45-73, 1991. [24] R. L . Grossman and R. Larson, "Viewing Hybrid Systems as Products of Control Systems and Automata," Proceedings of the 31st Conference on Decision and Control, Tucson, Arizona, pp. 2953-55, 1992. [25] Z. Manna and A . Pnueli, The Temporal Logic of Reactive and Concurrent Systems. Springer-Verlag, New York, 1992. [26] O. Maier, Z. Manna, and. A. Pnueli, "From Timed to Hybrid Systems," in Real-Time: Theory in Practice, Lecture Notes in Computer Science, Springer-Verlag, vol. 600, pp. 447-484, 1991. [27] Y . Zhang, A Foundation fro the Design and Analysis of Robotic Systems and Behaviors. PhD thesis, , Ph.D. Thesis, Dept. of Comp. Sc., University of British Columbia, 1994. [28] Y . Zhang and A . K. Mackworth, "Will The Robot Do the Right Thing?," in Proc. Artificial Intelligence 94, Banff, Alberta, pp. 255-262, May, 1994. [29] Y . Zhang and A . K . Mackworth, "Design and Analysis of Embedded Real-Time Systems: An Elevator Case Study," Tech. Rep. 93-4, Dept. of Comp. Sc., University of British Columbia, 1993. [30] C. G. Cassandras, Discrete Event Systems: Modeling and Performance Analysis. Asken Associates Inc. Pub., 1993. IX. Bibliography 134 [31] J. Peterson, Petri Net Theory and the Modeling of Systems. Prentice-Hall, Inc., N.J., USA, 1981. [32] W. Reisig, Petri Nets: An Introduction. Springer-Verlag, 1985. [33] W. Brauer, "Carl Adam Petri and Informatics," in Concurrency and Nets: Advances in Petri Nets, Springer-Verlag, pp. 13-21, 1987. [34] J. Ghofraniha and M . Rezai, "Dynamic Scheduling of a Job Shop Using a Petri Net Model," in Proc. of Production and Manufacturing Engg. Conference, Tehran, Iran, 1993. [35] M . Zhou and F. Dicesare, "Adaptive Design of Petri Net Controllers for Error Recovery in Automated Manufacturing Systems," IEEE Trans, on Systems, Man, and Cybernetics, vol. 19, no. 5, pp. 963-973, 1989. [36] M . D. Jeng and F. DiCesare, " A Review of Synthesis Techniques for Petri Nets with Applications to Automated Manufacturing Systems," IEEE Trans, on Systems, Man, and Cybernetics, vol. 23, no. 1, pp. 310-312, 1993. [37] J. E. Coolahan and N . Roussopolous, " A Time Petri Net Methodology for Specifying Real-Time System Timing Requirements," in Proc. International Workshop on Timed Petri Nets, Torino, Italy, pp. 24-31, 1985. [38] C. Ghezzi, D. Mandrioli, S. Morasca, and M . Pezze, " A Unified High-Level Net Formulation for Time-Critical Systems," IEEE Trans, on Software Engg., vol. 17, no. 2, pp. 160-172, 1991. [39] J. Baer, "Modelling Architectural Features with Petri Nets," in Petri Nets: Applications to Other Models of Concurrency, vol. Lecture Notes in Computer Sc. Springer-Verlag,. no. 255, pp. 258-277, 1986. [40] Y . Shieh, D. Ghosal, P. R. Chintamaneni, and S. K . Tripathi, "Modeling of Heirarchical Distributed Systems with Fault-Tolerance," IEEE Trans, on Software Engg., vol. 16, no. 4, pp. 444-457, 1990. IX. Bibliography 135 [41] R. David and H . Alia, "Petri Nets for Modelling of Dynamic Systems—A Survey," Automatical, vol. 30, no. 2, pp. 175-202, 1994. [42] C. L . Beck and B. Krogh, "Models for Simulation and Discrete Control of Manufacturing Systems," in Proceedings of Conf. on Robotics and Automation, pp. 305-310, 1986. [43] R. Sreenivas and B . H . Krogh, "On Petri Net Models of Infinite State Supervisors," IEEE Trans, on Automatic Control, vol. 37, no. 2, pp. 274-277, 1992. [44] A . Giua and F. DiCesare, "Petri Net Structural Analysis for Supervisory Control," IEEE Trans, on Robotics and Automation, vol. 10, no. 2, pp. 185-195, 1994. [45] D. Gracanin, P. Srinivasan, and K . Valavanis, "Parametrized Petri Nets and Their Application to Planning and Coordination in Intelligent Systems," IEEE Trans, on Systems, Man, and Cybernetics, vol. 24, no. 10, pp. 1483-1497, 1994. [46] S. Ramaswamy, K . Valavanis, and S. Landry, "Modeling, Analysis and Simulation of a Material Handling System with Extended Petri Nets," Proc. of the 31st Conference on Decision and Control, pp. 1665-1672, Dec. 1992. [47] S. Ramaswamy and K . Valavanis, "Modeling, Analysis and Simulation of Failures in a Material Handling System with Extended Petri Nets," IEEE Trans, on Systems, Man, and Cybernetics, vol. 24, no. 9, pp. 1358-1373, 1994. [48] P. Freedman, "Time, Petri Nets and Robotics," IEEE Trans, on Robotics and Automation, vol. 7, no. 4, pp. 417^133, 1991. [49] R. David and H . Alia, Petri Nets and Grafcet Tools for modelling discrete event systems. Prentice-Hall, 1992. [50] G. R. Gao, A Code Mapping Scheme for Dataflow Software Pipelining. Kulwer Academic Publishers, 1991. [51] E. A . Lee, "Dataflow Programming for Parallel Implementation of Digital Signal Processing Systems," in Discrete event Systems: Models and Applications, Lecture Notes in Control and Information Systems, Springer-Verlag, vol. 103, pp. 135-148, 1987. IX. Bibliography 136 [52] D. Hard, "On Visual Formalisms," Communications of the ACM, vol. 31, no. 5, pp. 514— 530, 1988. [53] N . Day, " A Model Checker for Statecharts (Linking Case Tools with Formal Methods)," Master's thesis, Dept. of Computer Science, University of British Columbia, 1993. [54] R. C. Waters, "System Validation via Constraint Modeling," ACM SIGPLAN Notices, vol. 26, no. 8, pp. 27-36, 1991. [55] Shapiro, "Validation of VLSI Chip Using Heirarchical Colored Petri Nets ," Microelectronics and Reliability, vol. 31, no. 4, pp. 607-625, 1991. [56] J. D. Noe, "Nets in Modeling and Simulation," in Net Theory and Applications, Lecture Notes in Computer Science, Springer-Verlag, vol. 84, pp. 347-367, 1980. [57] K . Jensen, "Coloured Petri Net : A High Level Language for System Design and Analysis," Advances in Petri Nets 1990, Lecture Notes in Computer Science, SpringerVerlag, no. 483, pp. 342-416, 1990. [58] K . Jensen, Coloured Petri Nets: Basic Concepts, Analysis Methods, and Practical Use. Springer-Verlag, 1992. [59] B. Berthomieu and M . Diaz, "Modeling and Verification of Time dependent Systems Using Time Petri Nets," IEEE Trans, on Software Engg., vol. 17, no. 3, pp. 259-273, 1991. [60] T. Agerwala, "Putting Petri Nets to Work," IEEE Computer, pp. 85-94, Dec. 1979. [61] K . Jensen, "Computer Tools for Construction, Modification and Analysis of Petri Nets," in Petri Nets: Applications and Relationships to other Models of Concurrency, Lecture Notes in Computer Science, Springer-Verlag, vol. 255, Part II, pp. 4-19, 1986. [62] F. Feldbrugge, "Petri Net Tool Overview 1989," Advances in Petri Nets 1989, Lecture Notes in computer Science, Springer-Verlag, no. 424, pp. 151-178, 1989. [63] J. Goutal, "List of Tools Based on Petri Nets at C R I M (Centre de Recherche Informatique de Montreal) @ http://www.crim.ca/Domaines_Services/GL/PETRI/," IX. Bibliography 137 1995. [64] "Petri Nets on World Wide Web (WWW) @ http:/www.daimi.aau.dkTpetrinet/," 1995. [65] G . Florin, ,C Fraize, and S. Natkin, "Stochastic Petri Nets: Properties, Application and Tools," Microelectronics and Reliability, vol. 31, no. 4, pp. 669-697, 1991. [66] W. M . Zuberek, "Timed Petri Nets, Definitions, Properties and Applications," Microelectronics and Reliability, vol. 31, no. 4, pp. 627-644, 1991. [67] J. Sifakis, "Performance Evaluation of Systems Using Nets," Net Theory and Applications, Proc. of Advanced Course on General Net Theory of Processes and Systems, Lecture Notes in Computer Science, Springer-Verlag, vol. 84, pp. 307-319, 1980. [68] P. Merlin arid D. J. Faber, "Recoverability of Communication protocols- Implications of a Theoretical Study," IEEE Transaction on Communications, vol. 24, no. 9, pp. 10361043, 1976. [69] G . Bruno and G. Marchetto, "Process Translatable Petri Nets for Rapid Prototyping of Process Control Systems," IEEE Trans, on Software Engg., vol: 12, no. 2, pp. 346-357, Feb. 1986. [70] K . Brand and U . Kopainsky, "Principles and Engineering of Process Control with Petri Nets," IEEE Trans, on Auto. Control, vol. 33, no. 2, pp. 138-149, Feb. 1988. [71] R. Valette, Petri Nets and Reliable Real Time Systems, pp. 222-227. in Application and Theory of Petri Nets, Springer-Verlag, 1982. [72] M . . R. Zargham and K . Danhof, "Toward a Definition of Fault Analysis for Petri Net Models," Information Processing Letters, vol. 34, pp. 299-305, May 1990. [73] N . Levenson and J. Stolzy, "Safety Analysis Using Petri Nets," IEEE Trans, on Software Engg., vol. 13, no. 3, pp. 386-397, 1987. [74] V . Krasnohaev and L. Krasnobaev, "Application of Petri Nets for Modeling of Detection and Location of Intermittent Faults in Computers," Automation and Remote Control, vol. 49, no. 9, pp. 1198-1204, 1989. IX. Bibliography 138 [75] T. Murata, "Some Recent Applications of High-Level Petri Nets," in Proc. of 1991 IEEE International Sym. on Circuits and Systems, Singapore, pp. 818-821, 1991. [76] J. Prock, " A New Technique for Fault Detection Using Petri Nets," Automatica, vol. 27, no. 2, pp. 239-245, 1991. [77] P. Cofrancesco, A . Cristoforetti, M . Villa, R. Scattolini, and D. W. Clarke, " A Workbench for Digital Control Systems," IEEE Control Systems Magazine, pp. 102105, 1991. [78] R. G. Willson and B. H . Krogh, "Petri Net Tools for the Specification and Analysis of Discrete Controllers," IEEE Trans, on Software Engg., vol. 16, no. 1, pp. 39-50, 1990. [79] J. L . Bail, H . Alia, and R. David, "Asymptotic Continuous Petri nets: An Efficient Approximation of Discrete Event Systems," in Proc. of the 1992 IEEE Inter. Conf. on Robotics and Automation, pp. 1050-1056, 1992. [80] N . Zerhouni and H . Alia, "Dynamic Analysis of Manufacturing Systems Using Continuous Petri Nets," in Proc. of the 1990 IEEE Inter. Conf. on Robotics and Automation, pp. 1070-1075, 1990. [81] A . K . Martin and C. H . Seger, "Discrete Conservative Approximations of Hybrid Systems," Tech. Rep. 93-44, Dept. of Comp. Sc., University of British Columbia, 1994. [82] L . A . Glasser and D. W. Dobberpuhl, The Design and Analysis of VLSI Circuit. AddisonWesley Pub. Co., 1991. [83] W. Reisig, "Combining Petri Nets and Other Formal Methods," Application and Theory of Petri Nets 1992, Lecture Notes in Computer Science, Springer-Verlag, vol. 616, pp. 24-44, 1992. [84] K . Lautenbach, "Linear Algebraic Techniques for Place/Transition Nets," Advances in Petri Nets in Lecture Notes in Comp. Science, Springer-Verlag, pp. 142-167, 1987. [85] T. Murata, "Petri Nets: Properties, Analysis and Applications," Proc. of the IEEE, vol. 77, no. 4, pp. 541-580, 1989. IX . Bibliography 139 [86] W. Reisig, "Petri Nets and Algebraic Specifications," Theoretical Computer Science, no. 80, pp. 1-34, 1991. [87] K . Ogata, Discrete-Time Control Systems. Prentice-Hall, N.J., 1987. [88] K . S. Tsakalis and P. Ioannou, Linear Time-Varying Systems: Control and Adaptation. Prentice-Hall, N.J., 1993. [89] N . Viswanadham, Y . Narahari, and T. L . Johnson, "Deadlock Prevention and Deadlock Avoidance in Flexible Manufacturing Systems Using Petri Net Models," IEEE Trans, on Robotics and Automation, vol. 6, no. 6, pp. 713-723, 1990. [90] N . N . Ivanov, "Algebraic Method of Determining Nonexistence of Deadlock Markings of Petri Nets," Automation and Remote Control, vol. 52, no. 17, part 2, pp. 986-989, 1991. [91] A . A . Desrochers and R. Y . Al-Jaar, Application of Petri Nets in Manufacturing Systems. IEEE Press, New York, 1995. [92] " M A T L A B User Manual, Version 4.2 by the MathWorks, Inc., U S A , " March 1994. [93] N . Sepehri, Dynamic Simulation and Control of Teleoperated Heavy-Duty Hydraulic Manipulators. PhD thesis, Dept. of Mechanical Engg., University of British Columbia, 1990. [94] P. D. Lawrence, F. Sassani, N . S. and. U Wallersteiner, and J. Wilson, "ComputerAssisted Control of Excavator-Based Machines," in 7995 International Off-Highway & Powerplant Congress & Exposition, Milwaukee, Wisconsin, 1993. [95] D. McCloy and H . Martin, Control of Fluid Power: Analysis and Design. John Wiley & Sons, 1980. [96] P. Dransfield, Hydraulic Control Systems - Design and Analysis of their Dynamics. Lecture Notes in Control and Information Sciences, Springer-Verlag, 1981. [97] R. Valette, J. Cardoso, and D. Dubois, "Monitoring Manufacturing Systems by Means of Petri nets with Imprecise Markings," Proc. of IEEE Int. Symposium on Intelligent IX. Bibliography 140 Control, pp. 233-237, 1989. [98] M . Rezai, M . R. Ito, and P. D. Lawrence, "Modeling and Simulation of Hybrid Control Systems by Global Petri Nets," in Proc. of 1995 IEEE International Symposium on Circuits and Systems, Seattle, USA, vol. II, pp. 908-911, May 1995. [99] M . Rezai, M . R. Ito, and P. D. Lawrence, "Petri Net Based Fault Tolerance," in Proc. of Iranian Conference on Electrical Engineering ICEE-94, Tehran, Iran, vol. on Control, pp. 199-208, 1994. [100] M . Rezai, P. D. Lawrence, and M . R. Ito, "Analysis of Faults in Hybrid Systems by Global Petri Nets," in Proc. of 1995 IEEE International Conference on Systems, Man and Cybernetics, Vancouver, Canada, 1995. [101] M . Rezai, M . Kaye, and R. Doraiswami, "Fault Identification in Digital Control Systems," in Proc. of IASTED International Conf. on Control and Modeling, Tehran, Iran, 1990. [102] J. C. Delaat and W. C. Merril, " A Real Time Microcomputer Implementation of Sensor Failure Detection for Turbofan Engines," IEEE Control Systems Magazine, pp. 29-37, June 1990. Appendix A Modeling of Logic Gates by GPNs In this appendix we show how logic gates are represented by GPNs. We show the nets for simpler gates. More complicated gates and switches can be built up by putting these gates together. Table A.8 shows the truth table for various logic gates. We will make use of this table in our presentation in this appendix. A B A A.B A.B A + B A + B 0 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 Table A.8 The Truth Table for Various Digital Logic Gates. A . 1 . Inverter G a t e We start with the inverter gate since the G P N model representing this gate is the simplest. The inverter gate inverts the logic sense of a binary signal. If we represent the input to this gate as A (the first column of Table A.8), the output is given by A (the third column). This gate can be modeled by two places representing the input and output and a transition representing the logical operation. Figure A.47 The Inverter Gate Modeled by a GPN. Figure A.47 shows the net modeling an inverter. The transition fires irrespective of the marking of place A . The output will just be the opposite of the input. 141 A.2. A N D Gate The logical operation of the A N D gate is presented by the fourth column of Table A.8. The global Petri net model of this gate is given in Figure A.48 and consists of three places and one transition. The transition will fire only when both inputs are equal to one which results in changing the output to one. The output remains zero for all other combinations of inputs. Figure A.48 The AND Gate Modeled by a GPN. A . 3 . N A N D Gate The G P N representing the N A N D gate can be constructed by putting the first two (AND and Inverter) nets described above together. The N A N D gate logical operation is given by the fifth column of Table A. 8. Figure A.49 The NAND Gate Modeled by a GPN. A.4. N O R Gate Since modeling a NOR gate by the G P N methodology is simpler than modeling an OR gate, we show the NOR model first. According to DeMorgan's theorem, we can write: 142 A + B = A.B (A.150) where the left hand side is the NOR operation. Therefore, if we invert our inputs A and B and then A N D them, the result will be the same if we had done a NOR operation on the inputs. Using this logic, the G P N modeling a NOR gate can be developed as shown in Figure A.50. Inverter AND © Figure A.50 The OR Gate Modeled by a GPN. A.5. O R Gate The G P N model of the OR gate can be constructed by adding an inverter to the output of the NOR gate in Figure A.50. 143 Appendix B Derivation of the Hybrid Transition Matrix In this appendix we present the derivation of H matrix expression in terms of the global Petri net parameters such as the weighting matrices and the transition firing vector. H matrix is part of the G P N dynamic equation: (B.151) M(k + l) = M(k) + H M{k) + Nf . k k H matrix at any instant k is defined by: H = -{Diag{Af )) + [One(A)Diag(f )B] T k k k . (B.152) We derive the expression for H matrix irrespective of the time instant k by substituting in: (B.153). H = -(Diag(Af)) + [One(A)Diag(f)B) , T For an m place, n transition GPN, the weighting matrices (A and B) and transition firing vector (/) are given as: "an A = ai2 • ^21 hi • .a/1 a/2 • 0,2n B hi - • «/?i . .hi ^>22 h • . • u hi • : r/ii b- h f • 2 = -fn - hi. • (B.l 54) Diag(Af) can be written by matrix multiplication of A and / , and then diagonalizing the resulting vector Af by Diag function: E ijfj a i=i n E 2jfj 0 0 n 0 a Af 3=1 Diag(Af) .= 0 n E E 2jfj a n aijfj E •i=i 144 aijfj (B.155) To find the second element on the right hand side of Equation (IV.73), we need to find the following: One(A) on 012 021 022 Ion °i2 0\n Diag(f) Oln 7i 0. 0 h 0 0 0 0 fn (B.156) Multiplying these two matrices gives us: '011/1 One(A)Diag(f) = • • oi /, 0 1 2 / 2 021/1 022/2 0/1 fl O12 f n •• 02nfi (B.157) ••• .Olnfn n Multiplying the above matrix by B and then taking transpose: •n n E oijfjbji i=i {One{A)Diag{f)B\ = 2 n E n 02jfjl>j\ i=i E oijfjbji -i=i E i=i (: n 02j/j&iJ E oijfjb j2 E 02.;/;,^l '1.,/Al oij/i^7 °2]fjbj2 E i=i E E X) oi-jfjbj i=i (B.158) °ljfj jn E h E oijfjbji 71 [One(A)D^(/)B] J = E Olj/j6j E o\jJ)bji •3 = 1 2 E 02>/i6j2 J2 oijfjbj, 3=1 E oi,7A'2 E (B.159) %7J6JT • i=i Finally substituting from Equations (B.155) and (B.159) in Equation (B.153), we find the expression for H matrix in terms of the net parameters. 145 H = -Diag(Af) + [One(A)Diag(f)B] = ' n n n n E ijfj + E °\jJ., .i\ E °2jfj ji ••• E j=i j=i j=i y=i n n n n E Oijfjbj - E «2i/i + E <>2jfj!>j2 • • • T a b b 2 i=i i=i ?J E °\jfi ii 7=1 b i=i n, E 2.;./'/^7 =1 o 7 146 °ijfj i\ b E °o/A'2 i = i • ' ii • • - =E1 "uli 7 ii + 7 E o/A» =1 w (B.160) Appendix C Diagonal A Matrix Transformation The analysis burden for any given global Petri net can be reduced if the net with a nondiagonal A matrix is transformed to a net with a diagonal A matrix which has an equivalent subnet. Two GPNs are said to have equivalent subnets if for a subset of their places, the changes in the markings of those palets are exactly the same for any string of events. In this appendix, a procedure for diagonalization of an A matrix is presented thorough a general case example. Figure C.51 shows a two-place, two-transition G P N with all possible arcs. Figure C.51 A Two-Place, Two-Transition GPN with All Possible Arcs The net (GPNi) parameters can be written as: GP^ Wpt = Wp (l,l) t = (P, T, A, B, W {\,2) pt W {2,\) W {2,2)\ pt Wpt, Wtp, M) T {*1,*2J W = pt 147 tp W (l,l) tp W {2,l) tp W (l,2) ip W {2,2) tp A= an an «21 «22 hi hi B= &12 'Mi{k)' M {k) M(k) h2 2 The A matrix above is not a diagonal matrix. We need to transform this matrix into a diagonal one. In the following, we show how this transformation will affect other net parameters. The GPNi dynamic equation is givens as: M(k + 1) = M(k) + H M(k) + Nf(k) . k We start by finding the incidence matrix N, and the hybrid matrix H. The incidence matrix N can be written as: N = Wl- W = pt Wtp'l, 1) - W {l, 1) W {2,1) - W (l,2)-W (2,l) W (2,2)-W (2,2)_ pt tp W (l,2)' pt tp pt tp ' pt The state transition vector is /(*) = fk= \f • f The hybrid matrix H is defined as: H = (-Diag{Af ) k k + [One{A)Diag{f )B] ). (C.165) T k The overall dynamic of this net is governed by this equation. We need to find each element of the above equation and substitute in it. Afk = Diag(Af ) = Diag «12 021 «22 fl h «ll/l + 012/2 «n/i + 021/1 + 011/1 + k 021/1 + 022/2 0 148 012/2 022/2 012/2 0 021/1 + 022/2 'i ° N E { A > [0(a ) ~ 0(a ) 21 r i 22 i Since we are assuming all elements of A matrix are nonzero. k k k [One(A)Di (f )BY ag k o" h 0 0 h hi hi h. ) - One{A)Diag{f )B One(A)Diag(f )B = 7i .0 \- 7i" Diag(f ) = Diag f_ 2 hi hi hhi + fihi fih 2 + fih Jihi + f hi hhi + hhi, 2 = fihi + f hi 2 Jihi + hhi fihi + hhi + 2 hhi hhi. Substituting from above equations in Equation (C.165), we find the hybrid transition matrix to be: H K -«n/i - 0 1 2 / 2 + fihi hhi + hhi + hhi hhi + hhi - 2ih + hhi + -anh a hhi (C.173) We want to transform the above net so that we have a new net with a diagonalized A matrix. Let the net which is obtained by this transformation be represented as: 1 1 1 1 GPN^ = [P ,T ,A,B,W ,W ,M pi tp ). There are four distinct synchronous output arcs, corresponding to the A matrix elements a n , an, an and 0 2 2 - Therefore, the size of the new A (denoted asA) has to be 4 x 4 so that we have only one element on each row and each column of the new A = A matrix. We will have a net which has four places and four transitions. P = {PUPIIPZIPA) T = {hiht^tu = {PUP2,Pld,P2d}, = {h,ht2d,tid}- 149 The first two places and transitions are the same as the ones in the previous net and the other two are dummy places and transitions. The net parameters are selected such that the marking of places p = pu and p\ = p d are always equal to p\ and p respectively. The z 2 2 other net parameters are selected as: W (l,l) W pt W (2,l) 0 0 W {2,2) pt = pt pt W (2,2) 0 W (2,2) 0 W (2,l) 0 W {2,2) 0 0 0 Gt22 A = M (k) = 0 0 0 0 M\(k) MJk) M (k) M' (k) 3 4 W (2,l)_ 0 0 pt pi tp tp n pt W (l,2) tp a W (l,l) pt W (2,l) 0 0 ip 0 0 W (l,2) W (l,l) w = 0 0 W (l,2) pt tp W (l,l) tp tp Wi (l,2)J tp au 0 ' 0 0 0 a2i. 0 0 p }2 p h b 22 bp 32 ^33 ^42 hi b B = J _ J M i (A;) M (k) 2 h{k) f2(k) k M (k) 44 'fi(k) f (k) = f = Mi(k) J Uk)\ 2 A l l net parameters for GPN in the above are written in terms their of counterpart parameters 1 in GPN\, except B matrix. We need to find this matrix and show that by this transformation, we do not change the net behavior. The incidence matrix for N =W tp w {\,\)-w {ix W (\,2)-W {2X 0 0 ip tp pt pi Wi„(2,l)-Wpt(l,2) Wi„(2,2)-Wp (2,2) 0 0 ' GPN X can be written as: W = pt t o • 0 0 0 W {2X -W (l,2) W (2,2 -W (2,2) tp tp pt pt W t p (l,l)-W p t (l,l] W (l,2)-W {2X tp pt If we compare Equations (163) and (178), we see that contribution to changes in the marking of equivalent places in GPN\ and GPN[ due to these two equations are the same. 150 Next we will rind the hybrid transition matrix for A Oil 0 0 0 " 0 «22 0 0 0 0 «12 0 0 0 0 h ( Diag(Af' k Oll/l h h fl « 2 2 j"2 auf2 . 0 2 1 / 1 . 0 0 0 022/2 0 022/2 0 0 012/2 0 0 auf2 0 0 0 0 . 0 2 1 / 1 . One A vr 021 . \ 011/1 Diag GPN . O(an) 0 0 0(a ) "011/1 / 22 0 0 0 0 0 0 0(a ) 0 0 0 0 O(o l) ] 2 Diag[f ) 2 /1 0 0 h 0 0 0 0 / 0 0 0 0 = k One[X)Diag(f' )B' 0 0 2 h = Diag^B k 7i 0 0 0 b b b 0 h 0 0 b b b 0 0 0 0 h 0 0 fl Jl 21 ^31 hi h i2 b hn .h 14 b b h 21 hp f2 p h 24 b b b b = }3 • J4 p 24 34 ^33 43 44 b b b ^32 42 b b Diag h)B k b }2 22 b One A)Diag[f )B hi '" i i "1 " hhi hp hp hu 151 h 4i b b h 42 b hp b fl 44 b b b 021/1 0 0 0" 0 1 .0 0 0 0 •1 0 0 0 1 0 The hybrid transition matrix for GPN can then be written as: X Yl&ll Hi. = h\\ h\2 his hl\ h 2 2 /i23 ^24 ^31 ^32 ^33 ^34 h\i /i42 /134 h\\ -Oll/l / l bp 2 ( / l ^ l / 2 &32 / l }2 h /2&33-012/2 . • f bp 2 /l&'l4 /i44 /2&31 hb' 2 - «22/2 fibp hu /2 24 /2^4 & The changes in the marking of the net GPNi (C.186) ^ 4 3 ' / l &44 ~ 21 .fl a (before transformation can be written by reference to Equation C.173. The change in marking of the first place is given as: - 012/2 + hhi Mi(k + 1) = [-a fi u + [fib + n + f b i]M (k) 2 2 1 f2b2i]M (k) 2 Similarly, the changes in the second place markings is given by: M (k 2 + [-02l/l + 1) = [/i6i2 + / 622]MiO) 2 - O22/2 + flb\2 + /2^22J^2(^) For the transformed net GPN[ to be equivalent of the original net (GPNi), the changes in its marking should be exactly the same as the changes in the marking of the original net. The changes in the marking of GPN[ is governed by the dynamic equation given in Equation (C.186). The changes in the first place marking of GPN' is given as: M'i(k + +f2b' iM (k) 2 2 l)=[fib -a fi\M' (k) n +. f b' M {k) 2 31 3 152 + u 1 hb' M' {k). 41 4 Now, since we are taking the dummy places pz and p 4 to be same as p\ and pi respectively, their markings also should be taken to be equivalent. The changes in marking of the first place in GPN[ given in Equation (189) can be written as: M' (k + 1)= 1 \-anfi + /l&41 + hb' +f bJM[(k) u +/2&21 2 2(k) M Comparing Equations (190) and (190), we can find the values of P>' matrix (of GPN[) in terms of elements of A and B matrices (of GPN\) so that the behavior of these two nets becomes equivalent. These values are found to be: hi = hi hi = hi - a p b = hi b n 41 = 6n Similarly, we can write the changes in marking for the other three places in GPN[ and find the values of remaining elements in B' matrix. M (k + 1)= fih 2 + -022/2 + fb2 M (fc + 1) = M (k + T 3 1 + fb 2 2 2 + 2 M^k) 32 h h 2 -012/2 + M 2 i k + /2^33 ) /l&13 + M (k + l) = M (k + l)= 4 2 + fib u - 0 2 l / l + /l&41 + / 2 ^ 2 4 153 + fb 2 u M {k) 2 M,(k) l( ) M k In this fashion the B matrix is found to be: }l b B J2 b 22 b 32 b 42 b 21 31 b b .^41 }3 b b b b }4 b h2 24 &21 ^22 $4 &21.-G12 44 hi b p b p b 43 b U b - «11 &12 u • 21 22 h -ai 2 b 22 hi • b b hi 2 — 0-22 22 b h 2 Therefore, if we select the second net (GPN[) parameters according to the following, any general two-place, two-transition non-diagonal net can be transformed to a diagonal one. GPN, = [P ,T ,A,B ,W ,W ,M pt = { p i ^ f t v ^ } P = 1*1^2^.3^4} = T A an 0 0 0 0 «22 0 0 0 0 au 0 = 0 0 0 . tp {Pl,P2,Pld,P2d}, {tl,t2,t2d, hd}- bn hi h2 hi hi - au hi hi bn - a i B = «21 b - an hi hi hi i2 b u 2 h2 h2 12 b 0 0 W (l,l) W {l,2) 0 0 W (2,l) W (2,2) w = W (l,2) W (l,l) 0 0 0 0 Wpt{2,2) Wp (2,l) 0 • 0 W i ( l , l ) W {l,2) W (2,l) W (2,2) 0 0 W = 0 0 W (2,l) W (l,l) 0 0 W {2,2) W {l,2) pt pt pt pt pt pt pt t p tp tp tp tp tp tp tp M (k) 'Mi(k) M' (k) M (k) 2 3 X( ), f c 'Mi(ky M (k) Mi(k) M (k) 2 ip f (k) = f = k 2 7i(*)" 7 i W f'Ak) h(k) Hk) Hk) L/ (*). Jl(k). 4 154 — 022 Appendix D The Hybrid System Global Petri Net Parameters In this appendix we include the G P N parameters for the hybrid developed in Chapter VI. These are parameters which were used for all the simulation and analysis carried out in that chapter. GPN = {P,T,W W ,A,B,M(0),TT}, ptt tp (D.201) where P=15, T=15 and 0 w, 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 1 0 0 0 0 4 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 155 0 (D.202) (D.203) A •o 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 o. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 o 0 0 0 0 0 0 0 0 0 0 0 0 1 0 •0 0 0 0 0 0 0 0 0 0 0 0 0 0 0" 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1. (D.204) "0 0 0 0 0 0 0 0 0 0 0 0 0 . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 A,, K 2 A 0 A' A'i 0 A T T 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 u 0 0 0 0 0 0 0 0 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0. 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 o- 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 -KjK a A'c K K T r n 2 1 A m B 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 p 0 1 0 .0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 4 TT - [3 1 M(0) = [0 1 0 0 0 3 1 3 1 4 (D.205) 1 1 25 0 0 of, (D.206) 1 1 3 3 1 1 (D.207) and finally, 1 156 1 1]. Appendix E Fault Detection, Identification and Reconfiguration (FDIR) Scheme Figure E.52 shows the configuration for a fault detection, identification and reconfiguration (FDIR) scheme. This scheme can be used for the excavator system along with all of its peripheral and input/output devices. This system consists of a set of sensors in form of joysticks. These are used to enter the desired input as Cartesian coordinates. These are converted to joint angles which in turn are the inputs of the controller. The actuation is provided through pilot valves and hydraulic subsystem. The position of them arm is read and fedback to the system through joint angle sensors. The fault detection, identification and reconfiguration (FDIR) scheme can written in M A T L A B . This scheme receives the system parameters and compares these with the estimated parameters provided by the global Petri net (GPN). The actions taken by the FDIR scheme will include an alarm with announcement of the fault type and logging of the appropriate data. The system may also be configured in an attempt to reach a safe and acceptable state by changing the controller parameters. 157 Fault / Disturbance Desired Input Joint Angles Joy Sticks Inverse Kinematics ^ Controller Pilot Valves Links Hydraulics Joint Angle Sensors Global Petri Net Model t Estimated Parameters Fault Detection, Identification & Reconfiguration Scheme (FDIR) J Alarm & Data Log Figure E.52 The FDIR Scheme Block Diagram 158 Reconfiguration
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Global Petri net modeling of hybrid systems and fault...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Global Petri net modeling of hybrid systems and fault analysis Riz̤āʼī, Muḥammad 1996
pdf
Page Metadata
Item Metadata
Title | Global Petri net modeling of hybrid systems and fault analysis |
Creator |
Riz̤āʼī, Muḥammad |
Date Issued | 1996 |
Description | In this dissertation, a new methodology for the modeling and analysis of hybrid systems is presented. Hybrid systems are those which have both event-driven (asynchronous) and time-driven (synchronous) elements. This new methodology is based on an extension of the Petri net (PN) theory. Petri nets have proven themselves to be an excellent modeling tool for discrete-event systems and computer architectures. This new extension of Petri nets, which is called a Global Petri Net (GPN), provides a means for extending these capabilities to discrete-time systems. Although, many extensions of PNs have been developed over the years, the GPN methodology is the first one to perform the modeling, analysis, and simulation of discrete-event and discrete-time dynamic systems in a unified PN framework. The GPN is formally defined, and the structural and behavioral differences between PNs and GPNs are presented. The derivation of GPNs from the basic PN, and derivation of the GPN dynamic equations are also given. Next, two modeling examples are provided. These two examples show that the GPN formalism can be used to model hybrid systems in various application areas. Analysis techniques, which can be used to investigate the system properties, are developed. These analysis techniques are based on the construction of the system reachability tree and linear algebraic equations. The properties which are analyzed by these techniques include controllability, boundedness, stability, and conservation. Theorems and proofs of these properties are stated and proven. An example of a distributed hybrid system is modeled at various levels of abstraction. This system consists of a hydraulic control system and its interfaces with a bus-based communication system. At the highest level, the system is modeled as a discrete-event system. At the lowest level, where the details of the hydraulic control system are modeled, a hybrid model is used. The nets at all levels are simulated and analyzed by the global Petri net simulation and analysis tool (GPNSAT), written specifically for this research. Various system level faults for a hydraulic control system are modeled and simulated. For each fault type, the simulation shows how various system outputs are affected. At each level of abstraction, the hybrid system is simulated and analyzed for various properties, such as stability, boundedness, controllability, conservativeness, and liveness. Analysis methods developed for GPNs provide distinct fault signatures for each of the system fault types. These fault signatures can be used to distinguish successfully each fault in a detection and recognition scheme. The major contribution of this thesis is the extension of Petri nets to encompass hybrid systems. This new modeling approach can be applied to a variety of systems in application areas such as, manufacturing, multimedia, production, digital, and communication systems. This extension also enables one to examine the impact of faults in either part of the system (synchronous or asynchronous) and the effect that fault would have on the other parts of the system. These effects can be analyzed or simulated either at design time or run-time. |
Extent | 6968812 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-03-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065013 |
URI | http://hdl.handle.net/2429/6055 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1996-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1996-14822X.pdf [ 6.65MB ]
- Metadata
- JSON: 831-1.0065013.json
- JSON-LD: 831-1.0065013-ld.json
- RDF/XML (Pretty): 831-1.0065013-rdf.xml
- RDF/JSON: 831-1.0065013-rdf.json
- Turtle: 831-1.0065013-turtle.txt
- N-Triples: 831-1.0065013-rdf-ntriples.txt
- Original Record: 831-1.0065013-source.json
- Full Text
- 831-1.0065013-fulltext.txt
- Citation
- 831-1.0065013.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065013/manifest