TABLE DES MATIÈRES - mastercorp.free.fr · Introduction 1 Introduction Origine des Réseaux de Pétri : Carl Adam Petri (1962) 1.1 Déﬁnition Un Réseau de Pétri est un graphe

Réseaux de Petri

SCIA 2007

Professeur : Stéphane Marielstf�rift.frAuteurs :

Thibaut Assus & Benoit Beaudenon

[email protected]

TABLE DES MATIÈRES

Table des matières

1 Introduction 41.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 D’un point de vue sémantique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Le marquage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Franchissabilité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.5 Règles de franchissement effectif . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6 Structures de contrôle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.6.1 Séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6.2 Alternative . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.6.3 Parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.6.4 Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.6.5 Rendez-vous . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.6.6 Sémaphore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.7 Réseaux de Pétri remarquables . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.7.1 Graphe d’états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.7.2 Réseaux de Pétri sans conflit . . . . . . . . . . . . . . . . . . . . . . . . 81.7.3 Réseaux de Pétri avec conflit mais simple . . . . . . . . . . . . . . . . . 91.7.4 Réseaux de Pétri Purs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.8 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.8.1 Marquage initial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.8.2 Marquages accessibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.8.3 Transitions franchissables . . . . . . . . . . . . . . . . . . . . . . . . . . 111.8.4 Séquences de transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.8.5 Franchissement effectif . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.8.6 Ordre sur les marquages . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Propriétés 122.1 Places et Réseaux de Pétri bornés (pour un marquage initial) . . . . . . . . . . 122.2 Vivacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3 Quasi-vivacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.4 Blocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.5 Etat d’accueil et Réseau de Pétri réinitialisables . . . . . . . . . . . . . . . . . . 152.6 Composantes conservatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3 Méthodes graphiques de détermination des propriétés 163.1 Graphe des marquages accessibles . . . . . . . . . . . . . . . . . . . . . . . . . 163.2 Graphe de couverture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3.2.1 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.2 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2.3 Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223.2.4 Un graphe de jeu ! ! ! . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.2.5 Propriétés et algèbre linéaire . . . . . . . . . . . . . . . . . . . . . . . . 243.2.6 Equation Fondamentale . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Reseaux de Petri 2

TABLE DES MATIÈRES

4 Méthodes de réduction 264.1 R1 : Substition de place (en fait suppression) . . . . . . . . . . . . . . . . . . . 26

4.1.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.1.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.1.3 Cas des jetons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.1.4 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.2 R2 : Suppression des places implicites . . . . . . . . . . . . . . . . . . . . . . . 294.2.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

4.3 R3 : Suppression des transitions neutres . . . . . . . . . . . . . . . . . . . . . . 304.3.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.3.3 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

4.4 R4 : suppression des transitions identiques . . . . . . . . . . . . . . . . . . . . 314.4.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.4.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.4.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4.5 Ra : Suppression des transitions impures . . . . . . . . . . . . . . . . . . . . . . 334.5.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.5.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334.5.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.6 Rb : Suppression des transitions pures . . . . . . . . . . . . . . . . . . . . . . . 354.6.1 Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6.2 Méthode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354.6.4 Cas irréductibles de réduction . . . . . . . . . . . . . . . . . . . . . . . 38

5 Extensions de Réseaux de Pétri 405.1 Réseaux de Pétri généralisés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.2 Réseaux de Pétri à capacités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.3 Réseaux de Pétri à arc inhibiteur . . . . . . . . . . . . . . . . . . . . . . . . . . 415.4 Réseaux de Pétri colorés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Reseaux de Petri 3

TABLE DES FIGURES

Table des figures

1 Exemple de transition franchissable . . . . . . . . . . . . . . . . . . . . . . . . 42 Franchissabilité des transitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Structure de contrôle : Séquence . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Structure de contrôle : Altarnative . . . . . . . . . . . . . . . . . . . . . . . . . 65 Structure de contrôle : Parallélisme . . . . . . . . . . . . . . . . . . . . . . . . . 66 Structure de contrôle : Synchronisation . . . . . . . . . . . . . . . . . . . . . . . 67 Structure de contrôle : Rendez-vous . . . . . . . . . . . . . . . . . . . . . . . . 78 Structure de contrôle : Sémaphore - Exemple 1 . . . . . . . . . . . . . . . . . . 79 Structure de contrôle : Sémaphore - Exemple 2 . . . . . . . . . . . . . . . . . . 710 Différence entre un Réseau de Pétri et un graphe d’états . . . . . . . . . . . . . 811 Réseaux de Pétri sans et avec conflits . . . . . . . . . . . . . . . . . . . . . . . . 812 Exemple de conflit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913 Transformation 1 de Réseau de Pétri impur . . . . . . . . . . . . . . . . . . . . 914 Transformation 2 de Réseau de Pétri impur . . . . . . . . . . . . . . . . . . . . 1015 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1217 Réseau de Pétri quasi-vivant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1318 Exemple de blocage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1419 Réseau de Pétri réinitialisable . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1520 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1621 Graphe de marquage accessible de la figure 20 . . . . . . . . . . . . . . . . . . 1622 Autre exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1723 Graphe de marquage accessible de la figure 22 . . . . . . . . . . . . . . . . . . 1724 Dernier exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1825 Graphe de marquage accessible de la figure 24 . . . . . . . . . . . . . . . . . . 1826 Exemple 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1927 Graphe de couverture de la figure 26 . . . . . . . . . . . . . . . . . . . . . . . . 1928 Graphe de couverture réduit de la figure 26 . . . . . . . . . . . . . . . . . . . . 2029 Exemple 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2130 Graphe de couverture réduit de la figure 29 . . . . . . . . . . . . . . . . . . . . 2131 Exemple 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2232 Graphe de couverture réduit de la figure 31 . . . . . . . . . . . . . . . . . . . . 2233 Exemple d’un jeu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2334 Modélisation du jeu sous forme de Réseau de Pétri. . . . . . . . . . . . . . . . . 2335 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2436 Exemple 1 de Réduction R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2737 Exemple 2 de Réduction R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2738 Exemple 3 de Réduction R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2739 Exemple 4 de Réduction R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2840 Exemple 5 de Réduction R1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2841 Exemple 1 de Réduction R2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2942 Exemple 2 de Réduction R2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2943 Exemple de réduction R3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3044 Exemple de réduction R4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3145 Exemple de réductions R1 et R2 combinées . . . . . . . . . . . . . . . . . . . . 3246 Exemple de transition impure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

Reseaux de Petri 4

TABLE DES FIGURES

47 Exemple 1 de réduction Ra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3348 Exemple 2 de réduction Ra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3449 Exemple 1 de réduction Rb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3550 Exemple 2 de réduction Rb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3651 Exemple 1 de réduction Ra et Rb . . . . . . . . . . . . . . . . . . . . . . . . . . 3752 Cas irréductibles : Place isolée, Transition puits, source et combiné . . . . . . 3853 Exemple 2 de réduction Ra et Rb . . . . . . . . . . . . . . . . . . . . . . . . . . 3954 Réseau de Pétri généralisé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4055 Réseau de Pétri à capacité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4056 Exemples de Réseau de Pétri à arc inhibiteur non franchissable . . . . . . . . . 4157 Exemple 1 de Réseau de Pétri à arc inhibiteur franchissable . . . . . . . . . . . 4158 Exemple 2 de Réseau de Pétri à arc inhibiteur franchissable . . . . . . . . . . . 4259 Réseau de Pétri coloré . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Reseaux de Petri 5

Introduction

1 Introduction

Origine des Réseaux de Pétri : Carl Adam Petri (1962)

1.1 Définition

Un Réseau de Pétri est un graphe bi-parti avec

• des arcs orientés entre les nœuds• deux types de nœuds• les arcs relient des nœuds de catégories différentes• une place est symbolisée par un rond• une transition est symbolisée par un trait noir

1.2 D’un point de vue sémantique

• on associe les places à des états / ressources• on associe les ressources

︸︷︷︸

R.P

à des operations/actions︸︷︷︸

systeme reel

1.3 Le marquage

Le marquage constiste à placer des marques ou des jetons dans les places.

1.4 Franchissabilité

Une transition est franchissable ssi chacune des places en amont/entrée contient aumoins un jeton.

•

P1

P2 P3

t1

FIG. 1 – Exemple de transition franchissable

Reseaux de Petri 6

Introduction

1.5 Règles de franchissement effectif

• opération atomique• consomme un jeton dans chacune des places en entrée• produit un jeton dans chacune des places en sortie

2 éléments importants :

• franchissabilité 6= franchissement effectif• il n’est pas question de temps

t r a n s i t i o n s o u r c et r a n s i t i o n p u i t

FIG. 2 – Franchissabilité des transitions

1.6 Structures de contrôle

1.6.1 Séquence

⇒La transition t2 ne sera franchie que si t1 l’a été

P1 P2

t1 t2

FIG. 3 – Structure de contrôle : Séquence

Reseaux de Petri 7

Introduction

1.6.2 Alternative

••

P1

P2 P3

t1 t2

FIG. 4 – Structure de contrôle : Altarnative

1.6.3 Parallélisme

•

P1

P2 P3

t1

t2 t3

FIG. 5 – Structure de contrôle : Parallélisme

1.6.4 Synchronisation

Vendeur Client

PayerPrendre

FIG. 6 – Structure de contrôle : Synchronisation

Reseaux de Petri 8

Introduction

1.6.5 Rendez-vous

• •

P1

P3

P2

P4

Echanges

FIG. 7 – Structure de contrôle : Rendez-vous

1.6.6 Sémaphore

•

•

P1

P2

P3

P4

Crayon

t1

t2

t3

t4

FIG. 8 – Structure de contrôle : Sémaphore - Exemple 1P r o d u c t e u r E n t r e p ô t C o n s o m m a t e u rE n t r e p ô tP l a c e L i b r ep 2

FIG. 9 – Structure de contrôle : Sémaphore - Exemple 2

Reseaux de Petri 9

Introduction

1.7 Réseaux de Pétri remarquables

1.7.1 Graphe d’états

FIG. 10 – Différence entre un Réseau de Pétri et un graphe d’états

1.7.2 Réseaux de Pétri sans conflit

FIG. 11 – Réseaux de Pétri sans et avec conflits

Reseaux de Petri 10

Introduction

1.7.3 Réseaux de Pétri avec conflit mais simple

t 1 t 2 t 3FIG. 12 – Exemple de conflit

t1 ou t2 et t2 ou t3← Dépendance entre entre les conflits.

1.7.4 Réseaux de Pétri Purs

Transformation d’un Réseaux de Pétri impur en son équivalent purt 1t 2

FIG. 13 – Transformation 1 de Réseau de Pétri impur

Reseaux de Petri 11

Introduction

FIG. 14 – Transformation 2 de Réseau de Pétri impur

Reseaux de Petri 12

Introduction

1.8 Notations

•

P2

P1

P3

P5P4

t2

t1

t3

t4

FIG. 15 – Exemple

1.8.1 Marquage initial

M0 =

10000

1.8.2 Marquages accessibles

∗M0 : L’ensemble des marquagaes accessibles.

∗M0 =

M0, M1 =

01100

M2 =

00110

M3 =

00011

, M4 =

01010

1.8.3 Transitions franchissables

M[t > (1)

M3[t4 > (2)

M0[t1 > (3)

Reseaux de Petri 13

Propriétés

1.8.4 Séquences de transitions

σ = t1t2 (4)

M0[σ > (5)

1.8.5 Franchissement effectif

M0[t1 > M1 (6)

M0[t1t2t3 > M3 (7)

M0[t1t3t2 > M3 (8)

1.8.6 Ordre sur les marquages

M′ ≥ M ⇔ ∀P, M′(P) ≥ M(P)

2 Propriétés

2.1 Places et Réseaux de Pétri bornés (pour un marquage initial)

• P est bornée pour M0 donnéessi ∃k ∈ N, ∀M ∈∗ M0, M(P) ≤ kP est k-bornée

• Un Réseau de Pétri est dit bornéssi toutes les places sont bornées

• Réseau sauf/binaire = Réseau non borné

• • •

•

P1

P2

FIG. 16 – Exemple

{

M0 =00

, M1 =01

}

Bornage et ordre sur les marquages. Si le réseau est non borné pour M0, alors il est nonborné pour tout M′

0 ≥ M0

Reseaux de Petri 14

Propriétés

2.2 Vivacité

Transition vivante tj est vivante pour M0 donnée si

∀M ∈ ∗M0, ∃ σ, σ′/M[σtjσ

′>

Réseau de Pétri vivant Un Réseau de Pétri vivant est un Réseau de Pétri dans lequel toutesles transitions sont vivantes

2.3 Quasi-vivacité

quasi-vivacité d’une transition tj est quasi-vivante pour M0 donné ssi

∃M ∈ ∗M0/∃σ, σ, σ′/M[σtjσ

′>

Réseau de Pétri quasi-vivant or toutes les transitions sont quasi vivantes.

•

P1

P2

P3

t1

t2

t3

FIG. 17 – Réseau de Pétri quasi-vivant

M0[t1 >

M0[t1t2 >

M0[t1t2t3 >

M0[t1t2t3t2t3 >

Réseau de Pétri quasi-vivant.M1

010

M1 ∈∗M0

M1[t1 > Réseau de Pétri non vivant

Reseaux de Petri 15

Propriétés

2.4 Blocage

Un blocage est un marquage dans lequel aucune transition n’est franchissable.

•

P1

P2 P3

P4

t1 t2

t3

t4

FIG. 18 – Exemple de blocage

M0 =

1000

, M1 =

0100

⇒ M1 a un bloquage

Reseaux de Petri 16

Propriétés

2.5 Etat d’accueil et Réseau de Pétri réinitialisables

Ma est un état d’accueil pour M0 donné

ssi ∀M ∈ ∗M0, ∃σ/M[σ > Ma

•

P1

P2

P3

t1

t2

t3

FIG. 19 – Réseau de Pétri réinitialisable

M0 =

100

, Ma =010

, M′a =

001

Réseau de Pétri est réinitialisable ssi M0 est 1 état d’accueil

2.6 Composantes conservatives

1 ensemble de placesC1 = {P1, P2, P4}

C2 = {P1, P3, P5}

Vecteurs de pondérations

V1 =

11010

V2 =

10101

1m(P1) + 1m(P2) + 1m(P4) = 1

Reseaux de Petri 17

Méthodes graphiques de détermination des propriétés

3 Méthodes graphiques de détermination des propriétés

3.1 Graphe des marquages accessibles

P1

P2P3

t1 t2

t3

FIG. 20 – Exemple

M0 1

0

0

t2

t1

0

1

0

0

0

1

t30

0

1

t3

FIG. 21 – Graphe de marquage accessible de la figure 20

Reseaux de Petri 18


•

P1

P2

P5

P3

P4

P6

t1

t3

t5

t2

t4

FIG. 22 – Autre exemple

M0 1

0

0

0

0

0

t1

0

1

1

1

0

0

t2

t3

0

0

0

1

1

0

0

1

0

0

0

1t5

t4


Reseaux de Petri 19


P

source

puits

FIG. 24 – Dernier exemple

M0

0 1 2 . . .

t1 t1 t1

t2 t2 t2


Reseaux de Petri 20


3.2 Graphe de couverture

3.2.1 Exemple 1

• P1

P2 P3

t1

t2

t3

FIG. 26 – Exemple 1

M0 1

0

0

t10

1

1

t2

t3

0

0

0

1

0

1 t10

1

2

t2

t3

0

0

1

1

0

2

M1

FIG. 27 – Graphe de couverture de la figure 26

Reseaux de Petri 21


M0 1

0

0

t10

1

1

t2

t3

0

0

0

1

0ω

t10

1ω

t2

0

0ω

t3

FIG. 28 – Graphe de couverture réduit de la figure 26

Reseaux de Petri 22


3.2.2 Exemple 2

• P1

P2

P3 P4

t2

t1

t3


M0 1

0

0

0

t1

0

1

0

0

t3

t2

1

0

0

0

0

1ω

0

t3

0

0ω

1

t2


Reseaux de Petri 23


3.2.3 Exemple 3

• P1 P2

P3

P4t1

t2

t3


M0 1

0

0

0

t2

0

1

0

0

t1

1

0ω

0

t2

0

1ω

0

t1

t3

0

1ω

ω

t1

t3

1

0ω

ω

t2


Reseaux de Petri 24


3.2.4 Un graphe de jeu ! ! !

Depart

+$1

P1

P2

P3

P4

Prison

P5

P6

P7

Arrivee

Lave− $1

Teleportations

FIG. 33 – Exemple d’un jeu. . .

P1

P2

P3

P5

P4P6P7

PCagnotte

t1

t2

t3

t8

t4

t5t6

t7

FIG. 34 – Modélisation du jeu sous forme de Réseau de Pétri. . .

Reseaux de Petri 25


3.2.5 Propriétés et algèbre linéaire

Réseau de Pétri non marqué :

Quadruplet : R = (P, T, Pre, Post)

où :• P = {P1, P2, . . . , Pn}• T = {t1, t2, . . . , tm}• P ∩ T = ⊘• Pre : P× T → {0, 1} application d’incidence avant• Post : P× T → {0, 1} application d’incidence arrière

P2

P1

P3

P5P4

t2

t1

t3

t4

FIG. 35 – Exemple

• Pre : (Pi, tj) est le poids de l’arc Pi → t1

• Post : (Pi, tj) est le poids de l’arc tj → Pi

• Pre(P3, t3) = 1• Post(P3, t3) = 0

Soit :• W− = [W−

i,j ] matrice d’incidence avant W−i,j = Pr(Pi, tj)

• W+ = [W+i,j ] matrice d’incidence arrière W−

i,j = Post(Pi, tj)

W− =

t1 t2 t3 t41 0 0 0 P1

0 1 0 0 P2

0 0 1 0 P3

0 0 0 1 P4

0 0 0 1 P5

W+ =

t1 t2 t3 t40 0 0 1 P1

1 0 0 0 P2

1 0 0 0 P3

0 1 0 0 P4

0 0 1 0 P5

W =︸︷︷︸

W+−W−

t1 t2 t3 t4-1 0 0 11 -1 0 01 0 -1 00 1 0 -10 0 1 -1

Soit :• σ = t1 t2 t3 séquence de transition• σ = vecteur caractéristique de σ

• σ = (1, 1, 1, 0) ⇒ premier 1 : nb de fois où t1 est franchie dans σ. . .

Reseaux de Petri 26


3.2.6 Equation Fondamentale

Mk = M1 + W.σ

M0 = (1, 0, 0, 0, 0)

M0[σ > M1]

W = W+ −W−

σ = t1t2t3

W =

-1 0 0 11 -1 0 01 0 -1 00 1 0 -10 0 1 -1

.

11100

+

10000

=

00011

V = vecteur de pondération (9)

= (α1, . . . , αi, . . . , αn) (10)

∀M ∈ M0 ∑ αi ×M(Pi) = Cte (11)

Vt.Mk = Vt.M0 + Vt.W.σ (12)

Vt.W.σ = 0 (13)

Vt.W.σ = 0 (14)

Vt.W = 0 (15)

C = P1, P2, P4 (16)

V = (1, 1, 0, 1, 0) (17)

Reseaux de Petri 27

Méthodes de réduction

4 Méthodes de réduction

Il existe 6 méthodes :

• 4 méthodes conservent les propriétés classiques : R1 → R4

• 2 méthodes conservent les invariants de marquage : Ra → Rb

Dans ce cours nous verrons :

• Conditions• Méthode de réduction• Cas des jetons

4.1 R1 : Substition de place (en fait suppression)

4.1.1 Conditions

Une place P peut être située si et seulement si :

• les transitions en sortie de P n’ont pas d’autre place en entrée que P• il n’existe pas de transition tj qui soit à la fois en entrée et en sortie de P (P doit être

pure)• au moins une transition en sortie de P n’est pas une transition puit. Si toutes ces condi-

tions sont remplies, P peut être supprimée.

4.1.2 Méthode

• on supprime la place• on supprime les transitions en sortie• on crée une transition ti,j par couple ti, tj des transitions en entrée et sortie de P

4.1.3 Cas des jetons

• si une transition en sortie, facile : marquage après franchissement• on doit étudier autont de réseaux que de transitions en sortie

4.1.4 Exemples

Reseaux de Petri 28


• •P1

P2

P3

P1

P3

t1

t2

t12

◦P2 = {t1}

P2◦ = {t2}

◦t1 = {P1}

t1◦ = {P2}

◦t2 = {P2}

t2◦ = {P3}

R1

FIG. 36 – Exemple 1 de Réduction R1

•

•

P1

P1

P4

P4

P2

P3

P3

P5

P5

t1

t2

t12

R1

◦P2 = {t1}

P2◦ = {t2}


• •

P1 P1P2 P2

P3

P4 P4

t1 t2

t3

t13 t23

R1

◦P3 = {t1, t2}

P3◦ = {t3}


Reseaux de Petri 29


• •

P1 P1

P2

P3 P3P4 P4

t1

t2 t3

t12 t23

R1

◦P2 = {t1}

P2◦ = {t2, t3}


• •

• •

P5

P1 P1P2 P2

P3 P3P4 P4

t1 t2

t3 t4

t13 t14 t23 t24

R1

◦P5 = {t1, t2}

P5◦ = {t3, t4}


Reseaux de Petri 30


4.2 R2 : Suppression des places implicites

4.2.1 Conditions

La place doit être implicite. Elle l’est ssi :

• son marquage n’a aucun impact sur le franchissement des transitions en sortie• Ce même margquage peut s’exprimer sous la forme d’une combinaison linéaire des

marquages des autres places

M(Pi) = (∑k 6=i

ak.M(Pk)) + b

4.2.2 Méthode

On supprime place et arcs en entrée et sortie.

4.2.3 Exemple

•

P1 P1

P2

P3 P3

t1 t1

R2

P2 est implicite


• •

P1 P1

P2

P3 P3

t1

t1

t3

t1

t1

t3

R2

M(P2) = M(P1) + M(P3)


Reseaux de Petri 31


4.3 R3 : Suppression des transitions neutres

4.3.1 Conditions

Une transition neutre est une transition dont les places en entrée sont aussi des places ensortie. tj est neutre ssi ◦tj = tj

◦

Si ∃ tk 6= tj tq ∀Pi ∈◦tj Post(Pi, tk) ≥ Pre(Pi, tj)

4.3.2 Méthode

On supprime transitions et arcs

4.3.3 Exemple

P1 P1P2 P2

t1

t2

t4

t5

t3

t1

t2

t4

t5

R3

FIG. 43 – Exemple de réduction R3

Reseaux de Petri 32


4.4 R4 : suppression des transitions identiques

4.4.1 Conditions

Deux transitions identiques. Deux transitions sont identiques si on a :

◦tj =◦ tk et tj◦ = tk

◦

4.4.2 Méthode

Suppression d’une des 2 transitions et les arcs correspondants.

4.4.3 Exemples

• •

P1 P1P2 P2

P3 P3

t1 t1t2

R4

FIG. 44 – Exemple de réduction R4

Reseaux de Petri 33


•

P2

P1

P3

P5P4

t2 t3

t4

t1

◦P2 = {t1}

P2◦ = {t2}

R1

1

• P1

P3

P5P4

t3

t4

t12

R2

2

• P1

P3

P5

t3

t4

t12

R1

3

•

•P1

P1

P5

t4

t123

t1234R1

4 5

FIG. 45 – Exemple de réductions R1 et R2 combinées

Reseaux de Petri 34


4.5 Ra : Suppression des transitions impures

4.5.1 Conditions

La transition doit être impure.

•P t

FIG. 46 – Exemple de transition impure

4.5.2 Méthode

• Suppression des arcs Pi → tj et tj → Pi où Pi est la place impure• Suppression de la transition si elle est isolée

4.5.3 Exemples

Pi t1

Ra

Pi

FIG. 47 – Exemple 1 de réduction Ra

Reseaux de Petri 35


• •

P1

P2

P3

P1

P3

t1 t1

Ra

P2

FIG. 48 – Exemple 2 de réduction Ra

Reseaux de Petri 36


4.6 Rb : Suppression des transitions pures

4.6.1 Conditions

On peut réduire tj si ◦tj 6= ∅ et t◦j 6= ∅

4.6.2 Méthode

• Supprime de la transition tj

• (Pi, Pk)/Pi ∈◦ tjPk ∈ t◦j

On va créer une place Pi+k

Le marquage de Pi+k = M(Pi) + M(Pk)• Les transitions en entrée de Pi + k osnt celles de Pi et Pk. Idem pour les transitions en

sortie.

4.6.3 Exemples

•

•

P1

P2

P1+2

t1

t2

t3

t1

t3

Rb

◦t2 = {P1}

t2◦ = {P2}

FIG. 49 – Exemple 1 de réduction Rb

Reseaux de Petri 37


•

•

•• • •

P1

P3

P2

P4

P1+3 P1+4 P2+3 P2+4

t1 t2

t3

t4 t5

t1 t2

t4 t5

Rb

◦t2 = {P1, P2}

t2◦ = {P3, P4}

FIG. 50 – Exemple 2 de réduction Rb

Reseaux de Petri 38


•

•P2

P1

P3

P5P4

t2

t1

t3

t4Rb

1

•

•

P1

P3

P5

P2+4

t1

t3

t4 Rb

2

•

•

P1

P3+5P2+4

t1

t4 Rb

3

• •• P1+3+5P1+2+4

t1

Ra

4

• •• P1+3+5P1+2+4

5

Invariants de marquage : {P1+2+4, P1+3+5}

FIG. 51 – Exemple 1 de réduction Ra et Rb

Reseaux de Petri 39


4.6.4 Cas irréductibles de réduction

•

P1+2

• P3+4

t1

• P3+4

t1

• P1+2

t1

t2

FIG. 52 – Cas irréductibles : Place isolée, Transition puits, source et combiné

Reseaux de Petri 40


•

•

•P1

P2

P5

P6

P3

P4

t1

t2

t3

t4

t5

Rb 1

•• •

P1+2

P5

P6

P3

P4

t1

t3

t4

t5Ra

2

•• •

P1+2

P5

P6

P3

P4

t1

t3

t4

t5

Rb 3

•• •

P1+2 P5+6P3

P4

t1

t3

t4

Ra

4

•• •

P1+2 P5+6P3

P4

t1

t3

t4

Rb 5

•• •

P1+2 P5+6

P3+4

t1 t4

Invariants de marquage : {P1+2, P5+6}

6

FIG. 53 – Exemple 2 de réduction Ra et Rb

Reseaux de Petri 41

Extensions de Réseaux de Pétri

5 Extensions de Réseaux de Pétri

5.1 Réseaux de Pétri généralisés

• • • •• ••

•••

P1

P3

P2

P4

P1

P3

P2

P4

t3 t3

3 3

2 2t1

FIG. 54 – Réseau de Pétri généralisé

La place R1 nécessite d’avoir 3 jetons pour que t1 soit franchissable et ce franchissementproduit 2 jetons dans P4

5.2 Réseaux de Pétri à capacités

• • • • • •

••

P1 P1

P2 P2

P2′t1

t2

t1

t2

Cap de P2 = 2

FIG. 55 – Réseau de Pétri à capacité

La place ainsi générée modélise la “capacité” ⇒ en franchissant 2 fois t1, de la place P2,la seule façon de la refranchir est de frarchir t2 avant.

Reseaux de Petri 42


5.3 Réseaux de Pétri à arc inhibiteur

P1 P2

P3

t1

• •

P1 P2

P3

t1

FIG. 56 – Exemples de Réseau de Pétri à arc inhibiteur non franchissable

•

•

P1 P1P2 P2

P3 P3

t1 t1

t1

FIG. 57 – Exemple 1 de Réseau de Pétri à arc inhibiteur franchissable

Reseaux de Petri 43


•

P1

P2

P1

P2 P′

t2 t3 t2 t3

t1 t1

t1

FIG. 58 – Exemple 2 de Réseau de Pétri à arc inhibiteur franchissable

Reseaux de Petri 44


5.4 Réseaux de Pétri colorés

P1 P2

P3

t1

beer()

f oo() bar()

FIG. 59 – Réseau de Pétri coloré

Reseaux de Petri 45

Documents

TABLE DES MATIÈRES - mastercorp.free.fr · Introduction 1 Introduction Origine des Réseaux de Pétri : Carl Adam Petri (1962) 1.1 Déﬁnition Un Réseau de Pétri est un graphe