Réseau de Petri

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Réseaux de Petri)
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Réseau.
Exemple d'un réseau de Petri Place-Transition, composé de :
  • deux places, les cercles
  • trois transitions, les traits noirs
  • quatre arcs, les flèches
  • deux jetons, les points noirs qui circulent de gauche à droite

Un réseau de Petri[1] (aussi connu comme un réseau de Place/Transition ou réseau de P/T) est un modèle mathématique servant à représenter divers systèmes (informatiques, industriels…) travaillant sur des variables discrètes.

Le problème du dîner des philosophes modélisé en Réseau de Petri

Les réseaux de Petri sont apparus en 1962, dans la thèse de doctorat de Carl Adam Petri. Les réseaux de Petri sont des outils graphiques et mathématiques permettant de modéliser le comportement dynamique des systèmes à événements discrets comme les systèmes manufacturiers, les systèmes de télécommunications, les réseaux de transport.

Définition[modifier | modifier le code]

Un réseau de Petri est un 6-uplet (S,T,F,M_0,W,K)\,, où[2] :

  • S définit une ou plusieurs places.
  • T définit une ou plusieurs transitions.
  • F définit un ou plusieurs arcs (flèches).

Un arc ne peut pas connecter deux places ni deux transitions, il ne peut connecter que des paires place-transition ; plus formellement : F \subseteq (S \times T) \cup (T \times S).

  • M_0 : S \to \mathbb{N} appelé marquage initial, où, pour chaque place s \in S, il y a n \in \mathbb{N} jetons.
  • W : F \to \mathbb{N^+} appelé ensemble d'arcs primaires , assignant à chaque arc f \in F un entier positif n \in \mathbb{N^+} qui indique combien de jetons sont consommés depuis une place vers une transition, ou sinon, combien de jetons sont produits par une transition et arrivent pour chaque place.
  • K : S \to \mathbb{N^+} appelé limite de capacité, faisant correspondre à chaque place s \in S un nombre positif n \in \mathbb{N^+} représentant le nombre maximum de jetons qui peuvent occuper une place.

De nombreuses définitions formelles existent. Cette définition concerne un réseau place-transition (ou P-T). D'autres définitions n'incluent pas la notion d'arc primaire ou la limite de capacité.

Représentation[modifier | modifier le code]

Détail d'un réseau de Petri

Un réseau de Petri se représente par un graphe biparti (composé de deux types de nœuds et dont aucun arc ne relie deux nœuds de même type) orienté (composé d'arc(s) ayant un sens) reliant des places et des transitions (les nœuds). Deux places ne peuvent pas être reliées entre elles, ni deux transitions. Les places peuvent contenir des jetons, représentant généralement des ressources disponibles.

La distribution des jetons dans les places est appelée le marquage du réseau de Petri.

Les entrées d'une transition sont les places desquelles part une flèche pointant vers cette transition, et les sorties d'une transition sont les places pointées par une flèche ayant pour origine cette transition.

Représentation matricielle[modifier | modifier le code]

La définition matricielle introduit les matrices PRE \in \mathcal{M}_{mn} et POST \in \mathcal{M}_{mn}.

  • PRE_{pt} = W(p,t)
  • POST_{pt} = W(t,p)

Ces matrices de même dimension représentent en ligne les places, et en colonne les transitions. PRE contient les valuations des arcs qui vont des places vers les transitions, POST concerne les arcs des transitions vers les places. Une valeur nulle dans une des matrices indique l'inexistence d'un arc dans un sens ou dans l'autre.

La matrice d'incidence C est définie par C = POST - PRE. Étant donnée une transition t, C_{pt} est le nombre de jetons qui seront ajoutés (ou retirés si le nombre est négatif) à la place p si la transition t est franchie.

Dynamique d'exécution[modifier | modifier le code]

Un réseau de Petri évolue lorsqu'on exécute une transition : des jetons sont retirés dans les places en entrée de cette transition et des jetons sont déposés dans les places en sortie de cette transition.

L'exécution d'une transition (pour un réseau de base ou un réseau coloré) est une opération indivisible qui est déterminée par la présence du jeton sur la place d'entrée.

L'exécution d'un réseau de Petri n'est pas déterministe, car il peut y avoir plusieurs possibilités d'évolution à un instant donné (ex: pour une place en amont de deux transitions concurrentes).

Si chaque transition dans un réseau de Petri a exactement une entrée et une sortie alors ce réseau est un automate fini.

Franchissement d'une transition[modifier | modifier le code]

Le fait que la transition t est franchissable à partir du marquage M se note M \stackrel{t}{\rightarrow}

On dit qu'une transition t est franchissable, si chaque place p en entrée contient un nombre de jetons supérieur ou égal à la valuation de l'arc qui la relie à la transition t. C'est-à-dire :

M \geq PRE_t

Note : PRE_t est la t-ième colonne de PRE.

Le franchissement d'une transition permet d'atteindre un nouveau marquage M' à partir de M: M \stackrel{t}{\rightarrow} M' :

M' = M + C_t

Séquence de transitions[modifier | modifier le code]

Une séquence de transitions est une séquence formée sur l'alphabet des transitions (voir Théorie des langages). Elle décrit une suite de transitions à activer.

On dit qu'une séquence de transitions \sigma = \sigma ' t est franchissable à partir du marquage M si:

  • \sigma ' est franchissable à partir de M et M \stackrel{\sigma '}{\rightarrow} M'
  • t est franchissable à partir de M', M' \stackrel{t}{\rightarrow}

À une séquence de transitions \sigma, on associe un vecteur commutatif \stackrel{\rightarrow}{\sigma} = (\alpha_1, ... , \alpha_m) (m est le nombre de transitions). \alpha_i est le nombre d'occurrences de la transitions i dans \sigma.


Exemple: Soit un réseau avec les transitions T = \{t_1,t_2,t_3\}. \sigma = t_2 t_1 t_3 t_1, le vecteur commutatif correspondant est \stackrel{\rightarrow}{\sigma} = (2, 1 ,1) (vecteur colonne)

Si la séquence \sigma est franchissable à partir du marquage M, alors on peut calculer le marquage M' obtenu par \sigma \stackrel{t}{\rightarrow}:

M' = M + C . \stackrel{\rightarrow}{\sigma}

Représentation graphique[modifier | modifier le code]

Graphe de marquage[modifier | modifier le code]

Le graphe des marquages d'un réseau (R,M_0) est un graphe orienté dont les nœuds sont les marquages de A(R,M_0), et chaque arc relie un marquage à un autre qui est immédiatement accessible par une transition : si M_0 \stackrel{t}{\rightarrow} M_1, un arc est tracé de M_0 à M_1 et il est marqué avec t.

Ce type de graphe donne une vue simple de l'évolution d'un réseau, néanmoins le graphe des marquages n'est pertinent que pour les réseaux bornés[3] : un réseau non borné a une infinité de marquages et ne pourrait être représenté.

L'algorithme de construction du graphe se définit récursivement, partant de l'état initial, on détermine de proche en proche les marquages accessibles.

  • S est l'ensemble des nœuds du graphe, il est initialisé à M_0
  • En entrée, l'algorithme prend un marquage M
Pour toute transition t faire
 Si M \stackrel{t}{\rightarrow} M_1 Alors
   Si M_1\notin S Alors
     S \leftarrow S \bigcup \{M_1\}
     Créer le sommet M_1
   Fin Si
   Créer l'arc (M,M_1)
   Appeler l'algorithme avec M_1
 Fin Si
Fin Pour
Graphe de Petri

Graphe de couverture[modifier | modifier le code]

Extensions[modifier | modifier le code]

Un réseau de Petri de haut niveau est un réseau coloré et hiérarchique.

Couleur[modifier | modifier le code]

Pour un réseau de Petri de base, on ne distingue pas les différents jetons. Dans un réseau de Petri coloré, on associe une valeur à chaque jeton.

Pour plusieurs outils associés aux réseaux de Petri colorés, les valeurs des jetons sont typées, et peuvent être testées et/ou manipulées avec un langage fonctionnel.

Hiérarchie[modifier | modifier le code]

Une autre extension du réseau de Petri est la hiérarchie (ou récursivité) : des éléments du réseau de Petri sont eux-mêmes composés d'un réseau de Petri.

Stochastique[modifier | modifier le code]

Les réseaux de Petri Stochastiques ajoutent de l'indéterminisme .

Notes et références[modifier | modifier le code]

  1. en français on prononce [petʁi̩]
  2. (en) Jörg Desel et Gabriel Juhás, « What is a Petri net? Informal answers for the informed reader », Lecture Notes in Computer Science, Springer, vol. 2128 « Unifying Petri Nets – Advances in Petri Nets »,‎ 2001, p. 1-25 (DOI 10.1007/3-540-45541-8_1, résumé).
  3. réseau dont toutes les places atteignables ont un nombre fini de jetons

Bibliographie[modifier | modifier le code]

Bibliographie francophone[modifier | modifier le code]

  • Annie Choquet-Geniet, Les réseaux de Petri : Un outil de modélisation, Éditions Dunod, coll. « Sciences Sup »,‎ 7 mars 2006, 240 p. (ISBN 2-10-049147-4)
  • René David et Hassane Alla, Du Grafcet aux réseaux de Petri, Paris, Hermès,‎ 1992, 2e éd. (ISBN 2-86601-325-5)
    à noter l'ouvrage en anglais traitant plus spécialement des extensions temporelles et continues : René David et Hassane Alla, Discrete, Continuous, and Hybrid Petri Nets, Berlin, Springer-Verlag,‎ 2005 (ISBN 3-540-22480-7)
  • Michel Diaz, Vérification et mise en œuvre des réseaux de Petri : ouvrage collectif sous la direction de Michel Diaz, Hermes Science Publications, coll. « Traité IC2 / Informatique et systèmes d'information » (ISBN 2-7462-0445-2)
  • M. Combacau et P. Esteban, Commandes à Réseaux de Petri, coll. « Techniques de l'Ingénieur » (lire en ligne)

Bibliographie anglophone[modifier | modifier le code]

  • (en) Janette Cardoso, Heloisa Camargo, Fuzziness in Petri Nets, Physica-Verlag,‎ 1999 (ISBN 3-7908-1158-0)
  • (en) Kurt Jensen, Coloured Petri Nets, Springer Verlag,‎ 1997 (ISBN 3-540-62867-3)
  • (en) Вадим Котов, Сети Петри (Petri Nets, in Russian), Наука, Москва,‎ 1984
  • (en) András Pataricza, Formális módszerek az informatikában (Formal methods in informatics), TYPOTEX Kiadó,‎ 2004 (ISBN 963-9548-08-1)
  • Carl Adam Petri, « Petri net », Scholarpedia 3(4):6477 (consulté le 13 juillet 2008)
  • (en) Wolfgang Reisig, A Primer in Petri Net Design, Springer-Verlag,‎ 1992 (ISBN 3-540-52044-9)
  • (en) Robert-Christoph Riemann, Modelling of Concurrent Systems: Structural and Semantical Methods in the High Level Petri Net Calculus, Herbert Utz Verlag,‎ 1999 (ISBN 3-89675-629-X)
  • (en) Harald Störrle, Models of Software Architecture - Design and Analysis with UML and Petri-Nets, Books on Demand,‎ 2000 (ISBN 3-8311-1330-0) With courtesy of the author, freely available online.
  • (en) Mengchu Zhou, Frank Dicesare, Petri Net Synthesis for Discrete Event Control of Manufacturing Systems, Kluwer Academic Publishers,‎ 1993 (ISBN 0-7923-9289-2)
  • (en) Mengchu Zhou, Kurapati Venkatesh, Modeling, Simulation, & Control of Flexible Manufacturing Systems: A Petri Net Approach, World Scientific Publishing,‎ 1998 (ISBN 981-02-3029-X)
  • (en) Dmitry Zaitsev, Clans of Petri Nets: Verification of protocols and performance evaluation of networks, LAP LAMBERT Academic Publishing,‎ 2013 (ISBN 978-3-659-42228-7, lire en ligne)

Liens externes[modifier | modifier le code]