Supervisory Control Theory

Introduction

Supervisory Control Theory ou théorie de la supervision des systèmes à évènements discrets introduit par P.J.Ramadge et W.M.Wonham [1] se base sur la théorie des langages et des automates [10]. Elle définit l’utilisation de trois entités : le SED, une spécification souhaitée et un superviseur. Cette théorie définit la possibilité de synthétiser un modèle de superviseur dit valide à partir du modèle du SED et de la spécification. Le premier objectif de cette démarche est de fiabiliser un système susceptible d’avoir un comportement qui peut être gênant ou dangereux. Le deuxième objectif est la possibilité pour un système dit ouvert, dont les comportements possibles sont multiples, de réaliser différents superviseurs dont les rôles seront de contraindre le système dans un comportement donné pour un contexte donné.

Principe de la théorie de la supervision

La théorie  de la supervision définit que ces trois entités, le SED, la spécification souhaitée et le superviseur sont modélisés par leurs langages conformément à la théorie des langages et des automates. Ceci permet de bénéficier des opérations liées aux langages et aux automates à états finis puisque les langages utilisés sont des langages réguliers. Dans l’ensemble de ce chapitre, ces entités sont considérées comme des automates notés G pour le système, K pour la spécification et S pour le superviseur de langage respectif L(G), L(K) et L(S).


Idéalement, le superviseur, une fois réalisé, est composé avec le SED pour former le système supervisé. A chaque changement d’état du système, le superviseur va suivre l’évolution du système et lui notifier l’ensemble des évènements qu’il est autorisé à générer (figure 35). Cependant, deux situations prises en compte par la théorie peuvent survenir. La première est que certains évènements, par nature, ne peuvent pas être interdits. La seconde situation est que certaines transitions du système ne peuvent être vues par le superviseur, l’empêchant de fournir un ensemble d’évènements autorisés cohérent. Ces deux situations sont définies dans la théorie de la supervision sous les notions de commandabilité et d’observabilité. Ainsi, un alphabet  est divisé en plusieurs ensembles notés c pour l'alphabet des évènements commandables, uc l'alphabet des évènements non commandable, o l'alphabet des évènements observables et uo l'alphabet des évènements non observables tel que

ce qui signifie qu'un évènement peut être à la fois non commandable et non observable, commandable et non observable, observable mais non commandable ou enfin commandable et observable. Ces notions de commandabilité et d'observabilité sont très importantes car elles vont conditionner les limites du superviseur et sa réalisation. De nombreux travaux approfondissent ces notions dans [1], [3], [5], [6].
Pour la réalisation du système supervisé, la théorie de la supervision définit que le modèle du superviseur, donc le langage L(S), peut être concrétisé par une fonction ou une table d'associations qui à une séquence d'évènements donnée renvoie une liste d'évènements autorisés. Une autre approche, illustrée par la figure 36, utilise l’intersection (ou le produit strict pour les automates) du langage du système et celui du superviseur afin d’obtenir le langage du système supervisé. Ainsi, le modèle du système supervisé est obtenu par:





La théorie de la supervision définit enfin la notion de superviseur bloquant par L(S/G)=Lmpréf(S/G).

Définition d'une spécification

La définition de la spécification est l'opération la plus difficile pour la théorie de la supervision car celle-ci doit répondre à différents critères afin d'être utilisable pour la génération du superviseur [1], [9]. Le but de la spécification est de définir le comportement du système bouclé, ainsi, si K est un automate décrivant la spécification valide, il faut avoir L(K)=L(S/G), comme illustré par la figure 37.




Pour cela, une méthode consiste à définir une première spécification par un automate E en considérant le comportement global voulu en s'intéressant à tous les évènements présents dans le système. Il est possible de réaliser l'opération de produit synchronisé de façon à obtenir L(K) qui sera égal à l'intersection de L(E) et de L(G), comme illustré par la figure 38.




Une autre méthode permet de définir le comportement voulu en ne considérant que certains évènements. Cependant, la spécification E doit être augmentée afin de correspondre au système. Ainsi, l'opération de produit synchronisé permet d'obtenir cette spécification (illustré par la figure 39). Cette méthode a pour avantage d’être simple mais elle implique une attention particulière aux évènements non utilisés pour la définition de E à cause du produit synchronisé qui va augmenter son langage.





L’opération de produit synchronisé est alors utilisée dans les deux cas tels que : K=G||sE car dans la première approche cela amène à faire un produit strict puisque E et G ont le même alphabet, dans la deuxième approche, cela va permettre l'augmentation du langage de E sur la considération du comportement intrinsèque de G. Enfin, il est nécessaire de valider la spécification K obtenue pour le système en vérifiant que celle-ci est non bloquante.

Une autre approche est de définir un automate qui invalide une séquence donnée. Ainsi, un automate est réalisé pour modéliser cette séquence dont tous les états sont marqués sauf le dernier qui représente la survenue de l'évènement qui réalise la séquence comme illustré par la figure 40. Ceci permet de réaliser des spécifications ciblées pour certains cas précis.





Il faut retenir que la théorie de la supervision ne fait pas état de méthode générique pour la définition de spécification. Chose qui n'est d'ailleurs pas son objectif puisque son but n'est que la synthèse d'un superviseur par la validation de la spécification K souhaitée sur le principe du blocage et de l'inclusion dans le langage de SED G. La réalisation d'une spécification reste donc un problème dans la démarche de synthèse de superviseur.

Synthèse du superviseur

La spécification étant définie, la synthèse du superviseur selon [1], [10] s’effectue par le produit du système G et de la spécification K suivi de l’opération Trim. Ceci est la base de la démarche pour la synthèse du superviseur mais elle ne prend pas en compte les aspects liés à la commandabilité et à l’observabilité des évènements. Cette opération de base s’explique par la relation

qui existe entre le superviseur, la spécification et le système, comme ré-illustré par la figure 41. Cette relation signifie que la spécification est l’objectif du système supervisé par l’égalité L(S/G)=L(K). Elle signifie également que le  langage du superviseur ne se limite pas nécessairement au langage de la spécification.

Commandabilité et Observabilité dans la synthèse du superviseur

Les notions de commandabilité et d’observabilité du superviseur pour le système sont liées aux événements commandables et observables. La nature de ces événements amène des particularités dans la relation entre le système et le superviseur lors de la supervision. Les événements non commandables ne peuvent pas être interdits par le superviseur et le système sera toujours susceptible de les réaliser. Les événements non observables ne permettent pas au superviseur de suivre l’évolution du système de manière cohérente. Le superviseur est alors susceptible après la survenue d’un évènement non observable de fournir une commande erronée.

Problèmes liés à la commandabilité

Comme il a été dit précédemment, les évènements non commandables ne peuvent pas être interdit pas le superviseur. Cette particularité, si elle n’est pas prise en compte lors de la synthèse amène à la réalisation d’un superviseur qui composé avec le système sera susceptible de violer la spécification comme illustré par la figure 42.



Pour prendre en compte cette particularité, la spécification est alors l’élément sur lequel vont intervenir les éventuelles corrections pour que la synthèse donne un superviseur commandable. La théorie de la supervision définit alors une spécification comme étant commandable si


Si la spécification n’est pas commandable, alors la théorie de la supervision définit qu'il existe un langage suprême commandable L(K') inclus dans L(K) qui est commandable (illustré par la figure 43). Ce langage est obtenu à l’aide de l’algorithme de Kumar [5]. Cet algorithme identifie dans l’automate K les états à partir desquels, dans le système, des évènements non commandables sont susceptibles d’être générés.

Problémes liés à l’observabilité

La notion d’observabilité caractérise les évènements de l’alphabet selon deux types, les évènements observables et les évènements non observables. Lors de la supervision, à chaque changement d’état du système, le superviseur, par la lecture de l’évènement qui vient d’être réalisé, est mis à jour afin de produire un nouvel ensemble d’évènements autorisés. Lors de la survenue d’un évènement non observable, le superviseur n’est pas notifié du changement d’état du système et n’est pas capable de fournir un ensemble d’évènements autorisés cohérent. Pour cela, la théorie de la supervision impose que la commande souhaitée pour le système soit la même avant et après un évènement non observable sinon le superviseur synthétisé sera non observable et la spécification risque alors d’être violée comme l’illustre les figures 44 et 45.

Exemple:
En considérant "c" comme étant non observable, si l'état 4 est interdit dans le système G alors il y a un problème d'observabilité dans la spécification K qui définit une commande différente avant et après l’évènement non observable. Un superviseur ne pourra donc pas savoir s'il se trouve dans l'état 1 ou l'état 3.








La théorie de la supervision caractérise alors la spécification K comme étant observable si elle permet la synthèse d’un superviseur observable. Si K n’est pas observable alors, contrairement à la notion de commandabilité, il n’existe pas de langage suprême observable qui puisse être calculé. Dans pareil cas, il est nécessaire de se rattacher à la notion de normalité.

Normalité et observabilité

La normalité, c’est l’invariance d’un langage par rapport à un autre suivant un alphabet donné. La normalité permet de vérifier qu’un langage prend en compte tous les évènements contenus dans un alphabet pour un autre langage. Dans le cadre de la théorie de la supervision, la normalité est rapprochée de l’observabilité en définissant l’alphabet intéressant comme étant celui des évènements non observables. Ainsi, la spécification K est définie comme normale pour le système G et pour les évènements non observable si :

La notion de normalité décrite dans [1] et [11] est très pratique car elle permet d'assimiler la notion d'observabilité. En fait, si un langage est normal alors il est observable et de plus il est possible de la même manière que pour la commandabilité de construire un langage suprême normal (cf. algorithme de Kumar [5]) si K n'est pas normal. A cela, il faut tout de même observer quelques restrictions, c'est à dire qu'il faut considérer les évènements non observables comme étant non commadables et ainsi il y a équivalence entre observabilité et normalité.

Supervision modulaire

La supervision modulaire, illustrée à la figure 46 et définie dans [1], [6], [11], [12] a pour intérêt de diviser le problème de la définition de la spécification en plusieurs modules. Pour un système G, n spécifications K seront définies qui permettront la génération de n superviseurs. Ceci permet de limiter la taille et la complexité de la spécification globale si plusieurs objectifs de commandes sont à réaliser. L'intersection des n superviseurs donnera alors le superviseur global. Les spécifications ne doivent pas être en conflit sinon le superviseur sera bloquant. Ainsi, si pour K1 et K2, deux spécifications, l'égalité

 
est respectée alors elles ne sont pas en conflits. Si K1 et K2 sont commandables alors leur intersection l'est aussi sinon leur langage suprême commandable l'est. Pour l'observabilité, il faut utiliser la notion de normalité afin d'obtenir un langage normal pour que le superviseur soit observable.

Supervision décentralisée

La supervision décentralisée [1], [11], [12], illustrée à la figure 47, propose de voir le système sous plusieurs points de vues locaux (en utilisant la projection) et de définir pour chaque point de vue une spécification restreinte afin de générer un superviseur local. Chaque superviseur aura la responsabilité de la gestion d'un sous-ensemble de l'alphabet du système, ces différents sous-ensembles de l’alphabet ne devant pas avoir d’intersection non vide sans un risque de conflit entre les différents superviseurs. Pour le superviseur généré en local, la supervision du système G revient à considérer les évènements supprimés par la projection comme non observables. Il ne va donc s'intéresser qu'à l'aspect du système pour lequel il a été conçu.





La conjonction des différents superviseurs va être réalisée par l'intersection des différents superviseurs en ayant réalisée une projection inverse sur l'ensemble de l'alphabet afin de préserver leurs comportements respectifs. Il faut cependant rester prudent car, si par l'utilisation de la supervision décentralisée il est possible de simplifier localement le problème en plusieurs sous système, la supervision ne prendra pas en compte les interactions possibles entre ces sous systèmes et ces dernières ne pourront pas être supervisées.

Conclusions

La théorie de la supervision donne un cadre théorique idéal pour la modélisation et la commande de systèmes à évènements discrets par la génération d'un superviseur valide en prenant en compte de nombreux aspects susceptibles de poser des problèmes tels que ceux liés aux événements non commandables ou non observables. Ceci reste un cadre théorique qui ne prend pas en compte les problèmes liés à l'implantation d'un superviseur dans un environnement d’exécution. Cet environnement n’est pas défini dans le cadre théorique de la supervision mais importe pourtant dans la réalisation de modèles de SED cohérents et dans la manière dont le ciblage sera effectué. Pour cela, l'ingénierie dirigée par les modèles propose une approche pour la définition et la transformation de modèles et établit alors comment réaliser et cibler un système supervisé dans un environnement d'exécution spécifique.

Références

[1] Ramadge P.J., Wonham W.M. The control of discrete-event systems. IEEE Transactions on Automatic Control, 1989, Vol. 77, N° 1, p. 81-98.

[3] V. K. Garg, R. Kumar, S. I. Marcus. On controllability and Normality of discrete event dynamical systems. Systems and control letters, 1991, Vol. 13, N°3, p. 157-168.

[5] R. Kumar, M. A. Shayman. Formulae relating controllability, observability and Co-observability. Automatica, 1998, Vol. 34, p. 211-215.

[6] H. Flordal. Modular controllability verification and synthesis of discrete event systems, Mémoire de these, Chalmers University of Technology, 2001.

[9] A. Overkamp, and J. H. van Schuppen. Control of discrete event systems. Amsterdam (NL), Stichting Mathematisch Centrum, 1994 p. 453-467.

[10] C. G. Cassandras, and S. Lafortune. Introduction to discrete event systems, Kluwer Academic Publishers, 1999, ISBN: 0-7923-8609-4.

[11] M. H. Lamouchi. Synthèse de superviseur pour des systèmes à évènements discrets partiellement observés,  Mémoire de thèse, Université de Montréal, département de génie électrique et de génie informatique de l'école polytechnique de Montréal, 2002.

[12] B. Gaudin. Synthèse de contrôleurs sur des systèmes à évènements discrets structurés. Mémoire de thèse, Université de Rennes, Institut de Formation Supérieure en Informatique et Communication, 2004.