Réseaux de PETRI Représentations graphiques

Dans les années 80, A l'occasion d'une journée d'études sur "les représentations graphiques de l'information", Michel Gondran (EDF) déclarait:

"Les représentations graphiques font désormais partie, des systèmes de signes que l'homme a du construire pour retenir, comprendre, analyser, vérifier et communiquer". On peut ajouter, implémenter. Il poursuivait aussi en rappelant à peu près ceci:
"Le développement de l'informatique donne une importance particulière à ces représentations. Ces représentations synthétiques permettent, en un coup d'oeil, de saisir la complexité d'une situation. Elles facilitent la mémorisation visuelle (temporaire ou définitive)".
Autant dire, un bon dessin vaut mieux qu'un long discours. Les réseaux de Pétri trouvent leur place dans cette catégorie de représentations.

Dans cette mème journée furent présentés, entre autres:

"La modélisation par les graphes" M. MINOUX (ENSTA)
"Réseaux de PETRI et applications" C. GIRAULT Institut de Programmation Paris VI

Dans les étapes d'étude, de modélisation, d'analyse, de vérification et de matérialisation des systèmes, l'apport des représentations graphiques n'est plus à démontrer. Les graphes aident le concepteur à concevoir, à modéliser, mais aussi à identifier les problèmes et à proposer les bonnes solutions.

S'agissant de la conception et de la matérialisation des parties contrôle au sein des structures numériques de fortes complexités, l'importance des enjeux (superficie, vitesse, consommation, temps de conception, travail en équipe, .....) s'accommode mal des méthodes empiriques. Ces systèmes imposent une approche méthodique et rigoureuse, de la définition du produit (Cahier des charges) en passant par le développement jusqu'à sa réalisation (implémentation).

Pour tout cela, les réseaux de PETRI me paraissent incontournables.

---

Historique

1962 - Carl Adam PETRI étudie les systèmes à l'université de BONN. Il propose un graphe biparti pour la modélisation de certains systèmes.

1966 - Premières publications sur le "Parallélisme" (machines parallèles et programmation parallèle)

1968 - Les travaux sont repris par un groupe de chercheurs chez:
    Rome Air Developpement Center
    Griffiss Air Force base N.Y
    Travaux conduits par Anatol HOLT.

1969 - Sous l'impulsion de NASLIN alors président de la section automatique de l'A.F.C.E.T (Association Francaise pour la Cybernetique Economique et Technique) se crée le groupe de travail "SYSTEMES LOGIQUES ".

1970 - Applied Data Research s'intéresse à son tour aux Réseaux de Petri en collaboration avec le projet MAC (systèmes concurrents et calculs parallèles). Travaux de référence au M.I.T. Participation déterminante de HACK.

HOLT soutient sa thèse de PhD sur "les blocages dans les systèmes informatiques" (Deadlock).

1972 - Le département de GIRAULT à Paris V s'est intéressé très tot aux RdP. tout particulièrement dans son contenu théorique et ses applications en informatique. Etudes et vérifications des propriétés des RdP entre autres (contributions de BERTHELOT, ROUCAIROL,... ).

Dans le cadre d'un contrat de la Délégation Générale à la Recherche Scientifique et Technique (D.G.R.S.T) et avec le concours de la TELEMECANIQUE, BLANCHARD (ENSTA) applique les RdP à la représentation des cahiers des charges des automatismes logiques industriels. Il propose aussi des méthodes de simplifications et d'implémentations automatisées dans un ouvrage de référence à l'époque "Synthèse des systèmes logiques" par Daclin et Blanchard - Cepadues Editions.

Rapport D.G.R.S.T 71.7.2912 Toulouse 1973 "Automatismes à séquences"
Blanchard, J.C Cavarroc, J. Gillon, J. Marchand, G. Guidez, G. Thuiller

A Toulouse, Le LAAS, avec VALETTE entre autres, se préoccupe de la modélisation des Cahiers des charges et de la commande en temps réel. On pourra consulter son ouvrage "Systèmes de commandes en temps réel" (M. Courvoisier / R. Valette - Editions SCM).

1974 : Contribution significative de James L. PETERSON ( Dpt of sciences - University of Texas) à la diffusion des Réseaux de Pétri.

1975 Tourres (E.D.F), qui préside alors la commission "systèmes logiques", propose le GRAFCET (Graphe de Commande Etape-Transition). Ce sera l'outil de représentation et description du cahier des charges des automatismes séquentiels industriels.

1978 Prunet au L.A.M (Montpellier) poursuit pour l'A.F.C.E.T la mise au point définitive des règles du GRAFCET.

"Je n'ai jamais rencontré de problème qui, correctement formulé, ne devienne pas plus complexe"
  Paul ANDERSON
 
  Domaines d'applications des RdP:

 - Modélisation des systèmes à commandes réparties et distribuées.
 - Spécification, modélisation, simulation et matérialisation des systèmes à comportements asynchrones concurrents et parallèles.
 - Etude comportementale des systèmes temps réels.
 - Evaluation des systèmes et prédictions des performances.
 - Vérification, validation, preuve et garantie à priori du bon fonctionnement des systèmes.
 - Partage de ressources, conflits, synchronisation et accélération des traitements par le parallèlisme.
 - Approche rigoureuse de la conception, de la représentation et de la synthèse des automatismes et systèmes logiques.
 - Représentation et clarification du cahier des charges avec passage rapide et automatisé à la réalisation .
 - Modélisation globale, modularisation et hiérarchisation.
 - Aide au travail en équipe (Pratique d'un seul et mème langage ou outil de représentation).
 - Analyse des risques de dysfonctionnement.
 - Dimensionnement des organes de stockage ou de mémorisation (tailles de buffers, ...... )

---

Publications (de l'époque)

"Automatismes à séquences"
Blanchard, J.C Cavarroc, J. Gillon, J. Marchand, G. Guidez, G. Thuiller
Rapport D.G.R.S.T 71.7.2912 Toulouse 1973

"Synthèse et réalisation de systèmes logiques décrits par réseaux de PETRI, à l'aide de mémoires mortes"
C. ANDRE - Laboratoire des Signaux et Systèmes (LASSY) Université de Nice

"Sur une méthode de conception assistée par ordinateur des systèmes logiques à évolutions simultanées"
C. ANDRE Thèse 3ème cycle NICE 1975

"Synthèse modulaire des automatismes logiques industriels"
BLANCHARD, GILLON, CAVARROC Journée d'étude AFCET section A.T Montpellier 8 Mars 1974

"Du grafcet au réseau de Petri"
René DAVID, Hassane ALLA Editions HERMES (11914 D 02 F 10)

"Réseaux de Pétri et systèmes parallèles"
Armand Colin 1992 G. Vidal Naquet, A. Choquet-Geniet

"Systèmes de commande en temps réel"
R. Vallette M. courvoisier (S.C.M)
(orientation: systèmes d'exploitation - temps réel )

"Comprendre, maitriser et appliquer le GRAFCET"
M. Blanchard (Collection Nabla, Cépadues Editions)

"Le GRAFCET, sa pratique et ses applications"
J.C. Bossy, P. Brard, P. Faugere, C.Merlaud (Educalivre)

"Le GRAFCET " Rapport de la commission Grafcet (1977)
A.F.C.E.T 156, Bd Pereire 75017 Paris

"Le Grafcet, diagramme fonctionnel" A.D.E.P.A 13 - 15 rue Perrier 92120 Montrouge

"Petri nets and GRAFCET" Ed Prentice Hall 1992 R. David, H. Alla

"Un outil graphique interactif pour la vérification des systèmes à évolution parallèle décrits par réseaux de PETRI"
Thèse de diplome de docteur ingénieur par CHEZALVIEL-PRADIN (I.N.S.A.T) Dec 1979
Université Paul SABATIER de Toulouse
Examinateurs: Grateloup, Azema, Blanchard, Boeri, Diaz, Dolle, Kalfon, Betrourne.

---

S'ensuit une longue série de publications ou l'on retrouve régulièrement S. HADDAD.


Cooperative Applications and Multi-Agent Systems
"Hierarchical Agreement in Wide Group Context"
S. HADDAD, F. NGUILLA 12th International Conference on Parallel
and Distributed Computing Systems Radisson Bahia Mar Beach Resort, Fort Lauderdale,Florida USA August 1999

"A consensus protocol using Different Failure Detectors in Large-Scale Networks"
S. HADDAD, F. NGUILLA 14th ISCA-CATA Cancun, Mexique April 1999

"A Formal Study of Interactions in Multi-agent Systems"
A. EL FALLAH SEGHROUCHNI,S. HADDAD, H.MAZOUZI 14th ISCA-CATA Cancun, Mexique April 1999

"Etude des interactions basée sur l'observation répartie dans un sytème multi-agents"
A. EL FALLAH SEGHROUCHNI,S. HADDAD, H. MAZOUZI Journées Francophones IAD et SMA. Eds Hermes. Nancy. Novembre 1998

"A consensus protocol for wide area networks"
A. EL FALLAH SEGHROUCHNI, S. HADDAD, F. NGUILLA
Austrian-Hungarian Workshop on Distributed and Parallel Systems (DAPSYS'98). Budapest, Hongrie, September 1998

"Coordination d'agents rationnels par planification distribuée"
S.BOUSSETTA, A. EL FALLAH-SEGHROUCHNI, S.
HADDAD , P. MORAITIS, M. TAGHELIT Revue d'Intelligence Artificielle. Volume 12 n°1. Janvier 1998

"A Structural Approach to Design Reliable Distributed Applications"
M. TAGHELIT , S. HADDAD , P. SENS
Second European Research Seminar on Advances in Distributed Systems. Zinal. Suisse. Mars 1997.

"A Recursive Model for Distributed Planning" A. EL FALLAH SEGHROUCHNI, S. HADDAD Second International Conference on Multi-Agent Systems. Décembre 1996. Kyoto, Japon

"A Coordination Algorithm for Multi-Agent Planning" A. EL FALLAH SEGHROUCHNI, S. HADDAD Modelling Autonomous Agents in a Multi-Agent Word Janvier 1996. Eindhoven, The Netherlands. Lecture Notes in Artificial Intelligence 1038.

"A Formal Model for Coordinating Plans in Multiagents Systems"
A. EL FALLAH SEGHROUCHNI, S. HADDAD
Proceedings of Intelligent Agents Workshop. Augusta Technology Ltd, Brooks University. Oxford United Kingdom. November 1995.

"Représentation et manipulation de plans à l'aide de réseaux de Petri"
A. EL FALLAH-SEGHROUCHNI, S. HADDAD Deuxièmes Journées Francophones Intelligence Artificielle Distribuée et Systèmes Multi-Agents. Voiron. Mai 1994.

"An Algorithm Providing Fault-tolerance for Layered Distributed Systems"
M. TAGHELIT, S. HADDAD, P.SENS IMACS-IFAC International Symposium on Parallel and Distributed Computing in Engineering Systems Corfou, Grèce. Juin 1991

Verification of Parallel Systems

"Theoretical Aspects of Recursive Petri Nets"
S. HADDAD , D. POITRENAUD 20th International Conference on Application and Theory of Petri Nets. Williamsburg. June 1999.

"Exploiting Symmetry in Linear Time Temporal Logic Model Checking : One Step Beyond"
K. AJAMI, S. HADDAD, J-M. ILIE First International Conference on Tools and Algorithms for the Construction and Analysis of Systems. Lisbonne. Portugal. March 1998

"A Symbolic Reachability Graph for Coloured Petri Nets"
G. CHIOLA, C. DUTHEILLET, G. FRANCESCHINIS, S. HADDAD Theoretical Computer Science 176(1-2) : 39-65 (1997)

"Contribution des réseaux de Petri de haut niveau pour l'étude des protocoles"
S. HADDAD, J.M. ILIE, M. TAGHELIT, C. DUTHEILLET, P. MOREAUX Technique et Science Informatiques. Numéro thématique "Méthodes Formelles : Validation de Systèmes Complexes", Volume 16, N° 6, Juin 1997

"Etude Critique de la Modélisation et de l'Evaluation de Protocoles dans un Environnement Estelle"
S. HADDAD, M. TAGHELIT, B. ZOUARI Revue Electronique sur les Réseaux et l'Informatique Répartie N° 4. Juillet 1996

"Symbolic Reachability Graph and Partial Symmetries"
S. HADDAD , J.M ILIE , M. TAGHELIT , B. ZOUARI
Sixteenth International Conference on Application and Theory of Petri Nets. Turin, Italy. June 1995. Lecture Note in Computer Science 935, p. 238-251.

"Une approche générique des systèmes parallèles"
S. HADDAD, M. TAGHELIT, B. ZOUARI Septièmes Journées Internationales des sciences de l'informatique. Informatique répartie Etat de l'art et perspectives. Tunis. Mai 1994.

"Conflict Sets in Coloured Petri nets"
C. DUTHEILLET, S. HADDAD Third International Workshop on Petri Nets and Performance Models, IEEE-CS Press, Toulouse, Octobre 1993. Actes du congrès p. 76-87

"Synthesis of Impartial Deadlock-free Programs for Concurrent Systems"
J. EZPELETA, S. HADDAD International Conference on Decentralized and Distributed Systems Septembre 1993.Actes du congrès p. 15-26

"A Protocol Specification Language with a High-level Petri Net Semantics"
B. ZOUARI, M. TAGHELIT, S. HADDAD International Conference on Decentralized and Distributed Systems Septembre 1993.Actes du congrès p. 105-122

"An Efficient algorithm for finding Structural Deadlocks in Colored Petri Nets"
K. BARKAOUI, C. DUTHEILLET, S. HADDAD Fourteenth International Conference on application and theory of Petri nets. Chicago, Etats-Unis, Juin 1993.

"Généricité et Parallélisme"
S. HADDAD Congrès biennal de l'AFCET, Paris. Juin 1993.

"Assessment of Estelle and EDT through Real Case Studies"
S. HADDAD, M. TAGHELIT, B. ZOUARI 13th IFIP symposium on Protocol Specification, Testing and Verification. Liege. Belgique. Mai 1993.

"Evaluation paramétrée de formules de logique temporelle"
I. VERNIER, S. HADDAD Cinquièmes rencontres sur le Parallélisme. Brest. France. Mai 1993.

"An Efficient Computation of Structural Relations in Unary Regular Nets"
C. DUTHEILLET, S. HADDAD Seventh International Symposium on Computer and Information Sciences (ISCIS VII), Antalya, Turquie, p. 73-79 Novembre 1992

"A Reduced State Graph for Symmetrical Protocols"
S. HADDAD, J-M. ILIE, B. ZOUARI Rapport IBP/MASI n° 92.57, Septembre 1992

"Evaluation of algorithms using ESTELLE"
S. HADDAD, M. TAGHELIT, B. ZOUARI Rapport IBP/MASI n° 92.37, Juin 1992

"SANDRINE : an analysis for the declaration of AMI-Nets"
X. BONNAIRE, C. DUTHEILLET, S. HADDAD Rapport IBP/MASI n° 92.20, Juin 1992

"Structural analysis of coloured nets. Application to the detection of confusion"
C. DUTHEILLET, S. HADDAD Rapport IBP/MASI n° 92.16, Mars 1992

"Résolution paramétrée de familles de systèmes linéaires"
J-M. COUVREUR, S. HADDAD, J-F. PEYRE RAIRO recherche opérationnelle vol. 26 n° 2 , 1992 p 183-206

"On Well-Formed Coloured Nets and their Symbolic Reachability Graph"
G. CHIOLA, C. DUTHEILLET, G. FRANCESCHINIS, S. HADDAD High-Level Petri Nets. Theory and Application. K. Jensen & G. Rozenberg eds, Springer-Verlag 1991 p. 373-396

" Computation of Generative Families of Positive Semi-Flows in Two Types of Coloured Nets"
J.M COUVREUR, S. HADDAD, J-F. PEYRE Twelth International Conference on Application and Theory of Petri Nets. Aarhus, Danemark , Juin 1991. Actes du congrés p. 122-144

"Résolution paramétrée d'une famille de systèmes d'équations linéaires à solutions positives"
J-M. COUVREUR, S. HADDAD, J-F. PEYRE Rapport de recherche IBP MASI 90.38. Septembre 1990

"Méthodes d'analyse dans les réseaux colorés"
S. HADDAD Journées d'Etude du Firtech Systèmes et Télématique, CNET, Issy les Moulineaux, Janvier 1990, Actes des Journées p 309-319

"A Reduction Theory for Coloured Nets"
S. HADDAD Advances in Petri Nets 1989. Lecture notes in computer science n° 424 Springer-Verlag p. 209-235 (Version préliminaire)

"Validation of Parallel Systems with Coloured Petri Nets"
S. HADDAD, J-M. COUVREUR Parallel Processing IFIP . edited by M. Cosnard, M.H. Barton and M. Vanneschi. North Holland 1988 p. 377-390

"Towards a General and Powerful Computation of Flows for Parametrized Coloured Nets"
S. HADDAD, J-M. COUVREUR Ninth European Workshop on Application and Theory of Petri Nets. Venise, Italie , Juin 1988. Actes du congrès vol. II

"AMI an Extensible Petri Nets Interactive Workshop"
J-M. BERNARD, J-L. MOUNIER, N.BELDICEANU, S.HADDAD Ninth European Workshop on Application and Theory of Petri Nets. Venise, Italie , Juin 1988. Actes du congrès vol. II

"Generalization of Reduction Theory to Coloured Nets"
S. HADDAD Ninth European Workshop on Application and Theory of Petri Nets. Venise, Italie , Juin 1988. Actes du congrés vol. II

"Algebraic Structure of Flows of a Regular Coloured Net"
S. HADDAD, C. GIRAULT Advances in Petri nets 1987. Lectures Notes in Computer Science n° 266 Springer-Verlag p. 73-88 (Version préliminaire)

"Specification and Properties of a Cache Coherence Protocol Model"
C. CHATELAIN, C. GIRAULT, S. HADDAD Advances in Petri Nets 1987. Lectures Notes in Computer Science n° 266 Springer-Verlag p. 1-20

"Une catégorie régulière de réseau de Petri de haut niveau : définition, propriétés et réductions. Application à la validation de systèmes distribués"
S. HADDAD Thèse de l'Université de PARIS 6. Juin 1987. Rapport MASI n° 197

"Un calcul d'une base de flots pour les réseaux colorés"
S. HADDAD Deuxième colloque C.N.R.S. C3. Angoulême, Mai 1987. Actes du congrès p. 205-224 (Version préliminaire)

"Les réseaux réguliers : spécification et validation par le logiciel ARP"
S. HADDAD , J-M. BERNARD Troisième colloque de génie logiciel AFCET. Versailles. Mai 1986. Actes du congrès p. 83-93

Performance Evaluation of Parallel Systems

"Bounds for rewards of systems with client/server interaction"
S. DONATELLI, S. HADDAD, P. MOREAUX, M. SENE 3rd International Meeting on the Numerical Solution of Markov Chain. Zaragoza, Spain September 1999

"Structured Characterization of the Markov Chain of Phase-Type Stochastic Petri Nets"
S. DONATELLI, S.HADDAD, P. MOREAUX Tenth International Conference for Computer Performance Evaluation TOOLS 98. Palma de Majorque, Espagne. September 1998.

"Distributions de Cox et Phase-type dans les réseaux de Petri stochastiques : une méthode efficace de résolution"
S. HADDAD, P. MOREAUX , G. CHIOLA RAIRO -Recherche Opérationnelle vol.32 n°3, 1998

"Efficient Handling of Phase-Type Distributions in Generalized Stochastic Petri Nets"
S. HADDAD, P. MOREAUX , G. CHIOLA Eighteenth International Conference on Application and Theory of Petri Nets. Toulouse, France. June 1997.

"Aggregation and Decomposition for Performance Evaluation of Asynchronous Products of High Level Petri Nets"
S. HADDAD, P. MOREAUX Document du Lamsade n° 102. Mai 1997

"Aggregation and Decomposition for Performance Evaluation of Synchronous Products of High Level Petri Nets"
S. HADDAD, P. MOREAUX Document du Lamsade n° 96. Septembre 1996

"Asynchronous Composition of High-level Petri nets : a quantitative approach"
S. HADDAD, P. MOREAUX
Seventeenth International Conference on Application and Theory of Petri nets. Osaka, Japon. June 1996. Lecture Note in Computer Science 1091, p. 192-211

"Evaluation of High-level Petri nets by means of aggregation and decomposition"
S. HADDAD, P. MOREAUX
Sixth International Workshop on Petri Nets and Performance Models. Durham, NC, USA. October 1995. IEEE Computer Society Press , p. 11-20

"Stochastic Well-Formed Coloured Nets and Multiprocessor Modelling Applications"
G. CHIOLA, C.DUTHEILLET, G. FRANCESCHINIS, S. HADDAD IEEE Transactions on Computers, November 1993, Volume 42, Number 11, p. 1343-1360

"Regular Stochastic Petri Nets"
C. DUTHEILLET, S. HADDAD Advances in Petri Nets 1990. Lecture Notes in Computer Science n° 483 Springer-Verlag p. 186-210

"Aggregation of States in Colored Stochastic Petri Nets: Application to a Multiprocessor Architecture"
C.DUTHEILLET, S. HADDAD Third International Workshop on Petri Nets and Performance Models, IEEE-CS Press, Kyoto, Japon, Decembre 1989. Actes du congrès p. 40-49 (Version préliminaire)