Chapitre 3 Les Réseaux de Pétri Introduction Un réseau de Petri est un modèle m

Chapitre 3 Les Réseaux de Pétri Introduction Un réseau de Petri est un modèle mathématique servant à représenter divers systèmes crée en 1962 par Carl Adam Petri. Les Réseaux de Petri sont un outil de modélisation universellement connu et reconnu pour les possibilités d’analyse, de validation et de vérification dont ils font preuve. Ils offrent une structure très simple et forment le support de nombreuses études théoriques des systèmes concurrents; ils permettent de représenter les concepts de parallélisme et de synchronisation. Cet outil de modélisation est particulièrement bien adapté à la représentation des systèmes dynamiques et discrets. Il se prête en effet à une construction modulaire et permet, dans la globalité du modèle obtenu, de repérer tous les sous-ensembles. Ses propriétés mathématiques permettent un suivi de la conservation ou de la non conservation des propriétés individuelles de chaque sous-ensemble. Les réseaux de Petri permettent aussi la vérification de propriétés aussi bien structurelles que comportementales. Un grand nombre de propriétés peuvent être exprimés à l'aide des réseaux de Petri telles que l'absence de blocage et la disponibilité permanente des fonctionnalités du système. 1. Définitions Un Réseau de Petri (RdP) est une structure graphique comportant: • un ensemble de places • un ensemble de transitions • un ensemble d’arcs orientés qui associent les places (d’entrée) aux transitions et les transitions aux places (de sortie) éventuellement porteurs de poids. Ces arcs sont des liens entre place et transition ou entre transition et place exclusivement. Dans cette structure se déplacent des jetons (ou marques) qui apparaissent dans les places et sont susceptibles de franchir les transitions selon certains critères de franchissement. L’état d’un réseau est défini par son marquage. Un marquage associe à chaque place un nombre entier positif, que l’on représente graphiquement par des jetons . Fig. 01. Exemples de Réseaux de Petri 1.1. Définition formelle Un RdP est un quadruplet Q = <P, T, Pré, Post > tel que : • P = {Pi}, i ∈{1,...,n} est appelé ensemble de places • T = {Tj}, j ∈{1,...,m} est appelé ensemble de transitions avec P∩T = ∅ • Pré est une application de P X T→ N dite fonction de précondition ou d'incidence avant. • Post est une application de P X T→ N dite fonction de postcondition ou d'incidence arrière. • Pré (Pi,Tj) est appelé poids de l'arc reliant Pi et Tj. • Post (Pi,Tj) est appelé poids de l'arc reliant Tj et Pi . Les places sont représentés par un cercle et les transitions en général par un trait. Le réseau de Petri est représenté par un graphe avec deux types de sommets les places et les transitions. Ces différents sommets sont reliés entre eux par des arcs qui joignent des palces à des transitions (les préconditions) et des transitions aux places (les postconditions). Il convient aussi qu'un arc possède un poids supérieur ou égale 1 (par défault 1). 1.2. Marquage On appelle marquage d'un réseau de Petri N = (P, T, Pré, Post) la fonction M: P → N où chaque place contient un nombre entier (positif ou nul) de marques ou jetons. Le nombre de marques ou de jetons contenu dans une place Pi sera noté m(Pi). Le marquage du réseau à l'instant i, M est défini par le vecteur de ces marquages M = (m(P1), m(P2), …,m(Pn)). Le marquage dit initial décrit l'état initial du système modélisé (M0). Exemple: Ce réseau de Petri possède 4 places, 4 transitions et 8 arcs orientés. Soit donc : P = {P1, P2, P3, P4} et T={T1, T2, T3, T4} ; Le marquage initial est M0 = (2,1,1,0) ; 1.3. Franchissabilité d'une transition Soit un réseau de Petri N, une transition Ti de N est franchissable, sensibilisée, tirable ou déclenchable pour un marquage M si et seulement si toutes les places immédiatement en amont (les places d'entrée) à cette transition Ti possèdent au moins le nombre de marques correspondant au poids des arcs reliant respectivement chacune de ces places à cette transition (∀ p∈P, m(p) ≥ Pre (p, Ti)). 1.3 Le franchissement ou le déclenchement d'une transition Toute transition sensibilisée par un marquage M est immédiatement franchie. Le déclenchement de cette transition consomme des jetons de ces places d'entrée et ajoute des jetons dans chacune des places immédiatement en avales (places de sorties). Le nombre de jetons consommés et produits correspond aux poids des arcs. Le déclenchement d'une transition conduit à un nouveau marquage M' défini, pour tout p, par: M'(p) = M(p) - Pre(p, Ti) + Post(p, Ti) Le franchissement de la transition Ti est noté par :        [ > ′ Exemple: Avant franchissement Après franchissement Les marquages sont les suivants : Avant franchissement : m(P1) = 3 ; m(P2) = 4 ; m(P3) = 1 ; m(P4) = 0 donc M(3, 4, 1, 0) (3, 4, 1, 0) - Pre(P1, T) - Pre(P2, T) + Post(P3, T) + Post(P4, T) = M'(1, 3, 2, 3) Après franchissement : m(P1) = 1 ; m(P2) = 3 ; m(P3) = 2 ; m(P4) = 3 donc M'(1, 3, 2, 3) (3, 4, 1, 0)  →′(1, 3, 2, 3) Remarques : 1) Le franchissement d'une transition ne garantit pas la conservation de la quantité de marques globale. Dans l’exemple précédent, on a globalement un jeton de plus après franchissement de la transition. Selon les poids attribués aux arcs liés à une transition donnée, les transitions sont : "Consommatrice", "Génératrice" ou "Conservatrice" de marques. Soit une transition T reliée à un ensemble de places par n arcs amont (entrants) et m arcs aval (sortants). Soit Pré(i) le poids d'un arc amont i de la transition T. Soit Post(j) le poids d'un arc aval j de la transition T. si ∑ Pré(i) !" < ∑ Post(j) '!" alors la transition est génératrice si ∑ Pré(i) !" > ∑ Post(j) '!" alors la transition est consommatrice si ∑ Pré(i) !" = ∑ Post(j) '!" alors la transition est conservatrice 2) Le temps de franchissement d'une transition est nul d'un point de vue purement théorique et en dehors de toute réalité physique. 3) Dans le principe initial des RdP, rien n'interdit le franchissement simultané de deux transitions du même réseau. Or, la simultanéité de deux événements n'est pas cohérente pour le physicien. 4) Les protocoles de franchissement et les conditions de déclenchement décrites précédemment ne prennent pas en compte la notion de temps. En effet, on fait évoluer le marquage d'un RdP sans prendre en compte ni la chronologie ni la durée des événements. Il est donc indispensable, pour l’application, de fixer un certain nombre de règles. Ces règles sont issues des contraintes temporelles imposées par les systèmes physiques. Elles sont issues des deux considérations suivantes : • Tout événement a une durée non nulle. • Deux événements indépendants ne peuvent être simultanés. L’évolution du marquage dans un RdP, peut alors dépendre du temps de séjour dans une place ou du temps de franchissement d’une transition donnés. 1.4. Séquence de franchissement et ensemble de marquage accessibles 1) Une séquence de franchissement à partir d'un marquage M0 est représentée par la suite des transitions δ= t1, t2, t3, . . . tn telles que le franchissement de chacune d'elles conduit à un marquage qui sensibilise la suivante : 0 12 →1 , 1 13 →2 , . . . , n-1 16 →n ou 0 12 →1 13 →2 18 → . . . 16 →n noté par 0 δ →n 2) Un marquage M est dit accessible s'il existe une séquence de franchissement δ tel que: 0 δ → 3) L'ensemble des marquages accessibles à partir du marquage M0 est noté par *M0 Exemple: On considère le RdP de l'exemple ci-dessous. Le marquage initial est M0=(1, 0, 0, 0, 0). Pour ce marquage M0, seule la transition T1 est validée et son franchissement conduit au marquage M1=(0, 1, 1, 0, 0). On notera ceci : M0  2 →M1 Pour M1, il y a deux transitions validées T2 et T3. On aura donc : M1  3 →M2 = (0, 0, 1, 1, 0) et M1  8 →M3 = (0, 1, 0, 0, 1) Pour M2, seule la transition T3 est validée, son franchissement conduit à M4 : M2  8 →M4 = (0, 0, 0, 1, 1) Pour M3, seule la transition T2 est validée, son franchissement conduit à M4 : M3  3 →M4 = (0, 0, 0, 1, 1) Pour M4, seule la transition T4 est validée, son franchissement conduit à M0 : M4  : →M0 = (1, 0, 0, 0, 0) Le franchissement, à partir de M0, de t1 puis t2 conduit au marquage M2. T1, T2 est unes séquence de franchissement noté : 0  2, 3    2 ou encore 0 δ →2 avec δ= T1, T2 Pour l'exemple, la séquence δ= T1, T2, T3 est applicable à partir de M0 et conduit au marquage M4. 0 = (1, 0, 0, 0, 0) δ! 2, 3, 8  4 uploads/Ingenierie_Lourd/ chapitre-3 2 .pdf

Tags
Ingénierie marquage transition franchissement réseau chaque
Documents similaires
  • 14
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager