Modélisation et Simulation :

Les réseaux de Pétri

Les Réseaux de Pétri (RdP) sont des outils à la fois graphiques et mathématiques permettant
de modéliser le comportement dynamique des systèmes à évènements discrets. Leur
représentation graphique permet de visualiser d’une manière naturelle le parallélisme, la
synchronisation, le partage de ressources…etc. Leur représentation mathématique permet
d’analyser le modèle pour étudier ses propriétés et de les comparer avec le comportement du
système réel.

1. Les réseaux de Pétri

Historiquement, le réseau est présenté par Carl Adam Pétri dans sa thèse "Communication
avec des Automates" en Allemagne à Bonn en 1962 . Ce travail a continu à être développé par
Anatol W. Holt, F. Commoner, M. Hack et leurs collègues dans le groupe de recherche de
Massachussetts Institute Of Technology (MIT) dans des années 70s. En 1975 la première
conférence de réseau de Pétri et des méthodes relationnels ont été organisés à MIT. En 1981
le premier livre du réseau de Pétri a été publié en Anglais par J. Peterson. Aujourd'hui, suivre
Pétri-Net Newsletter, chaque année il y a des 600 aux 800 d'oeuvres des réseaux de Pétri sont
publiés.

2. Définition informelle

Les Réseaux de Pétri permettant de modéliser les systèmes dynamiques, c'est-à-dire des
systèmes évoluant d'un état à un autre à la suite des événements externes ou internes . I
nformellement un RdP est un graphe orienté, comprenant deux sortes de noeuds: des places et
des transitions. Ce graphe est constitué de telle sorte que les arcs du graphe ne peuvent relier
que des places aux transitions ou des transitions aux places. On représente graphiquement les
places par des cercles et les transitions par des barres ou des traits. Chaque place contient un
nombre (ou non) de marques ou jetons (voir figure 1).
Master 2 académique Modélisation simulation

Figure 1: Les principes de base des réseaux de pétri

Dans la modélisation des systèmes, Les places servent à représenter les états du système
modélisé, tandis que les transitions représentent les changements d’état ou les événements.
Quelques interprétations typiques des transitions et leurs places d’entrées et de sorties sont
présentées dans Le tableau 4.1.

Tableau 1: Quelques interprétations typiques de transitions et de places

3. Définition formelle

Formellement un RdP est un quintuple, R= (P, T, F, W, M0) tel que :

Master 2 académique Modélisation simulation

La structure de RdP est donnée par le quadruplet Q= (P, T, F, W), Q représente le RdP
sans aucune spécification de marquage initial M0. Un RdP marqué est noté par R= (Q,M0).
Soit R= (P, T, F, W, M0) un RdP. On a les notations suivantes:
°t : l’ensemble des places d’entrée de la transition t.
t° : l’ensemble des places de sortie de la transition t.
°p : l’ensemble des transitions d’entrée de la place p.
P° : l’ensemble de transitions de sortie de la place p.
La figure 2 donne une idée sur toutes les notions définit dans cette section.

Figure 2: Définition formelle d'un Réseau de Pétri

4. Marquage

On appelle marquage une distribution de jetons sur les places. Le marquage initial noté

M0 est la distribution initiale de jetons dans le réseau à l’instant initial. Le marquage d’un

RdP est une application M : P - N donnant pour chaque place le nombre de jetons qu’elle
Master 2 académique Modélisation simulation

contient. Le marquage de la place pi est noté par M(pi) qui est un nombre entier. Un

marquage est représenté par un vecteur (voir figure 3).7

Figure 4.3: Exemple de marquage initiale

Le marquage M définit l'état du système décrit par le réseau à un instant donné. C'est un
vecteur colonne de dimension égale au nombre de places dans le réseau. Le iéme élément du
vecteur correspond au nombre de jetons contenus dans la place Pi.

5. Evolution d’un réseau de Pétri

L’évolution d’un RdP correspond à l’évolution de son marquage au cours du temps, cette
évolution simule le comportement dynamique du système modélisé, il se traduit par un
déplacement de marques. Déterminer l’évolution d’un RdP correspond en fait à le simuler,
terme plus généralement utilisé en modélisation.
Rappelant qu'à chaque arc ((p,t) ou (t,p)) est associé un nombre entier strictement positif
appelé poids de l’arc (W(p,t) ou W(t,p)) et notant que lorsque ce poids n’est pas signalé dans
le réseau de pétri, il est égal à "1" par défaut , on peut alors donner les règles de changement
de marquage du réseau suivantes :
Une transition t est validée (ou sensibilisée, franchissable ou tirable) si toutes les
places p en amont de celle-ci (p€°t) possèdent au moins W (p,t) jetons.

Un franchissement d'une transition validée t consiste à supprimer W (p, t) jetons de

chaque place d'entrée, et ajouter W(t,p) jetons à chacune de places de sortie de t.

Alors le franchissement d’une transition dans un marquage M donne un nouveau marquage.

Master 2 académique Modélisation simulation

D'une autre façon on peut dire qu'une transition est franchissable (validée) lorsque chaque
place qui lui est en amont (ou toutes les places d'entrée de la transition) contient un nombre de
jeton plus grand ou égale au poids de l'arc qui la relie à cette transition. Le franchissement
consiste à retirer un nombre de jeton égal au poids de l'arc de chacune des places d'entrée et à
rajouter un nombre de jeton égal au poids de l'arc à chacune des places de sortie de la même
transition voire figure 4.

Figure 4: Evolution d’un réseau de Pétri

Lorsqu’une transition est validée, cela n'implique pas qu'elle sera immédiatement franchie ;
Cela veut dire que les conditions nécessaires à son franchissement sont effectivement réunies.
L’évolution du RdP se fait par le franchissement d’une seule transition à la fois. Quand
plusieurs transitions sont simultanément validées, on ne peut pas savoir dans quel ordre elles
seront effectivement franchies. L’évolution n’est donc pas unique.
Master 2 académique Modélisation simulation

6. Structures fondamentales pour la modélisation des systèmes

Les RdP permettent de modéliser un certain nombre de comportements importants dans
les systèmes : le parallélisme, la synchronisation, le partage de ressources…etc. . Dans
cette section, sont présentées des structures apparaissant dans un réseau de Pétri reproduisant
ce type de comportements.
6.1 Parallélisme
Le parallélisme représente la possibilité que plusieurs processus évoluent simultanément au
sein du même système. On peut provoquer le départ simultané de l’évolution de deux
processus à l’aide d’une transition ayant plusieurs places de sortie. Pour cela, le RdP doit
contenir la structure présentée dans la figure 5, gauche. Le franchissement de la transition
T1 met une marque dans la place P2 (ce qui marque le déclenchement du processus 1) et une
marque dans la place P3 (ce qui marque le déclenchement du processus 2). Il est ensuite
possible de synchroniser l’achèvement des deux processus, voir figure 5, centre. La place
P22 correspond à la fin du processus 1 et la place P23 à la fin du processus 2. Le RdP
évoluera par franchissement de la transition T12. Pour cela, il est nécessaire que les places
P22 et P23 contiennent chacune au moins un jeton, c’est-à-dire que les processus 1 et 2 soient
terminés. Le RdP total est représenté figure 5 droite.

Figure 5: Parallélisme
6.2 Synchronisation Mutuelle
L a synchronisation mutuelle ou rendez-vous permet de synchroniser les opérations de
deux processus. Un exemple est donné dans la figure 6. Le franchissement de la transition
Master 2 académique Modélisation simulation

T7 ne peut se faire que si la place P12 du processus 1 et la place P6 du processus 2

contiennent chacun au moins une marque. Si ce n’est pas le cas, par exemple la place P12 ne
contient pas de marque, le processus 2 est “bloqué” sur la place P6 : il attend que l’évolution
du processus 1 soit telle qu’au moins une marque apparaisse dans la place P12.

Figure 6: Synchronisation mutuelle

6.3 Partage de ressources
C ette structure va modéliser le fait qu’au sein du même système plusieurs processus
partagent une même ressource. Dans la figure 4.7, la marque dans la place P0 représente une
ressource mise en commun entre le processus 1 et le processus 2. Le franchissement de la
transition T17 lors de l’´evolution du processus 1 entraîne la “consommation” de la marque
présente dans la place P0. La ressource que constitue cette marque n’est alors plus disponible
pour l’´evolution du processus 2 puisque le franchissement de la transition T7 n’est plus
possible. Lors de l’´evolution du processus 1, lorsque la transition T18 est franchie, une
marque est alors “redonnée” à la place P0 : la ressource redevient alors disponible pour
l’´evolution des deux processus.

Figure 7: Partage de ressource

Master 2 académique Modélisation simulation

6.4 Séquence
La séquence est une situation dans laquelle une série de transitions doivent obligatoirement se
dérouler l’une après l’autre. Par exemple : écrire un message doit avoir lieu avant envoyer le
message.

Figure8 : la séquence
6.5 le choix
La figure suivante représente le cas du choix :

Figure9 : le choix

6.6 Tampon à capacité

Dans cette situation on peut voire le schéma producteur/consommateur correspond à une
situation o`u l’un des processus produit des ressources nécessaires `a l’autre. On utilise une
place « tampon » pour matérialiser le nombre de ressource produites mais pas encore
consommées. On peut limiter la capacité du tampon pour éviter que le producteur ne «
prenne trop d’avance » sur le consommateur. On ajoute une place « compteur » initialisée à
la capacité désirée du tampon. Chaque ajout au tampon diminue le compteur d’une unité,
chaque retrait l’augmente. Lorsque le compteur est `a zéro le producteur se bloque jusqu’`a
ce que le consommateur ait consommé au moins une ressource du tampon.
Master 2 académique Modélisation simulation

Figure 9 : producteur/consommateur
7. Le graphe de marquage
Le graphe de marquage de R pour le marquage M est composé de :
Sommets tous les marquages Mj atteignables depuis M
Arcs s’il existe une transition t telle que le franchissement du t ramène M1
vers M2 on a un arc de M1 à M2 étiqueté par t.
7.1 Exemple de graphe de marquage
L’ensemble des marquages accessibles, A(R;M0), pour le RdP ci-dessous est: A(R;M0) =
{M0, M1, M2, M3,M4}.
Master 2 académique Modélisation simulation

L’évolution du RdP est représentée ci-dessous avec les marquages représentés sous la forme de
vecteurs colonnes L’évolution du RdP est représentée ci-dessous avec les marquages représentés sous
la forme de vecteurs colonnes.

8. Défnton matricielle des réseaux de Pétri :

Un RdP est un quadruplet (P; T; Pre; Post) ou :

P est un ensemble fini de places

T est un ensemble fini de transitions,
Pré est une application de P × T dans N dite d’incidence avant,
Post est une application de P × T dans N dite d’incidence arriere.
Master 2 académique Modélisation simulation

On utilise également la notation :

C = Post -- Pré
et C est en general appelee matrice d’incidence du reseau de Petri.
Exemple :

9. Séquence de franchissement
Pour caractériser une séquence de franchissements σ, on utilise son image commutative
σ .
Exemple
σ = t1t2 ; T = {t1, t2, t3} ; σ =1
1
0
Master 2 académique Modélisation simulation

Chaque composante de l’image commutative est le nombre d’occurrences de la transition

correspondante dans σ.
Exemple

Soit σ une sequence finie de transitions tirable depuis un marquage M0 d’un reseau R de
matrice d’incidence C. On a le marquage résultat est:

M1 = M0+ C × σ