Rdm23

Cours de r´eseau de Petri

Yann Mor`ere

Avril 2002

Table des mati`eres

Introduction 1

1 R´eseaux de Petri 3

2 Introduction au RdP 5

2.1 Principe de mod´elisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 R´eseaux de conditions et d’´ev`enements . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.1 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.2.2 D´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.3 R`egles d’activation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2.4 Conflit d’occurence d’´ev`enements . . . . . . . . . . . . . . . . . . . . . . 9

2.2.5 Conditions compl´ementaires . . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2.6 Repr´esentation de la dynamique d’un RdP . . . . . . . . . . . . . . . . . 11

2.3 R´eseaux de places et transistions . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.1 Un exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.3.2 D´efinition et r`egles d’activation . . . . . . . . . . . . . . . . . . . . . . . 14

2.3.3 Places compl´ementaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 R´eseaux color´es `a pr´edicats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4.1 Un exemple de r´eseau color´e . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4.2 D´efinition et r`egles d’activation . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.3 Quelques extensions des r´eseaux color´es . . . . . . . . . . . . . . . . . . . 17

2.4.4 Un exemple de r´eseau `a pr´edicats . . . . . . . . . . . . . . . . . . . . . . 18

2.4.5 D´efinitions et r`egles d’activation . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.6 les r´eseaux de Petri g´en´eralis´es . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.7 R´eseau de Petri FIFO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.8 R´eseau de Petri `a arcs inhibiteurs . . . . . . . . . . . . . . . . . . . . . . 20

2.4.9 R´eseaux de Petri `a priorit´es . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

3 Analyse de R´eseau de Petri 23

3.1 D´efinition de base . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.1 Graphe associ´e `a un RdP . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.2 Dynamique d’un RdP . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.3 Grammaire associ´ee `a un RdP . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1.4 Matrice d’incidence d’un RdP . . . . . . . . . . . . . . . . . . . . . . . . 28

3.1.5 Franchissement d’une transition . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.6 Conflit et parall´elisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.6.1 Conflit structurel . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.6.2 Conflit effectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.6.3 Parall´elisme structurel . . . . . . . . . . . . . . . . . . . . . . . 31

3.1.6.4 Parall´elisme effectif . . . . . . . . . . . . . . . . . . . . . . . . . 32

i

3.1.7 S´equence de franchissement . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2 Arbres et graphes de couverture . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.3 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.3.1 p-invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.4 Propri´et´es qualitatives des RdP . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.4.1 Les propri´et´es comportementales . . . . . . . . . . . . . . . . . . . . . . 42

3.4.1.1 Probl`emes d’atteignabilit´es . . . . . . . . . . . . . . . . . . . . 42

3.4.1.2 Dormitude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.4.1.3 Vivacit´e et blocage . . . . . . . . . . . . . . . . . . . . . . . . . 44

ii

Table des figures

2.1 Situation de conflit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3.1 Exemple de r´eseau de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

iii

Liste des tableaux

v

1 / 46

Introduction

R´eseau de Petri

Carl Adam Petri est un math´ematicien allemand qui a d´efini un outil math´ematique tr`es

g´en´eral permettant de d´ecrire des relations existant entre des conditions et des ´ev`enements, de

mod´eliser le comportement de syst`emes dynamiques `a ´ev`enements discrets.

¤

...