Réseau de Petri

Un réseau de Petri est un modèle mathématique permettant de représenter divers dispositifs œuvrant sur des variables discrètes.



Catégories :

Automatique - Robotique - Théorie des graphes - Méthode formelle

Recherche sur Google Images :


Source image : webdav-noauth.unit-c.fr
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

  • Un réseau de Pétri est borné si, pour tout marquage consécutif du marquage... si le marquage de chaque place P_i dans M_1 est supérieur ou identique à son marquage dans M_2.... Aucune transition n'est validée, pas de nouveau marquage.... (source : geekz)
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 dans la place de gauche

Un réseau de Petri (en français on prononce [petʁi̩]) est un modèle mathématique permettant de représenter divers dispositifs (informatiques, industriels, …) œuvrant sur des variables discrètes.

Histoire

C'est dans sa thèse de doctorat en 1962 que Carl Adam Petri introduit pour la première fois les réseaux de Petri.

Définition

Un réseau de Petri est un 6-uplet (S,T,F,M_0,W,K)\,, où (cf. Desel et Juhás[1])

Un arc ne peut pas être connecté entre 2 places ou 2 transitions ; plus formellement : F \subseteq (S \times T) \cup (T \times S).

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

Un réseau de Petri se représente par un graphe biparti (composé de deux types de nœuds) orienté (composé d'arc (s) ) 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 le plus souvent des ressources disponibles.

La distribution des jetons dans les places est nommé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 PRE \in \mathcal{M}_{mn} et POST \in \mathcal{M}_{mn}.

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 = POSTPRE. Étant donnée une transition t, Cpt 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

Un réseau de Petri évolue quand 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é.

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

Franchissement d'une transition

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 identique à la valuation de l'arc qui la relie à la transition t. Autrement dit :

M \geq PRE_t

Note : PREt 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 + Ct

Séquence de transitions

Une séquence de transitions est une séquence constitué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 σ = σ't est franchissable à partir du marquage M si :

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


Exemple : Soit un réseau avec les transitions T = {t1, t2, t3}. σ = t2t1t3t1, le vecteur commutatif correspondant est \stackrel{\rightarrow}{\sigma} = (2, 1 ,1)

Si la séquence σ 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}

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 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 Stochastiques ajoutent de l'indéterminisme et des probabilités de tir.

Notes et références

  1. Desel, Jörg and Juhás, Gabriel «What Is a Petri Net? Informal Answers for the Informed Reader», Hartmut Ehrig et al. (Eds. )  : Unifying Petri Nets, LNCS 2128, pp. 1-25, 2001. [1]

Bibliographie

Outre les références présentées dans l'article en version anglaise, le lecteur francophone pourra consulter :

Recherche sur Amazone (livres) :




Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/R%C3%A9seau_de_Petri.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 14/04/2009.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu