Modélisation par Réseaux de Pétri
• Un réseau de Petri est un outil graphique et mathématique permettant de
modéliser et de vérifier le comportement dynamique des systèmes à événements
discrets comme les systèmes manufacturiers, les systèmes de télécommunications
et les réseaux de transport.
• En général, Les RDP sont adaptés a la modélisation des systèmes a
évolution parallèle asynchrones
Un Réseau de Pétri (RdP) est un graphe orienté comprenant deux types de sommets :
• les places (correspond à une variable d’état )
• les transitions (correspond à un événement et/ou une action )
• Les arcs peuvent être pondérés. Dans le cas ou le poids de tous les arcs sont égaux à 1, le
RDP est dit ordinaire.
• Une place contient un certain nombre de marques (jetons) qui indique la valeur de la
variable d’état correspondante.
• La distribution des jetons dans les places donne un état du RDP (et donc du système).
Éléments de modélisation
1. Parallélisme 2. Synchronisation 3. Exclusion Mutuelle
2.
Exemples
1. Lancements de tâches parallèles (RDV)
2. Synchronisation de deux processus (P1 doit passer avant P2)
3. Partage de ressources (en nombre limite)
Définition: on appelle Réseau de pétri non marqué le quadruplet Q=<P,T,I,O> où:
P est un ensemble fini non vide de places
T est un ensemble fini non vide de transitions
PT=
I(Ti) est l’ensemble des places qui sont en entrée de la transition i.
O(Ti) est l’ensemble des places qui sont en sortie de la transition i.
• On appelle Réseau de pétri marqué R=<Q,M0> où M0 est le marquage initial
Evolution d’un RdP
• Lorsque qu’il y a un poids n sur l’arc qui part d’une place Pi vers une transition Tj, cela
signifie que la transition est franchissable s’il y a au moins n marques dans la place Pi.
• Lors du franchissement de Tj, on retirera n marques à la place Pi. S’il y a un poids m sur
l’arc qui part de la transition Tj vers la place Pk, lors du franchissement de Tj, on
ajoutera m jetons dans la place Pk.
Le marquage d’un Réseau de Pétri à un instant donné est un vecteur colonne dont la
valeur de la ième composante est le nombre de marques dans la place Pi à cet instant.
Le passage du marquage Mk au marquage Ml par franchissement de la transition Tj est noté
: Mk|Tj > Ml.
Le nombre de marques dans la place Pi pour le marquage Mk est noté Mk(Pi).
A partir d’un même marquage, il peut être possible de franchir plusieurs transitions,
menant ainsi à des marquages différents. L’ensemble des marquages accessibles à partir
du marquage M0 (le marquage initial) est noté *M0.
Une séquence de franchissement est une suite de transitions qui sont successivement
franchies pour passer d’un marquage à un autre.
Un marquage Mk couvre un marquage Ml (noté: Mk≥ Ml) si, pour chaque place, le
nombre de marques de Mk est supérieur ou égal au nombre de marques de Ml :
Propriété. Pour un Réseau de Pétri non marqué Q, soit L(Q,M0) l’ensemble des
séquences de franchissement à partir du marquage initial M0.
[Link]étés d’un RDP
2.1 Réseau de Pétri borné et Réseau sauf
• Une place Pi est bornée pour un marquage initial M0 si pour tout
marquage accessible à partir de M0, le nombre de marques dans Pi
reste borné.
• Elle est dite k-bornée si le nombre de marques dans Pi est toujours
inférieur ou égal à k.
• Un RdP marqué est k-borné si toutes ses places sont k-bornées.
• Un RdP marqué est sauf ou binaire pour un marquage initial M0 s’il
est 1-borné.
Propriété. Si un RdP marqué n’est pas borné pour le marquage initial
M0 alors il n’est pas borné pour le marquage initial
2.2 Une transition Tj est vivante pour un marquage initial M0 si pour
tout marquage accessible M k, il existe une séquence de
franchissements à partir de Mk contenant Tj :
2.3 Un RdP marqué est vivant pour un marquage initial M0 si toutes
ses transitions sont vivantes pour ce marquage initial.
2.4 Un RdP est dit conforme s’il est sauf et vivant.
2.5 Une transition Tj est quasi vivante pour un marquage initial M0
s’il existe une séquence de franchissements à partir de M 0
contenant Tj :
2.6 Un RdP marqué est quasi vivant pour un marquage initial M0 si
toutes ses transitions sont quasi vivantes pour ce marquage initial.
2.7 Un blocage (ou état puits) est un marquage pour lequel aucune
transition n’est validée.
2.8 Un RdP marqué est dit sans blocage pour un marquage initial M0
si aucun marquage accessible n’est un blocage.
Définition. Un RdP marqué a un état d’accueil Ma pour un marquage
initial M0 si:
Propriétés. Soit un Réseau de Pétri <Q,M0> présentant un état
d’accueil Ma.
A. Il est sans blocage si et seulement s’il existe une transition
franchissable à partir du marquage d’accueil Ma.
B. Une transition est vivante pour < Q ,M0 > si et seulement si elle est
quasi vivante pour <Q,Ma>.
2.9 Un RdP est réinitialisable pour un marquage initial M0 si M0 est un
état d’accueil.
2.10 Deux transitions t1 et t2 sont dites en conflit structurel si et
seulement si elles ont au moins une place d’entrée en commun
2.11 Un conflit effectif est l’existence d’un conflit structurel et d’un
marquage M tels que le nombre de marques dans la place Pi est
strictement inférieur à la somme des poids des transitions de sortie
de Pi validées par le marquage M.
Remarque. Les propriétés précédentes dépendent du marquage initial.
3. Analyse d'un RDP par graphe de marquage
La façon la plus simple est de construire le graphe de marquages
accessibles s'il est fini, dans le cas contraire on construit le graphe de
recouvrement.
Graphe de recouvrement
• 1. Marquer la racine M0 (marquage initial).
• 2. Tant qu'il existe un nouveau marquage:
• a) Sélectionner un nouveau marquage M
• b) S'il n y a aucune transition tirable par M, marquer M
deadend.
• c) Pour toutes les transitions franchissables par M, trouver un
marquage accessible immédiatement de M. Q', la valeur de M', est
définie comme suit:
S'il existe sur le chemin M0---->M' un marquage M'' de valeur
Q''Q' alors pour toutes place p tel que Q''(p)<Q''(p) on a
Q'(p):=
Soit a une valeur entière:
1. a< 2. <= 3. +a= 4. -a=
Remarques
• On n'ajoute que de nouveaux marquage au graphe de recouvrement.
• Le graphe de recouvrement est toujours fini.
• Un RDP est k-borné si le symbole n'apparait pas dans le graphe de
recouvrement. La borne k est donnée par le nombre de jetons le plus
grand du graphe.
• Une transition t est non vivante ssi elle n`apparait pas dans le graphe
de recouvrement
• Si chaque sommet du graphe est sur un circuit orienté qui contient le
marquage initial, alors le RDP est réversible.
• S'il y a des marquages deadend dans le graphe alors il y a des
blocages dans le système modélisé.
Exemple
La séquence de transitions: t1t3t4t4 est tirable selon le graphe de
recouvrement mais ne l'est pas sur le RDP donc on ne peut pas
décider de la propriété de vivacité avec le graphe de recouvrement.
4. Invariants
4.1. Composantes conservatives:
Soit R un Réseau de Pétri et P l’ensemble de ses places.
On a un invariant de marquage s’il existe un ensemble de places
et un vecteur d’entiers naturels appelé vecteur de pondérations q tels que
P’ est appelé composante conservative.
Un RdP est conservatif si et seulement si P’ = P.
Remarque. La propriété “composante conservative” est indépendante du
marquage initial M0. Par contre, la valeur de la constante dépend de
M0 .
4.2 Composante répétitive
• On appelle séquence répétitive stationnaire, une séquence de
franchissements S telle que
• La séquence est dite complète si elle contient toutes les transitions
du RdP.
• On appelle séquence répétitive croissante, une séquence de
franchissements S telle que
• On appelle séquence répétitive décroissante, une séquence de
franchissements S telle que
• On appelle composante répétitive l’ensemble T0 des transitions de
T apparaissant dans la séquence S.
• Le RdP est dit répétitif si T = T0.
Propriété . Si S est une séquence répétitive pour le marquage initial
M0 alors c’est aussi une séquence répétitive pour le marquage
initial
• Une séquence de transition S1 est un préfixe de S2 s’il existe une
séquence S3 telle que: S1S3=S2.
• Une séquence répétitive minimale est une séquence répétitive telle
qu’aucun de ses préfixe stricts (de longueur non nulle) n’est une
séquence répétitive.
5. Etude des propriétés des Réseaux de Pétri par algèbre linéaire
5.1 Structure
Un RdP ordinaire non marqué est un quadruplet Q =< P ,T, Pre, Post >:
P={P1,…,Pn} un ensemble fini non vide de places.
T={T1,…,Tm} un ensemble fini non vide de transitions.
Pré : P×T → N est l’application d’incidence avant telle que :
pré(Pi,Tj)= 0 s’il n’existe pas un arc de Pi à Tj
pré(Pi,Tj)=wij de l’arc reliant Pi à Tj
Post : P×T → N est l’application d’incidence arrière telle que :
post(Pi,Tj)= 0 s’il n’existe pas un arc de Tj à Pi
post(Pi,Tj)=wij de l’arc reliant Tj à Pi
• Ensemble des places d’entrée de la transition tj:
0T ={p P/pre(p ,t )>0}
j i i j
• Ensemble des places de sortie de la transitionTj:
T0j={piP/post(pi,tj)>0}
• Ensemble des transitions d’entrée de la place Pi:
0P ={t T/post(p ,t )>0}
i j i j
• Ensemble des places d’entrée de la place Pi:
P0i={tjP/pre(pi,Tj)>0}
•La matrice d’incidence avant est associée à l’application Pre, elle est
définie par: W-=[w-ij] avec w-ij=pre(pi,tj)
• La matrice d’incidence arrière est associée à l’application Post, elle
est définie par: W+=[w+ij] avec w+ij=post(pi,tj)
La matrice d’incidence W du RDP est définie par : W=W+-W-
5.2 Marquage et évolution
soit <Q,M0> un rdp marqué
Une transition tj est franchissable si pi0tj, M(pi)>=pre(pi,tj).
Apres franchissement, on obtient un nouveau marquage M’ donné par:
pi P, M’(pi)=M(pi)-pre(pi,tj)+post(pi,tj).
Le vecteur caractéristique d’une séquence de franchissement S, notée
v(s), est le vecteur de Nm tel que le jeme élément de v(s) est le
nombre de franchissements de la transition tj dans la séquence S.
Equation fondamentale: Si Mk\S>ML Alors ML=Mk+W.v(s)
Remarques.
v(ss’)=v(s)+v(s’)
v(s) est un vecteur caractéristique possible s’il lui correspond une
séquence de franchissement possible.
5.3 Pondération des places et invariants de marquage
A. Pondérations
Soit un vecteur ft=[q1,…,qn]Nn la composante qi est le poids de Pi
Soit P(f) l’ensemble de places pi tel que qi≠0.
Soit S une séquence franchissable à partir de M0. M0\S>Mk
[Link]-fT.M0= fTW.v(s) correspond à un accroissement pondéré du
nombre de jetons.
Propriété: Le RDP est structurellement borné ssi f>0, ftW≤0
Remarque: un RdP est structurellement borné si le réseau est borné
quelque soit le marquage initial.
B. Invariant de marquage
Si fTW=0 alors, d’après l’équation
fTMk-fTM0=fTW.v(s)
Mk M0, fTMk=fTM0
On a donc qiM(Pi)=constante. P(f) est donc une composante
conservative. On peut donc calculer les composantes conservatives en
cherchant f≠0 tel que fT .W=0.
Propriété: toutes les places pi de P(f) sont bornées: M(Pi)≤ft.M0/qi
Le vecteur f≠0 tel que fT .W=0 est appelé p-semi flot.
Propriétés. soit f et f’ deux semi flots et αN et βN
α.f+β.f’ est un p-semi flot avec: P(α.f+β.f’)=P(α.f)P(β.f’)
Si ff’ alors f-f’ est un p-semi flot.
5.4 Composantes répétitive
T(v(s)) est l’ensemble des transitions qui apparaissent dans la séquence
de franchissement S de vecteur caractéristique v(s).
Propriété. un ensemble D de transitions est une composante répétitive
stationnaire si et seulement s’il existe une séquence de franchissement
S telle que T(v(s)) =D et W.v(s)=0.
D est une composante répétitive croissante si W.v(s)>0
On appelle T-semi flot, tout vecteur v(s) tel que W.v(s)=0