Réseau de Petri - Définition

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éterministe, car il peut y avoir plusieurs possibilités d'évolution à un instant donné.

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 t est franchissable à partir du marquage M se note

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 :

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' = M + C_t

Séquence de transitions

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

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

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

Exemple: Soit un réseau avec les transitions T = {t₁,t₂,t₃}. σ = t₂t₁t₃t₁, le vecteur commutatif correspondant est

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

Représentation graphique

Graphe de marquage

Le graphe des marquages d'un réseau (R,M₀) est un graphe orienté dont les noeuds sont les marquages de A(R,M₀), et chaque arc relie un marquage à un autre qui est immédiatement accessible par une transition : si , un arc est tracé de M₀ à M₁ 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 : 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 noeuds du graphe, il est initialisé à M₀
• En entrée, l'algorithme prend un marquage M

      Pour toute transition t faire       Si 

    
    
 Alors         Si 

    
    
 Alors           

    
    
           Créer le sommet M1         Fin Si         Créer l'arc (M,M1)         Appeler l'algorithme avec M1       Fin Si      Fin Pour      

Graphe de couverture

(...)