Résumé

Separation des états du graphe de marquages d’un réseau de Petri pour la commande par supervision des systèmes à événements discrets

Média

0:00
available

Métriques

25
9
988.24 Ko
 application/pdf
bitcache://2b9bdbc5c2640185f41f5403983933dffdf41fd1

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2017-1/19870</identifier><creators><creator><creatorName>Mohaman Gonza</creatorName></creator><creator><creatorName>Laurent Bitjoka</creatorName></creator><creator><creatorName>Hassane Alla</creatorName></creator></creators><titles>
            <title>Separation des états du graphe de marquages d’un réseau de Petri pour la commande par supervision des systèmes à événements discrets</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2017</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Fri 22 Sep 2017</date>
	    <date dateType="Updated">Fri 22 Sep 2017</date>
            <date dateType="Submitted">Mon 23 Oct 2017</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2b9bdbc5c2640185f41f5403983933dffdf41fd1</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>33777</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Résumé—L’espace d’états accessibles d’un système à événements discrets (SED) modélisé par réseau de Petri (RdP) correspond au graphe de marquages. L’exploration de ce graphe, bien que fastidieuse, permet d’identifier l’ensemble des états pertinents à la synthèse d’une commande par supervision. Cependant, la dynamique du RdP traduit par le graphe de marquages peut être sujette au problème d’explosion combinatoire. Celle-ci est minimisée lorsqu’on réalise le produit synchrone des RdP du SED pour obtenir un modèle RdP du fonctionnement désiré en boucle fermée. Dans cet article, partant des règles de franchissement des transitions des RdP, le graphe de marquages a été représenté par la fonction de transition, puis écrit sous forme matricielle. Les éléments de la matrice de transition ont ensuite été codifiés selon le caractère interdit ou autorisé de l’état qu’ils représentent par la spécification du SED. Cette codification a permis de séparer les états du graphe de marquages en ensemble d’états interdits et autorisés suivant un hyperplan défini par une fonction de décision. Parmi les états interdits, il y a des états interdits générés par la synchronisation via des transitions associés aux événements incontrôlables. L’hyperplan est alors constitué ou permet d’identifier les états interdits frontières nécessaires au calcul d’un contrôleur optimal, par la méthode des invariants de marquages. Mots clés— Réseau de Petri, Graphe de marquages, Matrice de transition, Hyperplan, Système à Evènements Discrets I. INTRODUCTION Dans le cadre de l’automatique des systèmes à événements discrets (SED), la théorie de supervision [1][2] fournit de nombreux concepts et résultats fondamentaux pour la synthèse de commande par supervision. La recherche académique explore cette théorie mathématique afin de disposer d’un cadre formel pour l’industrie [3]. Les résultats obtenus sont remarquables surtout pour des systèmes modélisés par les réseaux de Petri [4][5][6]. Mais, le passage de la synthèse à l’implantation de la commande n’est pas systématique à cause du phénomène d’explosion combinatoire inhérent au SED modélisé par les automates d’une part [7], et à la taille du graphe de marquages lorsque le SED est modélisé par réseau de Petri d’autre part [8]. Ces résultats semblent être limités, voire exploratoires seulement [9][10] et le concept de contrôlabilité peut s’avérer insuffisant [11][12]. En effet, une spécification de commande peut être jugée incontrôlable alors qu’en réalité elle est réalisable par un système de commande ayant la caractéristique d’être déterministe. Par ailleurs, le calcul classique du langage suprême contrôlable peut mener à un ensemble restreint, voire vide, pour une spécification qui pourrait être implantée sans aucune incontrôlabilité [13][14]. Pour les SED modélisés par les réseaux de Petri (RdP), la méthode des invariants de marquages, basée sur l’expression de la spécification sous la forme des contraintes nécessaire au calcul du contrôleur, résout le problème des états interdits par l’ajout de places et d’arcs «de contrôle» au RdP du SED [15][16]. Le contrôleur obtenu ne peut garantir le respect des spécifications que si tous les événements du SED sont contrôlables. Car, la synchronisation des modèles RdP via les transitions associées aux évènements incontrôlables génère des états interdits supplémentaires. D’où la nécessité de séparer l’espace d’états du SED en ensembles d’états autorisés et interdits, afin de fournir à cette méthode l’ensemble adéquat des contraintes [17][18]. De manière classique, le calcul du contrôleur est réalisé en représentant les spécifications par des contraintes linéaires [19]. Malheureusement, cette approche ne permet pas de discerner les états qui peuvent être injectivement codés comme des états appartenant à des ensembles précis ou locaux [20][21]. Dans ce cas, la séparation des états du graphe de marquages du modèle RdP de commande du SED est effectuée par un ensemble d’états intermédiaires constituant l’hyperplan de séparation [22][23]. Notre démarche consistera à représenter le graphe de marquages accessibles [24] du RdP de commande du SED en boucle fermée par une matrice de transition (section III). Les éléments de cette matrice seront codifiés par une fonction associative, qui affecte une valeur algébrique à chaque état selon la spécification (section III). A partir de la matrice de transition codifiée, une fonction de décision sera définie pour assurer la séparation des états tout en déterminant les états de l’hyperplan (section IV). En fin, une application de la démarche à un exemple (section V) permettra de comparer les résultats à la méthode proposée par [18] pour la détermination des contraintes bijectives. Separation des états du graphe de marquages d’un réseau de Petri pour la commande par supervision des systèmes à événements discrets. Mohaman GONZA1 , Laurent BITJOKA1 , Hassane ALLA2 1. LESIA (Laboratoire d’Energie, Signal, Imagerie et Automatique), ENSAI, Université de Ngaoundéré, Cameroun mohaman.gonza@univ-ndere.cm, lbitjoka@univ-ndere.cm 2. Laboratoire GIPSA-Lab, Université Joseph Fourrier, Grenoble, France hassane.alla@gipsa-lab.grenoble-inp.fr II. GRAPHE DE MARQUAGES ET ENSEMBLES D’ETATS D’UN RESEAU DE PETRI DE COMMANDE PAR SUPERVISION A. Graphe de Marquages d’un Réseau de Petri L’espace d’états accessibles d’un SED modélisé par le RdP correspond au graphe de marquages de ce RdP, qu’il soit ordinaire ou généralisé. Le RdP ordinaire peut être défini comme un 3-plet R = (P, T, W) où P et T sont deux ensembles finis et non vides respectivement de places et de transitions ; W : (PT)∪(TP) {0,1} est une application d’incidence [25][26]. Un RdP généralisé est défini comme un RdP ordinaire sauf que, l’application d’incidence est définie par W : (PT)∪(TP) ℕ. L'état d'un SED modélisé par un RdP est déterminé par le marquage M : P ℕ des places à un instant donné. C'est un vecteur de dimension le nombre de places, qui peut être représenté graphiquement par des jetons associés à une place donnée.  T ni PMPMPMM )()()( 0  (1) Un réseau de Petri augmenté d’un marquage initial M0 sera noté R = (P, T, W, M0). L’analyse du comportement du SED modélisé par un RdP marqué consiste à construire le graphe de marquages G du RdP à partir du marquage initial M0. Le graphe de marquages G d’un RdP est défini comme un 4-uplet G = (M, , , M0) où M est l’ensemble fini de marquages,  est l’ensemble fini des événements associés aux transitions,  est la fonction de transitions d’états de M    M, et M0 M est le marquage initial. En principe, pour chaque transition ti validée par M0, on crée un nouveau sommet représentant le marquage Mi tel que M0 [tiMi et on joint M0 au marquage Mi par un arc portant l’étiquette ti. On poursuit la construction à partir de ces nouveaux nœuds. La construction est arrêtée lorsque les marquages ne valident aucune transition, ce qui suffit à prouver que le réseau est non vivant, soit les marques ont un prédécesseur qui leur est égal. L’ensemble des marquages obtenus correspond à l’espace d’états accessibles [27], A(R ; M0) défini par : A(R; M0) = {Mi  ℕP ∃  T*, M0 [ Mi} (2) Avec  = t1 . . . tn séquence de franchissement de transitions A chaque séquence de franchissement  = t1 . . . tn est associée un vecteur caractéristique noté  tel qu’on puisse avoir une équation fondamentale : T i WMM  0 (3) Si l’ensemble des états accessibles est fini, on pourra effectivement construire le graphe et vérifier certaines propriétés (ex. absence de blocage) du RdP. Lorsque l’ensemble des états accessibles est infini, on construit un graphe, appelé graphe de couverture qui permet de savoir par exemple si le RdP est borné [28]. B. Etats autorisés et interdits Soient RP = {PP , TP , P , WP} et RS = {PS , TS , S, WS} les modèles RdP du procédé et de la spécification d’un SED. Le modèle en boucle fermée du SED à contrôler peut être obtenu en réalisant la composition synchrone [29] des deux : R= RPRS telle que : P = Pp ∪PS ; T=TP∪TS – TPS ; =P∪S (4) A partir du modèle R= RPRS, on peut construire le graphe de marquages accessibles du SED en remplaçant chaque transition par l’événement associé. Une fois ce modèle construit, les différents ensembles de l’espace d’états accessibles peuvent être déterminés en appliquant l’algorithme de Kumar sur le graphe de marquage de R [20]. En effet, l’ensemble des événements  peut être répartis en ensembles d’événements contrôlables c et incontrôlables u tels que :  = c∪u. A cause de la synchronisation avec des événements incontrôlables, le procédé ne peut pas respecter la spécification ; il apparait donc un problème d’états interdits. Définition II.1. Soient MP et MS les marquages des places du procédé RP et ceux de la spécification RS ; l’ensemble des états interdits MU est ainsi défini: MU = {(MP, MS) |∃ t u ∀Pi RP, M(Pi) = k et ∃ Pj RS, M(Pj) = n ; k  n} (5) Il y a aussi un autre type d’état interdit qu’il faut ajouter à l’ensemble défini ci-dessus : ce sont les états faiblement interdits. L’ensemble d’états faiblement interdits est constitué de tout marquage qui n’est pas lui-même interdit, mais à partir duquel un marquage interdit peut être atteint via une séquence de transitions incontrôlables   u Définition II.2. Soit MA l’ensemble des états autorisés par la spécification, l’ensemble des états faiblement interdits MF sera ainsi défini : MF = {Mi | Mi MA, MjMU et σ u, Mi [σMj} (6) A partir des ensembles MF et MU, on peut construire deux autres ensembles d’états très utiles dans la synthèse de commande par supervision : - L’ensembles des états interdits frontières MIF correspondant aux états faiblement interdits accessibles par occurrence d’événements contrôlables. MIF = {Mj | Mi MA, MjMU ou MF et σ  c, Mi[σMj} (7) - L’ensemble des états autorisés critiques MAC correspondant aux états à partir desquels l’occurrence d’événements contrôlables mène à un état frontière. MAC = {Mi |Mi MA, MjMIF et σc, Mi[σMj} (8) Par l’interdiction de franchissement d’événements contrôlables d’états autorisés critiques vers les états interdits frontières, on empêche l’accessibilité de tous les états interdits. En somme, l’espace d’états accessibles pertinent du modèle RdP de commande par supervision est constitué de l’ensemble d’états autorisés MA et de l’ensemble d’états interdits frontières MIF . Exemple II.1. Un système manufacturier est composé de deux machines identiques M1 et M2, et d’un stock entre les deux machines. Les deux machines travaillent en série et de façon indépendante, puisent des pièces brutes en amont et rejettent des pièces usinées en aval. Le fonctionnement du système doit respecter la présence d’un stock de capacité limité à 1 situé entre les deux machines. FIG. 1. MODELES DE RDP DU PROCEDE RP ET DE LA SPECIFICATION RS DE L’EXEMPLE II.1 La FIG.1 montre les modèles RdP de l’exemple II.1, dont le graphe de marquages du modèle R=RPRS est donné à la FIG. 2 ci-dessous. FIG. 2. GRAPHE DE MARQUAGES DE L’EXEMPLE II.1 Il est facile de voir sur le graphe de marquages de la FIG. 2 que la séquence de transitions construit sur le mot d1f1d1f1 s’écrit : (M0, d1f1d1f1) = M2. Ainsi, le langage généré par le graphe de marquages, noté L(R), est l’ensemble des étiquettes des séquences de transitions. Les événements d1 et d2 désignent les démarrages des machines tandis que les événements f1 et f2 désignent les fins de cycle des machines. Nous avons : -  = {d1, f1, d2, f2} , Σc = {d1, d2} et Σu = {f1, f2} - Etats autorisés : MA = {M0, M1, M2, M4, M5, M7} - Etats interdits frontières : MU = {M3, M6} - Etats critiques est : MAC = {M2, M5} Les états résultant de M3 [f1 et M6 [f1 sont des états non accessibles, qui ne font pas partie du graphe de marquages qui se veut fini. Cependant, ils peuvent être considérés comme des états interdits pour les besoins de simplification dans la réduction des contraintes [29]. III. MATRICE DE TRANSITION ASSOCIEE AU GRAPHE DE MARQUAGES DU RDP D’UN SED A. La Matrice de Transition Le graphe de marquages, espace d’états accessibles par la détermination des successeurs partant d’un marquage initial, peut être représenté sous forme matricielle [30]. Pour construire un graphe de marquages, il faut préciser l’alphabet  , l’ensemble des états M et l’état initial M0. La fonction de transition d’un graphe de marquages déterministe est  : M x   M. Lorsque le graphe de marquages est non-déterministe, la fonction de transition est  : M x M*. Elle peut être spécifiée explicitement par une table que nous appelons matrice de transition de dimension n x m (Tableau I) avec : - n : le nombre de lignes constituées des états - m : le nombre de colonnes constituées des transitions étiquetées par les événements Considérons le cas de deux RdP R1 et R2 d’un SED à contrôler, définis sur les alphabets respectifs, 1 et 2. La composition synchrone R1 et R2 donne un RdP R= R1 R2 défini sur  = 1∪2 , l’union des deux alphabets. L’ensemble T peut être divisé en trois sous-ensembles disjoints: 1\2, 2\1 et 1∩2 . Soient M0 = (M10, M20) l’état initial et Mi = (M1i, M2i)  A(R, M0) un état quelconque. Les cases de la table de transition sont constituées des résultats du franchissement des transitions associées aux événements, à savoir Mi[tj tel que : - (M10, M20) [σ (M1i, M20), si σ(E1\E2) - (M10, M20) [σ (M10, M2i), si σ(E2\E1) - (M10, M20) [σ (M1i, M2i), si σ(E1∩E2) La fonction de transition fait le bilan de l’action de toutes les liaisons du RdP en assurant l’intégrité des informations vis-à-vis du graphe de marquages G, dont les états sont désignés Mi et les transitions associées aux evenements sont désignées tj. Nous associons à G une martice  = [ij] appélée matrice de transition définie par : ij = Mi[tj (9) Nous choisissons de représenter cette écriture sous forme de table, appelée matrice de transitions associée au graphe de marquages du RdP R= R1 R2. RP RS P1P3P6P2P3P5 P2P3P6 f1 d1 d1 d2 d2 P1P 3P5 P1P4P5 P2P4P5 f2 d1 P1P4P6P2P4P6 f1 f2 M1 M2 M3 M0 M7 M4 M6 f1 f2 d1 f1 M5 TABLEAU I. MATRICE DE TRANSITION D’UN GRAPHE DE MARQUAGES  t1 t2  tm M0 00 02  0m M1 11 12  1m      Mn n1 n1  nm Considérons le graphe de marquages de la FIG. II, défini par : M = {M0, M1, M2, M3, M4, M5, M6, M7} et  = {d1, f1, d2, f2}. La fonction de transition δ est décrite explicitement par sa matrice de transition (Tableau II) TABLEAU II : MATRICE DE TRANSITION DU GRAPHE DE MARQUAGES DE LA FIGURE 2  d1 f1 d2 f2 0M { 1 M }    1M  { 2M } 0  2M { 3M }  { 7M }  3M { 4M } x   4M  { 5M }   5M { 6M }   { 2M } 6M  x  { 3M } 7M { 4M }   { 0M } B. Codification de la Matrice de Transition La matrice de transition offre deux avantages : i) d’abord, elle donne une description exhaustive du graphe de marquages intégrant les événements, les états et la fonction de transition ; 2) ensuite, elle permet une visualisation très intuitive du fonctionnement du graphe de marquages pour simuler une séquence de transitions t1 . . . tm telle que pour tout couple de transitions successives (tj, tj+1) l’état destination de tj est l’état origine de tj+1. Par ailleurs, les éléments ij = Mi [tj de la matrice de transitions peuvent être injectivement codés [21] de façon à permettre la séparation des états suivant leurs caractères interdit ou autorisé par la spécification. Ainsi, on peut déterminer facilement l’ensemble des états interdits et ensuite l’ensemble des états interdits frontière. La codification consiste à attribuer une valeur algébrique définie par une fonction associative notée : g : ij {-1, 1} (10) Cette fonction attribue une valeur aux états Mi résultant du franchissement de la transition tjT. Nous obtenons ainsi une matrice de transition codifiée (Tableau III) A=[aij]IRnxm dont les éléments sont notés aij et tels que :       sinon;0 tionspécificalaparinterditestMsi tionspécificalaparautoriséestMsi ij a i i ;1 ;1 (11) Lorsque l’état Mi résultant du franchissement d’une transition tj est autorisé par la spécification, alors aij= 1; sinon, aij= -1 lorsque Mi est interdit par la spécification. Les éléments aij des états interdits par la spécification dits « états interdits de départ » sont tous considérés négatifs. Appliquons cette codification à la matrice de transition du tableau II. La spécification exige l’interdiction de marquages des places P2 et P6 simultanément. C’est-à-dire qu’il ne faut pas que la machine M1 soit en état de marche si le stock est plein. L’exploration du graphe de marquages permet d’identifier les états M3 = P2P3P6 et M6 = P2P4P6 comme états interdits par la spécification. En appliquant la règle de codification, nous obtenons le résultat du tableau III suivant. TABLEAU III : MATRICE DE TRANSITION CODIFIEE DU GRAPHE DE MARQUAGES DE LA FIGURE 2  d1 f1 d2 f2 0M 1 0 0 0 1M 0 1 0 0 2M -1 0 1 0 3M -1 0 0 0 4M 0 1 0 0 5M -1 0 0 1 6M 0 0 0 -1 7M 1 0 0 1 IV. SEPARATION DES ETATS DU GRAPHE DE MARQUAGES ET SYNTHESE DU CONTROLEUR A. Séparation des Etats du Graphe de Marquages Considérons le fait que le graphe de marquages du modèle RdP de commande du SED en boucle fermée correspond à un automate à états finis ; alors il y a suffisamment d’ensembles pour discerner tous les états du système [31]. De plus, si un événement n’est pas autorisé en un état, il doit exister un ensemble qui “inhibe” cet événement en cet état. La séparation consiste à associer à chaque état Mi du graphe de marquages son ensemble interdit MU ou autorisé MA vis-à-vis d’un ensemble d’états constituant l’hyperplan de séparation, noté H. Nous associons à H une fonction de décision g(Mi) définie sur l’ensemble des états M =MAMU par : g(Mi)= + i, Mi ; i  IR et  = 0 un vecteur du mot vide  (12) H sépare strictement MA et MU si et seulement si :         ni MMtoutpourMg Uii Aii ,,0 ;0)( 0)(  (13) Si H ne sépare pas strictement M, alors il existe un ensemble MH tel que : MH = {Mi : g(Mi) = 0} (14) Rappelons que la codification de la matrice de transition est tributaire des états interdits par la spécification. A cet effet, l’ensemble MH des états constituant l’hyperplan peut appartenir soit à l’ensemble d’états (faiblement) interdits : on parle d’états d’interdits frontières; soit à l’ensemble d’états autorisés : on parle d’états autorisés critiques. Pour caractériser la séparation, nous considérons T = t1 …tm une base canonique et normée à 1 de g(Mi) telle que la matrice de transition codifiée dans cette base soit la matrice A(t1 …tm), notée A = [i]. Soit g(Mi) la réponse qui permet de distinguer Mi comme état interdit ou autorisé, nous posons : g(Mi)= [aij ]. [tj ]T . Mi (15) Pour l’exemple II.1 nous pouvons écrire : nn4n3n2n1 n T 2211n4n3n2n1n 114131211 1 T 2211141312111 004030201 0 T 04030201 0 T 2211040302010 ].Ma+a+a+[a= .M]fdf[d].aaa[a=)g(M- ].Ma+a+a+[a= .M]fdf[d].aaa[a=)g(M- ].Ma+a+a+[a= M.1]11[1].aaa[a= .M]fdf[d].aaa[a=)g(M-  Nous remarquons que : g(Mi)=aij. Mi = i . Mi avec i= aij (16) Sous forme de matricielle : [g(M)] = [A][M] avec A= [i ] (17) Comme les marquages sont toujours positifs (Mi  0), la séparation va dépendre du signe de   m j iji a 1  - i  0 : Mi est un état interdit par la synchronisation des transitions incontrôlables (y compris les états interdits de départ) - i  0 : Mi est un état autorisé par la spécification - i = 0 : Mi est un état interdit frontière ou un état critique appartenant à l’ensemble MH constituant l’hyperplan de séparation. La codification de la matrice de transition permet donc de déterminer les états interdits générés par la synchronisation d’événements incontrôlables, sans que l’on ait à explorer les branches du graphe de marquages pour détecter les séquences d’événements incontrôlables qui mènent le SED vers les états interdits par la spécification. L’application de notre méthode de séparation des états au graphe de marquages de la FIG. 2 à partir de la matrice de transition codifiée (Tableau III) donne le résultat présenté au Tableau IV. TABLEAU IV : SEPARATION DES ETATS DU GRAPHE DE MARQUAGES  d1 f1 d2 f2 i=aij 0M 1 0 0 0 1 1M 0 1 0 0 1 2M -1 0 1 0 0 3M -1 0 0 0 -1 4M 0 1 0 0 1 5M -1 0 0 1 0 6M 0 0 0 -1 -1 7M 1 0 0 1 2 Nous pouvons distinguer les états tels que définis à la Section II : - Etats autorisés : {M0, M1, M2, M4, M5, M7} - Etats interdits frontière : {M3, M6} - Etats critiques : {M2, M5} MH B. Synthèse du Contrôleur par la Méthode des Invariants de Marquages Les deux ensembles constitués par l’ensemble des états interdits frontières et l’ensemble des états autorisés critiques sont essentiels à la synthèse du contrôleur. En effet, par l’interdiction de franchissement des événements contrôlables d’états autorisés critiques vers les états interdits frontières, on empêche l’accessibilité de tous les états interdits par la spécification. La synthèse du contrôleur optimal consiste à utiliser les contraintes linéaires liées aux états interdits frontières pour déterminer par le concept des invariants [15][32], les places de contrôles à ajouter au modèle du système en boucle fermée. Soit WR la matrice d’incidence du modèle RdP du SED en boucle fermée. Le contrôleur est le RdP formé des transitions du modèle du procédé et d’un ensemble des places de contrôle qui fonctionnent en parallèle avec le SED. Soit WC la matrice d’incidence du RdP correspondant au contrôleur. L’objectif du contrôleur est de forcer le SED à respecter des contraintes de type )bl( ,  telles que    n i ii b)P(M.l 1 (17) Où M (Pi) est le marquage de la place Pi, li et k sont les nombres réels. La contrainte de type (17) peut être transformée en une égalité en ajoutant une variable positive et entière M (PC) telle que :  n i Cii b=)(PM+)(PM.l 1 (18) Tout P-semi-flot X, tel que XT = [l1 , …, li, …, ln, 1] = [LT , 1], où li  IN, permet d’avoir l'invariant de marquage donné par la relation suivante : XT .Mj = XT .M0 (19) Il est démontré que [9][32] : XT .W = 0 (20) La matrice L= [l1 , …,li,…,ln]T permet de calculer de manière algébrique la matrice d’incidence du contrôleur selon la relation : WC = - LT WR et MC0 = b - LT MR0 (21) Où Mc0 est le marquage initial des places de contrôle et MR0 est le marquage initial du procédé. Calculons par la méthode des invariants le contrôleur pour le système manufacturier de l’exemple II.1. La matrice d’incidence du procédé WR est :                            0110 0110 1100 1100 0011 0011 RW Les états interdits frontières M3 et M6 modélisent le fonctionnement où la machine M1 a déjà commencé la fabrication d’une pièce, alors que M2 n’a pas encore fini ou commencé le traitement de la pièce précédemment usinée par M1.  Construisons les contraintes : 2)()()(6 2)()()(3 642642 632632   PMPMPMPPPM PMPMPMPPPM - Le vecteur de contraintes est :              2 2 ; 101010 100110 bLT  Calculons le contrôleur WC = - LT WR =         1001 1201 et MC0= b – LT MR0 =       2 1 FIG. 3. MODELE SED DE L’EXEMPLE II.1 SOUS CONTROLE : A) RDP DU SYSTEME CONTROLE ; B) GRAPHE DE MARQUAGES. Le graphe de marquages du SED sous contrôle montre que si une place de contrôle n’est pas marquée, alors la transition correspondante est bloquée à condition que l’événement qui lui est associé soit contrôlable d1. Le contrôleur obtenu de cette manière est optimal malgré qu’il ne soit pas capable d’empêcher l’événement incontrôlable f2 de se produire. V. APPLICATION ET DISCUSSION A. Application sur un Système Manufacturier Exemple V.1. On considère un système composé de deux machines et d’un robot (FIG. 4) tiré de [29]. Chaque machine opère sur une seule pièce brute à la fois. Lorsque la machine a fini son travail (événement incontrôlable ftmi), le robot décharge la machine et lorsqu’il a fini le déchargement de la machine (événement incontrôlable fdmi), il transfère la pièce vers un stock. Après la fin du transfert (événement incontrôlable ftri), le robot revient à son état initial. Seul le début de tâche sur chaque machine (événement c1 et c2) est contrôlable. La spécification est imposée par le robot.  Modèles RdP du procédé et du robot d1 f P1 P2 P6 P5 2 PC1 PC2 d2 f P3 P4 A) P1P3P6 PC2P2P3P5 PC2 f1 d1 d2 P1P 3P5PC1 P2 C2 P1P4P5 P2 C1PC2 P2P4P5 PC1 f2 d1 P1P4P6PC1 M1 M2 M0 M7 M4 f2 f1 M5 B) FIG. 4 : MODELES RDP DU SYSTEME : R1, RDP DES DEUX MACHINES ET R2, RDP DE SPECIFICATION DU ROBOT  Graphe de marquages et matrice de transition FIG. 5: GRAPHE DE MARQUAGES ACCESSIBLES DE R= R1R2 TABLEAU VI : MATRICE DE TRANSITION DU SYSTEME  c1 c2 ftm1 ftm2 fdm1 fdm2 ftr 1M 2M 5M      2M  7M 3M     3M  8M   4M   4M  9M     1M 5M 7M   6M    6M      4M  7M   8M 10M    8M   x  9M   9M 12M    X  5M 10M    X  11M  11M  12M     2M 12M         Séparation des états du graphe de marquages Considérons l’état interdit Mi où la machine M1 est en marche (P2 marquée) et le robot est en train de transférer la pièce (P9 marquée). Cet état sera interdit quel que soit l’état de la machine M2. Cette spécification interdit au système d’atteindre les états M11 = P2P4P9 et M12 = P2P5P9 , qui seront ici des états interdits par la spécification. La synchronisation des modèles R1 et R2 via les événements incontrôlables (ftm1, ftm2, fdm1, fdm2) ne permet pas de respecter cette spécification. Donc, il y a des états interdits supplémentaires à déterminer par la codification de la matrice de transition. TABLEAU V: MATRICE DE TRANSITION CODIFIÉE  c1 c2 ftm1 ftm2 fdm1 fdm2 ftr I =aij 1M 1 1 2 2M 1 1 2 3M 1 1 2 4M 1 1 2 5M 1 1 2 6M 1 1 2 7M 1 1 2 8M -1 1 0 9M -1 -1 1 -1 10M -1 -1 -2 11M -1 -1 -2 12M -1 Nous distinguons les états tels que définis à la Section II : - Les états autorisés : {M1, M2, M4, M5, M7} - Les états interdits frontières : {M8, M9, M10} avec M8  MH l’hyperplan B. Discussion Comparons notre méthode à celle proposée par Vasiliu [18].  Méthode proposée par Vasiliu Cette méthode est basée sur une vision spatiale du graphe de marquages du RdP de fonctionnement du SED en boucle fermée. Les contraintes nécessaires au calcul (algorithme) du contrôleur sont dérivées de l’équation d’hyperplan qui sépare le graphe de marquages en ensembles d’états autorisés et interdits. Appliquons directement cette méthode à notre exemple d’application en suivant les étapes ci-après : - Construction du graphe de marquages SED en boucle fermée (FIG. 5) - Identification des ensembles d’états autorisés et interdits Il s’agit d’appliquer l’algorithme de Kumar [33] pour déterminer l’espace d’états pertinents constitués de deux P1P4P7 P2P4P P3P4P8 c1 c2 ftm1 c2 c2 P1P5P7 P2P5P P3P5P8 c1 ftm2 ftm1 P1P6P8 P2P6P c1 ftm2 ftr ftr ftr M1 M2 M3 M5 M6 M7 M8 M10 P1P4P9 fdm 1 M4 c2 P1P5P9 fdm 1 M9 fdm c2 fdm M11 P2P5P c1 ftr M12 P2P4P c1 ftm2 ftm2 fdm ftm1 c1 ftm2 P1 P2 P4 P5 c2t1 t2 t5 t4 Machine 2 P7 t7 Robot t9 R1 R2 P3 t3 P6 t6fdm1 fdm2 P8 t8 ftr t10 ftm1 ftm2 fdm1 fdm2 t11 P9 Machine 1 ensembles nécessaires et suffisants : l’ensemble d’états autorisés et l’ensemble d’états interdits frontières. L’ensemble des états interdits frontières identifié est : {M7, M8, M9, M10, M11} par le franchissement des transitions associées aux événements contrôlables c1 et c2. Nous pouvons constater que l’état M7 identifié comme état autorisé par notre approche, est plutôt un état interdit frontière ici. Or, il est un état prédécesseur des états interdits frontières M8 et M10 et ne pose aucun problème pour le calcul du contrôleur. Par ailleurs, le nombre d’états interdits frontières est important sans pour autant être tous nécessaires au calcul du contrôleur, qui peut être de taille importante. - Détermination des contraintes La contrainte liée à un état est définie par :  n j jiji PMac 1 )(: (22) Elle caractérise l’équation d’un hyperplan de séparation d’un espace n-dimensionnel tel que : - ai1M(P1) + ai2M(P2) + ... + ainM(Pn) = ain+1 ; soit la frontière entre les deux ensembles. - ai1M(P1) + ai2M(P2) + ... + ainM(Pn) ≤ ain+1 ; soit un état autorisé - ai1M(P1) + ai2M(P2) + ... + ainM(Pn) > ain+1 ; soit un état interdit Considérons l’état interdit frontière M8. M8 est interdit  M(P3) + M(P5) + M(P8) > 2 , d’où la contrainte admissible : M(P3) + M(P5) + M(P8)  2 Cette contrainte doit interdire l’état frontière associé et sans interdire un état autorisé quelconque. Pour garantir cela, il faut calculer l’ensemble minimal des coefficients par optimisation de la contrainte telle que : M8 = P3P5P8  a3 + a5 + a8 > a10 a1 + a4 + a7  a10 a2 + a4 + a7  a10 MA autorisé  a3 + a4 + a8  a10 avec a1 + a4 + a9  a10 a1 + a5 + a7  a10 a1 + a6 + a8  a10 La solution : M(P3) – M(P8)  0 Cette méthode, bien que systématique, a comme inconvénient la construction et l’exploration du graphe de marquages pour identifier les états interdits frontières. En général, dans les systèmes réels, il y a un grand nombre d’états interdits, donc la complexité du calcul de la contrainte pour trouver la solution de séparation augmente. Pour notre approche, le contrôleur doit avoir pour chaque état interdit frontière une place de contrôle et on peut réduire le nombre de contraintes [28][34]. En outre, nous utilisons les états critiques constituant l’hyperplan pour identifier les états interdits d’un point de vue spatial et/ou comportemental suivant la spécification. C. Calcul du contrôleur du système manufacturier  Construction des contraintes des états interdits frontières {M8, M9, M10}: 2)()()( 2)()()( 2)()()( 86210 9519 8538    PMPMPMPPPM PMPMPMPPPM PMPMPMPPPM 862 951 853 Le vecteur de contraintes est :                       2 2 2 ; 010100010 100010001 010010100 bLT La matrice d’incidence du SED en boucle fermée WR :                                       1100100 0110110 1010010 0110000 0011000 0101000 0000110 0000011 0000101 RW  Calcul du contrôleur WC = - LT WR =              0220101 1111201 0101220 ; MC0 = b- LT MR0 =           2 1 2  Modélisation de la commande du système en boucle fermée    1 1 2 min n j ja 2 c1 P1 P2 P4 P5 c2 2 2 P7 P3 P6 2 2 P8 ftm1 ftm2 fdm 1 fdm 2 ftr P9 PC1 PC2 PC3 FIG. 6: MODELE RDP DU SED EN BOUCLE FERMEE SOUS CONTROLE VI. CONCLUSION Notre travail est situé en amont de la méthode des invariants de marquages, car celle-ci ne fournit pas de solution de contrôle optimale si elle est implémentée de manière classique. En effet, des états interdits peuvent être générés lorsque la synchronisation entre le modèle du procédé et celui de la spécification est réalisée via des transitions incontrôlables. Par ailleurs, les inclusions totales ou partielles de support entre les états interdits et les états autorisés peuvent entraîner l’interdiction d’un grand nombre de comportement désirés du SED. Pour contourner cet obstacle, nous avons proposé une méthode simple de séparation du graphe de marquages, espace d’état du RdP du SED en boucle fermée. Notre approche permet de déterminer les états interdits frontières, résultant de l’opération de composition synchrone, et les contraintes admissibles qui garantissent l’optimalité du contrôleur même en termes de transitions incontrôlables. Les états interdits frontières et/ou états autorisés permettent de séparer les états du graphe de marquages en ensemble d’états interdits et ensemble d’états autorisés. Une matrice de transition associée au graphe de marquages est codifiée par une fonction associative, qui prend en compte les états interdits par la spécification. La fonction de décision a permis de définir l’ensemble d’états frontières constituant l’hyperplan de séparation. En perspective, nous chercherons à déterminer les contraintes admissibles directement à partir de la structure du RdP du SED en boucle fermée et à trouver une équivalence de la condition de contrôlabilité de la théorie de supervision basée sur les RdP. REFERENCES [1] P. J. Ramadge and W. M. Wonham, “Supervisory control of a class of discrete event processes,” Lecture Notes in Computer Science (LNCIS), Springer-Verlag, Germany, vol. 63, pp. 477-498, 1983. [2] C. Cassandras and S. Lafortune, “Introduction to discrete event systems,” 2nd Edition, Springer - Verlag, 2008. [3] F. Charbonnier, H. Alla and R. David, “The Supervised control of discrete-Event dynamic Systems,” IEEE Transactions on control systems technology, vol. 7, no 2, 1999. [4] H. Alla, R. David, M. Di Mascolo et J-L. Ferrier, “Analyse et commande des systèmes à événements discrets,” Editions Hermès Science, 2000. [5] M. Machin, J. Guiochet, D. Powell et H. Waeselynck, “Introduction à la synthèse de supervision,” Rapport LAAS CNRS 13067, Hal Archives Ouvertes, 2013. [6] J. M. Roussel, “Contribution à la commande sûre des systèmes à evènements discrets,” Habilitation à diriger des recherches, ENS Cachan, HAL archives ouvertes, 2015. [7] P. Marangé, T. Abdelouahed, F. Gellot et V. Carré-Ménétrier, “Etude du comportement global d’un SED en vue de la validation de sa commande spécifiée par Grafcet, ” Journal européen des systèmes automatisés JESA, Vol 42, no 1, pp. 63-94, 2009. [8] H-E. Gougam, A. Subias et Y. Pencolé, “Diagnosticabilité de motifs de supervision par dépliage de réseaux de Petri,” Manifestation avec acte : 5e Journées Doctorales /Journées Nationales MACS, Strasbourg, pp.139-144, 2013. [9] G. Ciardo, Y. Zhao and J. Xiaoqing, “Ten Years of Saturation, A Petri Net Perspective, Lecture Notes in Computer Science,” K. Jensen, S. Donatelli, and J. Kleijn (Eds.): ToPNoC V, LNCS 6900, Springer- Verlag, pp. 51-95, 2012. [10] M. Sogbohossou et A. Vianou, “Un dépliage par processus pour calculer le préfixe complet des réseaux de Petri,” Proceedings of CARI, pp. 97, 2016. [11] M. Nourelfath et E. Niel, “Relaxation du concept de contrôlabilité pour une synthèse de la commande des systèmes de production,” Première Conférence Internationale Francophone d’Automatique (CIFA), Lille, pp. 526-531, 2000. [12] S. Rezig, “Approches Canoniques pour la Synthèse des Contrôleurs Réseaux de Petri,” Thèse PhD, Université de Lorraine, 2016. [13] W. M. Wonham, “Notes on control of discrete-event systems,” Technical report, no ECE 1636F/1637S, Department of ECE, University of Toronto, 2003. [14] A. Ghaffari, N. Rezg, and X. Xie, “Design of a live and maximally permissive Petri net controller using the theory of regions,” IEEE Trans. Robot. Autom, vol 19 no 1: pp 137–141, 2003. [15] K. Yamalidou, J. O. Moody, M. Lemmon and P. Antsaklis, “Feedback control of Petri Nets based on place invariants,” Automatica, vol. 32, no. 1, pp. 15-28, 1996. [16] Yin and S. Lafortune, “On the decidability and complexity of diagnosability for labeled Petri Nets,” IEEE Transactions on Automatic Control, 2017. [17] J. Komenda, S. Lahaye et J-L. Boimond, “Le produit synchrone des automates (max, +),” JESA-MSR, vol. 43, pp. 1033-1047, 2009. [18] A-I Vasiliu, “Synthèse de contrôleurs des systèmes à événements discrets basée sur les réseaux de Pétri,” Thèse PhD, HAL archives ouvertes, 2012. [19] A. Giua and C. Seatzu, “A systems theory view of Petri nets,” in C. Bonivento, L. Marconi, C. Rossi & A. Isidori, eds, “Advances in Control Theory and Applications,” Lecture Notes in Control and Information Sciences, Springer, vol. 353, pp. 99–127, 2007 [20] R. Kumar, V. Garg and V.I. Marcus, “On controllability and normality of discret event dynamics systems,” Systems and control letters, vol 17, pp. 157-158, 1991. [21] E. Badouel, Darondeau et L. Bernardinello, “Polynomial algorithms for the synthesis of bounded nets,” Proccedings Caap 95, Lecture notes in computer science vol 915, pp. 364–378. Springer, 1994. [22] A. Amirou, “Optimisation des SVMs pour la discrimination des signaux,” Thèse de doctorat, Université Mouloud Mammeri –Tizi- Ouzou, 2015. [23] J. E. Falk, Y. Bandurova and L. Yeganova, “Sets separation problems and global optimization,” Third world congress of nonlinear analysts, Elsevier science Ltd, vol 47, pp.1857-1867, 2001. [24] H. Wimmel, “Infinity of intermediate states is decidable for Petri Nets,” Lecture Notes in Computer Science, Applications and theory of Petri Nets international Conference, ICATPN, J. Cortadella and W. Reisig (Eds.), LNCS 3099, Springer, pp. 426–434, 2004. [25] R. David and H. Alla, “Discrete, continuous, and hybrid Petri Nets,” Springer, 2010. G. Feuillade et S. Pinchinat, “Spécifications modales de réseaux de Petri,” RS - JESA –MSR’05, vol 39, pp. 287-301, 2005 [26] J-L. Ferrier et J-L. Boimond, “Systèmes dynamiques à événement discrets: du modèle à la commande,” Séminaire JDA'99, hal.archives- ouvertes, 2013. [27] J. Desel and J. Esparza, “Negotiations and Petri Nets,” Proceedings of the International Workshop on Petri Nets and Software, Engineering PNSE’15, Brussels, Belgium, vol. 1372, 2015. [28] E-B. Dorsaf, S. Haddad and R. Hennicker, “Refinement and asynchronous composition of modal Petri Nets,” Lecture Notes in Computer Science LNCS 6900, K. Jensen, S. Donatelli, and J. Kleijn (Eds.), Springer, pp. 96–120, 2012. [29] A. Dideban and H. Alla, “Reduction of constraints for controller synthesis based on safe Petri nets,” Automatica, vol. 44, no 7, pp. 1697– 1706, 2008 [30] J. Hopcroft, R. Motwani, and J. Ullman, “Introduction to Automata Theory, Languages and Computation,” 3rd Edition, Prentice Hall, 2007 [31] A. Ehrenfeucht and G. Rozenberg, “Partial 2-structures, Part II: State Spaces of Concurrent Systems,” Acta Informatica, vol. 26, pp. 343–368, 1990 [32] C. Seatzu, M. J. Silva and H. van Schuppen, “Control of discrete-event systems, Automata and Petri net Perspectives,” Lecture Notes in Control and Information Science, Springer, vol. 433, 2012. [33] R. Kumar, “Supervisory synthesis techniques for discrete event dynamical systems,” Thesis PhD, University of Texas, 1991. [34] J. Moody and P. Antsaklis, “Petri net supervisors for DES with uncontrollable and unobservable transitions,” IEEE Trans. Autom. Control, vol. 45, no 3, pp. 462–476, 2000.