Système À Événements Discrets

AU 2015/2016
Système à événements discrets
Zied ACHOUR
1
I. Types de systèmes
• Systèmes continus
– variables d'état continues et temps continu
• Systèmes échantillonnés
– variables d'état continues et temps discret
• Systèmes discrets
– variables d'état discrètes et temps continu
• Systèmes à événements discrets
– variables d'état discrètes et temps discret
– Cas particulier : le domaine des variables est
{0,1}
2
II. Définitions générales
Système
Ensemble de composants en interaction accomplissant
conjointement une fonction particulière en respectant un
ensemble de contraintes
Système à Evénements Discrets

C’est des systèmes dynamiques dont l’espace des états est discret
et dont l’évolution est conforme à l’occurrence d’événements
physiques à des intervalles de temps généralement irréguliers ou
inconnus. Leurs trajectoires d’états sont constantes par morceaux.
Evénement
Changement de valeur d’une variable survenant à une date
donnée. 3
II. Définitions générales
Niveau du
stock
a a d a a
t1 t2 t3 t4 t5 Temps
Considérons l’exemple d’un système de production. L’évolution du

niveau d’un stock est déterminée par l’occurrence des événements
a : arrivée d’une pièce dans le stock et

d : départ d’une pièce du stock.
4
III. Outils de modélisation - 1. Notion de modèle
1. Notion de modèle
Approximation, vue partielle plus ou moins abstraite de la réalité
afin d ’appréhender un système plus simplement. Un modèle est
établi selon un point de vue donné pour un objectif donné. Donc,
un modèle est partiel et subjectif.
2. Langages formels
a. Alphabet
Ensemble fini de symboles. Dans le cas d’un SED, un alphabet
pourra par exemple représenter l ’ensemble des événements
d’entrée possibles d’un système. On note par exemple  = {a,b}
b. Chaîne ou Mot ou Séquence
Défini sur un alphabet  c’est une suite finie d ’éléments de . Par
exemple abba est un mot défini sur .
5
III. Outils de modélisation - 2. Langages formels
• La longueur d’un mot, notée ImotI représente le nombre de

symboles de ce mot (par exemple, IabbaI = 4)
• Soit un alphabet . On note n l’ensemble des mots de longueur n.
Par exemple, sur  = {a,b} :
0 = {} où  est le mot vide de symbole
1 = {a,b}
2 = {aa,bb,ab,ba}
• * est l ’ensemble de tous les mots que l ’on peut construire sur .
* = U(i>=0) i
Dans notre exemple, * = {, a, b, aa, bb, ab, ba, aaa, aab, abb, …}
6
c. Langage
• Un langage défini sur un alphabet  est un sous ensemble de *
Par exemple, l’ensemble des séquences telles que « a » apparaît
en premier et telles que a et b apparaissent alternativement est
décrit par le langage
L = {, a, ab, aba, abab, ababa, …}. C ’est un langage infini.
• plusieurs opérations ensemblistes sont définies sur les langages :

L’union de L1 et L2 : notée L1  L2 = {wIw  L1 ou w  L2 }
L’intersection de L1 et L2 : notée L1  L2 = {wIw  L1 et w  L2 }
La concaténation de L1 et L2 : notée L1 . L2 = {wIw = xy, x  L1 et y 
L2 } 7
d. Préfixes d’une chaîne et préfixe-clôture d’un langage

La chaîne u est dite préfixe de uv.

La préfixe-clôture de L est le langage contenant tous les préfixes
des chaînes de L.
On notera par L la préfixe-clôture du langage L.
L = {s1  Σ*  s2  Σ*, s1s2  L}
La préfixe-clôture du langage L = {aabb} est :
L = {ε, a, aa, aab, aabb}.

8
Si L = L alors L est préfixe-clos.
Exemple
le langage L1 = {aabb} n’est pas préfixe-clos
le langage L2 = {ε, a, aa, aab, aabb} est préfixe-clos.
9
e. Expressions régulières et langages réguliers
C’est une expression dont les opérandes sont des symboles de Σ, et
les opérateurs sont pris dans l’ensemble {+, ., *}.
Exemple : a + a.b*

Un langage régulier est un langage qui peut être défini par une
expression régulière.
Exemple : soit le langage L sur l’alphabet Σ = {a, b} qui comprend
toutes les chaînes telles que a et b apparaissent alternativement et
telles que a apparaît en premier.
Le langage L = {ε, a, ab, aba, abab, ababa, …}.
(a.b)* . (ε + a) Ou ε + a . (b.a)* . (ε + b)
10
III. Outils de modélisation - 3. Automate
3. Automate
Un automate est une machine à états qui permet de traduire la
relation entrées/sorties d’un SED en utilisant les bases de la
théorie des langages.
a. Définition
Un automate est un quintuplet : A = (Q, Σ, f, q0, Qm) où :

Q : l ’ensemble des états
Σ : un alphabet d ’entrée
f : la fonction de transition d ’états définie de Q x Σ  Q
q0 : l ’état initial
Qm : l ’ensemble des états finaux (F  Q)
11
a
a
q0 q1 b
g a,g
q2 b
Q :
Σ :
f :
q0 :
Qm: 12
Equivalence d’automate
13
14
Définitions :
Le langage généré par A = (Q, Σ, f, q0, Qm) est
L(A) = {s  Σ*  f(q0, s) est défini}

Le langage marqué par A est
Lm(A) = {s  Σ*  f(q0, s)  Qm}

L(A) est toujours préfixe-clos L(A) = L(A).

Le langage Lm(A)  L(A) puisque Qm  Q
15
b. Equivalence d’automates

Deux automates sont dits équivalents s’ils génèrent et marque les

mêmes langages (Figure 1.3).

Définition Les deux automates A1 et A2 sont dits équivalents si
L(A1) = L(A2) et Lm(A1) = Lm(A2).
a a
a a a
q0 q1 q0 q1 q2
b b
b
16
d. Produit et composition d’automates

On défini deux mécanismes d’intégration d’automates : le produit

synchrone, noté par , et la composition synchrone, noté par .
Pour simplifier, nous présentons ces deux mécanismes pour
l’intégration de deux automates A1 et A2 uniquement.
17
• Le Produit synchrone A1  A2
A1 = (Q1, Σ, f1, q01, Qm1)
A2 = (Q2, Σ, f2, q02, Qm2)
A1  A2 = (Q1 Q2, Σ, f, (q01, q02), Qm1 Qm2) où
f((q1, q2), e) = (f1(q1, e), f2(q2, e)) si f1(q1, e)! et f2(q2, e)!
f((q1, q2), e) = non définie sinon
18
• La composition synchrone A1  A2
A1 = (Q1, Σ1, f1, q01, Qm1)
A2 = (Q2, Σ2, f2, q02, Qm2)
A1  A2 = (Q1 Q2, Σ1 Σ2, f, (q01, q02), Qm1 Qm2) où
f((q1, q2), e) = (f1(q1, e), f2(q2, e)) si f1(q1, e)! et f2(q2, e)!
f((q1, q2), e) = (f1(q1, e), q2) si f1(q1, e)! et e Σ2
f((q1, q2), e) = (q1, f2(q2, e),) si e Σ1 et f2(q2, e)!
f((q1, q2), e) = non définie sinon

La notation f(q, e)! signifie que l’événement e est tirable à partir de
19
l’état q
20
Exemple 1
Soit une machine sujette à des pannes qui ne doit pas être réparée
qu'au plus une fois.
Modèle du procédé G Modèle de la spécification E
 : occurrence d’une panne de la machine

 : occurrence de fin de réparation.
21
Le fonctionnement souhaité K est obtenu par la composition

synchrone de ces deux automates G et E. K = G ║ E
22
Exemple 2
Considérons un système manufacturier composé de deux
machines identiques : M1 et M2, et un stock entre ces deux
machines.
Dans son état initial (q0), la machine M1 est à l'arrêt. L'événement

d1 modélise le début du cycle de la machine, l'occurrence de cet
événement conduit la machine dans l'état de marche (q1). f1
représente la fin du cycle. Lorsque la machine M1 est en marche
(q1), l’occurrence de l’événement p1 conduit la machine dans un
état de panne (q2). La réparation de la machine, ramène 23la
Exemple 2
Dans son état initial (q0), la machine M1 est à l'arrêt. L'événement
d1 modélise le début du cycle de la machine, l'occurrence de cet
événement conduit la machine dans l'état de marche (q1). f1
représente la fin du cycle. Lorsque la machine M1 est en marche
(q1), l’occurrence de l’événement p1 conduit la machine dans un
état de panne (q2). La réparation de la machine, ramène la
machine dans son état initial. La machine M2 est similaire à M1.
24
Exemple 2
Un modèle automate du système manufacturier est obtenu en
effectuant le composé synchrone des modèles M1 || M2
25
Modèle de la Spécification : Un stock de capacité limitée à 1, situé
entre les 2 machines. Les machines travaillent en série.
Le stock est supposé vide dans son état initial.
26
27
Exemple 3
Prenons l'exemple du chat et de la
souris pouvant se déplacer dans
un labyrinthe de 5 pièces. Le
chat peut évoluer à travers 7
portes (C1 à C7) et la souris à
travers 6 portes (M1 à M6).
Le SED noté G est ici une

combinaison (composition) des
deux systèmes indépendants :
celui associé au chat, noté C, et
celui associé à la souris, noté M.
28
L'objectif de la commande consiste, dans la conception du
système global (procédé + commande), à prendre en 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 contrôlables (on peut assurer leur
ouverture ou fermeture), excepté la porte C7 (toujours ouverte)
29
Machine de Moore
• C’est un automate déterministe dans lequel une sortie peut
prendre des valeurs (associées aux états) dans un ensemble fini de
grandeurs discrètes. La sortie est émise à la fin de la séquence
d’entrée.
• Une machine de Moore est un 6-uplet M = (Q, Σ, f, q0, , ) où :

Q, Σ, f, q0 ont la même signification que pour un automate fini, 
est un alphabet fini de sortie et  est la fonction d’affectation de
sortie  : Q   30
Exemple : ouverture automatique d ’une porte
• on considère une porte coulissante (type grand magasin) dont
on désire commander l ’ouverture et la fermeture en fonction de
deux informations détectant la présence de personnes au seuil
intérieur ou extérieur de la porte (détectée par des capteurs
optiques ou des tapis sensitifs).
31
• Séquences d’entrée possibles :
une personne seule sort : pi pi  pe pe
une personne seule entre :  pe  pe  pi  pi
remarque : à la sortie,  pi  pe peuvent être simultanés.
Dans tous les cas, l’ouverture doit se faire sur occurrence de  pi
et la fermeture sur occurrence de  pe.
Cette séquence peut se réduire à  pi  pe
(idem pour l’entrée :  pe  pi)
• Conditions de sécurité :
si une personne est entrée ( pe ), la fermeture ne devra se faire
que si :  pi ./pe./pi (soit  pi ./pe)
dans le cas d’une sortie, la fermeture doit se faire ssi  pe./pi 32
33
Exemple : sas de sécurité d’une banque
• On considère un sas de sécurité de banque dont on veut gérer le
verrouillage et le déverrouillage des portes intérieures et
extérieures (VER INT, VER EXT, DEVER INT et DEVER EXT).
La manœuvre des portes est manuelle.
• Les clients demandent le
déverrouillage des portes par
des boutons poussoirs
(Ap int, Ap ext, …)
• Deux capteurs de fermeture

de porte (int fer, ext fer)
permettent le verrouillage. 34
3
1
2
35
36
III. Outils de modélisation - 4. RdP
37
38
39
40
41
42
Propriétés des RdP :
• Un RdP est borné pour un marquage initial M0 si toutes ses places sont
bornées ( pour tout marquage accessible le nombre de marques de chaque
place est fini) pour M0.
• Un RdP est sauf pour un marquage initial M0 si pour tout marquage
accessible chaque place contient au plus une marque.
• Un RdP est vivant pour un marquage initial M0 si toutes ses transitions sont
vivantes (quelque soit l’évolution, il subsiste toujours une possibilité de
franchir la transition).
• Un blocage (ou état puit) est un marquage tel qu’aucune transition n ’est
validée.
• Un RdP est dit sans blocage pour un marquage initial M0 si aucun de ses
marquages accessibles n ’est un blocage.
• Un RdP est réinitialisable pour un marquage initial M0 si depuis tout
marquage accessible il existe une séquence conduisant à M0.
R1 est borné, non vivant (deux états de blocage) et non réinitialisable.
R2 est sauf, vivant et réinitialisable. 43
44
45
46
47
48
49
50
Les RdP non autonomes
51
52
Le cas du conflit de franchissement
53
54
Les RdP P-temporisés
55
56
Les RdP T-temporisés
57
58
59
60
• III. Outils de modélisation - 4. RdP
Modèles du procédé
1 f1
ff1
2 t1
ft1
Modèles du procédé
contrôlé
approches pour Procédé
la Synthèse de la événements événements
autorisés générés
commande Superviseur
Cahier des charges

(spécifications)
64
Objectif de la synthèse
M0
R T3 T1
M1 M2
T4 T1 T3 T2
R est contrôlable : M3 M4 M5
T1 T2 T3
Les transitions à partir T4 T2
M6 M7
d’états admissibles vers des T2 T4
T4 T2
états non admissibles sont
M8
contrôlables.
T4 T2
65
Objectif de la synthèse
T4 est incontrôlable
R
M0 M0
T3 T1 T3 T1
M11 M2 M2
T4 T1 T3 T2 T3 T2
M33 M4 M5 M4 M5
T1 T2 T3
T4 T2
M77
M T2 T3
T4
T2
Marquages M88 R est réduit au plus grand
interdits
T4 sous-graphe contrôlable
T2
66
Théorie des régions :
Pour interdire une transition d’état interdite (M, t, M’), une place de contrôle Pc
doit vérifier :
 Une condition de séparation de l’événement (M, t, M’)
M ' ( Pc )  M 0  Pc   C  Pc ,     M  C ( Pc , t )  0
 Une condition d’atteignabilité pour chaque état Mi  R
M i ( Pc )  M 0  Pc   C  Pc ,    M i  0
 L'équation de cycle de chaque cycle   R
C ( Pc , .)    0
67
T1 Solution
M0(Pc)= 0, C(Pc,T1)= -1
M0 M1
R T2 C(Pc,T2)= 1, C(Pc,T3)= -1
T3 Pc
P1 
C(Pc,T2) + C(Pc,T3) = 0 T1 T2 T3
M0(Pc)  0
M1(Pc) = M0(Pc) + C(Pc,T2)  0 P2
Controlled model 68
M1(Pc) = M0(Pc) + C(Pc,T1) < 0
Théorie des régions
Soit le graphe de marquage G :
M0 t1 M1 t2 M2 t4 M6
1 t1 2 t3
t4 t3 t2 t1
M3 M4 M5 M7
T1
P1
T2
1 P5 P2 2 P6 3 P4
T3
P3
T4
69
Théorie des régions (Badouel et Darondeau 1999)
Soit le graphe de marquage G :
M0 t1 M1 t2 M2 t4 M6
1 t1 2 t3
t4 t3 t2 t1
M3 M4 M5 M7
C(p,t1)+ C(p,t2)+ C(p,t3)+ C(p,t4)=0 (1)

M0(p)  0 Conditions d’atteignabilité (2)
Equation de cycle
M1(p)=M0(p)+C(p,t1)  0 (3)
M2(p)=M0(p)+C(p,t1)+C(p,t2)  0 (4)
M3(p)=M0(p)+C(p,t1)+C(p,t2)+C(p,t3)  0 (5)
M4(p)=M0(p)+2.C(p,t1)+C(p,t2)  0 Conditions de séparation (6)
M5(p)=M0(p)+2.C(p,t1)+2.C(p,t2)  0 (7)
M6(p)=M0(p)+2.C(p,t1)+2.C(p,t2)+2.C(p,t3)  0 (8)
M7(p)=M0(p)+2.C(p,t1)+2.C(p,t2)+C(p,t1) < 0 (9) 70

Système À Événements Discrets

Transféré par

Droits d'auteur :

Formats disponibles

Système À Événements Discrets

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Système À Événements Discrets

Transféré par

Droits d'auteur :

Formats disponibles

AU 2015/2016

Système à événements discrets

Système à Evénements Discrets

Considérons l’exemple d’un système de production. L’évolution du

a : arrivée d’une pièce dans le stock et

• La longueur d’un mot, notée ImotI représente le nombre de

• plusieurs opérations ensemblistes sont définies sur les langages :

La chaîne u est dite préfixe de uv.

L = {s1  Σ*  s2  Σ*, s1s2  L}

La préfixe-clôture du langage L = {aabb} est :

L = {ε, a, aa, aab, aabb}.

Si L = L alors L est préfixe-clos.

Un automate est un quintuplet : A = (Q, Σ, f, q0, Qm) où :

L(A) = {s  Σ*  f(q0, s) est défini}

Lm(A) = {s  Σ*  f(q0, s)  Qm}

Deux automates sont dits équivalents s’ils génèrent et marque les

On défini deux mécanismes d’intégration d’automates : le produit

A1  A2 = (Q1 Q2, Σ, f, (q01, q02), Qm1 Qm2) où

f((q1, q2), e) = non définie sinon

A1  A2 = (Q1 Q2, Σ1 Σ2, f, (q01, q02), Qm1 Qm2) où

Modèle du procédé G Modèle de la spécification E

 : occurrence d’une panne de la machine

Le fonctionnement souhaité K est obtenu par la composition

Dans son état initial (q0), la machine M1 est à l'arrêt. L'événement

Le SED noté G est ici une

• Une machine de Moore est un 6-uplet M = (Q, Σ, f, q0, , ) où :

• Deux capteurs de fermeture

Cahier des charges

 Une condition de séparation de l’événement (M, t, M’)

 Une condition d’atteignabilité pour chaque état Mi  R

Soit le graphe de marquage G :

Soit le graphe de marquage G :

C(p,t1)+ C(p,t2)+ C(p,t3)+ C(p,t4)=0 (1)

Vous aimerez peut-être aussi