SED Chap 3

Télécharger au format pdf ou txt
Télécharger au format pdf ou txt
Vous êtes sur la page 1sur 95

Chapitre 3

Les réseaux de Petri


Étude comportementale – Aspect
dynamique
Année Universitaire 2015 / 2016

1
Chapitre III

Formalisation
• L'un des intérêts de ce formalisme, c'est la possibilité de
vérifier formellement des propriétés

• Nécessite le recours à la formalisation (matrice d'incidence,


séquence de franchissement, vecteur caractéristique, équation
d'état)

• Propriétés structurelles (structure du réseau) et/ou


comportementales (évolution du réseau)

M. F. Karoui 2
Chapitre III

Formalisation
Réseau de Petri: R = {P, T, Pre, Post}
• P = ensemble de places (P = {P1, P2, .., Pm} )
• T = ensemble de transitions (T= {T1, T2, .., Tn})

• Pre = PxT → N places précédentes


Pre(p, t) = nombre de jeton nécessaire dans la place p pour le franchissement
de la transition t

• Post = PxT → N places suivantes


Post(p, t) = nombre de jeton produits dans la place p lors du franchissement
de la transition t

⇒ C = Post (Pi, Tj) – Pré (Pi, Tj) matrice d'incidence


(W+) – (W-)
W+ : matrice d’incidence arrière
W- : Matrice d’incidence avant

M. F. Karoui 3
Chapitre III

Formalisation

2
P0
T0

M. F. Karoui 4
Chapitre III

Formalisation

• Exercice T1

– P?
2 7
– T? 5 T2
3
– Pré (Pi, Tj) ? P1 1 P2
– Post (Pi, Tj) ? 6
T3 4
1

M. F. Karoui 5
Chapitre III

Formalisation
Réseau de Petri: R = {P, T, Pre, Post}
=> Représentation matricielle T1

2 7
5 T2
3
P1 1 P2
6
T3 4
1

Pré : Post :

M. F. Karoui 6
Chapitre III

Formalisation
Réseau marqué: N = {R,M}
Le marquage d'un RdP R=(P, T, Pre, Post) est son état.
Formellement, un marquage est une application M:P→N
donnant pour chaque place le nombre de jetons qu'elle contient.
Le marquage initial est généralement noté M0. M0= {1,0}

Notation matricielle:
– Transitions en colonnes
– Places en lignes
– Marquage = vecteur colonne

M. F. Karoui 7
Chapitre III

Formalisation

• Exercice

Notation matricielle
Pré?
Post?
C?
M0?

M. F. Karoui 8
Chapitre III

Formalisation

M. F. Karoui 9
Chapitre III

Formalisation

M. F. Karoui 10
Chapitre III

Formalisation

C=

C=

M. F. Karoui 11
Chapitre III

Formalisation

C=

Une colonne de cette matrice correspond à la modification du


marquage apportée par le franchissement de la transition
correspondante.

Par exemple la première colonne indique que le franchissement


de de la transition T1 consiste à retirer un jeton dans la place P1
et ajouter un jeton ans P2
M. F. Karoui 12
Chapitre III

Formalisation : Propriétés dynamique


Dynamique (sémantique) d'un RdP
– Transition T franchissable
• une transition T est franchissable ssi, pour toute place p,

M(p) > Pre(p, t)

– Franchissement d'une transition t


• Si une transition T est franchissable à partir du marquage M,
alors le nouveau marquage de toute place p est
M'(p) = M(p) - Pre(p, t) + Post(p, t)
= M(p) + C(p, t)
avec C = Post - Pre (matrice d'incidence)

M. F. Karoui 13
Chapitre III

Formalisation : Propriétés dynamique


Dynamique (sémantique) d'un RdP
– Exemple
• T1 est franchissable car

Pré (P1, t1) < M0


• Après le franchissement de T1
M = M0 - Pré(., T1) + Post(., t1)

2 1 1
2 1 0 5 0 1
= 3 - 0 + 0
0 6 4 7 3 0
0 0

2 2 5 5
= - + =
3 0 7 10

M. F. Karoui 14
Chapitre III

Formalisation : Propriétés dynamique

Dynamique (sémantique) d'un RdP


– Exemple

• calcul direct avec la matrice d'incidence


M = M0 + C(., t1)

2 1
3 -1 1
= 3 + 0 = 5
7 -3 -4 10
0

donne (heureusement) le même résultat

M. F. Karoui 15
Chapitre III

Formalisation
• Exercice
– A partir du
marquage initiale ,
calculez les
marquage suivant:
M1 après tir de T1 ,
puis M2 après tir de
T3 puis M3 après tir
de T3 puis M5 après
tir de T2 puis M6
après tir de T1

M. F. Karoui 16
Chapitre III

Formalisation

T1 T2

T3 T3

T1 T2 T3 T4
T2 est une séquence de
transitions
franchissables

M. F. Karoui 17
Chapitre III

Formalisation :propriétés dynamiques


Dynamique (sémantique) d'un RdP : séquence de transitions
Soit un RdP R=(P, T, Pre, Post) de marquage initial M0
Soit t1 t2 ... tn des transitions de T telles que
M0 /t1→ M1 /t2→ M2 … /tn→ Mn
alors, t1 t2 ... tn est appelée séquence de transitions franchissables
(successivement)

De plus
Mn = M + C . VsT
où Vs est le vecteur caractéristique de la séquence de transitions
s = t1 t2 ... tn
tel que Vs(t) donne le nombre d'occurrences de la transition t dans s
On note :
M /s→ Mn
M. F. Karoui 18
Chapitre III

Formalisation :propriétés dynamiques


Equation d'état

Mf = M + C . VsT

Remarque :
s = s1 . s2 => Vs = Vs1 + Vs2
Vs1 = Vs2 => M + C . Vs1T = M + C . Vs2T même si s1≠s2

M. F. Karoui 19
Chapitre III

Formalisation :propriétés dynamiques


Dynamique (sémantique) d'un RdP : séquence
de transitions
Exemple :

T = {T1, T2, T3, T4}


VT2T3T4T1T3 = (1, 1, 2, 1)

M. F. Karoui 20
Chapitre III

Formalisation :propriétés dynamiques


Remarques importantes :
– ATTENTION ! Le vecteur caractéristique ne fait que compter le
nombre d'apparition des transitions. Il ne donne pas, comme la
séquence, l'ordre dans lequel celles-ci ont lieu.

T = {T1, T2, T3} V = (1, 2, 1)

Le vecteur V ci-dessus est le vecteur de comptage de toutes les


séquences de franchissement suivantes :

<T1, T2, T3, T2>, <T3, T1, T2, T2>, <T3, T2, T2, T1>, <T1, T3, T2, T2>,
<T1, T2, T2, T3>, …

M. F. Karoui 21
Chapitre III

Formalisation :propriétés dynamiques


Remarques importantes :
– ATTENTION ! L'équation d'état permet de calculer le marquage atteint
après franchissement d'une séquence de transitions. Elle ne permet pas de
dire que la séquence est franchissable !!
T1 T2 T3 T4
P1 P2 P3 P4 P5

La séquence <T1, T2, T3> est franchissable,


Les séquences <T2, T1, T3>, <T3, T2, T1>, <T2, T3, T1> ne le sont pas !
Elles ont pourtant même vecteur de comptage. L'équation d'état donnera
donc le même résultat pour les quatre.

M. F. Karoui 22
Chapitre III

Formalisation :propriétés dynamiques


Aperçu (incomplet et approximatif) des raisonnements faisables sur un RdP
– Le rôle de l'équation d'état est de matérialiser, en termes de jetons, l'évolution du RdP.
Elle représente l'outil qui va permettre de calculer le résultat du franchissement de
transitions. En tant que tel, elle est nécessaire. Il faut toutefois l'utiliser correctement, en
pas à pas.

Eq. Eq. Eq.


M0 M1 M2 M3
Etat Etat Etat

Pb Pb Pb

L'équation d'état peut signaler un non-franchissement. Une transition est franchissable


s'il y a suffisamment de jetons dans chacune de ses places en entrée. La matrice
d'incidence fournit le nombre de jetons produits par le déclenchement de chaque
transition.

L'équation d'état appliquée à une séquence réduite à une transition fournit le nombre de
jetons qui restent après « exécution » de cette transition.
=> Si ce nombre est négatif, alors la transition n'est pas franchissable.
M. F. Karoui
(Attention : réciproque fausse) 23
Chapitre III

Formalisation :propriétés dynamiques


Aperçu… des raisonnements faisables…
– L'équation d'état peut également servir à autre chose. Il est possible de calculer
le marquage initial nécessaire pour franchir une séquence donnée et arriver à
un marquage donné. Le travail se fait, dans ce cas-là, « à l'envers ».

M0 = Mf - C . VsT P1
P2
Eq. Eq. Eq.
M0 M1 M2 Mf
Etat Etat Etat 2
T1
Pb Pb Pb
P3
P4
– Exemple :
Quel marquage initial pour le marquage final T2
2
Mf= [2, 5, 1, 4, 0] et la séquence <T1, T2, T2> P5

M. F. Karoui 24
Chapitre III

Formalisation :propriétés dynamiques


– Exemple :
Quel marquage initial pour le marquage final P1
P2
Mf= [2, 5, 1, 4, 0] et la séquence <T1, T2, T2>
=> calcul de M2 2
T1

x 2 0 -1 3
P3
y 5 -2 0 5
0 P4
M2 = z = 1 - 1 -1
1 => M2= 2
t 4 0 -1 5
u 0 0 2 -2
T2
2
P5

Impossible :Mf inaccessible par T2

M. F. Karoui 25
Chapitre III

Formalisation :propriétés dynamiques


Aperçu… des raisonnements faisables…
– Autre Exemple :
Quel marquage initial pour le marquage final
Mf= [2, 5, 1, 4, 5] P1
P2
la séquence <T1, T2, T2>
2

T1

P3
P4

T2
2
P5

M. F. Karoui 26
Chapitre III

Formalisation :propriétés dynamiques


=> calcul de M2 Mf= [2, 5, 1, 4, 5]
2 0 -1 3
5 -2 0
0
5 la séquence <T1, T2, T2>
M2 = 1 - 1 -1 = 2
1
4 0 -1 5
5 0 2 3 P1
P2
=> calcul de M1 3 0 -1 4
-2 0 5 2
5 0
M1 = 2 - 1 -1 = 3 T1
1
5 0 -1 6 P3
3 0 2 1 P4

=> calcul de M0
4 0 -1 4 T2
-2 0 7 2
5 1 P5
M0 = 3 - 1 -1 = 2
0
6 0 -1 6
1 0 2 1

M. F. Karoui 27
Chapitre III

Formalisation :propriétés dynamiques


Aperçu… des raisonnements faisables…
– L'équation d'état peut également déterminer le marquage initial
minimal pour franchir une séquence donnée, sans se préoccuper du
marquage final.

M0 + C . VsT > 0

Eq. Eq. Eq.


M0 M1 M2 Mf > 0
Etat Etat Etat

Pb Pb Pb

M. F. Karoui 28
Chapitre III

Formalisation :propriétés dynamiques


Aperçu… des raisonnements faisables…
– Exemple :
Quel marquage initial minimal permettant le franchissement
de la séquence <T1, T2, T2>
P1
P2

2
T1

P3
P4

T2
2
P5

M. F. Karoui 29
Chapitre III

Formalisation :propriétés dynamiques


=> calcul des contraintes sur M1
x 0 -1 0 x 1
y -2 0 0 séquence <T1, T2, T2>
0 y 0
Mf = z + 1 -1 > 0 => z > 1
1
t 0 -1 0 t 1
0 2 0 P1
u u 0
P2
=> calcul des contraintes sur M2
2
x 0 -1 1 x 2 T1
y -2 0 0 y 0
0 P3
M2 = z + 1 -1 > 1 => z > 2
1 P4
t 0 -1 1 t 2
u 0 2 0 u 0
T2
=> calcul des contraintes sur M0 2
P5
x 0 -1 2 x 2
y -2 0 0 y 2
1
M1 = z + 1 -1 > 2 => z > 1
0
t 0 -1 2 t 2
u 0 2 0 u 0
M. F. Karoui 30
Chapitre III

Validation

• Types d'analyse formelle pour les RdP:


– Analyse par énumération
– Analyse structurelle
– Analyse par réduction

• Enumération de tous les états possibles du


système.

M. F. Karoui 31
Chapitre III

Graphe des marquages


Marquage accessible et graphe de marquage
– Marquages accessibles (ou successeurs)
• Un marquage M' est un marquage accessible (successeur de M) s'il
existe une séquence de transitions s tel que
M / s → M'

• L'ensemble des marquages accessibles depuis M est noté A(R,M)

– Graphe des marquages accessibles


• Le graphe des marquages accessibles, noté GA(R,M), est le graphe
ayant comme sommets les marquages de A(R,M) et tel qu'il existe
un arc entre deux sommets M1 et M2 si et seulement si
M1 / t → M2
où t est une transition du RdP

M. F. Karoui 32
Chapitre III

Graphe des marquages

Algorithme de construction du graphe des


marquages : (en français)
• Stocker le premier état issu du marquage initial
• Pour tout état stocké et non traité :
– Pour toute transition sensibilisée : construire l’état
successeur et le stocker s’il est nouveau.
– Si plus de transition tirable: marquer l’état comme
traité.
• Si plus d’état à traiter : fin.

M. F. Karoui 33
Chapitre III

Validation
Exemple : Marquage accessible et graphe de marquage

M. F. Karoui 34
Chapitre III

Graphe des marquages


Exemple ⇒ Graphe de marquage :
Idle1 Idle2
1 (Idle1
0
d1 d2
1 Idle2
f1 f2
Busy1 Res Busy2 0
1 Res)
f1 f2

T= (d1, f1, d2, f2)


0 1
d1 d2
Idle1 -1 1 0 0 (Busy1) 1 0
Busy1 1 -1 0 0 1 0
P= Idle2 C= 0 0 -1 1 0 (Busy2) 1
Busy2 0 0 1 -1 0 0
Res -1 1 -1 1

M. F. Karoui 35
Chapitre III

Graphe des marquages


• Commande de va-et-vient d'un vérin

M. F. Karoui 36
Chapitre III

Graphe des marquages


• Commande de va-et-vient d'un vérin

M. F. Karoui 37
Chapitre III

Graphe des marquages

• Exemple pour un RdP généralisé.

M. F. Karoui 38
Chapitre III

Graphe des marquages


• Exemple pour un graphe non cyclique.
• Rmq: s'il n'y a pas de cycle dans le graphe des marquages,
c'est qu'il y a une "fin", un blocage (deadlock)

P0

T0

P1

T1

M. F. Karoui 39
Chapitre III

Graphe des marquages


Marquage accessible et graphe de marquage

Remarque importante : le graphe des marquage peut être infini


=> dans ce cas, le RdP est non borné

Exemple : (1) —t→ (2) —t→ (3) —t→ (4) —t→ …


2
t

M. F. Karoui 40
Chapitre III

Graphe des marquages

• Exemple pour un graphe borné.

M. F. Karoui 41
Chapitre III

Graphe des marquages

• Exemple pour un graphe non borné

M. F. Karoui 42
Chapitre III

Graphe des marquages


• Exemple pour un graphe non borné (2)
P1

Ta

P3
P2

Tb Tc

P5
P4

Te Td

M. F. Karoui 43
Chapitre III

Graphe de couverture

• Comment traiter les graphes non bornés ?


• Le problème : une augmentation infinie du nb de
jetons dans certaines places.
• Notion de marquage supérieur. Mb > Ma si :
– pour chaque place Pi : ∀i, Mb(Pi) ≥Ma(Pi)
– Il existe une place Pj tel que : ∃j / Mb(Pj) > Ma(Pj)
– Il existe une séquence de transitions allant de Ma à Mb
• Si un GM contient deux marquages dont l'un est
supérieur à l'autre, alors ce graphe est non borné.

M. F. Karoui 44
Chapitre III

Graphe de couverture
• Algorithme de construction du graphe de
couverture(GC) :
– début : idem que GM
– À chaque nouveau marquage trouvé, on vérifie qu'il
n'est pas supérieur à l'un des marquages existant.
– si c'est le cas, on transforme ce marquage en
remplaçant le marquage des places non bornées par ∞.
– on ne cherchera pas les successeurs de ces marquages.
– etc.
• Le graphe de couverture remplace le graphe de
marquage pour les RdP non bornés.

M. F. Karoui 45
Chapitre III

Graphe de couverture

Graphe de couverture ?

M. F. Karoui 46
Chapitre III

Graphe de couverture

M. F. Karoui 47
Chapitre III

Graphe de couverture
P1

Ta
Graphe de couverture ?
P3
P2

Tb Tc

P5
P4

Te Td

M. F. Karoui 48
Chapitre III

Graphe de couverture

P1

Ta

P3
P2

Tb Tc

P5
P4

Te Td

M. F. Karoui 49
Chapitre III

Validation : vérification de propriétés


• Vérification formelle de la structure du réseau: vérification de
propriétés comportementales (générales) indépendantes de la
"signification" du RdP
• Principales propriétés comportementales:
– Bornage des marquages : réseau borné ou sauf(borne=1)
– Utilité des transitions : réseau vivant, ou quasi-vivant
– Sans blocage : pas de verrou mortel (deadlock)
– Possibilité de réinitialisation : réseau réinitialisable ou propre
– Déterminisme
• Vérification formelle de la conformité du réseau: vérification
d'un certain nombre de propriétés spécifiques, dépendantes du
cahier des charges.
M. F. Karoui 50
Chapitre III

Analyse par énumération


• L'analyse par énumération permet la vérification de propriétés
sur l'ensemble des états possibles du système :
– Construction du graphe (GM ou GC)
– Parcours du graphe
– Vérification pour chacun des marquages si la propriété est
vérifiée

• Rmq1: le GM permet la vérification de toutes les propriétés


comportementales des RdP.
• Rmq2: Le GC ne permet que de vérifier le bornage et la
quasi-vivacité.
M. F. Karoui 51
Chapitre III

Vérification de propriétés
Pour un marquage initial donné:
• réseau borné: toutes ses places sont bornées
• place bornée: nombre de jetons toujous inférieur à une borne k.
∀M, ∀p : M(p) ≤k
• réseau sauf (binaire) : k=1.
• Exemple : modélisation d'un stock à capacité limitée.
• Exemple réseau sauf : modélisation d'un fonctionnement de
type automatisme logique (MEF).

M. F. Karoui 52
Chapitre III

Vérification de propriétés
• Exemple de réseaux borné et sauf

M. F. Karoui 53
Chapitre III

Vérification de propriétés
• Réseau vivant: chacune de ses transitions est vivante.
• Transition Ti vivante: pour tout marquage M, il existe une séquence de
franchissement (transitions) qui permettra de franchir Ti.

séquence de franchissement
permettant le tir de Ta à
partir de M3

M. F. Karoui 54
Chapitre III

Vérification de propriétés

• Le RDP suivant est il vivant ?

M. F. Karoui 55
Chapitre III

Vérification de propriétés

• Réseaux non vivant : transition T3 non vivante


• Rmq: visible dans le GM : cycle infini entre M1 et M2 qui ne contient pas T3
M. F. Karoui 56
Chapitre III

Vérification de propriétés
• Une transition Tj est quasi-vivante si il existe au moins une
séquence de franchissement contenant Tj à partir de M0
Ex : dans l'exemple précédent, T3 est quasi-vivante.
• Un blocage (deadlock) est un marquage à partir duquel plus
aucune transition n'est tirable
• Remarque :
– Vivant ⊂ Quasi vivant
– Blocage⊂ Non vivant

M. F. Karoui 57
Chapitre III

Vérification de propriétés
• Réseau réinitialisable ou propre: pour chaque marquage, il
existe une séquence de franchissement permettant de revenir
dans l'état initial

M. F. Karoui 58
Chapitre III

Vérification de propriétés
• Exemple de réseau non réinitialisable:

M. F. Karoui 59
Chapitre III

Vérification de propriétés
• "Un système déterministe est un système dans lequel chaque
état n'a qu'un seul successeur possible".
• Application aux RdP: un RdP est déterministe s'il n'existe pas
de conflit effectif.
• Conflit structurel: le jeton d'une place est partagé entre deux
transitions. (indépendant du marquage)

• Conflit effectif: conflit structurel ET le marquage ne permet


pas le tir des deux transitions.

M. F. Karoui 60
Chapitre III

Exercice: producteur/consommateur
Quand sa "production" est finie (production d'une seule pièce à la
fois), un producteur dépose la pièce produite dans un stock, s'il
y a de la place libre dans ce stock dont la capacité est de 3
unités. Dès qu'il a pu faire le dépôt, il commence à produire
une autre pièce. Un consommateur, dès qu'il a fini de
"consommer" (une seule pièce à la fois), prélève une pièce
dans le stock s'il n'est pas vide.
Représenter le fonctionnement de ce système par un RdP avec un
marquage initial correspondant à la figure.
Quels sont les invariants de marquage de ce système, et quelles
sont leurs significations ?

M. F. Karoui 61
Chapitre III

Correction: producteur/consommateur

M. F. Karoui 62
Chapitre III

Exercice: Gestion de cabine


1) On considère le protocole suivant de gestion des cabines et des paniers
d’une piscine. A l’entrée, un client qui a trouvé une cabine libre y entre et se
change en posant ses vêtements dans la cabine. Il demande ensuite un panier
qu’il remplit pour libérer la cabine. Après baignade le client rentre dans une
cabine avec son panier, le vide et le libère. Ensuite il se rhabille et libère la
cabine. Soit Nc le nombre de cabines et Np le nombre de paniers. Modéliser
ce protocole avec Nc = 3 et Np = 5. Le nombre de clients à la baignade
(c'est-à-dire après déshabillage et avant rhabillage) est-il borné ? Le RdP
est-il borné ? Montrer qu'il y a un état de blocage. Y-a-t-il blocage pour
toutes valeurs de Nc et de Np ?
2) Définir un protocole tel qu'il n'y ait pas de blocage, et donner le RdP
correspondant.
3) Modifier le RdP du 2) pour modéliser le nombre des clients qui attendent
une cabine pour entrer à la piscine.

M. F. Karoui 63
Chapitre III

Correction:
Gestion de cabine

M. F. Karoui 64
Chapitre III

Correction:
Gestion de cabine

M. F. Karoui 65
Chapitre III

Exercice: Boules de billard


On considère deux boules de billard, A et B qui se déplacent sur une même
ligne parallèle à une des bandes. Chaque boule peut avoir trois états : en
mouvement vers la gauche, vers la droite, ou arrêtée. On demande de
modéliser le comportement de ces boules par un RdP en supposant que :
a) une boule qui heurte une bande repart dans l'autre sens à la même vitesse,
b) si les deux boules sont en mouvement (elles sont supposées avoir la même
vitesse) elles repartent chacune en sens inverse quand elles se heurtent.
c) si une boule est arrêtée et heurtée par l'autre, la première se met en
mouvement et l'autre s'arrête (on suppose qu'il n'y a pas de ralentissement et
arrêt par frottement). On commentera plusieurs états initiaux possibles.

Boule A Boule B

M. F. Karoui 66
Chapitre III

Correction: Boules de billard

M. F. Karoui 67
Chapitre III

Analyse structurelle

• L'analyse par énumération n'est pas toujours possible


à cause de sa complexité, même après réductions.
• L'analyse structurelle est indépendante du marquage
initial et dépend directement de la structure du RdP:
pas de construction du GM.
• Algèbre linéaire

M. F. Karoui 68
Chapitre III

Composantes répétitives

• Equation fondamentale : Mf = M + C . VsT


• S’il existe C . VsT=0 alors Mf = M
(L'ensemble des transitions franchissables de Vs
ramène au vecteur initial).
• Définition : on appelle composante stationnaire
(=invariant de transitions) l'ensemble des transitions de
S telles que : C . VsT=0
• Propriété: S’il existe toujours une transition de cet
ensemble tirable alors le RDP est vivant.

M. F. Karoui 69
Chapitre III

Composantes répétitives
2 invariants de transitions:
• 1er invariant :
• CommandeX
• Xfabriqué
• Xvendu
• 2ème invariant :
• CommandeY
• Yfabriqué
• Yvendu
• Toutes les transitions
appartiennent à un invariant.
⇒ Le réseau est vivant !

M. F. Karoui 70
Chapitre III

Composantes non stationnaires

• Equation fondamentale : Mf = M + C . VsT


• S’il existe C . VsT>0 alors Mf > M
⇒Réseau non borné
• Définition : on appelle composante non
stationnaire l'ensemble des transitions de S
telles que : C . VsT>0

M. F. Karoui 71
Chapitre III

Composantes non stationnaires

• S={T0,T1}
• Vs=[1 1]
• C. VsT>0
• S est une
composante non
stationnaire
• Le RDP est non
borné
M. F. Karoui 72
Chapitre III

Composantes conservatives

• Définition : Vp= Vecteur colonne de pondération des places

• K=VpT.Mi représente une combinaison linéaire des places

• Equation d’état : VpT.Mf = VpT.M + VpT.C . VsT

• S’il existe Vp tel que: VpT.C =0 alors : VpT.Mf = VpT.M

⇒ L'ensemble des places contient toujours le même nb de jetons.

• Définition : on appelle composantes conservatives ( invariants de


places) les solutions en Vp de l'équation :

VpT.C =0

M. F. Karoui 73
Chapitre III

Composantes conservatives

1 invariant de places:
• Attente
• FabricationX
• FabricationY
• XAVendre
• YAVendre
Toutes les places sont couvertes
par des p-invariants.
⇒Le réseau est borné

M. F. Karoui 74
Chapitre III

Composantes conservatives
Exemples d'interprétations:
• Si une composante conservative est telle que K0 = 0 :
– aucune de ces places n’est marquée dans M0.
– elles restent vides quelque soit le marquage.
⇒C'est anormal
• Si une composante conservative est telle que K0 = 1 :
– il y a toujours une de ces places marquées d’un jeton, et pas plus
d'un jeton.
⇒L'interprétation de ces places doit donc être booléenne
• Si un RdP est tel que toutes ses places appartiennent à des
invariants de place de constantes = 1, il est sauf !
⇒L'interprétation du réseau doit donc être complètement
booléenne

M. F. Karoui 75
Chapitre III

Composantes conservatives
Exemple P1 -1 1 0 0

P2 1 -1 0 0

P1 P3 P= P3 C= 0 0 -1 1

P4 0 0 1 -1

P5 -1 1 -1 1

d1 d2 T= (d1, f1, d2, f2)

P2 P5 P4

f1 f2

⇒Composantes conservatrices positives ?

M. F. Karoui 76
Chapitre III

Composantes conservatives
VpT.C =0 VpT.C => M2 – M1 – M5 = 0

M1 – M2 + M5 = 0
VpT = (M1, M2, M3, M4, M5)
M4 – M3 – M5 = 0

M3 – M4 + M5 =0
-1 1 0 0
VpT = (M1, M2, M3, M4, M5)
1 -1 0 0
C= 0 0 -1 1 (1 , 1 , 0 , 0 , 0 )
0 0 1 -1 (0 , 1 , 0 , 0 , 1 )
-1 1 -1 1 (0 , 0 , 1 , 1 , 0 )
(0 , 0 , 0 , 1 , 1 )
(0 , 1 , 0 , 1 , 1 )

M. F. Karoui 77
Chapitre III

Composantes conservatives
P1 P3
-1 1 0 0
1
1 -1 0 0
M0= 0
d1 d2 C= 0 0 -1 1
1
P2 P5 P4 0 0 1 -1
0
-1 1 -1 1
f1 f2 1

1 (P1 0 0
1 + P2) 0 1 (P2
V1= 0 V2= 1 (P3 V3= 0 Il est toujours
0 1 + P4) 1 + P4 possible de
+ P5) trouver
0 0 1
d’autres
•V1’.M0=1 et V1’.C= 0 =>V1’.Mi=1 => Mi(P1)+Mi(P2)=1 invariant s en
additionnant
•V2’.M0=1 et V2’.C= 0 =>V2’.Mi=1 => Mi(P3)+Mi(P4)=1 les invariants
•V3’.M0=1 et V3’.C= 0 =>V3’.Mi=1 => Mi(P2)+Mi(P4)+Mi(P5)=1 minimaux

M. F. Karoui 78
Chapitre III

Composantes conservatives
P3
c2
P1
P4
c1
P6 f2
P2
P5
f1
t2
P7

• Invariants de marquage minimaux?

M. F. Karoui 79
Chapitre III

Composantes conservatives
P3
c2 P’ = {P1, P2 } ⇒ m1 + m2 = 1
P1
P4 P’’ = {P3, P4, P5} ⇒ m3 + m4 + m5 = 1
c1
P6 f2 P ’’’ = {P6, P7} ⇒ m6 + m7 = 1
P2
P5
f1
t2
P7

• Les ensembles P’, P’’, P ’’’, sont des composantes conservatives. A partir de cet
ensemble de relations, nous pouvons construite l’invariant suivant: m1 + m2 + m3+
m4 + m5+ m6 + m7 = 3
• Dans cet invariant nous pouvons trouver toutes les places du RdP
• RDP conservatif
M. F. Karoui 80
Chapitre III

Analyse Globale
•RDP A non bloqué
•RDP B non bloqué
•RDP A et RDP B bloqués

• L'analyse des "sous-RdP" pris séparément est correcte.


• Mais leur interaction est bloquantes !!
• ⇒Nécessité d'une analyse globale

M. F. Karoui 81
Chapitre III

Transformation des RDP


• Graphe des marquages : vérification de propriétés de façon
exhaustive.
• Problème = complexité du GM pour les systèmes complexes.

• Solution : réduction du RdP grâce à des transformations


conservant les propriétés comportementales.

• Inconvénient : pas de conservation de la signification physique


du RdP=> difficile de remonter à la cause de l'erreur lorsqu'il y
en a.

⇒C'est l'Analyse par réduction

M. F. Karoui 82
Chapitre III

Transformation de Boussin: R1

• Suppression d'une transition isolée.

M. F. Karoui 83
Chapitre III

Transformation de Boussin: R2

• Suppression d'une place isolée.

M. F. Karoui 84
Chapitre III

Transformation de Boussin: R3

• Suppression d'une transition isolée bouclée.

M. F. Karoui 85
Chapitre III

Transformation de Boussin: R4

• Suppression d'une place isolée bouclée.

M. F. Karoui 86
Chapitre III

Transformation de Boussin: R5

• Fusion de plusieurs transitions isolées

M. F. Karoui 87
Chapitre III

Transformation de Boussin: R6

• Fusion de plusieurs places isolées

M. F. Karoui 88
Chapitre III

Transformations simples
Notion de résidu :
• RESIDU = RdP sur lequel on ne peut plus appliquer de
transformation.
• Il n’est pas unique. Il dépend de l’ordre des transformations.

M. F. Karoui 89
Chapitre III

Transformations simples

M. F. Karoui 90
Chapitre III

Exercice

Après Réduction

M. F. Karoui 91
Chapitre III

Exercice

Après Réduction

M. F. Karoui 92
Chapitre III

Exercice

Après Réduction

M. F. Karoui 93
Chapitre III

Exercice

Après Réduction

M. F. Karoui 94
Chapitre III

Exercice

Après Réduction

M. F. Karoui 95

Vous aimerez peut-être aussi