Download pdf - Ch2 Modeles Pour Les SED Avec Supervision 2

5/17/2018 Ch2 Modeles Pour Les SED Avec Supervision 2 - slidepdf.com

http://slidepdf.com/reader/full/ch2-modeles-pour-les-sed-avec-supervision-2 1/25

Systèmes Dynamiques à Evénements Discrets

_____________________________________________________________________________________________________________

Modèles et Systèmes Jean-Louis Ferrier, Jean-Louis Boimond juin 04

____________________________________________________________________________________________1

SYSTÈMES DYNAMIQUES A ÉVÉNEMENTS DISCRETS :DU MODÈLE À LA COMMANDE

Jean-Louis FERRIER, Jean-Louis BOIMOND

ISTIA - Université d'AngersLaboratoire d'Ingénierie des Systèmes Automatisés (LISA)

62 Avenue Notre-Dame du Lac, F-49000 ANGERSe-mail : [email protected]

web : http://www.istia.univ-angers.fr/LISA

Les Systèmes Dynamiques à Evénements Discrets sont une classe de systèmes dynamiques, pour la plupart "man-made" et complexes.

Par opposition aux systèmes dynamiques "continus", ils satisfont généralement les deux propriétés suivantes :a) l' espace d'état est décrit par un ensemble discret

b) les transitions d'état apparaissent seulement en des instants discrets du temps ; ces transitions d'état sont associées à des événements.

De nouveaux outils et de nouvelles méthodologies doivent être développés afin de modéliser, concevoir, analyser les performances et

commander de tels systèmes.

1. INTRODUCTION

2. SYSTEMES A EVENEMENTS DISCRETS

2.1. Un exemple de SED 2.2. Systèmes continus, systèmes à événements discrets

3. DIFFERENTS MODELES POUR LES SED

3.1. Réseaux de Petri 3.2. Algèbre des dioïdes 3.3. Langages et Automates

3.3.1. Langages 3.3.2. Automates

4. COMMANDE DES SED

4.1. Réseaux de Petri de commande

4.2. Suivi de trajectoires : séquences de dates de ti rs

4.3. Commande sous contraintes : un exemple

5. COMMANDE PAR SUPERVISION

6. CONCLUSION




_____________________________________________________________________________________________________________


____________________________________________________________________________________________2

1. INTRODUCTION

Les systèmes automatisés de production, à l'initiative de l'Homme, sont caractérisés par une forte complexitéet flexibilité ; selon un certain point de vue, ils peuvent être spécifiés par des modèles à "événements discrets".

Les systèmes de trafic (aérien, ferroviaire,...), les systèmes de communication, le génie logiciel,... sont d'autresexemples de systèmes dynamiques dont l'activité est due aux occurrences asynchrones d'événements discrets,

dont certaines sont provoquées (appui sur une touche du clavier) et d'autres pas (panne spontanée d'unéquipement) [Ho 89] [Cassandras 93].

Dans la section 2 le concept de Systèmes Dynamiques à Evénements Discrets (SDED), qui sera par lasuite abrégé en Systèmes à Evénements Discrets (SED), sera illustré. Un parallèle avec les systèmesdynamiques "classiques" à variables continues sera tenté et les différences entre ces systèmes1 seront mises en

exergue.Si le cadre de modélisation des systèmes linéaires est bien établi, il n'en est pas de même pour les SED.

Quelques exemples simples illustreront en section 3 les potentialités de modélisation et d’analyse par les réseaux

de Petri, par l'algèbre (max,+), par les automates et les langages.Les notions de signal de commande et de loi de commande dans le cadre des SED seront abordées en

section 4.

En section 5 la commande par supervision, qui repose sur la théorie des langages et des automates, sera

esquissée.

Dans la conclusion, il sera tenté de dégager quelques éléments de réflexion sur cette classe de systèmes

"artificiels" dont le développement depuis quelques décades a été concomitant de celui de l'informatique.

2. SYSTEMES A EVENEMENTS DISCRETS

2.1. Un exemple de SED

Une souris se déplace de manière spontanée (elle agit sans intervention extérieure) à l'intérieur d'unlabyrinthe.

Les salles Si communiquent par des portes

unidirectionnelles P1 et P3 et bidirectionnelle P2.

On note par " pi" l'événement : "la souris passe par

la porte Pi".

fig. 1.a fig. 1.b

Soit ∑ l'ensemble des événements : ∑ = { p1, p2, p3}.

1 Le concept de système est caractérisé par :

- des "composants" en interaction

- une "fonction" particulière qu'il est sensé réaliser, avec le respect d'un ensemble de contraintes.

Quelques définitions de "système" :

* "Un système est un objet complexe, formé de composants distincts reliés entre eux par un certain nombre de relations" - Encyclopaedia

Universalis.

* "An assemblage or combination of things or parts forming a complex or unitary whole" - Webster's Dictionary.

* " A combination of components that act together to perform a function not possible with any of the individual parts" - IEEE Standard

Dictionary of Electrical and Electronic Terms.

P1

P3

P2

S1

S0

S2

A B C 1 2

3

2




_____________________________________________________________________________________________________________


____________________________________________________________________________________________3

On conçoit que les situations (ou comportements) possibles sont :

• la souris est dans la salle S0

• la souris est dans la salle S1

• la souris est dans la salle S2 ce qui définit trois états différents, relatifs aux possibilités d'occupation des salles.Le passage de l'état "souris en S0" (état A) à "souris en S1" (état B) a lieu sur l'occurrence de l’événement p1. On

peut alors construire le diagramme des états (fig. 1.b). L'espace d'état s'écrit X = { A, B, C }.

2.2. Systèmes continus, systèmes à événements discrets

Des grandeurs telles que la position, la vitesse, l'accélération, le niveau, la pression, la température, le débit,la tension, le courant,... sont des variables continues, dans le sens qu'elles peuvent prendre n'importe quelle valeur

dans R lorsque le temps, lui-même "continu", évolue. Les équations différentielles (et aux différences) sont alors

un outil de base approprié pour la modélisation, l'analyse et la commande des systèmes physiques à temps continu

(et à temps discret) correspondants, de même que pour des systèmes autres que physiques et/ou à base de lois dela nature (i.e., dynamique des populations).

Comme nous pouvons le constater sur l'exemple présenté au § 2.1., notre environnement est fait aussi de

systèmes pour lesquels :- les grandeurs auxquelles nous avons affaire sont discrètes, telles que le nombre de produits dans un stock, lenombre de processeurs en activité, ...- l'évolution est conditionnée par l'occurrence d'événements, à "certains instants", tels que la fin d'exécution d'unetâche, le franchissement d'un seuil devant entraîner une action, l'arrivée d'un produit, d'un client, la défaillanced'un dispositif, ...

On sait que le comportement d'un système continu à l'instant t peut être résumé par son état qui représentela mémoire minimale du passé nécessaire à la détermination du futur2.

Pour les modèles à état continu, l'espace d'état est un continuum composé de tous les vecteurs à n

dimensions à composantes dans R (fig. 2.a). Dans la description des systèmes échantillonnés avec une période

T e, généralement constante, la variable réelle t est remplacée par la variable entière k . Ces systèmes sont décritspar des équations aux différences. Il est important de noter que la discrétisation du temps n'implique pas la

discrétisation de l'espace d'état. L'état peut prendre n'importe quelle valeur dans l'ensemble des nombres réels,comme dans le cas continu. On ne distinguera donc pas fondamentalement dans la suite les systèmes décrits par

des équations différentielles et par des équations aux différences : ils sont simplement à temps continu ou à temps

discret et la variable temps est une variable naturelle indépendante qui apparaît comme argument de

toutes les fonctions d'entrée, d'état ou de sortie.

2 L'état X (t i) d'un système au temps t i est l'information nécessaire en t i telle que la sortie y(t ), pour tout t ≥ t i, est uniquement déterminée à partir

de cette information X (t i) et de la connaissance du signal d'excitation u(t ), pour t ≥ t i.L'espace d'état d'un système est l'ensemble de toutes les valeurs possibles que peut prendre l'état, c’est ici un continuum.

Un modèle de système s'écrit dans l'espace d'état sous la forme générale (cas continu) :

X t•

( ) = f ( X (t ), u(t ), t ) X (t 0) = X 0

y(t ) = g( X (t ), u(t ), t )

Dans le cas des systèmes linéaires invariants dans le temps cette forme se réduit à :

temps continu temps discret

X t•

( ) = A X (t ) + Bu(t ) X (t 0) = X 0 X (k +1) = F X (k ) + Gu(k ) X (k 0) = X 0

y(t ) = C X (t ) + Du(t ) y(k ) = C X (k ) + Du(k)




_____________________________________________________________________________________________________________


____________________________________________________________________________________________4

Pour les modèles à événements discrets (fig. 2.b), l'espace d'état est un ensemble discret et l'état

change seulement à certains instants du temps , de façon instantanée. A chacune de ces transitions, on peut

associer un événement, d'où la définition informelle d'un SED.

Dans le jeu d'échec par exemple, chaque configuration définit un état. L'espace d'état résultant est grand, mais discret.

étatX (t ) =

x (t )x (t )

1

2

x 2

x 1

X

temps

2X 6X 4

X 1

X 5

X 3

e 1 e 2 e 3 e 4 e 2 e 5 e 6 e 7

t t j t k t m t n t o t p

(espace d'état discret X)

événement

t li

état

fig. 2.a

X = { X 1, X 2, X 3, X 4, X 5, X 6 } ensemble (discret) d’états = espace d’états

∑ = { e1, e2, e3, e4, e5, e6, e7 } ensemble d'événements discret

fig 2.b

fig. 2. Comparaison des trajectoires pour

a) un modèle à état continu (système continu)

b) un modèle à événements discrets (SED)

La trajectoire (constante par morceaux) saute d'un état à un autre avec l'occurrence d'un événement

Remarques : • un même événement (e2) peut conduire à des états différents.

• des événements différents (e1 et e5) peuvent conduire à un même état • des événements (e3) peuvent se produire et être inactifs pour ce système

• la séquence des états et le temps de maintien associé à chaque état caractérisent la trajectoire.

Lorsque l'entrée du SED est spécifiée de manière déterministe comme une séquence d'événements{e1, e2,...}, sans information sur le temps auquel les occurrences de ces événements se produisent, partant d'un

état initial, on décrit la trajectoire en termes de séquence d'états résultants : on a un modèle non temporisé qui décrit le comportement logique du système et qui permet de répondre en particulier à la question :"Un état particulier peut-il être atteint ?"

Un Système à Evénements Discrets est un système à espace d'état discret dont les transitions entre états sontassociées à l’occurrence d’événements discrets asynchrones.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________5

Lorsque l'entrée du SED est spécifiée de manière déterministe comme une séquence d'événements auxquels

sont associées les dates d'occurrence t i, on peut construire la trajectoire complète du modèle temporisé et

répondre notamment aux questions :"Quand un état particulier sera-t-il atteint ?""Combien de temps le système passe-t-il dans un état particulier ?"

"Combien de fois un état particulier peut-il être atteint sur un intervalle de temps donné ?"




_____________________________________________________________________________________________________________


____________________________________________________________________________________________6

3. DIFFERENTS MODELES POUR LES SED

Rappelons qu'un modèle est une approximation, une vue partielle plus ou moins abstraite de la réalité afin del’appréhender plus simplement, selon un point de vue et qu’il est établi pour un objectif donné.

Un modèle est donc subjectif puisqu'il est établi en fonction des objectifs, du jugement, de la nature et de laqualité des informations dont dispose le concepteur. Il peut être exprimé par des mathématiques, des symboles,

des mots,...[Calvez 90].Seront présentés succinctement les réseaux de Petri, l’algèbre (max,+), les langages et automates, trois outils

de modélisation et d'analyse des systèmes qui trouvent également une application en commande.

3.1. Réseaux de Petri

Les réseaux de Petri (RdP), qu’ils soient ordinaires, généralisés, colorés, temporisés, temporels,stochastiques,... sont un outil graphique à support mathématique permettant de modéliser, visualiser et analyserdes évolutions comportant du parallélisme, de la synchronisation et du partage de ressource [Brams 83] [Murata89] [David et al. 89] [Alla et al. 00].

Un RdP ordinaire non marqué peut être défini par un 4-uplet, Q = ⟨P, T , Pré, Post⟩ tel que :

P = {P1, P2, ..., Pn} est un ensemble fini et non vide de places ;

T = {T 1, T 2, ..., T m} est un ensemble fini et non vide de transitions ;

P∩ T = ∅ c’est-à-dire que les ensembles P et T sont disjoints (avec P ∪ T ≠ ∅) ;

Pré : P × T → {0,1} est l’application d’incidence avant ;

Post : P × T → {0,1} est l’application d’incidence arrière.

Pré(Pi , T j) est le poids de l’arc (orienté) reliant la place Pi à la place T j ; ce poids vaut 1 si l’arc existe et 0 sinon. Post(Pi, T j) est le

poids de l’arc (orienté) reliant la transition T j à la place Pi.

Un RdP généralisé non marqué est défini comme un RdP ordinaire non marqué, sauf que :

Pré : P × T → ℵ et Post : P × T → ℵ .

Un RdP marqué, ordinaire ou généralisé, est un RdP auquel on associe un marquage initial m0 à la structure définie précédemment.

On appelle matrice d’incidence avant la matrice W- = [wij-] , où wij

- = Pré(Pi, T j), et matrice d’incidence arrière la matrice

W+ = [wij+] , où wij

+ = Post(Pi, T j).

On appelle matrice d’incidence , la matrice W = W+ - W- = [wij] de dimension n × m. Une colonne de cette matrice correspond à

la modification du marquage apportée par le franchissement de la transition correspondante. La matrice d’incidence est une

représentation structurelle du RdP, elle est indépendante du marquage.

Le franchissement d’une transition T j ne peut s’effectuer que si le marquage de chacune des places Pi directement en amont de cette

transition est tel que : m(Pi) ≥ poids (Pi → T j) = wij- (condition nécessaire). Le franchissement (tir) de T j consiste à retirer wij

- marques

dans chacune des places directement en amont de T j et à ajouter wij+ marques dans chacune des places directement en aval de T j .

Un RdP P-temporisé (respectivement T -temporisé) est un 2-uplet⟨ R, Tempo

⟩ tel que :

R est un RdP marqué ;

Tempo est une application de l’ensemble P des places (respectivement de l’ensemble T des transitions) dans l’ensemble des

nombres rationnels positifs ou nuls. Tempo(Pi) = d i est la valeur de la temporisation associée à la place Pi (respectivement Tempo(T j)

= d j est la valeur de la temporisation associée à la transition T j).

On notera aussi l’existence des RdP P-temporels (respectivement T-temporels), pour lesquels on associe aux places (respectivement

aux transitions) une temporisation dont la valeur se situe à l’intérieur d’un intervalle [a, b]. Cette situation se rencontre typiquement

pour les bains de trempage ou les fours pour lesquels une pièce doit séjourner entre une durée minimale et une durée maximale.

Un RdP synchronisé est un 3-uplet ⟨ R, E , Sync⟩ tel que :

R est un RdP marqué ;

E est un ensemble d’événements externes ;

Sync est une application de l’ensemble T des transitions de R dans E ∪ {e}, où e est l’événement toujours occurrent.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________7

Exemple : Un système du type file d'attente élémentaire est représenté fig. 3.a. Chaque client qui arrive est, soit serviimmédiatement par le serveur, soit il doit d'abord attendre dans la file jusqu'à ce que le serveur soit disponible.Après avoir reçu le service, chaque client repart. Vue comme un SED, on associe à la file d'attente un ensemble

d'événements ∑ = {a, s, d } où a désigne l'événement "arrivée du client ", s l'événement "démarrage duservice" et d l'événement "départ du client ". La fig. 3.b représente une modélisation de ce procédé par réseau

de Petri synchronisé :

P = {F , SO, SL} ; T = {T 1, T 2, T 3} ; ∑ = {a, s, d } ; m0T = [0, 0, 1]

avec F : file, SO : serveur occupé, SL : serveur libre, Σ : ensemble des événements externes

• le tir de la transition source T 1 est lié à

l’occurrence de l’événement a.

• le tir de la transition T 2 est lié à 2

conditions :- validation par la présence d'au moins un

client dans la file F (matérialisée par la

présence d’au moins un jeton dans la place

F ) et le fait que le serveur soit libre

(présence d’un jeton dans la place SL),

- le démarrage effectif du service

(occurrence de l’événement s).

• un jeton dans la place SO indique que le

serveur est occupé.

fig. 3.a fig. 3.b

L'état du système modélisé par le RdP est représenté par le vecteur de marquage définissant le nombre de

jetons que contient chaque place. L’évolution de l’état (dynamique du système) correspond donc à une évolutiondu marquage. L’évolution du marquage se produit par le franchissement de transitions : à l'occurrence d'unévénement correspond le franchissement d'une transition, si certaines conditions sur le marquage de ses placesamont sont satisfaites (dans le cas d’un RdP autonome seuls les marquages des places interviennent pour lefranchissement des transitions). L'espace des marquages accessibles tient lieu d'espace d'états.

Par analyse, deux types de propriétés sont étudiées à partir d’un modèle RdP :

• celles indépendantes du marquage initial (propriétés de structure),

• celles dépendant du marquage initial (propriétés de comportement).Parmi les principales propriétés que l’on peut extraire du modèle citons la bornitude, la vivacité (non blocage),

l’accessibilité, la réinitialisabilité, la présence de conflits effectifs, le temps de cycle (pour un RdP temporisé), etc.Les principales méthodes d’analyse des propriétés peuvent être classées en trois groupes :

• graphe des marquages ou de l’arborescence de couverture. Une arborescence est un graphe particuliercomposé d’arcs orientés qui divergent progressivement à partir d’un nœud appelé racine de l’arborescence(une arborescence ne contient pas de circuit),

• algèbre linéaire (dans ℵ),

• réduction de RdP.L'algèbre linéaire rend possible l'étude de propriétés structurelles, en particulier par la recherche des

invariants linéaires de places (composantes conservatives) et des invariants linéaires de transitions (composantes

répétitives) et donne aussi des résultats dépendant du marquage. On peut en déduire si le réseau est borné ousauf, sans blocage et s'il est réinitialisable ou vivant.

arrivée

client

File Serveurdépart

client

a T 1 arrivée client

SL F

s T 2 démarrage service

SO

d T 3

départ client

(fin du service)




_____________________________________________________________________________________________________________


____________________________________________________________________________________________8

Si depuis un marquage mi, on atteint un marquage mk avec la séquence de franchissement S (de vecteur

caractéristique s de dimension m dont la composante numéro j correspond au nombre de franchissements de latransition T j dans S), on peut écrire l'équation fondamentale :

mk = mi + W ⋅ savec W la matrice d'incidence du réseau.

On notera deux structures particulières de RdP :

• les graphes d’état, tels que toute transition a exactement une place d’entrée et une place de sortie. Ilspermettent de visualiser des conflits (décisions), mais pas des phénomènes de synchronisation ;

• les graphes d’événements, tels que toute place a exactement une transition d’entrée et une transition de sortie.Ils permettent de visualiser des phénomènes de synchronisation mais pas de conflits. De nombreux résultatsexistent pour cette sous-classe de modèles.

Un RdP peut décrire un fonctionnement qui dépend du temps. Pour évaluer les performances dynamiques(temporelles) du modèle, on peut associer des temporisations (nombres rationnels) aux transitions ou aux places.Sous certaines conditions, après un certain régime transitoire, le réseau fonctionne en régime permanent. Pourétudier le régime stationnaire (régime permanent) d'un RdP temporisé, on s'intéresse aux fréquences defranchissement des transitions, ce qui permet de déterminer une période minimale de fonctionnement d'un réseautemporisé3 [Sifakis 79] [Ramamoorthy et al. 80] [Mares et al. 94].

3.2. Algèbre des dioïdes

La structure algébrique de dioïde permet de modéliser et d’évaluer les performances de certains systèmes à

événements discrets, essentiellement les graphes d'événements temporisés (GET)4, via des équations d’étatlinéaires, ce qui n'est pas possible par utilisation de l'algèbre classique [Baccelli et al. 92].

Cette approche présente de grandes analogies de forme avec la théorie "classique" des systèmes linéairescontinus.

A la différence du modèle d’état classiquement associé à un RdP, l’état considéré ici pour aboutir à cettereprésentation linéaire est associé non plus aux places des GET mais à leurs transitions. Le temps, associé aux

événements, est intégré de manière naturelle à cette classe de modèles.

L’ensembleR∪ {-∞}, muni des lois max (notée ⊕) et + (notée ⊗) est un dioïde car il respecte les axiomes suivants :

l’opération ⊕ est associative ((a ⊕ b) ⊕ c = a ⊕ (b ⊕ c)), commutative (a ⊕ b = b ⊕ a), idempotente (a ⊕ a = a) et admet un élément

neutre noté ε (c’est-à-dire (a ⊕ ε= a)) ;

l’opération ⊗ est associative, distributive par rapport à ⊕ (c’est-à-dire ((a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c))), admet un élément neutre noté e

(c’est-à-dire (a ⊗ e = e ⊗ a = a)) et un élément absorbant ε (c’est-à-dire (a ⊗ ε= ε ⊗ a = ε)).

∀ a, b ∈ R∪ {-∞}, a ⊕ b = max(a, b) et a ⊗ b = a+b ; ε= -∞ et e = 0. Généralement on écrira ab pour a ⊗ b.

La structure algébrique (R∪ {-∞}, ⊕, ⊗), notéeRmax, est un dioïde commutatif (⊗ est commutative).

3

• La borne minimale de la période de fonctionnement, ou temps de cycle, pour un RdP P-temporisé s’exprime par :

τmin = max {xk T ⋅ D ⋅ W+ ⋅ y / xk

T ⋅ m0}, l’expression entre accolades étant évaluée pour chaque P-invariant xk T.

D est une matrice diagonale telle que Dii = d i ; W+ est la matrice d’incidence arrière ; y est le T-invariant.

• Soit un graphe d’événements temporisé fortement connexe. L’ensemble de ses circuits élémentaires est C = {C 1, C 2, ...}. Soient C k un circuit

élémentaire, d (C k ) la somme des valeurs des temporisations des places composant ce circuit et m(C k ) la somme des valeurs des marquages des

places composant ce circuit. On montre alors que la borne minimale (fonctionnement en vitesse propre) du temps de cycle pour le graphe

d’événements considéré s’exprime simplement par :

τmin = max {d (C k ) / m(C k )}, l’expression entre accolades étant évaluée pour chaque circuit élémentaire C k ∈ C .

4 On rappelle que les graphes d'événements (GE) sont une sous-classe des réseaux de Petri ; ils modélisent des actions qui coopèrent en se

transmettant des résultats, mais ne permettent de modéliser ni des choix, ni des conflits d'allocation de ressources entre processus.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________9

De manière duale on définit le dioïde noté Rmin par la structure algébrique (R∪ {+∞}, ⊕, ⊗), les opérations ⊕ et ⊗ étant

définies par a ⊕ b = min(a, b) et a ⊗ b = a + b, avec ε= +∞ et e = 0.

La plus petite solution de l’équation linéaire x = ax ⊕ b est donnée par x = a*b avec a* = ⊕k ∈ N ak .

L’équation linéaire ax = b n’admet pas toujours une solution unique (quand elle existe). Cependant, il existe un sous-ensemble S de sous-

solutions ayant une borne supérieure. Cette borne est appelée résiduée à gauche de b par a.

Pour obtenir un modèle linéaire au sens de Rmax, il faut que le RdP associé soit un graphe d'événements.

Dans l'approche (max,+), l'état est constitué des dates de franchissement des transitions et xi(k ) représentela date du k

e franchissement de la transition T i. On associe à la place Pi la temporisation d i ; un jeton arrivé dansla place Pi doit rester dans cette place pendant d i unités de temps (il est indisponible). Le k

e tir de T i peut seproduire après la k

e arrivée d’un jeton dans les places en amont de T i ; ces places auront donc reçu de leurs

transitions amont (une transition pour chaque place), la quantité k - m0(Pi) jetons, où m0 est le marquage initial du

graphe. A chaque transition T i , on peut associer une application appelée dateur xi : k → xi(k ).

Si, au lieu de s’intéresser aux dates de franchissement des transitions d’un graphe d’événements temporisé, onconsidère le nombre de franchissements des transitions jusqu'à l’instant t , la description du comportement du

graphe peut se représenter par des équations (min,+)-linéaires. A chaque transition T i , on peut associer une

application appelée compteur xi : t → xi(t ).

Exemple :

Considérons une machine susceptible de fabriquer une pièce en d 3 unités de temps. Cette durée inclut lechargement et le déchargement [Boimond 93]. La machine est pourvue d’un stock d’entrée. Le modèle dusystème est représenté ci-dessous :

fig. 4

Le tir de la transition T 0 indique qu’une pièce pénètre dans le

stock d’entrée représenté par la place P1.Le tir de T 1 représente le chargement de la pièce sur la machine

quand celle-ci est libre (jeton alors présent dans la place P2) et

qu’une pièce est présente dans le stock d’entrée.

La temporisation d 3 associé à la place P3 représente le temps de

fabrication.

Le tir de T 2 indique que la fabrication d’une pièce est terminée,

la machine est disponible.

Dans l’algèbre (max,+), le comportement du modèle au plus tôt (l’inégalité ≥ entre le premier et le

deuxième membre des deux équations ci-dessous devient l’égalité =) est décrit par : x1(k +1) = max ( x2(k ), x0(k +1)) et x2(k ) = x1(k ) + d 3

qui s’écrit, en omettant ⊗ pour alléger l'écriture,

x1(k +1) = d 3 x1(k ) ⊕ x0(k +1)

x2(k ) = d 3 x1(k ) où x1, x2, x0 sont des scalaires.

En posant, par analogie avec la théorie des systèmes, x0(⋅) = u(⋅) et x2(⋅) = y(⋅), alors l’équation d’état et

l’équation de sortie s’écrivent :

x1(k +1) = d 3 x1(k ) ⊕ u0(k +1)

y(k ) = d 3 x1(k )

Cette représentation d’état peut se généraliser pour un modèle relatif à un système plus complexe (MIMO)et toujours se ramener à une forme récurrente markovienne du type :

T 0

P1

T 1

P2

P3

T 2

d 3




_____________________________________________________________________________________________________________


____________________________________________________________________________________________10

X (k ) = AX (k -1)⊕ BU (k )Y (k ) = CX (k )

où ul( j), xi( j) et y p( j) représentent ici les temps auxquels ont lieu respectivement les je tirs de ul (entrée ou

commande), de xi (transition T i), de y p (transition de sortie).

Les lois ⊕ et ⊗ utilisées pour le calcul matriciel suivent les mêmes règles que celles de l'algèbre usuelle :

Si A ∈ (Rmax)n× p, B ∈ (Rmax)n× p, alors C = A ⊕ B, avec cij = aij ⊕ bij = max(aij, bij).

Si A ∈ (Rmax)n× p, B ∈ (Rmax) p×q, alors C = A ⊗ B, C ∈ (Rmax)n×q et cij =⊕k

(aik ⊗ bkj) = maxk

(aik + bkj).

L’élément neutre pour ⊗ est la matrice identité, notée e, dont les éléments sur la diagonale principale sont égaux à 0 et tous les autres à

−∞ ; l’élément neutre pour ⊕ est la matrice zéro, notée ε, dont tous les éléments sont égaux à −∞.

Si l’entrée n’est pas une contrainte pour l’évolution de l’état du GET, celui-ci fonctionne alors en régime

autonome. Le calcul de la valeur propre λ de la matrice d’évolution A (cas irréductible)5 d’un GET permet de

déduire la période du régime stationnaire : la valeur propre λ correspond au temps de cycle du GET, c’est-à-dire au temps séparant deux tirs consécutifs d’une transition. Ce régime périodique est généralement atteint après

un régime transitoire fini. La séquence et les dates de franchissement des transitions peuvent être déterminéesanalytiquement pour le régime transitoire. On détermine ainsi avec précision le début du régime permanent

[Mares et al. 94].

Outre la représentation d’état présentée, il est possible d’obtenir une représentation du comportemententrée-sortie des systèmes étudiés :

• la sortie correspond à une sup-convolution de la réponse impulsionnelle par l’entrée ;

• la sortie d’un GET mono-entrée mono-sortie apparaît comme le produit d’une série de transfert par une série

d’entrée par l’utilisation des transformées en γ et en δ (analogues à la transformée en z) ;

• la prise en compte simultanée des aspects événementiel et temporel conduit à une représentation bi-dimensionnelle et à l’établissement d’une matrice de transfert entrée-sortie.

3.3. Langages et Automates

Ils permettent de traiter mathématiquement les problèmes relatifs aux SED, essentiellement d’un point de

vue logique (analyse qualitative).La théorie des automates à états finis (à nombre d’états fini) a été principalement développée avec la théorie

des langages. Ces modèles reviennent à spécifier des ensembles d’états et des transitions entre ces états[Arnold 92].

Chaque SED a un ensemble d’événements qui lui est associé, ces événements font évoluer le SED. Cet

ensemble Σ peut être vu comme un alphabet d’un langage et les séquences d’événements sont des mots (aussiappelés chaînes) de ce langage. Un automate est alors un dispositif qui engendre un langage en manipulantl’alphabet (les événements).

3.3.1. Langages

5Le problème de la recherche de valeurs propres et vecteurs propres de la matrice A s’exprime comme la recherche de couples (λ, v), avec v ≠ ε

tels que :

A ⊗ v = λ ⊗ v.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________11

Un langage L, défini sur un alphabet Σ, est un ensemble de mots, ou de chaînes, formés à partir des (étiquettes des) événements dans Σ . La

longueur d’un mot s, notée s , correspond au nombre d’événements qui le composent.

Soit Σ = {α, β, γ } un alphabet. On peut alors définir un langage, par exemple, L1 = {ε, α, αββ} constitué de 3 mots seulement où le mot

vide est noté ε, soit Ø=ε . Un langage L2 tel que L2 = {tous les mots possibles de longueur finie qui démarrent avec l’événement α}

comporte un nombre "infini" de mots, ce langage ne peut pas être totalement décrit par une énumération.

La classe des langages réguliers peut être représentée par une expression régulière, expression compacte. Des opérations sur

des ensembles sont ainsi transformées en des opérations algébriques sur des expressions régulières. Les expressions régulières sont définiesà partir d’expressions élémentaires et des opérations de concaténation, d’union, de fermeture itérative6 [Hopcroft et al. 79]. Les

expressions régulières sur ∑ sont les expressions formées par les règles suivantes :

• ∅ , ε et les éléments de ∑ sont des expressions régulières,

• si r 1 et r 2 sont des expressions régulières, alors (r 1 ⋅ r 2), (r 1 + r 2), (r 1)* et (r 2)

* sont des expressions régulières.

Un exemple de calcul de L* : soit { }cbaabc L ,= , alorsn

n L L

∞

=∪=

0

*. On calcule de manière itérative { }ε=0

L , { }cbaabc L L L ,01 == ,

{ }{ } { }cbacbacbaabcabccbaabcabccbaabccbaabc L L L ,,,,.,12 === , 23 L L L = , etc., ce qui conduit à

{ },...,,,,,,*

cbacbacbaabcabccbaabcabccbaabc L ε= . La concaténation n’est pas commutative baab ≠ .

Le théorème de Kleene établit l’équivalence entre les langages réguliers et les langages modélisables par des automates finis : il existe

toujours un automate qui génère un langage régulier donné et, à l’inverse, le langage d’un automate s’exprime toujours par une expression

régulière.

Quelques opérations sur les ensembles, utilisées par la suite, méritent d’être présentées.

L’ensemble ∑ * est un ensemble infini qui contient tous les mots susceptibles d’être formés à partir des éléments de ∑.

La notation ∑1− ∑2 correspond à la différence de deux ensembles :

∑1 − ∑2 = {σ σ est dans ∑1 et σ n’est pas dans ∑2}.

Le power set d’un ensemble ∑, noté 2∑, est l’ensemble de tous les sous-ensembles de ∑. Soit { }ba ,=Σ , alors { } { } { }{ }baba ,,,,Ø2 =Σ .

Une chaîne s1 est dite préfixe d’une chaîne s3 s’il existe une chaîne s2 ∈ ∑ * telle que s1s2 = s3. Une chaîne est le préfixe d’elle-même.

Le langage Préf( L) est la fermeture préfixielle d’un langage L. Le langage Préf( L) consiste en tous les préfixes des mots de L :

Pref( L) = {s1 ∈ ∑ * ∃ s2 ∈ ∑ *, s1s2 ∈ L}.

Un langage L est fermé par ses préfixes (ou préfixe-clos) si L = Préf( L). Par exemple, { }αββαε ,,= L n’est pas préfixe-clos ;

{ }αββαβαε ,,,= L est préfixe-clos.

Exemple :

Soit Σ = {α, β, γ }, l’expression régulière (α + β)⋅γ * dénote le langage infini L = {α, β, αγ , βγ , αγγ , βγγ , αγγγ ,...}.

Il est à remarquer qu’un langage régulier n’est pas nécessairement constitué d’un nombre fini de mots. Enrevanche, tout langage fini peut être décrit par une expression régulière : si { }nsss L ,,, 21 K= , alors l’expression

régulière nsss +++ L21 définit ce langage.

3.3.2. Automates

Les automates considérés seront des automates finis (dont le nombre d’états est fini) et déterministes.

Un automate fini peut être défini par un 5-uplet A = ( X, Σ, f , x0, X F ) tel que :

X est l’ensemble (fini) des états ; c’est l’espace des états, il est discret ;

Σ est un alphabet fini ;

f est la fonction de transition (partielle si non définie pour certaines valeurs) d’état f : X × Σ → X ;

6 Soient l’alphabet Σ et deux langages A et B construits sur ce même alphabet.

• Concaténation : A⋅ B = {w w = u⋅v, u∈ A, v∈ B} ; l’élément neutre pour l’opération " ⋅" est le mot vide ε, à savoir r ⋅ε= ε⋅r = r .

• Union : A ∪ B = {w w ∈ A ou w ∈ B}.

• Fermeture itérative (étoile de Kleene) : A* = ∪=

∞

n 0 An

avec A0

= ε et An

= A⋅ An-1

, ∀ n ≥ 1. L’expression régulière associée à r *

est alors : r *

= ε

+ r + rr + rrr + ... on obtient un ensemble infini de chaînes.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________12

x0 est l’état initial ;

X F est l’ensemble d’états finals, X F ⊆ X.

L’état courant xi du système modélisé par l’automate résume l’information sur le passé. Cette information est suffisante pour déterminer

l’évolution future, connaissant les entrées appliquées appartenant à l’ensemble Σ .

Un langage L engendré par un automate (d’états) fini A est dit régulier. On le note L( A).

Exemple : Soit l’automate représenté figure 5. L’état initial est repéré par une flèche entrante, l’état final x j, aussi appeléétat marqué, est représenté par un double cercle.

Soit Σ = {α, β} et l’expression régulière (α + β)*α.

Le langage L décrit par l’expression régulière (α + β)*α peut être reconnu par l’automate fini de la figure 5 ;c’est le langage marqué Lm qui s’exprime par : { }K,,,,,, βαααβααααβαααα=m L .

xi x j

α

β

β

α

fig. 5

où X = { xi, x j}

x0 =

xi ;

X F = {

x j}et

f ( xi, α) = x j f ( xi,β) = xi

f ( x j,α) = x j f ( x j,β) = xi

L’automate engendre le langage L( A) décrit par l’expression régulière ( ) ( ) αβαβα ∗∗ +++ . Ce langage

s’exprime par : ( ) { }K,,,,,,,,,, βαααβααααβββααβααβαε= A L .

Une chaîne, ou séquence, s appartient au langage L d’un automate si f ( x0, s) ! (c’est-à-dire si f ( x0, s) estdéfinie). Une chaîne s est reconnue par un automate si f ( x0, s) = x avec x ∈ X F .

Soit P l’automate modélisant le comportement d’un procédé. Soit L(P) tel que L(P) ⊆ ∑ * et L(P) non vide,

le langage constitué de tous les mots de l’automate P donné. Toute séquence d’événements qui se produit dans

l’automate est précédée de ses préfixes, donc L(P) = Préf( L(P)). Le langage Lm(P) tel que Lm(P) ⊆ L(P) estappelé langage marqué de l’automate, il est constitué de tous les mots de l’automate dont l’exécution traduit laréalisation d’une tâche (on atteint un –ou plusieurs- état final, c’est-à-dire marqué). Généralement, le langagemarqué n’est pas fermé par ses préfixes : les premières étapes d’une tâche ne représentent pas la réalisation decette tâche. Le couple ( L(P), Lm(P)) ainsi défini modélise le comportement de l’automate et du SED sous-jacent.

Un automate est dit déterministe si l’état initial est unique et si la relation de transition, appliquée à un couple

( xi, σ), définit toujours un unique état. Un automate non déterministe peut avoir plusieurs états initiaux, et sa

relation de transition est définie par f : X × ∑ → 2 X et non plus par f : X × ∑ → X .Un état x j ∈ X est dit accessible s’il existe une chaîne s ∈ ∑ * telle que x j = f ( x0, s), c’est-à-dire que

l’automate peut y accéder depuis l’état initial.

Un état xi ∈ X est dit co-accessible s’il existe une chaîne s ∈ ∑ * telle que x j = f ( xi, s) ∈ X F , c’est-à-direque à partir de cet état l’automate peut atteindre un état marqué.

Un automate A est qualifié de non-bloquant lorsque tout état accessible est co-accessible, ce qui s’écritaussi : L( A) = Préf( Lm( A)) ; toute chaîne qui peut être générée par A est le préfixe d’un mot marqué.

Si on suppose qu’un langage est décrit par une expression régulière, on sait alors construire l’automate fini

associé à ce langage. Le problème inverse consiste à construire une expression régulière décrivant L( A) à partird’un automate A.

Exemple :




_____________________________________________________________________________________________________________


____________________________________________________________________________________________13

Soit l’automate A de la fig. 6.

x1

x2

x3

x4

x5

a b b

ac

fig. 6

Procédons à la mise en équation du modèle afin d’établir le langage et le langage marqué correspondants del’automate A [Gouin 99]. Le langage )( A L correspond à tout ce qui peut être fait depuis l’état initial 1 x . Le

langage marqué )( A Lm correspond à tout ce qui peut être fait à partir de l’état initial pour atteindre un –ou

plusieurs- état marqué.Deux résultats sont nécessaires pour la résolution des équations :

la plus petite solution de l’équation X = AX + B est X = A*

B (1)et la plus petite solution de l’équation X = XA + B est X = BA

*. (2)

• Langage L( A).Depuis chaque état, il faut décrire tout ce que l’automate peut faire (mise en équations), puis procéder parsubstitution pour définir l’équation de l’état initial 1 x uniquement par des événements (résolution de l’équation).

L’automate A se traduit par le système :

x1 = ax2 + ε

x2 = bx3 + cx5 + ε

x3 = ax2 + bx4 + ε

x4 = x5 = ε

La première équation exprime que depuis x1, l’automate peut rester dans l’état x1 (événement ε), ou atteindrel’état x2 (sur occurrence de l’événement a).

En procédant par substitution, on obtient :

x3 = ax2 + b + ε

x2 = bx3 + c + ε = bax2 + bb + b + c + ε

= (ba)* (bb + b + c + ε) (application de (1)).Ainsi :

x1 = a(ba)*(bb + b + c + ε) + ε = a(ba)*(ε + b + c + bb) + ε = L(A).

• Langage Lm( A).Ce langage représente tout ce que l’automate peut faire à partir de l’état initial pour atteindre un état marqué.

Une première méthode, qui pourrait être qualifiée de "backward", procède de la manière suivante : pour tout étataccessible et co-accessible -c’est-à-dire dans l’exemple 4321 ,,, x x x x ( 5 x n’est pas co-accessible)-, il faut

chercher comment l’automate a pu arriver dans cet état, puis procéder par substitution pour résoudre l’équationde l’état marqué. Si l’automate contient plusieurs états marqués, il faut résoudre une équation par état marqué etle langage sera un « ou » entre ces différentes équations. L’automate A donne lieu au système :

x1 = ε ; x2 = x1a + x3a ; x3 = x2b ; x4 = x3b.

En procédant par substitution et en appliquant la relation (2), soit par exemple ba xa x 22 += , d’où ( )∗= baa x2 ,

on aboutit à : x4 = a(ba)*

bb = Lm( A).Une deuxième méthode, qui pourrait être qualifiée de "forward", procède de la manière suivante : depuis tout état

accessible et co-accessible il faut chercher tout ce que l’automate peut faire pour atteindre un état marqué, puis




_____________________________________________________________________________________________________________


____________________________________________________________________________________________14

procéder par substitution pour résoudre l’équation de l’état initial. D’après l’automate A, il est possible deconstruire le système :

x1 = ax2 ; x2 = bx3 ; x3 = bx4 + ax2 ; x4 = ε .En procédant par substitution et en utilisant la relation (1), on aboutit à :

x1 = a(ba)*bb = Lm( A). Une autre expression possible est : babab A L

m*)()( = .

Les concepts d'automate et de langage sont largement exploités dans la commande par supervision des SED.

4. COMMANDE DES SED

L'objectif d'une commande est d'imposer au procédé un comportement spécifié, tout en respectant un

ensemble de contraintes.

La synthèse de la commande est basée sur un modèle du procédé.Le respect d’objectifs temporels nécessite des outils mathématiques aptes à manipuler des dates.

Cette section se veut volontairement synthétique, seules les grandes lignes de la commande des SED sontabordées. La section 5 développera en détail les aspects commande par supervision.

4.1. Réseaux de Petri de commande

Les RdP permettent à la fois de modéliser le procédé et d'en représenter la commande [Godon et al. 97].Dans le contexte des réseaux de Petri, les spécifications ou contraintes peuvent se décliner en état interdit(marquage interdit), ensembles de marquages interdits, séquences d’événements interdites,... Pour cela, on va

restreindre par le contrôle le fonctionnement du procédé de telle manière que seulement les marquages légauxpuissent être atteints, donc interdire le tir de certaines transitions contrôlables. Généralement les modèles RdPsont compacts, ils permettent de représenter un grand nombre d’états possibles du procédé avec un nombre de

places et de transitions limité. De plus, on peut mettre à profit la structure du modèle (graphes d'événements,graphes d'états,...) et les propriétés résultantes (invariants, bornitude,...) pour diminuer la complexité algorithmiquede la synthèse de la commande [Holloway 90] [Baghdadi 96][Holloway et al. 97].Des méthodologies de synthèse de la loi de commande ont été proposées ; parmi les outils existants, l'atelier

logiciel Petri MAKER permet, dans un environnement homogène, de modéliser, d'évaluer les performances et decommander un système, via une interface d'entrées-sorties [Godon et al. 95a][Godon 96].Cette méthodologie aété appliquée à la commande de convertisseurs statiques [Sechilariu et al. 95].

4.2. Suivi de trajectoires : séquences de dates de tirs

Considérons un objectif de pilotage en juste à temps d’un SED. Dans le cas d’un GET, il s’agit de répondreau problème suivant : connaissant les dates de tir désirées des transitions de sortie, à quels instants doit-on tirer

au plus tard les transitions d’entrée afin que les jetons sortent au plus tard avant les dates désirées ? Dans lecas d’une ligne de production cela revient à introduire les matières premières le plus tard possible tout enrespectant les demandes des clients.Dans le cas théorique où le modèle est exact, une commande optimale vis-à-vis du juste à temps, reposant surune structure en boucle ouverte a été proposée en utilisant l’algèbre (max,+) [Baccelli 92].

Afin de compenser d’éventuelles erreurs de modélisation et/ou l’influence de perturbations extérieures, unestructure de commande en boucle fermée a été développée. Les différentes approches retenues s'inspirent de la

théorie linéaire des systèmes continus : problème de l’inversion du modèle, mise en œuvre d’un modèle deréférence, principe de la commande adaptative, synthèse de feedback linéaire dans les dioïdes. [Boimond et al.

96][Hardouin et al. 97][Menguy 97][ Cottenceau et al. 99a][Cottenceau 99b][Lahaye et al. 99].




_____________________________________________________________________________________________________________


____________________________________________________________________________________________15

4.3. Commande sous contraintes : un exemple

Prenons l'exemple bien connu [Wonham 87] du chat et de la souris pouvant se déplacer dans un labyrinthede 5 pièces (fig. 6.a). Le chat peut évoluer à travers 7 portes (C 1 à C 7) et la souris à travers 6 portes ( M 1 à M 6).

Le SED à commander (procédé) noté G est ici une combinaison (composition) des deux systèmesindépendants : celui associé au chat, noté C, et celui associé à la souris, noté M. Ils peuvent être représentés par

les matrices des fig. 6.b et fig. 6.c.

chat

souris

fig. 6.a fig. 6.b et 6.c fig. 6.d

Par exemple, la souris peut se déplacer de la pièce R2 à la pièce R1 en franchissant la porte M 2 (événement m2) ;le chat peut se déplacer depuis la pièce R3 à la pièce R4 à travers C 5 (événement c5).

L'objectif de la commande consiste, dans la conception du système global (procédé + commande), à prendreen compte les contraintes suivantes :

• dans l'état initial, le chat est dans la pièce R2 et la souris dans la pièce R4

• Les animaux ne doivent jamais être dans la même pièce

• le système peut être réinitialisé (l'état initial est toujours accessible)

• toutes les portes sont commandables (on peut assurer leur ouverture ou fermeture), excepté la porte C 7 (toujours ouverte)

tout en permettant un déplacement maximal des animaux.Les systèmes C et M ont chacun 5 états, leur produit synchronisé (composition) G permet de représenter le

comportement global du système composé du chat et de la souris. Il comporte donc 5 × 5 = 25 états.Une méthodologie de prise en compte des différentes contraintes (statiques et dynamiques) conduit, par

affinages successifs, à une réduction du nombre des états de G, puis à l'obtention d'un modèle de commande quel'on peut représenter par un réseau de Petri. La fig. 6.d montre le résultat obtenu pour notre exemple.

Les algorithmes mis en jeu, implantés sur calculateur, produisent un code exécutable, en mesure decommander le système [Godon et al. 97].

Une application de la théorie de la supervision à la commande d'un atelier flexible est présentée dans[Charbonnier et al. 95]. La synthèse de la commande est basée sur les concepts d'une modélisation parautomates et langages. La supervision suppose que l'on puisse interdire l'occurrence de certains événements, cequi sous-entend la notion d'événements contrôlables et événements incontrôlables. La section 5 a pour objectif de

présenter de manière détaillée la commande par supervision.

M1

M3

M2

R1

R0

R2

R4 R3

M4 M5

M6

C1

C2

C3

C4

C5

C6

C7

0 1 2 3 4

0

1

2

3

4

c1 c4

c2 c7

c3

c7 c5

c6

0 1 2 3 40

1

2

3

4

m1 m4

m3

m2

m6

m5

m4 ou c2 m5 ou c3

ouverture des portes M 5 et C3

fermeture des portes M5 et C3




_____________________________________________________________________________________________________________


____________________________________________________________________________________________16

5. COMMANDE PAR SUPERVISION

Comme il a été déjà mentionné, l’objectif de toute commande est d’imposer au procédé un comportement spécifié , tout en

respectant un ensemble de contraintes.La synthèse de la commande est basée sur un modèle du procédé.

Au niveau d’une description logique (qualitative), le comportement d’un SED est spécifié par la liste ordonnée des

événements, sans tenir compte du temps entre deux événements consécutifs. Un objectif typique de commande par

supervision est de faire en sorte qu’une séquence non désirée d’événements ne se produise pas.

5.1. Introduction

Les modèles machines à états sont de manière conceptuelle les plus attractifs à cause de leur simplicité inhérente et par lefait qu'ils peuvent être décrits de façon adéquate par des automates à états finis et la théorie des langages réguliers.

Dans une approche automate, on modélisera un SED au niveau de son comportement logique par une paire de langages

notés L et Lm :

L = Pref( L) est l’ensemble des séquences que le SED peut générer, Lm ⊆ L est le langage associé aux séquences qui conduisent à des états marqués ; il est utilisé pour représenter la réalisation

de certaines opérations particulières ou tâches.

Les langages L et Lm sont définis sur l’ensemble des événements, noté ∑.

Exemple 5.1. Soit l’automate de la figure 5.1 qui modélise le comportement d’un système suite à l’occurrence des

événements a, b, c ∈ ∑. L’état q0 est l’état initial, l’état q2 est l’état marqué.

q0

q1

q2

bc

a

Figure 5.1. Automate modélisant le comportement d’un système.

Partant de l’état initial, on peut atteindre q0 par l’occurrence de l’événement ε, de la séquence (d’événements) ab, de la

séquence abab, etc. Partant de l’état initial, on peut atteindre q1 par l’occurrence de la séquence a, de la séquence aba , etc.

Partant de l’état initial, on peut atteindre q2 par l’occurrence de l’événement c, de la séquence abc , etc. Le langage L associé à

ce modèle automate du procédé s’écrit donc sous forme d’une expression régulière : L = (a⋅b)*⋅(ε + a + c)

Partant de l’état initial, on peut atteindre q2 (état marqué) par l’occurrence de c, de la séquence abc , de la séquence ababc,

etc. Le langage Lm associé à ce modèle du procédé s’écrit donc sous forme d’une expression régulière : Lm = (a⋅b)*⋅c

Cet exemple sera repris ultérieurement.Apportons quelques informations supplémentaires.

On dispose d’un ensemble ∑ de trois événements a, b, c. En l’absence d’autres données, on peut construire à partir de ces

trois événements une infinité de mots (ε, cabacb, aaabcbcca, etc.) Ces mots appartiennent à ∑ *, et sont indépendants de

toute considération physique. Si l’automate est censé représenter les comportements possibles du système, l’ensemble des

comportements possibles est alors un sous ensemble de ∑ *. Si on impose une spécification du type ababc, alors cela revient

à restreindre le comportement (physiquement) possible. Affectons à l’état q0 la signification machine en attente, à l’état q1 la

signification machine en opération et à l’état q2 machine à l’arrêt. Envisageons deux cas, l’objectif étant de satisfaire la

spécification, à savoir la séquence ababc :




_____________________________________________________________________________________________________________


____________________________________________________________________________________________17

• si tous les événements sont contrôlables (cela signifie par exemple que la machine étant en attente le “conducteur ”de la

machine décide quand il le veut d’autoriser ou pas l’occurrence de l’événement a ou l’occurrence de l’événement c), on

interdira d’abord l’occurrence de c (les autres événements étant autorisés à se produire). Puis, après l’occurrence de a,

on pourra n’interdire aucun événement (si on admet que a et c sont alors sans effet compte tenu du comportement

physique du système). Après l’occurrence de b, on devra interdire c, puis après l’occurrence de a, on n’interdira aucun

événement. Après l’occurrence de b on interdira a et autorisera c.

Nous laissons au lecteur le soin de faire la relation avec un distributeur automatique de billets (simplifié) tel que le clavier

comporterait trois touches et le code confidentiel serait ababc.

• si par exemple seul l’événement c n’est pas contrôlable, cela signifie que le conducteur de la machine ne pourra pas

interdire l’occurrence de l’événement c dès lors que la machine est en attente, ce qui peut amener au non respect des

spécifications.

C’est la présence d’événements incontrôlables qui rend difficile la synthèse d’une commande pour les systèmes à

événements discrets.

Dans une approche réseaux de Petri, l’occurrence d’un événement correspond au franchissement d’une transition, sicertaines conditions relatives au marquage des places sont satisfaites. L’état du système est représenté par le vecteur desmarquages des places. L’espace des marquages accessibles tient lieu d’espace d’état.

5.1.1. Modélisation et commande des SED

Dans la théorie de base de RW, il est supposé que les événements associés au procédé se produisent instantanément ,spontanément , c’est-à-dire qu’il n’y a pas de mécanisme de forçage auxiliaire, et de manière asynchrone, c’est-à-dire qu’ils nesont pas dépendants d’une horloge. De plus on suppose qu’ils sont observables à l’extérieur du procédé par leur étiquette σ.Le problème du chat et de la souris va servir à illustrer les différentes notions rencontrées.

Exemple 5.2. Le procédé est constitué de cinq pièces ( R0 à R4), dans lesquelles se trouvent un chat et une souris. Les

pièces communiquent entre elles par diverses portes, à l’usage exclusif d’un des animaux (figure 5.2a). Ainsi, seul le chat peut

emprunter les portes C i, tandis que la souris ne peut emprunter que les portes M j (dans le sens indiqué par les flèches). En

associant un événement à chaque franchissement de porte et un état à chaque situation géographique des animaux, on décrit

successivement par les figures 5.2b et 5.2c les comportements du chat et de la souris. Le passage de l’état “ souris en R0” à

l’état “souris en R4” a lieu sur l’occurrence de l’événement (instantané, spontané, asynchrone) m4. L’ensemble des

événements relatifs à ce procédé s’écrit : ∑ = {m1 , m2 , ..., m6 , c1 , c2 , ..., c7}. On suppose que l’état initial du système est décrit

par “chat en R2” et “souris en R4”. On conçoit que la modélisation du comportement du “couple chat-souris” nécessite uneopération supplémentaire que l’on appellera composition et qui sera définie plus loin.

R1

R2

R0

R1

R2

R0

R3

R4

m1

m2

m3

m4

m5

m6

c2

c3

c6

c7

c1

c4

c7

c5 R

3 R

4

R1

R 2

R0

R 3

R 4

C 2

M 2

M 1

C 3

M 3

C 1

C 4

M 6

M 4

C 6

M 5

C 5

(a) (b) (c)

C 7

Figure 5.2. (a) Possibilité d’évolution des animaux. (b) Modélisation du comportement du chat. (c) Modélisation du comportement de la

souris.

Après analyse et modélisation (partielle) du procédé, énonçons les spécifications que doit remplir le système :

• les deux animaux ne doivent jamais se rencontrer (on comprend aisément pourquoi). Ceci est un problème d’exclusion

mutuelle, de sécurité.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________18

• les deux animaux doivent pouvoir toujours regagner leur pièce initiale, c’est-à-dire R2 pour le chat et R4 pour la souris.

Ceci est un problème de retour à l’état initial ou réinitialisation.

Pour cela, chaque porte peut être ouverte ou fermée, à l’exception toutefois de C 7, toujours ouverte. Un événement est

associé au franchissement d’une porte par l’un des animaux. Interdire l’occurrence d’un événement consiste, dans le

système, à fermer la porte associée. Par conséquent, à l’exception de l’événement c7 qu’on ne peut interdire de se produire et

qui sera qualifié d’événement incontrôlable, puisque associé à la porte C7 toujours ouverte, tous les autres événements

peuvent être interdits par la fermeture des portes correspondantes et seront qualifiés d’événements contrôlables.

Le rôle de la commande (supervision) est d’observer la séquence (trajectoire) des événements générés par le procédé et après

chaque événement généré, compte tenu de la partition entre événements contrôlables et incontrôlables, d’autoriser ou

interdire l’occurrence des événements contrôlables (on ouvrira ou fermera les portes correspondantes) de manière à satisfaire

les spécifications. Par exemple pour le premier point des spécifications, on conçoit que si la séquence des événements est :

c3c1c2m5 suivis de m6, alors il faudra que le superviseur interdise pour ce point de fonctionnement l’occurrence de

l’événement c3 (la porte devra être fermée). Si au cours du fonctionnement, on se trouve dans la situation pour laquelle le

chat est en R1 et la souris en R3, on conçoit que l’occurrence de l’événement incontrôlable c7 ne pouvant être interdite, l’un

des animaux servira de déjeuner à l’autre et la spécification ne sera pas respectée. L’occurrence de cet événement non

contrôlable fait sortir de la spécification ; cette notion sera formalisée par les langages contrôlables (ou commandables) .

Remarque 5.1. Nous avons introduit la notion de spécification en énonçant que les deux animaux ne devaient pas se

trouver dans la même pièce. Cette spécification a un caractère négatif par le fait qu’elle indique ce que ne doit pas faire le

procédé pour des raisons de sécurité. Dans les systèmes de production il est courant de rencontrer des spécifications dutype “le stock de pièces entre deux machines ne doit pas dépasser une quantité donnée” ; ceci peut être assimilé à une

contrainte (de stock). Une spécification du type “l’ordre de réparation des machines, en cas de pannes multiples est imposé”

présente un caractère posi tif , en ce sens qu’elle indique ce que doit faire le procédé ; il en est de même du problème de

reinitialisation évoqué précédemment. La modélisation des spécifications, exprimées la plupart du temps sous forme littérale,

est en général un problème difficile.

5.1.2. Composition d’automates

Un procédé réel est souvent composé de procédés élémentaires en interaction plus ou moins forte. Supposons deuxmachines indépendantes au sein d’un même atelier. Leur comportement individuel peut être décrit par un automate (un pourchaque machine), chaque automate disposant de son propre alphabet des événements. Le comportement de l’ensemble desdeux machines, vu de l’atelier, peut être décrit par un seul automate moyennant une composition des deux automates

précédemment évoqués. On parle alors de composition asynchrone (aucun événement commun). Dans le cas où ces deuxmachines ont une liaison qui les amène à partager au moins un événement commun, on parlera de composition synchrone. Lacomposition est donc l’outil permettant de construire un procédé complexe à partir de procédés élémentaires. De plus, onverra dans la section 5.2. qu’elle intervient aussi dans l’élaboration de la commande par supervision du procédé : il y acomposition du procédé avec les spécifications. La composition occupe donc une place essentielle dans l’étude dessystèmes à événements discrets.

En désignant par ∑1 (respectivement ∑2) l’ensemble des événements associé au procédé 1 (respectivement au procédé 2),

nous traitons trois cas de composition7, selon que :

Σ1 ∩ Σ2 ≠ 0 synchronisation d’événements avec étiquettes σi en commun

Σ1 ∩ Σ2 = 0 pas de synchronisation d’événements

Σ1 = Σ2 synchronisation totale

On définit le produit cartésien de Q par X , noté Q × X , par l’ensemble des paires ordonnées (q, x) telles que q ∈ Q et x ∈ X.

5.1.2.1. Composition synchrone

Soit L1 ⊆ ∑1*, L2 ⊆ ∑2

*, avec Σ1 ∩ Σ2 ≠ 0 et Σ = Σ1 ∪ Σ2

Soient deux automates A1 = (Q, Σ1, δ, q0, Qm) et A2 = ( X , Σ2, ξ, x0, X m)

Le composé synchrone Ar de A1 et A2, noté Ar = A1|| A2 est défini par le 5-uplet :

(Q × X , Σ1 ∪ Σ2, δ × ξ, q0 × x0, Qm × X m)

où Q × X est l'ensemble des états

Σ1 ∪ Σ2 = Σ représente l'alphabet de Ar

q0 × x0 est l'état initial

7 La composition synchrone est généralement définie sur les langages Li et nécessite les opérations de projection et de projection inverse.

Nous retiendrons que la composition synchrone est associative : ( L1 L2) L3 = L1 ( L2 L3).




_____________________________________________________________________________________________________________


____________________________________________________________________________________________19

Qm × X m est l'ensemble des états finals

et où la fonction de transition d'états δ × ξ est définie par :

(δ × ξ)((q, x), σ) = (q' , x' ) si δ (q, σ) = q' ! et ξ ( x, σ) = x' ! (synchronisation sur un événement commun) (1)

(δ × ξ)((q, x), σ) = (q' , x) si δ (q, σ)! avec σ ∈ Σ1 \ Σ2 (2)

(δ × ξ)((q, x), σ) = (q, x' ) si ξ ( x, σ)! avec σ ∈ Σ2 \ Σ1. (3)

Les événements qui appartiennent à ((Σ2 \ Σ1) ∪ (Σ1 \ Σ2)) n'introduisent pas de contrainte et peuvent être exécutés dès que

possible.

Exemple 5.3. Soient Σ1 = {α, β} et Σ2 = {β, γ }. Les automates A1 et A2 associés aux deux procédés considérés sont

représentés ci-après.

On déduit : L1 = {ε, α, αβ, αββ, ...} et L2 = {ε, β, βγ , ...}Σ1 ∩ Σ2 = β et Σ = Σ1 ∪ Σ2 = {α, β, γ }.

• Dans leur état initial, les deux automates ne sont pas sensibles à l’événement commun β ; la relation (1) ne peut

s’appliquer. L’événement α appartient à l’ensemble des événements actifs lorsque l’automate A1 est dans l’état initial et α

n’appartient pas à l’ensemble des événements ∑2 associés à l’automate A2 (α ∈ Σ A1(q) \ Σ2) ; la relation (2) s’applique

donc. On peut par ailleurs vérifier que β appartient bien à l’ensemble des événements actifs lorsque l’automate A2 est

dans l’état initial, mais β appartient aussi à ∑1 ; la relation (3) ne peut s’appliquer. L’automate résultant de la composition

( Ar ) évoluera donc depuis son état initial vers l’état suivant sur l’occurrence de l’événement α, comme représenté ci-

dessous.

• L’automate A1 a évolué depuis son état initial vers l’état suivant sous l’occurrence de l’événement α. L’automate A2 est

resté dans son état initial. Ces deux automates deviennent maintenant sensibles à l’événement (commun) β. La relation (1)

peut s’appliquer. L’automate Ar évoluera comme représenté ci-dessous.

• L’automate A1 devient alors sensible à l’événement β, l’automate A2 à l’événement γ . La relation (3) s’applique alors :

l’événement γ appartient à l’ensemble des événements actifs de l’automate A2 dans son état courant et γ n’appartient pasà l’ensemble des événements ∑1 associés à l’automate A1. L’automate Ar évoluera comme représenté ci-dessous.

• A l’étape suivante, β étant un événement commun, la relation (1) s’applique. On obtient pour Ar :

α

α β γ

α β

α β γ β

α

β

β

1 β

γ

2

3

1 2

1111

21




_____________________________________________________________________________________________________________


____________________________________________________________________________________________20

• L’événement α est maintenant actif pour A1 et γ l’est pour A2. Ils remplissent respectivement les conditions associées aux

relations (2) et (3).

Si on considère l’évolution selon γ on obtient pour Ar :

Si on considère l’évolution selonα on obtient pour Ar :

• Nous laissons le soin au lecteur de terminer la construction de l’automate Ar (le composé synchrone) qui représente tous

les comportements possibles du procédé résultant du couplage des deux procédés élémentaires par l’intermédiaire de

l’événement β (ceci n’est pas sans rappeler l’expérience bien connue en physique d’un couplage élastique entre deux

pendules élémentaires ; toutefois les outils mathématiques utilisés pour modéliser les comportements sont totalement

différents). Le résultat final est représenté ci-dessous .

5.1.2.2. Composition asynchrone

Soit L1 ⊆ ∑1*, L2 ⊆ ∑2

*, avec Σ1 ∩ Σ2 = 0 et Σ = Σ1 ∪ Σ2 (pas d’événement commun)

Soient deux automates A1 = (Q, Σ1, δ, q0, Qm) et A2 = ( X , Σ2, ξ, x0, X m)

Le composé Ar de A1 et A2, noté Ar = A1|| A2 est défini par le 5-uplet :

(Q × X , Σ1 ∪ Σ2, δ × ξ, q0 × x0, Qm × X m), avec

(δ × ξ)((q, x), a) = (q' , x) si δ (q, a) = q' pour a ∈ Σ1 (4)

(δ × ξ)((q, x), a) = (q, x' ) si ξ ( x, a) = x' pour a ∈ Σ2 (5)

La composition asynchrone n’est qu’un cas particulier de la composition synchrone.

Exemple 5.4. Soient deux machines indépendantes qui traitent des pièces brutes et produisent des pièces usinées. On

peut associer à chacune d’elle un automate décrivant son comportement, avec ses événements associés.

Soit ∑1 = {d 1, f 1, p1, r 1} l’ensemble des événements associé à l’automate noté M 1 et Σ2 = {d 2, f 2, p2, r 2} l’ensemble des

événements associé à l’automate noté M 2. On associe aux événements respectivement les significations de début

d’opération, fin d’opération, panne, réparation.

γ

α β γ β

α

M 1

α β γ β

1 q1 q2

1 r 1

d 1

q0

α β γ β α

γ

γ

2 q4 q5

q3

2 r 2

d 2

M 2




_____________________________________________________________________________________________________________


____________________________________________________________________________________________21

Σ1 ∩ Σ2 = 0 et Σ = Σ1 ∪ Σ2 = {d 1, f 1, p1, r 1, d 2, f 2, p2, r 2}

Le modèle défini par M r = M 1|| M 2 est représenté par le graphe de transitions d'états ci-dessous :

Il représente le comportement global du système composé des deux machines élémentaires.

Remarques 5.2. Bien que ceci n’ait aucune relation avec la composition, on note sur les figures précédentes la présence

de traits associés à certains événements. Ceci permet de particulariser les événements en événements contrôlables et non

contrôlables. En effet, le départ d’un cycle de fonctionnement d’une machine peut être autorisé ou interdit (donc

contrôlable), alors que la panne est une chose qui ne peut malheureusement pas être interdite, elle est par conséquent

toujours autorisée (donc non contrôlable).

Ainsi, ΣC = {d 1, d 2, r 1, r 2} et Σu = { f 1, f 2, p1, p2}Si m est le nombre d’états associé à l’automate M 1 et n le nombre d’états associé à l’automate M 2, le nombre d’états

associé à l’automate M r sera égal à m x n dans le cas d’une composition asynchrone.

5.1.2.3. Composition complètement synchrone

Σ1 = Σ2 = Σ. Compte tenu de ces hypothèses sur les ensembles, les relations (2) et (3) de la section 5.1.2.1. ne seront jamais vérifiées.

La relation de composition se réduit à :

(δ × ξ)((q, x), a) = (q' , x' ) si δ (q, a) = q' et ξ ( x, a) = x' pour a ∈ Σ et (q, x)∈ (Q× X )

et non définie sinon (6)

Exemple 5.5. Soient Σ1 = {α, β, γ , δ} =Σ2 = Σ et S1 et S2 deux automates dont on veut réaliser la composition.

S1

S2

α

β

α

β

γ

δ

à partir de là,

pas d'événement

commun

⇒ blocage

q05 f 1

q15 p1 q25

q24 q14 q04

q03 q23 q13

d1

d1

d1

p1

p1

f 1

f 1

r1

r1

r1

r2 r2 r2 p2 p2 p2

f 2 f 2 f 2 d2 d2 d2




_____________________________________________________________________________________________________________


____________________________________________________________________________________________22

L’automate résultant Sr est représenté ci-après.

L’opération de composition complètement synchrone est généralement notée ‘×’ ; les langages résultants obéissent aux

relations ci-dessous :

L(Sr ) = L(S1 × S2) = L(S1)∩ L(S2)

Lm(Sr ) = Lm(S1 × S2) = Lm(S1)∩ Lm(S2)

Ce type de composition complètement synchrone se rencontrera lors du fonctionnement en parallèle du procédé avec son

superviseur (voir § 5.2).

α

β




_____________________________________________________________________________________________________________


____________________________________________________________________________________________23

6. CONCLUSION

L'espace d'état des Systèmes à Evénements Discrets est discret et le changement d'état est lié àl'occurrence d'événements.

Pour cette (large) classe de systèmes, la conception (intégrant la sûreté de fonctionnement), la mise enévidence de caractéristiques par l'analyse et l’évaluation de performances, le respect d'un comportement parsynthèse d'une commande, nécessitent le développement de modèles et de méthodologies spécifiques. La prise en

compte d'incertitudes, de perturbations, de défaillances, conduit à des modèles stochastiques.

Il n'existe pas de cadre théorique unique pour l'étude des SED. En l’absence de théorie standard, denombreux outils reconnus sont utilisés à la fois par des chercheurs de la communauté Automatique et deschercheurs de la communauté Informatique, tels que les réseaux de Petri, l’algèbre des dioïdes, les automates etles langages, les files d’attente,... Cette diversité peut s’expliquer du fait de l’intérêt scientifique relativementrécent pour ces systèmes et aux différents problèmes qu’ils soulèvent. ; vis-à-vis des systèmes de production, la

planification de la production, l’ordonnancement de la production, l’approvisionnement des entrées, la gestion desflux peuvent être considérés, selon un certain point de vue, comme appartenant à la famille des SED.

Les systèmes industriels deviennent de plus en plus complexes et les détails nécessaires pour modéliser etcommander sont différents à chaque niveau8. Les procédures de décomposition, d'agrégation,... facilitent l'étudede ces systèmes. "Le" modèle adopté doit être adapté à son objectif.

Classiquement, l'évaluation des performances à base de modèles est faite par simulation sur calculateur ou pardes techniques analytiques.

L'exposé a mis en évidence les notions de comportement logique et de comportement temporel (régimetransitoire puis régime permanent pour un fonctionnement cyclique). Certains problèmes d'optimisation consistent

par exemple à minimiser le nombre de ressources, un temps d'attente, à maximiser un flux de sortie,... La stabilité(par exemple le nombre de pièces dans un stock est fini), la commandabilité, l'observabilité sont également des

concepts étudiés dans le cadre des SED.

Le nombre d'états physiques d'un SED explose de manière combinatoire (si de plus on couple troissystèmes possédant respectivement, l, m, n états, on obtient en général un système résultant à lxmxn états). Lestemps de calculs peuvent devenir prohibitifs. Pour la synthèse de la commande, on recherchera des algorithmesperformants. Parallèlement on s'oriente pour les systèmes complexes vers le contrôle décentralisé.

Enfin, on ne peut ignorer -comme c'est le cas des procédés manufacturiers- l'interaction entre l'Homme etle SED.

8 On peut rencontrer des systèmes dont le fonctionnement est manifestement de type "continu", excepté sur l'occurrence d'événements discrets

qui provoquent des sauts de leur trajectoire. Ces sauts peuvent correspondent à des changements de mode opératoire. On associe généralement à

de tels systèmes le qualificatif de "hybrides" Plus généralement, des systèmes hybrides ont un comportement qui est dé terminé par l’interaction

entre une partie continue et une partie discrète [Cebron et al. 99].




_____________________________________________________________________________________________________________


____________________________________________________________________________________________24

BIBLIOGRAPHIE

[Alla et al. 01] A. Alla, R. David, M. Di Mascolo, J.-L. Ferrier. Analyse et commande des systèmes à événements discrets.

Hermès Ed., 2000.

[Arnold 92] A. Arnold. Systèmes de transitions et sémantique des processus communicants . Masson, 1992.

[Baccelli et al. 92] F. Baccelli, G. Cohen, G.J. Olsder, J.P. Quadrat. Synchronization and linearity. An algebra for Discrete Event

Systems. Wiley, 1992.

[Baghdadi 96] L. Bagndadi - Ben-Naoum. "Control of discrete event systems modelled as Petri nets". Thèse de l’Université

Catholique de Louvain, Belgique, décembre 1999.

[Boimond 93] J.L. Boimond. "Internal model control of discrete-event process in the max-algebra". ECC'93, p. 150-157,

Groningen (NL), 28 juin-1 juillet 1993.

[Boimond et al. 96] J.-L. Boimond, J.-L. Ferrier. "Internal model control and max-algebra. controller design". IEEE transactions on

Automatic Control, vol. 41, n° 3, p. 457-461, 1996.

[Brams 83] G.W. Brams. Réseaux de Petri : théorie et pratique. Masson, 1983.

[Calvez 90] J.P. Calvez. Spécification et conception des systèmes . Masson, 1990.

[Cassandras 93] C.G. Cassandras. Discrete Event Systems : modeling and performance analysis. Aksen Associates Incorporated

Publishers, 1993

[Cebron et al. 99] B. Cebron, M. Sechilariu, J. Burger. "Optimal control of hybrid dynamical systems with hysteresis". ECC’99,

Karlsruhe, Allemagne, 31 août-3 sept. 1999.

[Charbonnier 95] F. Charbonnier, H. Alla, C. Foulard. "Commande par supervision d'un atelier flexible". Actes des Journées EEA-

Automatique, avril 1995.

[Cottenceau et al. 99a] B. Cottenceau, L. Hardouin, J.-L. Boimond, J.-L. Ferrier. "Synthesis of greatest linear feadback for timed-event

graphs in dioid". IEEE transactions on Automatic Control, vol. 44, p. 1258-1262, 1999.

[Cottenceau 99b] B. Cottenceau. "Contribution à la commande de systèmes à événements discrets : synthèse de correcteurs pour

les graphes d’événements temporisés dans les dioïdes". Thèse de l’Université d’Angers, octobre 1999.

[David et al. 89] R. David, H. Alla. Du Grafcet au réseaux de Petri. Hermès, 1989.

[Godon et al. 95a] A. Godon, J.L. Ferrier. "L’atelier logiciel Petri Maker. Commande de systèmes par réseaux de Petri". Revue

d’Automatique et de Productique Appliquée (RAPA), vol. 8, n° 6, p. 813-821, 1995.

[Godon 96] A. Godon. "Contribution à la commande des systèmes à événements discrets par réseaux de Petri". Thèse de

l’Université d’Angers, novembre 1996.

[Godon et al. 97] A. Godon, J.L. Ferrier. "Supervisory control for synchronized and colored Petri nets under static and dynamic

constraints". MCPL’97 - IFAC/IFIP, Campinas, Brésil, 31 août - 3 sept. 1997.

[Gouin et al. 99a] A. Gouin, J.-L. Ferrier. "Modélisation et commande supervisée des SED temporisés". MSR’99, Modélisation des

systèmes réactifs, Cachan, p. 383-394, 24-26 mars 1999.

[Gouin 99b] A. Gouin. "Contribution à la commande de systèmes à événements discrets temporisés : synthèse de superviseur

dans le cadre de modèle automate". Thèse de l’Université d’Angers, décembre 1999.




_____________________________________________________________________________________________________________


____________________________________________________________________________________________25

[Hardouin et al. 97] L. Hardouin, E. Menguy, J.-L. Boimond, J.-L. Ferrier. "SISO discrete event systems control in dioid agebra".

Special issue of Journal Européen des Systèmes Automatisés (JESA), vol. 31, n° 3, p. 433-452, 1997.

[Ho 89] Y.C. Ho, guest editor, special Issue on Dynamics of Discrete Event Systems

Proc. IEEE , vol. 77, n° 1, janvier 1989.

[Holloway et al. 90] L.E. Holloway, B.H. Krogh. "Synthesis of feadback control logic for a class of controlled Petri nets". IEEE

transactions on Automatic Control, vol. 35, p. 514-523, 1990.

[Holloway et al. 97] L.E. Holloway, B.H. Krogh, A. Giua. "A survey of Petri nets methods for controlled discrete event systems".

Discrete event dynamic systems : theory and applications, vol. 7, p. 151-190, 1997.

[Hopcroft et al. 79] J.E. Hopcroft, J.D. Ullman . Introduction to Automata Theory, Languages, and Computation. Addison-Wesley,

1979.

[Kumar et al. 91] R. Kumar, V. Garg, S.I. Marcus. "On controllability and normality of discrete event dynamical systems".

Systems and Control Letters, vol. 17, p. 157-168, 1991.

[Kumar et al. 95] R. Kumar, V. Garg. Modeling and control of logical discrete event systems. Kluwer Academic Publishers, 1995

.[Lahaye et al. 99] S. Lahaye, J.-L. Boimond, L. Hardouin. "Graphes d’événements temporisés avec ajout/retrait dynamique de

jetons : comportement asymptotique, représentation dans l’algèbre (min,+)". MSR’99, Modélisation des systèmes

réactifs, Cachan, p. 27-37, 24-26 mars 1999.

[Mares et al. 94] M. Mares, J.L. Ferrier. "Réseaux de Petri et algèbre (max,+) : deux approches pour l'étude des systèmes à

événements discrets". APII , vol. 28, n° 4, p. 311-329, 1994.

[Menguy 97] E. Menguy. "Contribution à la commande des systèmes linéaires dans les dioïdes". Thèse de l’Université

d’Angers, novembre 1997.

[Murata 89] T. Murata. "Petri nets : properties, analysis and applications". Proc. IEEE , vol. 77, n° 4, p. 541-580, avril 1989.

[Ramadge et al. 87] P.J. Ramadge, W.M. Wonham. "Supervisory control of a class of discrete-event processes". SIAM J. Contr.

Optim., vol. 25, n° 1, p. 206-230 , janv. 1977.

[Ramadge et al. 89] P.J. Ramadge, W.M. Wonham. "The control of discrete-event systems". Proc. IEEE , vol. 77, n° 1, p. 81-97,

janv. 1989.

[Ramamoorthy et al. 80] C.V. Ramamoorthy, G.S. Ho. "Performance evaluation of asynchronous concurrent systems using Petri nets".

IEEE Trans. on Software Engineering, vol. 6, n° 5, p. 440-449, sept. 1980.

[Sechilariu et al. 95] M. Sechilariu, J. Berrué, J.L. Ferrier. "Faisabilité et limites d'une commande interactive de convertisseurs

statiques". RGE , n° 1, p. 41-49, janvier 1995.

[Sifakis 79] J. Sifakis. "Use of Petri Nets for performance evaluation". Acta Cybernetica, vol. 4, n° 2, p. 185-202, 1979.

[Wonham et al. 87] W.M. Wonham , P.J. Ramadge. "On the supremal controllable sublanguage of a given language". SIAM J. Contr.

Optim., vol. 25, n° 3, p. 637-659, mai 1987.

[Wonham 95] M. Wonham. Notes on control of discrete event systems. ECE 1636F/1637S, University of Toronto, Caanada,

1995.