Voir la source de Réseau de Petri

{{Homonyme|Réseau (homonymie)}}
{{Début d'illustration |droite|largeur=300}}
[[Image:Animated_Petri_net_commons.gif|300px|Exemple d'un réseau de Petri]]
{{Fin d'illustration |
Animated_Petri_net_commons.gif |
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'''<ref>en [[français]] on prononce [{{APIb|petʁi̩}}]</ref> (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 ([[informatique]]s, [[industrie|industriels]]…) travaillant sur des [[Mathématiques discrètes|variables discrètes]].

[[Image:4-philosophers.gif|thumb|right|300px|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 (informatique)|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.

== Définition ==
Un réseau de Petri est un [[N-uplet|6-uplet]] <math>(S,T,F,M_0,W,K)\,</math>, où<ref>{{article
 | langue       = en
 | prénom1      = Jörg
 | nom1         = Desel
 | prénom2      = Gabriel
 | nom2         = Juhás
 | titre        = {{lang|en|texte=What is a Petri net? Informal answers for the informed reader}}
 | périodique   = {{lang|en|texte=Lecture Notes in Computer Science}}
 | éditeur      = Springer
 | volume       = 2128
 | titre volume = {{lang|en|texte=Unifying Petri Nets – Advances in Petri Nets}}
 | année        = 2001
 | pages        = 1-25
 | résumé       = http://www.springerlink.com/content/a6lmwqye66ll5w56/
 | doi          = 10.1007/3-540-45541-8_1
}}.</ref> :
* <math>S</math> définit une ou plusieurs ''places''.
* <math>T</math> définit une ou plusieurs ''transitions''.
* <math>F</math> 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 : <math>F \subseteq (S \times T) \cup (T \times S)</math>.

* <math>M_0 : S \to \mathbb{N}</math> appelé ''marquage initial'', où, pour chaque place <math>s \in S</math>, il y a <math>n \in \mathbb{N}</math> jetons.
* <math>W : F \to \mathbb{N^+}</math> appelé ensemble d'''arcs primaires'' <!--TRADUC ? known as a set of arc weights,-->, assignant à chaque arc <math>f \in F</math> un entier positif <math>n \in \mathbb{N^+}</math> 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.
* <math>K : S \to \mathbb{N^+}</math> appelé ''limite de capacité'', faisant correspondre à chaque place <math>s \in S</math> un nombre positif <math>n \in \mathbb{N^+}</math> 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 ==
[[Image:Detailed petri net.png|right|Détail d'un réseau de Petri]]
Un réseau de Petri se représente par un [[Théorie des graphes|graphe]] [[Graphe biparti|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 ===
La définition matricielle introduit les matrices <math>PRE \in \mathcal{M}_{mn}</math> et <math>POST \in \mathcal{M}_{mn}</math>.

*<math>PRE_{pt} = W(p,t)</math>
*<math>POST_{pt} = W(t,p)</math>

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

== Dynamique d'exécution ==
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éterminisme|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 ===
Le fait que la transition <math>t</math> est franchissable à partir du marquage <math>M</math> se note <math>M \stackrel{t}{\rightarrow}</math>

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

<math>M \geq PRE_t</math>

Note : <math>PRE_t</math> est la t-ième colonne de <math>PRE</math>.

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

<math>M' = M + C_t</math>

=== Séquence de transitions ===
Une séquence de transitions est une séquence formée sur l'alphabet des transitions (voir [[Langage formel]]). Elle décrit une suite de transitions à activer.

On dit qu'une séquence de transitions <math>\sigma = \sigma ' t</math> est franchissable à partir du marquage M si :
* <math>\sigma ' </math> est franchissable à partir de M et <math>M \stackrel{\sigma '}{\rightarrow} M'</math>
* t est franchissable à partir de M', <math>M' \stackrel{t}{\rightarrow}</math>

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


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

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

<math>M' = M + C . \stackrel{\rightarrow}{\sigma}</math>

=== Représentation graphique ===
==== Graphe de marquage ====
Le graphe des marquages d'un réseau <math>(R,M_0)</math> est un graphe orienté dont les nœuds sont les marquages de <math>A(R,M_0)</math>, et chaque arc relie un marquage à un autre qui est immédiatement accessible par une transition : si <math>M_0 \stackrel{t}{\rightarrow} M_1</math>, un arc est tracé de <math>M_0</math> à <math>M_1</math> et il est marqué avec <math>t</math>.
 
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<ref>réseau dont toutes les places atteignables ont un nombre fini de jetons</ref> : 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é à <math>M_0</math>
* En entrée, l'algorithme prend un marquage <math>M</math>

 Pour toute transition t faire
  Si <math>M \stackrel{t}{\rightarrow} M_1</math> Alors
    Si <math>M_1\notin S</math> Alors
      <math>S \leftarrow S \bigcup \{M_1\}</math>
      Créer le sommet <math>M_1</math>
    Fin Si
    Créer l'arc <math>(M,M_1)</math>
    Appeler l'algorithme avec <math>M_1</math>
  Fin Si
 Fin Pour

[[Image:Reachability graph for petri net.png|Graphe de Petri|alt=resp|thumb]]

==== Graphe de couverture ====
Un graphe de couverture est semblable à un graphe de marquage dans lequel on va utiliser un symbole, par exemple <math>\omega</math>, pour indiquer la présence d'un nombre arbitrairement grand de jetons (en pratique une infinité) : une transition peut alors prélever et ajouter librement des jetons sur cette place. Il s'agit cependant d'une sur-approximation et certaines transitions paraissant possibles sur le graphe de couverture peuvent ne pas l'être en pratique.

== Propriétés mathématiques des réseaux de Petri ==
L'un des intérêts des réseaux de Petri provient de l'équilibre entre leur capacité de modélisation et la complexité de leur analyse. De nombreuses propriétés que l'on désirerait obtenir pour des systèmes concurrents sont automatiquement déterminées pour des réseaux de Petri même si certaines peuvent être coûteuses en termes de calcul dans le cas général. Plusieurs sous-classes de réseaux de Petri ont donc été étudiées afin de modéliser diverses classes de systèmes concurrents tout en facilitant la détermination de ces propriétés.

Pour une présentation plus complète de la décidabilité et de la complexité des problèmes sur les réseaux de Petri, le lecteur se reportera à l'article de Esparza et Nielsen <ref>{{article| url = http://citeseer.ist.psu.edu/226920.html | titre = Decidability issues for Petri nets – a survey | prénom1 = Javier | nom1 = Esparza | prénom2 = Mogens | nom2 = Nielsen | journal = Bulletin of the EATCS | année première édition = 1994 | numéro d'édition = Revised | date = 1995 |consulté le=2014-05-14}}</ref>.

=== Accessibilité ===
Le [[problème d'accessibilité]] pour les réseaux de Petri revient à décider, pour un réseau <math>N</math> et un marquage <math>M</math> si <math>M \in R(N).</math>.

Il s'agit évidemment d'un problème de chemin sur le graphe de marquage défini ci-dessus, ou bien jusqu'à ce que l'on atteigne le marquage <math>M</math> ou que l'on sache qu'il ne peut pas être atteint. Ce problème est en général beaucoup plus difficile qu'il n'y parait car le graphe de marquage est généralement infini et il n'est pas évident de déterminer quand l'on peut s'arrêter de chercher.

Bien que l'accessibilité semble être une bonne manière de trouver les états défectueux (par exemple pour prouver la correction d'un programme), dans les cas pratiques la construction du graphe de marquage est beaucoup trop complexe. Pour simplifier ce problème, on recourt donc à la [[logique temporelle linéaire]] en complément de méthode d'analyse des tableaux pour prouver que ces états ne peuvent être atteints. La logique temporelle utilise des méthodes de semi-décision pour déterminer un ensemble de conditions nécessaire à l'accessibilité de l'état avant de prouver que ces conditions ne peuvent être satisfaites.

=== Détermination des bornes ===
Une place d'un réseau de Petri est dite ''k-bornée'' si elle ne contient pas plus de <math>k</math> jetons dans l'ensemble des marquages accessibles, y compris le marquage initial. Elle est dite ''sûre'' si elle est ''1-bornée'' et bornée si elle est ''k-bornée'' pour un entier <math>k</math>.

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

=== Couleur ===
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 [[programmation fonctionnelle|un langage fonctionnel]].

=== Hiérarchie ===
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 ===
Les réseaux de Petri [[Processus stochastique|stochastiques]] ajoutent de l'[[Indéterminisme (mathématiques)|indéterminisme]].

== Notes et références ==
<references />

== Bibliographie ==

=== Bibliographie francophone ===
*G.W. Brams, ''Réseaux de Petri : Théorie et Pratique'', Masson, 1983. {{ISBN|2-903607-12-5}}
*{{Ouvrage |langue=fr |prénom1=Annie |nom1=Choquet-Geniet |titre=Les réseaux de Petri |sous-titre=Un outil de modélisation |lieu=Paris |éditeur=[[Éditions Dunod]] |collection=Sciences Sup |année=2006 |mois=mars |jour=7 |pages totales=240 |isbn=2-10-049147-4}}
* {{Ouvrage |langue=fr |prénom1=René |nom1=David |prénom2=Hassane |nom2=Alla |titre=Du Grafcet aux réseaux de Petri |lieu=Paris |éditeur=Hermès |année=1992 |numéro d'édition=2 |pages totales=500 |isbn=2-86601-325-5}}{{Commentaire biblio|à noter l'ouvrage en anglais traitant plus spécialement des extensions temporelles et continues :  {{ouvrage|titre=Discrete, Continuous, and Hybrid Petri Nets|prénom1=René|nom1=David|prénom2=Hassane|nom2=Alla|éditeur=Springer-Verlag|lieu=Berlin|année=2005|isbn=3-540-22480-7}}}}
*{{Ouvrage |prénom1=Michel |nom1=Diaz |titre=Vérification et mise en œuvre des réseaux de Petri |sous-titre=ouvrage collectif sous la direction de Michel Diaz |éditeur=Hermes Science Publications |collection=Traité IC2 |série=Informatique et systèmes d'information |année= |isbn=978-2-7462-0445-4 |isbn2=2-7462-0445-2}}
*{{Ouvrage |prénom1=M. |nom1=Combacau |prénom2=P. |nom2=Esteban |titre=Commandes à Réseaux de Petri |éditeur= |collection=Techniques de l'Ingénieur |année=2005 |mois=mars |jour=10 |isbn= |lire en ligne=http://www.techniques-ingenieur.fr/base-documentaire/electronique-automatique-th13/automatique-sequentielle-42395210/commandes-a-reseaux-de-petri-s7572/}}
* Marc Bourcerie, ''Réseaux de Petri, Elaboration pour les systèmes de production, cours et exercices corrigés'', [[Éditions Ellipses]], coll."technosup", {{date-|février 2011}}
*{{Ouvrage |prénom1=Marion |nom1=Juan |prénom2=David |nom2=Mailland |prénom3=Nicolas |nom3=Fifis |prénom4=Guy |nom4=Gregoris |titre= Modélisation des pannes d’une antenne active et modifications d’architecture |éditeur= |collection=Techniques de l'Ingénieur |année=2021 |mois=décembre |jour=10 |isbn= |lire en ligne=https://www.techniques-ingenieur.fr/base-documentaire/environnement-securite-th5/securite-des-systemes-industriels-42830210/modelisation-des-pannes-d-une-antenne-active-et-modifications-d-architecture-se1221/}}

=== Autres langues ===
*{{Ouvrage|
prénom1=Janette|
nom1=Cardoso|
auteur2=Heloisa Camargo|
titre=Fuzziness in Petri Nets|
éditeur=Physica-Verlag|
année=1999|
pages totales=318|
isbn=3-7908-1158-0|
lire en ligne=https://books.google.com/books?id=ssFFZ_4DpVcC&printsec=frontcover
}}.
*{{Ouvrage|
langue=en|
prénom1=Kurt|
nom1=Jensen|
titre=Coloured Petri Nets|
sous-titre=basic concepts, analysis methods, and practical use|
lieu=Berlin/Heidelberg/Paris etc.|
éditeur=Springer Verlag|
année=1997|
pages totales=265|
isbn=3-540-62867-3
}}.
*{{Ouvrage|
prénom1=Вадим|
nom1=Котов|
titre=Сети Петри (Petri Nets, in Russian)|
éditeur=Наука, Москва|
année=1984|
isbn=
}}.
*{{Ouvrage|
prénom1=András|
nom1=Pataricza|
titre=Formális módszerek az informatikában (Formal methods in informatics)|
éditeur=TYPOTEX Kiadó|
année=2004|
isbn=963-9548-08-1
}}.
*{{lien web
  | nom = Petri
  | prénom = Carl Adam
  | nom2 = Reisig
  | prénom2 = Wolfgang
  | titre = Petri net
  | série = Scholarpedia 3(4):6477
  | url = http://www.scholarpedia.org/article/Petri_net
  | consulté le = 13 juillet 2008}}
*{{Ouvrage|
prénom1=Wolfgang|
nom1=Reisig|
titre=A Primer in Petri Net Design|
éditeur=[[Springer Science+Business Media|Springer-Verlag]]|
année=1992|
isbn=3-540-52044-9
}}.
*{{Ouvrage|
prénom1=Robert-Christoph|
nom1=Riemann|
titre=Modelling of Concurrent Systems : Structural and Semantical Methods in the High Level Petri Net Calculus|
éditeur=Herbert Utz Verlag|
année=1999|
pages totales=252|
isbn=3-89675-629-X|
lire en ligne=https://books.google.com/books?id=XSoK7L9SZ5oC&printsec=frontcover
}}.
*{{Ouvrage|
prénom1=Harald|
nom1=Störrle|
titre=Models of Software Architecture : Design and Analysis with UML and Petri-Nets|
éditeur=[[Books on Demand]]|
année=2000|
isbn=3-8311-1330-0
}}. <span style="color:gray;">With courtesy of the author, freely available [http://www.pst.informatik.uni-muenchen.de/~stoerrle/V/Dissertation.pdf online].</span>
*{{Ouvrage|
langue=en|
prénom1=Mengchu|
nom1=Zhou|
auteur2=Frank Dicesare|
titre=Petri Net Synthesis for Discrete Event Control of Manufacturing Systems|
lieu=Boston/Dordrecht/London|
éditeur=Kluwer Academic Publishers|
année=1993|
pages totales=233|
isbn=0-7923-9289-2
}}.
*{{Ouvrage|
coauteur=Kurapati Venkatesh|
prénom1=Mengchu|
nom1=Zhou|
titre=Modeling, Simulation, & Control of Flexible Manufacturing Systems|
sous-titre=A Petri Net Approach|
éditeur=[[World Scientific|World Scientific Publishing]]|
année=1998|
isbn=981-02-3029-X
}}.
*{{Ouvrage|
prénom1=Dmitry|
nom1=Zaitsev|
titre=Clans of Petri Nets : Verification of protocols and performance evaluation of networks|
éditeur=LAP LAMBERT Academic Publishing|
année=2013|
isbn=978-3-659-42228-7|
lire en ligne=https://www.morebooks.de/store/gb/book/clans-of-petri-nets/isbn/978-3-659-42228-7
}}.

=== Liens externes ===
* {{Référence web
| url=http://www.univ-valenciennes.fr/gdr-macs/node/5258
| titre=PetriParC - GDR MACS
| lien=
| site=www.univ-valenciennes.fr/gdr-macs
}}
* {{Référence web
| url=http://www3.ec-lille.fr/~rdp/
| titre=Groupe francophone de recherche sur les réseaux de Petri
| lien=
| site=lagis.ec-lille.fr
}}
* [https://projects.laas.fr/tina/index.php TINA - TIme petri Net Analyser], sur ''www.laas.fr''

{{Portail|robotique|électricité et électronique|informatique théorique}}

{{DEFAULTSORT:Reseau de Petri}}
[[Catégorie:Automatique|R]]
[[Catégorie:Méthode formelle]]