Reseaux de Petri

PARTIE A : GENERALITES

Presentation

Le cours "Reseaux de Petri" introduit un formalisme graphique et mathematique puissant pour modeliser, analyser, et valider les systemes a evenements discrets (SED). Les reseaux de Petri sont particulierement adaptes pour representer des systemes avec concurrence, synchronisation, et partage de ressources. Ils sont utilises en automatique, informatique, logistique, et de nombreux autres domaines.

Annee Universitaire : 2023-2024
Semestre : 8
Categorie : Automatique / Systemes a Evenements Discrets

---

PARTIE B : PARTIE DESCRIPTIVE

Details de l'experience

Environnement et contexte

Le cours combinait theorie formelle (algebre, theorie des graphes) avec applications pratiques via des outils logiciels de modelisation et simulation (PIPE, Tina). Nous avons modelise des systemes varies: systemes de production, protocoles de communication, workflows, et analyse leurs proprietes (vivacite, bornitude, absence de blocage).

Ma fonction

Dans ce cours, j'ai ete responsable de :

• Comprendre la syntaxe et semantique des reseaux de Petri
• Modeliser des systemes concurrents et distribues
• Analyser les proprietes structurelles et comportementales
• Utiliser l'equation d'etat et invariants
• Verifier proprietes (vivacite, bornitude, reversibilite)
• Simuler et valider des modeles
• Appliquer les extensions (temporises, colores, stochastiques)
• Utiliser les reseaux de Petri pour concevoir et valider des systemes de commande

PARTIE C : PARTIE TECHNIQUE

Cette section explore les aspects techniques des reseaux de Petri.

Concepts techniques appris

1. Definition et Syntaxe

Reseau de Petri R = (P, T, Pre, Post) :

• P : ensemble de places (etats, ressources)
• T : ensemble de transitions (evenements, actions)
• Pre : P x T → N (arcs des places vers transitions, poids)
• Post : T x P → N (arcs des transitions vers places, poids)

Representation graphique :

• Places : cercles
• Transitions : rectangles (ou barres)
• Arcs : fleches avec poids (1 si omis)
• Jetons (tokens) : points noirs dans places

Marquage M : P → N

Fonction indiquant nombre de jetons dans chaque place. M0 = marquage initial.

2. Regles de Franchissement

Transition t est franchissable (enabled) ssi :

∀p ∈ P: M(p) ≥ Pre(p,t)

Assez de jetons dans chaque place d'entree.

Franchissement de t :

M' = M - Pre(·,t) + Post(t,·)

On retire Pre(p,t) jetons de chaque place p, on ajoute Post(t,p).

Notation : M →t M'

Sequence de franchissement :

M0 →t1 M1 →t2 M2 → ... →tn Mn

3. Graphe de Marquage

Ensemble d'accessibilite R(M0) :

Ensemble de tous les marquages atteignables depuis M0.

Graphe de marquage :

• Sommets : marquages
• Arcs : transitions

Representation de l'espace d'etats.

Probleme : explosion combinatoire (nombre de marquages peut etre exponentiel).

4. Proprietes Comportementales

Bornitude :

∃ k tel que ∀M ∈ R(M0), ∀p ∈ P : M(p) ≤ k

Systeme borne : nombre de jetons limite. Important : evite debordements (buffers, files).

1-sur (safe) : borne par 1.

Vivacite (liveness) :

Une transition est vivante si elle peut toujours redevenir franchissable.

Niveaux de vivacite :

• L0 (mort) : jamais franchissable
• L1 (potentiellement franchissable) : franchissable au moins une fois
• L2 : peut etre franchie infiniment sur une sequence
• L3 : peut etre franchie infiniment souvent (sur toute sequence infinie)
• L4 (vivante) : franchissable depuis tout marquage accessible

Reseau vivant : toutes transitions L4-vivantes.

Blocage (deadlock) :

Marquage M ou aucune transition n'est franchissable.

Reversibilite :

∀M ∈ R(M0) : M0 ∈ R(M)

On peut toujours revenir a l'etat initial.

Quasi-vivacite :

∀t ∈ T, ∃M ∈ R(M0) : t franchissable depuis M.

Toute transition peut etre franchie au moins une fois.

5. Equation d'Etat

Matrice d'incidence C :

C = Post^T - Pre^T

C(t,p) = gain net de jetons dans p par franchissement de t.

Equation d'etat fondamentale :

M = M0 + C^T · σ

Ou σ est le vecteur de franchissement (nombre de fois chaque transition a ete franchie).

Usage :

Condition necessaire (mais pas suffisante) d'accessibilite. Si M inaccessible, alors pas de solution entiere positive a l'equation.

6. Invariants

P-invariants (invariants de places) :

Vecteur y ≥ 0 tel que :

C · y = 0

Interpretation :

y^T · M = y^T · M0 = constante

Combinaison ponderee de jetons conservee.

Exemple : conservation de ressources.

T-invariants (invariants de transitions) :

Vecteur x ≥ 0 tel que :

C^T · x = 0

Interpretation :

Sequence de transitions ramenant au meme marquage. Si x franchissable depuis M, alors M →* M.

Usage : cycles, comportements repetitifs.

Reseau couvert par P-invariants :

Toute place appartient a au moins un P-invariant. ⇒ Reseau borne.

7. Sous-Classes de Reseaux

Graphe d'etats :

Chaque transition a exactement une place d'entree et une de sortie. Modelise automates finis.

Graphe d'evenements :

Chaque place a exactement une transition d'entree et une de sortie. Modelise synchronisation.

Reseau libre choix (free choice) :

Si deux transitions partagent place d'entree, elles ont meme ensemble de places d'entree. Simplifie analyse.

Reseau sauf (safe) :

1-borne.

8. Extensions des Reseaux de Petri

Reseaux de Petri Temporises (TPN) :

Ajout du temps : delais sur transitions ou durees de franchissement.

Types :

• P-temporise : jetons ont age minimal avant utilisation
• T-temporise : transition franchit apres delai

Analyse : plus complexe (espace d'etats infini). Classes d'etats, automates temporises.

Reseaux de Petri Colores (CPN) :

Jetons ont "couleurs" (types, attributs).

Avantages :

• Modele compact (un jeton colore represente plusieurs jetons classiques)
• Donnees structurees

Outil : CPN Tools

Reseaux de Petri Stochastiques (SPN) :

Transitions avec taux de franchissement (lois exponentielles).

Usage : evaluation de performances (comme files d'attente). Equivalent a chaines de Markov continues.

Reseaux de Petri Hybrides :

Variables continues et discretes. Modelise systemes hybrides (manufacturiers, thermiques, etc.).

9. Analyse par Reduction

Transformations preservant proprietes :

Fusion de places paralleles :

Places avec memes transitions amont/aval.

Fusion de transitions paralleles :

Transitions avec memes places amont/aval.

Elimination de places implicites :

Place dont marquage toujours suffit (contrainte redondante).

Elimination de transitions :

Sous certaines conditions (ne change pas comportement).

Objectif : simplifier modele avant analyse.

10. Outils Logiciels

PIPE (Platform Independent Petri net Editor) :

• Modelisation graphique
• Simulation
• Analyse (graphe de marquage, invariants)
• Java, open source

Tina :

• Construction graphe de marquage
• Verification proprietes temporelles (CTL)
• Synthese de controleurs

CPN Tools :

• Pour reseaux colores
• Simulation, state space analysis

ROMEO :

• Reseaux temporises avec stopwatches
• Temps dense

GreatSPN :

• Stochastiques
• Evaluation de performances

11. Commande par Reseaux de Petri

Synthese de controleurs :

Probleme : systeme (plante) + specifications → controleur

Approches :

Theorie de la supervision :

Desactiver transitions interdites pour respecter specifications.

Controle par place de controle :

Ajouter places (avec arcs) pour imposer contraintes.

Exemple : eviter blocage, limiter nombre de pieces en cours (WIP).

Applications :

• Systemes de production flexibles (FMS)
• Workflows
• Protocoles de communication

12. Applications

Systemes de production :

• Modeliser lignes de fabrication
• Partage de ressources (machines, robots)
• Ordonnancement
• Detection de blocages

Protocoles de communication :

• Handshake, synchronisation
• Detection d'interblocages
• Verification de protocoles

Workflows :

• Processus metier
• Gestion de documents
• Validation de processus

Systemes informatiques :

• Allocation memoire
• Synchronisation de threads
• Gestion de transactions

Systemes embarques :

• Controle concurrent
• Verification avant implementation

PARTIE D : PARTIE ANALYTIQUE

Connaissances et competences mobilisees

• Comprehension des systemes a evenements discrets
• Modelisation graphique et formelle
• Algebre lineaire (matrices, invariants)
• Theorie des graphes
• Analyse de proprietes (vivacite, bornitude)
• Utilisation d'outils logiciels de simulation
• Verification formelle
• Synthese de lois de commande

Auto-evaluation

Ce cours a ete mathematiquement riche et conceptuellement dense. Les reseaux de Petri sont un formalisme elegant mais necessitent un changement de paradigme par rapport aux systemes continus etudies precedemment.

La representation graphique est intuitive et pedagogique. Visualiser les jetons circuler dans le reseau aide a comprendre la dynamique. Cependant, passer du graphique au formel (matrices, equations) demande rigueur.

L'analyse des proprietes (vivacite, bornitude) est cruciale pour valider un systeme. Un modele qui bloque ou dont les files explosent est inutilisable. Les methodes d'analyse (graphe de marquage, invariants) fournissent des outils rigoureux.

Le graphe de marquage est conceptuellement simple mais peut devenir gigantesque (explosion combinatoire). C'est une limite pratique importante. Les techniques de reduction et les analyses partielles (invariants sans construire tout le graphe) sont essentielles.

Les invariants (P et T) sont puissants. Les P-invariants permettent de prouver la bornitude elegamment. Les T-invariants revelent les cycles et comportements repetitifs.

L'equation d'etat (M = M0 + C^Tσ) est centrale. Elle offre une condition necessaire d'accessibilite calculable algebriquement, sans explorer tous les etats.

Les extensions (temporises, colores, stochastiques) augmentent l'expressivite mais complexifient l'analyse. Il y a un trade-off entre pouvoir de modelisation et analysabilite.

La synthese de controleurs par theorie de la supervision ouvre des perspectives interessantes pour automatiser la conception de systemes surs.

Les outils logiciels (PIPE, Tina) sont indispensables pour traiter des reseaux realistes. Modeliser a la main est formateur mais limite a des exemples jouets.

Les applications sont nombreuses et variees. Cela montre la generalite du formalisme. Tout systeme avec evenements, concurrence, et ressources partagees peut beneficier d'une modelisation par reseau de Petri.

Mon avis

Ce cours fournit des outils puissants pour les systemes a evenements discrets, complementaires aux techniques continues. Il est essentiel pour l'automaticien travaillant sur systemes manufacturiers, protocoles, ou systemes embarques.

Points forts :

• Formalisme rigoureux et visuel
• Analyse de proprietes critiques (vivacite, absence de blocage)
• Applicabilite large
• Outils logiciels disponibles

Points a ameliorer :

• Plus de cas d'etudes industriels complexes
• Lien avec implementation (code genere depuis modele)
• Comparaison avec autres formalismes (automates, algebre de processus)
• Techniques pour gerer explosion combinatoire

Reflexions personnelles :

Les reseaux de Petri sont un langage graphique universel pour SED. Leur avantage majeur est l'integration de la modelisation, simulation, et verification formelle dans un meme cadre.

La verification formelle est cruciale pour systemes critiques (aerospatial, medical, nucleaire). Prouver mathematiquement l'absence de blocage ou de depassement de capacite evite bugs catastrophiques.

Cependant, l'explosion combinatoire reste le defi majeur. Pour systemes realistes de grande taille, le graphe de marquage complet est incalculable. Les techniques d'abstraction, reduction, et verification symbolique sont des recherches actives.

La modularite et composabilite des reseaux de Petri sont limitees. Combiner plusieurs sous-reseaux peut etre ardu. Les reseaux colores et hierarchiques aident mais la complexite reste.

Le lien avec l'implementation est parfois flou. Modeliser c'est bien, mais comment passer du modele au code (PLC, microcontroleur)? La generation automatique de code depuis reseaux de Petri existe mais n'est pas standard.

Applications professionnelles :

Competences en reseaux de Petri applicables dans :

• Automatisation industrielle : conception et validation systemes de production
• Conception systemes embarques : verification proprietes temps reel
• Reseaux de communication : protocoles, gestion ressources
• Logiciels : modelisation workflows, processus metier
• Recherche : formalisation et analyse de systemes complexes

Le marche :

Moins mainstream que controle continu ou programmation classique. Niche dans domaines critiques necessitant verification formelle. Competence differenciante pour ingenieurs systemes complexes.

L'avenir :

• Integration avec Model-Based Design (Simulink, etc.)
• Codesign hardware/software
• Verification de systemes cyber-physiques
• IA et apprentissage : synthese automatique de modeles depuis donnees

En conclusion, les reseaux de Petri sont un formalisme puissant pour modeliser, analyser et verifier des systemes a evenements discrets. Ils completent les automates et les langages de description (GRAFCET, Statecharts) en offrant une semantique mathematique rigoureuse et des outils d'analyse formelle. Ils restent utilises en recherche et dans l'industrie pour les systemes critiques.

---

Documents de Cours

∀p ∈ P: M(p) ≥ Pre(p,t)

M' = M - Pre(·,t) + Post(t,·)

M0 →t1 M1 →t2 M2 → ... →tn Mn

C = Post^T - Pre^T

M = M0 + C^T · σ

C · y = 0

y^T · M = y^T · M0 = constant

C^T · x = 0