Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Leçon 16 Introduction aux Réseaux de PETRI Objectif : A l'issue de la leçon l'é

Leçon 16 Introduction aux Réseaux de PETRI Objectif : A l'issue de la leçon l'étudiant doit être capable : SARA JEBBOR Leçon 16 : Introduction aux Réseaux de PETRI SOMMAIRE SARA JEBBOR Page 3 Leçon 16 : Introduction aux Réseaux de PETRI Introduction En 1964 « Carl Adam Pétri » a définit les réseaux qui portent depuis son nom. Le formalisme des réseaux de Pétri est un outil permettant l'étude de systèmes dynamiques et à évènements discrets. Il permet d'obtenir une représentation graphique (mathématique) modélisant le système. L'analyse de cette représentation (réseau de Pétri) peut révéler des caractéristiques importantes du système concernant sa structure et son comportement dynamique. Les Caractéristiques principales des RdP sont :  Distribution des états et des changements d’états dans le réseau.  Dépendance et indépendance d’ensembles d’événements représentées explicitement (relations de causalité).  Représentation à différents niveaux d’abstraction (i.e. détaillés comme abstraits).  Vérification des propriétés possibles car basées sur un formalisme mathématique rigoureux.  Modélisation simulable.  Représentation graphique. Notions de Base Définition d'un RdP Un RdP est un graphe composé de 2 types de nœuds : - Les places (Pi) qui permettent de décrire les états du système modélisé. L'ensemble de ces places est noté P = {P1, P2, ...}. - Les transitions (Ti) qui représentent les changements d'états. L'ensemble de ces transitions est noté T = {T1, T2, ...}. Les places et transitions sont reliées par des arcs orientés. On dira qu’un RdP est un graphe biparti orienté. Places, transitions et arcs. Eléments Définition Représentation Place Il s’agit d’une condition, un prédicat logique d'un état du système. Elle est soit vraie, soit fausse. Une place est représentée par un cercle. P Transition Il s’agit des événements qui sont des actions se déroulant dans le système. Le déclenchement d'un événement dépend de l'état T SARA JEBBOR Page 4 Leçon 16 : Introduction aux Réseaux de PETRI du système. Un état du système peut être décrit comme un ensemble de conditions. Les conditions nécessaires au déclenchement d'un événement sont les pré- conditions de l'événement. Une transition est représentée par un trait. Arc _ Un arc reliant une place à une transition : Un arc reliant une transition à une place : Marquage Chaque place contient un nombre entier positif ou nul de marques ou jetons. Le nombre de marque contenu dans une place Pi sera noté soit M(Pi) soit mi. Le marquage du réseau à l'instant i, Mi est défini par le vecteur de ces marquages mi : Mi = (m1, m2, …, mn). Il s’agit d’un vecteur colonne de dimension le nombre de places dans le réseau. Le marquage dit initial décrit l'état initial du système modélisé (M0). 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 ; – P∩T = l’ensemble vide ; – 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. Q définit la structure du RdP. Le marquage à un instant donné définit la valeur des variables d’´état du RdP à un instant donné. SARA JEBBOR Page 5 Leçon 16 : Introduction aux Réseaux de PETRI Exemple 1 : Exemple 2 : Exemple 3 : SARA JEBBOR Page 6 Leçon 16 : Introduction aux Réseaux de PETRI Remarque : Le marquage à un instant donné définit l'état du RdP, ou plus précisément l'état du système décrit par le RdP. L'évolution de cet état correspond donc à l'évolution du marquage (par franchissement de transitions). Par abus de langage, nous appellerons des RdP marqués (Rdp) et les Rdp non marqués. A tout marquage accessible à partir du marquage initial par franchissement d'une séquence de transitions correspond un état du système. Franchissement d'une transition Une transition est franchissable (ou validée) lorsque toutes les places qui lui sont en amont (ou toutes les places d'entrée de la transition) contiennent au moins un jeton ou bien le nombre de jetons exigé par une condition de franchissement. Exemple 1 : Cas1 Cas2 Cas2 après franchissement T2 ne peut pas être franchie car P2 ne contient aucun jeton. Le franchissement consiste à retirer un jeton de chacune des places d'entrée et à rajouter un jeton à chacune des places de sortie de la même transition. Le franchissement de T1 consiste à enlever un jeton de P1 et un jeton de P2 et à rajouter un jeton dans P3 et un jeton dans P4. Exemple 2 : SARA JEBBOR Page 7 Leçon 16 : Introduction aux Réseaux de PETRI Cas3 Cas3 après franchissement Le franchissement de T1 consiste à enlever un jeton de P1 et à ajouter un jeton à chacune des places P2, P3 et P4. Remarque : Une transition franchissable n'est pas forcément immédiatement franchie. Exemple 3 : Transition source Une transition sans place d'entrée est toujours franchissable : c'est une transition source. Le franchissement d'une transition source consiste à rajouter un jeton à chacune de ces places de sortie. Exemple 4 : Transition puits Une transition sans place de sortie est une transition puits. SARA JEBBOR Page 8 Leçon 16 : Introduction aux Réseaux de PETRI Le franchissement d'une transition puits consiste à retirer un jeton de chacune de ses places d'entrée. Séquence de franchissement Une séquence de franchissement S est une suite de transitions Ti, Tj…Tk qui peuvent être franchies successivement à partir d'un marquage donné. Une seule transition peut être franchie à la fois. On note alors : Mi[S-> Mj ou Mi[S > Mj ou Mi S Mj : à partir du marquage Mi, le franchissement de la séquence S aboutit au marquage Mj. Exemple : Séquence de franchissement On a deux séquences de franchissement T1T2 et T1T3, donc deux marquage se présentent : M1 pour la séquence T1T2 et M2 pour la séquence T1T3. M0[T1T2->M1 et M0[T1T3->M2 avec M1= [0010]T et M2= [0001]T Couverture Un marquage Mk couvre un marquage Ml si, pour chaque place, le nombre de marques de Mk est supérieur ou égal au nombre de marques de Ml : Pour tout i Mk(Pi) ≥ Ml(Pi) La couverture est stricte si de plus : il existe m tel que Mk(Pm) > Ml(Pm). 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. Si M0’ ≥ M0 alors L(Q,M0) est inclus dans L(Q,M0’). Marquages accessibles SARA JEBBOR Page 9 Leçon 16 : Introduction aux Réseaux de PETRI L'ensemble des marquages accessibles *M0 est l'ensemble Mi des marquages qui peuvent être atteint par le franchissement d'une séquence S à partir du marquage initial M0, ce dernier est bien inclue dans cet ensemble : *M0 = {Mi tel que Mi[S-> Mj}  Pour un RdP donné, à partir d'un marquage initial M0, un marquage Mq est dit accessible si et seulement s’il existe S tel que : M0[S -> Mq.  On dit qu'un marquage M1 couvre M2 (on note M1 ≥ M2) si et seulement si M1(Pi) ≥ M2(Pi) pour toute place Pi.  On dit qu'un marquage M1 couvre strictement M2 (on note M1 > M2) si et seulement si M1≥ M2 et il existe au moins une place Pi telle que M1(Pi) > M2(Pi). Ou bien, si et seulement si M1 couvre M2 et M1 différent de M2. Exemple : *M0 = {M0, M1, M2, M3} avec M0 = [1000]T ; M1 = [0100]T ; M2 = [0010]T et M3 = [0001]T Remarque : une séquence peut comporter une seule transition franchissable. Graphe de marquages On utilise le graphe de marquages quand le nombre de marquages accessibles est fini. Pour l’exemple précèdent on a : SARA JEBBOR Page 10 Leçon 16 : Introduction aux Réseaux de PETRI RdP autonome et non autonome Un RdP autonome décrit le fonctionnement d'un système dont les instants de franchissement ne sont pas connus ou indiqués. Exemple : RdP autonome Le moment de passage de l'été à l'automne est inconnu. Un RdP non autonome décrit le fonctionnement d'un système dont l'évolution est conditionnée par des événements externes ou par le temps. Un RdP non autonome est synchronisé et/ou temporisé. RdP Particuliers Graphe d'état (Graphe de transitions) SARA JEBBOR Page 11 Leçon 16 : Introduction aux Réseaux de PETRI C'est une représentation graphique des possibilités d'évolution du RdP. Elle est obtenue en partant du marquage initial et en étudiant à chaque marquage obtenu Mi après le franchissement d’une transition Tj les différentes possibilités d’évolution du RdP. Ceci correspond aux différentes transitions validées par le marquage Mi. Un réseau de Pétri non marqué est un graphe d'état si et seulement si toute transition a exactement une seule place d'entrée et une seule place de sortie. Exemple : Chacune des transitions T1, T2, T3, T4 et T5 possède uploads/Ingenierie_Lourd/ introduction-aux-rdp.pdf