Discrete, Continuous, and Hybrid Petri Nets (eBook)

René David, Hassane Alla (Autoren)

eBook Download: PDF

2005 | 2005
XXII, 526 Seiten
Springer Berlin (Verlag)
978-3-540-26821-5 (ISBN)

Infos

Petri nets do not designate a single modeling formalism. In fact, newcomers to the field confess sometimes to be a little puzzled by the diversity of formalisms that are recognized under this 'umbrella'. Disregarding some extensions to the theoretical modeling capabilities, and looking at the level of abstraction of the formalisms, Condition/Event, Elementary, Place/Transition, Predicate/Transition, Colored, Object Oriented... net systems are frequently encountered in the literature. On the other side, provided with appropriate interpretative extensions, Controled Net Systems, Marking Diagrams (the Petri net generalization of State Diagrams), or the many-many variants in which time can be explicitly incorporated -Time(d), Deterministic, (Generalized) Stochastic, Fuzzy...- are defined. This represents another way to define practical formalisms that can be obtained by the 'cro- product' of the two mentioned dimensions. Thus Petri nets constitute a modeling paradigm, understandable in a broad sense as 'the total pattern of perceiving, conceptualising, acting, validating and valuing associated with a particular image of reality that prevails in a science or a branch of science' (Thomas S. Kuhn).

Inhalt

Foreword 5
Preface 8
Acknowledgements 10
Contents 12
Notation 18
Bases of Petri Nets 22
1.1 BASIC CONCEPTS 22
1.1.1 Places, Transitions and Arcs 22
1.1.2 Marking 23
1.1.3 Firing of a Transition 24
1.1.4 Autonomous and Non-autonomous Petri Nets 25
1.1.5 The Essential Characteristics 26
1.2 SPECIAL PETRI NETS 26
1.2.1 Particular Structures 27
1.2.2 Abbreviations and Extensions 30
1.3 MODELING OF SOME CONCEPTS 38
NOTES and REFERENCES 41
Properties of Petri Nets 42
2.1 PRESENTATION OF THE MAIN PROPERTIES 42
2.1.1 Notations and Definitions 42
2.1.2 Bounded Petri Net, Safe Petri Net 45
2.1.3 Liveness and Deadlock 46
2.1.4 Conflicts 51
2.1.5 Invariants 55
2.2 SEEKING THE PROPERTIES OF PETRI NETS 58
2.2.1 Graph of Markings and Coverability Root Tree 58
2.2.2 Linear Algebra 62
2.2.3 Reduction Methods Preserving Some Properties 72
2.2.4 Other Results 74
2.2.5 Concluding Remarks 77
NOTES and REFERENCES 80
Non-Autonomous Petri Nets 82
3.1 INTRODUCTION 82
3.2 SYNCHRONIZED PETRI NETS 84
3.2.1 Principle 85
3.2.2 Iterated Firing On Occurrence of an External Event 91
3.2.3 Properties of the Synchronized PNs 97
3.3 INTERPRETED PETRI NETS 105
3.3.1 Definition of a Control Interpreted Petri Net 106
3.3.2 Interpretation Algorithm of a Control Interpreted PN 110
3.3.3 Interpreted PN Without Outputs: Generalization of the Concept of Synchronized PN 113
3.4 TIMED PETRI NETS 114
3.4.1 General Information 114
3.4.2 Constant Timing 117
3.4.3 Stochastic Petri Nets 124
NOTES and REFERENCES 129
Autonomous Continuous and Hybrid Petri Nets 132
4.1 AUTONOMOUS CONTINUOUS PETRI NETS 132
4.1.1 From Discrete Petri Net To Continuous Petri Net 132
4.1.2 Definition 135
4.1.3 Reachability and Conflicts 137
4.2 AUTONOMOUS HYBRID PETRI NETS 143
4.2.1 Intuitive presentation 143
4.2.2 Definition 145
4.2.3 Reachability and conflicts 147
4.3 PROPERTIES OF AUTONOMOUS CONTINUOUS AND HYBRID PETRI NETS 154
4.3.1 Definitions and Properties Similar for Discrete and Continuous Petri Nets 154
4.3.2 Reachability and Limit Reachability for a Continuous Petri Net 156
4.3.3 e- Liveness for a Continuous Petri Net 159
4.3.4 Lim-Liveness for a Continuous Petri Net 160
4.4 EXTENDED HYBRID PETRI NETS 164
4.4.1 Threshold Test 164
4.4.2 Zero Test and Arc Weight 0+ 165
4.4.3 Marking 0+ 167
4.4.4 Definition 168
NOTES and REFERENCES 169
Timed Continuous Petri Nets 170
5.1 DEFINITION OF THE MODEL 170
5.1.1 Limit Case of a Discrete Timed Petri Net 171
5.1.2 Analysis of Some Basic Behaviors 172
5.1.3 Definitions 184
5.2 CONFLICTS 191
5.2.1 Existence of an Actual Conflict 191
5.2.2 Conflict Resolution 192
5.3 SPEED CALCULATION ALGORITHMS 194
5.3.1 There is No Structural Conflict 195
5.3.2 Resolution By Priorities 197
5.3.3 Resolution By Sharings And Priorities 210
5.3.4 Complete Algorithm For All IB-states 223
5.4 PROPERTIES 226
5.4.1 Illustratory Examples 226
5.4.2 General Properties 229
5.4.3 Modeling Power 233
5.5 MAXIMAL SPEEDS FUNCTIONS OF TIME 235
NOTES and REFERENCES 237
Timed Hybrid Petri Nets 240
6.1 DEFINITION OF THE MODEL 240
6.1.1 Intuitive Presentation 241
6.1.2 Events To Be Considered 242
6.1.3 Conflict Resolutions 244
6.1.4 Flow Rate and Maximal Firing Speed 247
6.1.5 Formal Definitions 249
6.2 ALGORITHM 256
6.2.1 Resolution for a Case 4 Conflict 257
6.2.2 Consequences of Various Events 262
6.2.3 Timed Hybrid PNs Automatically Treated in Algorithm 6.1 264
6.2.4 Algorithm for Building the Evolution Graph 270
6.2.5 Resolution of a Case Not Treated by Algorithm 6.1 275
6.3 VARIANTS OF THE MODEL 276
6.3.1 Synchronized D-Transitions 276
6.3.2 Stochastic Timings for D-Transitions 279
6.3.3 C-Transitions with Flow Rates Functions of Time 280
6.4 EXTENDED TIMED HYBRID PETRI NETS 282
6.4.1 Modeling of Zero Buffers 283
6.4.2 Arc Weight 0+ for Testing if a C-Place is Empty 286
6.4.3 Pure Delay of a Continuous Flow 289
6.4.4 Conclusion on Timed Extended Hybrid Petri Nets 296
NOTES and REFERENCES 297
Hybrid Petri Nets with Speeds Depending on the C-Marking 300
7.1 APPROXIMATION OF TIMED DISCRETE SYSTEMS BY VHPNs 300
7.1.1 Weakness of Basic Timed Hybrid PNs for Small Numbers 301
7.1.2 Simple Cases of Variable Speed Hybrid PN 302
7.1.3 General Case of VHPN 306
7.1.4 Application Examples 315
7.2 ASYMPTOTIC HYBRID PETRI NETS ( AHPNs) 320
7.2.1 A C-Transition Has a Single Input C-Place 321
7.2.2 Several Input C-Places 326
7.2.3 Generalization 327
7.2.4 Differences Between VHPN and AHPN Behaviors 331
7.3 OTHER MODELS 335
7.3.1 Liquid Flow 335
7.3.2 Differential Hybrid Petri Nets 336
7.3.3 Transfer Line with Operation-Dependent Failures 339
NOTES and REFERENCES 340
Postface 342
Post.1 USE & ANALYSIS OF VARIOUS PN MODELS
Post.2 RELATIONS AMONG KINDS OF HYBRID PNs 343
Appendices 348
Appendix A Regular Expressions and Languages 348
Appendix B Conflict Resolution 350
Appendix C Elements of Graph Theory 354
Appendix D Algebra of Events 356
Appendix E About Grafcet 360
Appendix F Modeling Power of Synchronized PNs 366
Appendix G Timed Petri Nets Are Special Cases of Synchronized Petri Nets 368
Appendix H Time Petri Nets 374
Appendix I Linearity of the Fundamental Equation for Continuous Petri Nets 378
Appendix J Notation 0+ and Non-Standard Analysis 382
Appendix K Sharing Between Two Transitions 384
Appendix L Graph of Relations Among Conflicts 390
Appendix M Piecewise Constant Maximal Speeds 394
Appendix N From Hybrid PNs to Hybrid Automata 402
Appendix O P& T-Timed Petri Nets and Modeling Power
Exercises 414
Solutions to Exercises 454
References 522
Index 536

Produkt-Details

• Erscheint lt. Verlag: 8.9.2005
• Zusatzinfo: XXII, 526 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Informatik ► Theorie / Studium ► Künstliche Intelligenz / Robotik
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: Bipartite Graphs • Continuous Petri Nets • control engineering • Discrete Petri Nets • Hybrid Petri Nets • Petri net • Petri Nets
• ISBN-10: 3-540-26821-9 / 3540268219
• ISBN-13: 978-3-540-26821-5 / 9783540268215