Remerciez-le!

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

Modélisation des Systèmes à Evénements Discrets y Réseaux de Pétri TELECOM Nanc

Modélisation des Systèmes à Evénements Discrets y Réseaux de Pétri TELECOM Nancy 1ère Année Vincent Bombardier (MdC 61ème Section) Centre de Recherche en Automatique de Nancy -UMR CNRS 7039- Vincent Bombardier Jeudi 6 février 2014 Département: Ingénierie des Systèmes Eco-Technique Projet Systèmes Intelligents Ambiants Plan du cours 1. Généralités 2. Formalisme de base Définition Représentation matricielle Marquage Définition, Représentation matricielle, Marquage, Graphe associé 3 Fonctionnement d’un RdP 3. Fonctionnement d un RdP Transition Franchissable, matrice d’incidence, séquence de franchissement, franchissable, Equation de franchissement, franchissable, Equation fondamentale, Grammaire associée, Marquage accessible et graphe, arbre de couverture. 4. Analyse structurelle des RdP – Propriétés Propriétés structurelles, Conflit, Propriétés Vincent Bombardier Jeudi 6 février 2014 T2 p , , p fonctionnelles, Invariants. 1. Généralités 1.1 ORIGINE / OBJECTIFS Carl Adam Petri définit en 1962 un outil mathématique Carl Adam Petri définit en 1962 un outil mathématique très général pour décrire les relations existant entre des conditions et des événements. D’origine mathématique, cet outil est ensuite très utilisé en informatique et en cet outil est ensuite très utilisé en informatique et en automatique. Un réseau de Petri (RdP) est un outil de modélisation permettant l’étude de systèmes dynamiques et discrets. La syntaxe des RdP est graphique et la sémantique est fondée sur une représentation mathématique. L’analyse d’un RdP peut révéler des caractéristiques importantes du système modélisé concernant sa structure et son t t d i L é lt t comportement dynamique. Les résultats de cette analyse sont utilisés pour évaluer le système et en permettre la modification et/ou l’amélioration le cas Vincent Bombardier Jeudi 6 février 2014 T3 modification et/ou l amélioration le cas échéant. 1. Généralités 1.2 AVANTAGES DES RDP Adaptés aux systèmes distribués Présentation graphique intuitive Présentation graphique, intuitive Analyse formelle, preuve N b t i ( l é t k ti fl ) Nombreuses extension (colorés, stockastiques, flous, ..) Quantité d’outils ou support : Design CPN http://www.daimi.au.dk/CPnets/intro Vincent Bombardier Jeudi 6 février 2014 T4 1. Généralités 1.3 EXEMPLES D’APPLICATIONS INDUSTRIELLES DES RDP Bases de données distribuées Multiprocesseurs à mémoire distribuée Multiprocesseurs à mémoire distribuée Simulateur de combat S tè é t i d it (PSA P t Cit ë ) Systèmes mécatroniques de voitures (PSA Peugeot‐Citroën) Réseau de téléphones portables (Nokia) Contrôle à distance multipoint de chaînes hi‐fi (Bang&Olufsen) Processus de gestion de déchets nucléaires Autres exemples : http://www.daimi.au.dk/CPnets/intro/example_indu.html Vincent Bombardier Jeudi 6 février 2014 T5 2. Formalisme de base 2.1 DEFINITION D’UN RESEAU DE PETRI Un RdP ordinaire non marqué est un quadruplet Q =(P, T, Pré, Post) où : P = {P1, P2, …, Pn} est un ensemble fini non vide de Places T = {T1 T2 Tm} est un ensemble fini non vide de Transitions T = {T1, T2, …, Tm} est un ensemble fini non vide de Transitions Avec P et T disjoints Pré : PxT {0,1} est l’application d’incidence avant (Pré(Pi,Tj) = 1 si un arc existe entre Pi et Tj) Un RdP généralisé est défini de la même manière mais avec : Post : PxT {0,1} est l’application d’incidence arrière (Post(Pi, Tj) = 1 si un arc existe entre Tj et Pi) Un RdP généralisé est défini de la même manière mais avec : Pré : P x T N est l’application d’incidence avant (Pré(Pi, Tj) = poids de l’arc si l’arc existe entre Pi et Tj, 0 sinon) Post : P x T N est l’application d’incidence arrière (Post(Pi, Tj) = poids de l’arc si l’arc existe entre Tj et Pi, 0 sinon) Vincent Bombardier Jeudi 6 février 2014 T6 2. Formalisme de base 2.2 NOTATION MATRICIELLE On représente les applications d’incidence avant et arrière par des MATRICES: m lignes pour m Places g p n colonnes pour n Transitions Pré (., t) ou Post (.,t) sont les colonnes associées à la transition t Pré(p,.) ou Post (p,.) sont les lignes associées à la place p Ex1: R= (P,T, Pré, Post) avec P={P1, P2, P3, P4, P5} et T={T1, T2, T3, T4} ( , , , ) { , , , , } { , , , } PRE POST Vincent Bombardier Jeudi 6 février 2014 T7 Matrice d’incidence avant Matrice d’incidence arrière 2. Formalisme de base 2.3 MARQUAGE Dans un RdP marqué, chaque place contient un nombre entier >=0 de marques ou jetons M(Pi) = mi Un réseau marqué est définit par le couple : Un réseau marqué est définit par le couple : N=<R, M> avec M une application de N ‐> P appelée marquage Le marquage du RdP est le vecteur M = (m1, …,mi, …mp) avec mi = M(Pi) marquage de la place Pi ou nombre de marques (ou jeton) de Pi 2.4 GRAPHE ASSOCIE A UN RDP Un RdP est un graphe orienté biparti (alternant deux types de sommets : PLACES et TRANSITIONS). Tout arc orienté doit obligatoirement avoir un sommet à chacune de ses extrémités. G = <P, T, , V> associé au RdP R=<P, T, Pré, Post> est défini par: p P, (p) = {tT tq Pré (p,t) >0} t T, (t) = {pP tq Post (p,t) >0} Ex1: R= (P,T, Pré, Post) avec P={P1, P2, P3, P4, P5} et T={T1, T2, T3, T4} Avec M0 = [0, 1, 1, 0, 0]T PRE POST Vincent Bombardier Jeudi 6 février 2014 T8 3 ‐ Fonctionnement d’un RdP 3.3 MATRICE D’INCIDENCE L i d’i id d RdP i d d l i C P P é La matrice d’incidence du RdP ci‐dessous est donc la matrice C = Post ‐ Pré Cette matrice est indépendante du marquage et indique en colonne la modification Vincent Bombardier Jeudi 6 février 2014 T9 du marquage apportée par le franchissement de la transition correspondante 3 ‐ Fonctionnement d’un RdP 3.4 TRANSITION FRANCHISSABLE : FONCTIONNEMENT D’UN RÉSEAU Une transition t est franchissable pour un marquage M ssi : p P, M(p) ≥ Pré (.,t) Notation: M0 ( T1 > : T1 est franchissable à partir du marquage M0 Le franchissement de t donne M’ tel que: p P, ’(p) = M(p) ‐ Pré (p,t) + Post (p,t) = M(p) + C(p,t) Notation: M0 ( T1 > M1 : Le franchissement de T1 à partir de M0 donne M1 M [1 0 0 0 0]T M0 = [1, 0, 0, 0, 0]T M0 ≥ Pré (., T1) = [1, 0, 0, 0, 0]T T1 Franchissable: M0 ( T1 > Donc M0 ( T1 > M1 = [0, 1, 1, 0, 0]T Vincent Bombardier Jeudi 6 février 2014 T10 3 ‐ Fonctionnement d’un RdP 3.3 SÉQUENCE DE FRANCHISSEMENT : EQUATION FONDAMENTALE Une séquence de transition T1 T2 est franchissable pour un marquage M ssi : M ( T1 > M1 ET M1 ( T21 > M2 Notation: M ( T1 T2 > M2 On définit une séquence s de T* comme franchissable pour M donnant M’’ ssi soit s =  alors M’’ = M s = s’t avec s’ T* et t T ET M’ tq M ( s’ > M’ et M’( t > M’’ L’équation fondamentale d’un RdP s’écrit : Mk = Mi + C . s M tq M ( s > M et M ( t > M Elle permet de trouver le marquage résultat (Mk) du tir d’une séquence S à partir du marquage Mi. Le vecteur caractéristique s s’écrit comme un vecteur de dimension m (nombre de Vincent Bombardier Jeudi 6 février 2014 T11 transitions) dont la jème composante correspond au nombre de franchissements de la transition Tj dans la séquence S) 3 ‐ Fonctionnement d’un RdP 3.3 SÉQUENCE DE FRANCHISSEMENT : EXEMPLE Le marquage atteint à partir du marquage Mi = (0,1,1,0,0) par franchissement de T2 est : Mk = Mi + C.s Le marquage atteint à partir du marquage Mk = (0,0,1,1,0) q g p q g k ( , , , , ) par franchissement de la séquence (T3 T4 T1 T3) est : Vincent Bombardier Jeudi 6 février 2014 T12 3 ‐ Fonctionnement d’un RdP 3.4 MARQUAGE MINIMAL Permet de déterminer si une séquence est franchissable pour un marquage M. On définit les applications Pré et C sur P x T* telles que : M ( s > si et seulement si Pré ( s ) ≤M M ( s > si et seulement si Pré ( . , s ) ≤ M Alors: M ( s > M si et seulement si M = M + C ( . , s ) et s est franchissable Les applications Pré et C sont définies par récurrence sur la longueur de s: soit s =  alors Pré ( p , s) = C ( p , s ) = 0 s = s’ t et s = s t et Pré ( p , s) = max (Pré ( p , s’ ) ; Pré ( p , t ) ‐ C ( p , s’ ) Le marquage minimal pour que franchissement de s depuis M est donné par Pré C ( p , s ) = C ( p , s’ ) + uploads/Ingenierie_Lourd/ cm-rdp.pdf