Ouvrir le menu principal

Wikipédia β

Page d'aide sur l'homonymie Pour les articles homonymes, voir Réseau (homonymie).
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 et de vérifier 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.

Le diagramme d'activité UML et le Grafcet sont des dérivés simplifiés de réseau de Petri, mis à part qu'à un modèle basé sur un réseau de Petri est associée une représentation mathématique de matrices de transitions d'état permettant d'assurer des preuves formelles de théorie des graphes, d'algèbre temporelle et de processus stochastiques markoviens.

Sommaire

DéfinitionModifier

Un réseau de Petri est un 6-uplet  , où[2] :

  •   définit une ou plusieurs places.
  •   définit une ou plusieurs transitions.
  •   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 :  .

  •   appelé marquage initial, où, pour chaque place  , il y a   jetons.
  •   appelé ensemble d'arcs primaires , assignant à chaque arc   un entier positif   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.
  •   appelé limite de capacité, faisant correspondre à chaque place   un nombre positif   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ésentationModifier

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 matricielleModifier

La définition matricielle introduit les matrices   et  .

  •  
  •  

Ces matrices de même dimension représentent en ligne les places, et en colonne les transitions.   contient les valuations des arcs qui vont des places vers les transitions,   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   est définie par  . Étant donnée une transition  ,   est le nombre de jetons qui seront ajoutés (ou retirés si le nombre est négatif) à la place   si la transition   est franchie.

Dynamique d'exécutionModifier

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 transitionModifier

Le fait que la transition   est franchissable à partir du marquage   se note  

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

 

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

Le franchissement d'une transition permet d'atteindre un nouveau marquage   à partir de  :   :

 

Séquence de transitionsModifier

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   est franchissable à partir du marquage M si:

  •   est franchissable à partir de M et  
  • t est franchissable à partir de M',  

À une séquence de transitions  , on associe un vecteur commutatif   (m est le nombre de transitions).   est le nombre d'occurrences de la transitions i dans  .


Exemple: Soit un réseau avec les transitions  .  , le vecteur commutatif correspondant est   (vecteur colonne)

Si la séquence   est franchissable à partir du marquage M, alors on peut calculer le marquage M' obtenu par  :

 

Représentation graphiqueModifier

Graphe de marquageModifier

Le graphe des marquages d'un réseau   est un graphe orienté dont les nœuds sont les marquages de  , et chaque arc relie un marquage à un autre qui est immédiatement accessible par une transition : si  , un arc est tracé de   à   et il est marqué avec  .

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é à  
  • En entrée, l'algorithme prend un marquage  
Pour toute transition t faire
 Si   Alors
   Si   Alors
      
     Créer le sommet  
   Fin Si
   Créer l'arc  
   Appeler l'algorithme avec  
 Fin Si
Fin Pour
 
Graphe de Petri

Graphe de couvertureModifier

Un graphe de couverture est presque la même chose qu'un graphe de marquage. La différence se situe lors d'un graphe qui implique une infinité de jetons. Si une transition « crée » un jeton à chaque fois qu'elle est traversée et qu'on peut répéter cette transition, nous allons donc faire un graphe de couverture pour représenter la progression du graphe.

ExtensionsModifier

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

CouleurModifier

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érarchieModifier

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.

StochastiqueModifier

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

Notes et référencesModifier

  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 »,‎ , 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

BibliographieModifier

Bibliographie francophoneModifier

  • G.W. Brams, Réseaux de Petri : Théorie et Pratique, Masson, 1983. (ISBN 2-903607-12-5)
  • Annie Choquet-Geniet, Les réseaux de Petri : Un outil de modélisation, Éditions Dunod, coll. « Sciences Sup », , 240 p. (ISBN 2-10-049147-4)
  • René David et Hassane Alla, Du Grafcet aux réseaux de Petri, Paris, Hermès, , 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, (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)
  • Marc Bourcerie, Réseaux de Petri, Elaboration pour les systèmes de production, cours et exercices corrigés, Éditions Ellipses, coll."technosup", février 2011

Bibliographie anglophoneModifier

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

Liens externesModifier