Diagnosticabilité

La recherche de diagnosticabilité d'un système d'événement discret est un sous-domaine dans la recherche de diagnostic. La diagnosticabilité est la capacité de mesurer l'état d'un système à fin de diagnostiquer toute faute du système dans un délai fini. La recherche sur la diagnosticabilité d'un système d'événement discret peut fournir les suggestions sur la conception d'un système, surtout les positions des capteurs du système.

Histoire

Diagnosticabilité est une tentative de traduction du terme anglais diagnosability. En réalité, diagnosability n'existe pas dans le vocabulaire anglais. Il est cité premièrement dans Sampath et al. 1995. Tout d'abord, diagnosticabilité apparaît comme un concept dans le domaine de diagnostic du système d'événement discret. La diagnosticabilité est devenu un sous domaine très important dans ce domaine.

Définition

La diagnosticabilité est une capacité de mesurer l'état d'un système à fin de diagnostiquer toute faute du système dans un délai fini.

Définition[1] — Un langage algébrique préfix fermé et vivant L(G) est diagnosticable qui respecte la projection P et la partition $\Pi _{f}$ en $\Sigma _{f}$ , si

(\forall i\in \Pi _{f})(\exists n_{i}\in N)[\forall s\in \Psi (\Sigma _{f}i)](\forall t\in L/s)\quad [\|t\|\geq n_{i}\Rightarrow D].

Condition D est :

\omega \in P_{L}(G)^{-1}P(st)\Rightarrow \Sigma _{fi}\in \omega .

G est un automate fini
L(G) est le langage généré par G
$\Psi (\Sigma _{fi})=\{s\sigma \in L(G)|\sigma \in \Sigma _{fi}\}$ est l'ensemble des séquences se terminant par une faute de $\Sigma _{fi}$
L/s est l'ensemble des séquences suffixes de s dans L(G)
$\|t\|$ est la longueur de la séquence t
$P_{L}(G)^{-1}P(u)$ désigne toutes les séquences $v$ dans L(G) telle que $P(v)=u$ .

Cette définition signifie que pour toutes les séquences suffixes de $s$ , on peut diagnostiquer d'une faute de type $F_{i}$ avec un délai fini. On peut noter dans cette définition, qu'il n'est pas montré que les événements doivent être observables. Alors, les chercheurs proposent d'autres types de définitions.

Définition — Une faute est diagnosticable si elle peut être diagnostiqué certainement dans un nombre fini d'événements observables après sa occurrence[2].

Aussi une autre définition :

Définition[3] — Un événement non observable $e_{d}$ dans un langage vivant n'est pas diagnosticable s'il existe deux séquences $S_{N}$ et $S_{Y}$ qui satisfont les conditions suivantes :

$S_{Y}$ contient $e_{d}$ ; $S_{N}$ ne contient pas $e_{d}$ ;
$S_{Y}$ est arbitrairement long après $e_{d}$ ;
$P(S_{Y})=P(S_{N}).$

$e_{d}$ est diagnosticable s'il n'existe pas tel couple.

Approches principales

Maintenant, la recherche sur la diagnosticabilité du système d'événement discrets est très active. Etant donné la définition de la diagnosticabilité, les approches différentes ont été proposées pour tester la diagnosticabilité des systèmes. Les approches peut être classifiées en 3 parties. Les approches centralisées, les approches décentralisées et les approches modulaires. Alors, il s’agit 3 type de diagnosticabilité[4] :

Diagnosticabilité locale : la capacité d'un module à diagnostiquer ses fautes correspondantes à l'aide de ses seules observations locales.
Diagnosticabilité modulaire : la capacité d'un système à diagnostiquer chacun de ses fautes à l'aide des seules observations du module d'appartenance de la faute.
Diagnosticabilité centralisée (ou globale, monolithique) (la diagnosticabilité de Sampath) : la capacité d'un système à diagnostiquer n'importe laquelle de ses fautes à l'aide de l'ensemble de ses observations.

Approches centralisées

Selon la définition de diagnosticabilité centralisé, les hypothèses suivantes sont faites :

le langage généré doit être vivant ;
il n'existe pas de cycle d'événements non observables ;
chaque faute est inobservable et permanente.

Approche de diagnostiqueur

Basé sur la définition de la diagnosticabilité globale, l'approche de diagnostiqueur[1] est la première approche pour étudier la diagnosticabilité du système. L'idée principale est de construire le diagnostiqueur de système et après cela, il est prouvé que la langue est diagnosticable si et seulement s’il n’existe pas de cycles indéterministes[1] pour tous les types de fautes. Cette approche intuitive est inspirée par la définition de la diagnosticabilité. Cependant, il n'est pas toujours possible de construire le diagnostiqueur pour un système complexe, car il y a peut-être le problème de l'explosion combinatoire. Ça vaut dire, dans le pire des cas, l'espace d'état du diagnostiqueur est exponentielle dans le cardinal de sorte que la complexité en temps est également exponentielle du nombre d'états du système et doublement exponentielle du nombre de types de fautes. Il s'agit d'un problème critique pour tester la diagnosticabilité d'un système complexe.

Approche de vérificateur

Pour résoudre le problème d'explosion combinatoire et simplifier la complexité algorithmique, deux approches de vérificateur[5] - [6] sont proposées. L'idée principale est de construire le vérificateur de système. Il est prouvé que la langue est diagnosticable si et seulement si le vérificateur n’a pas de cycles confondus pour tous la partition de types de fautes. Étant démontré, l'approche de vérificateur nécessite temps polynomial dans le cardinal de l'espace d'état du système. Par conséquent, la diagnosticabilité est vérifiable en temps polynomial. En outre, l'approche de Cassez[7] est similaire à l'approche du vérificateur, et sa complexité est également polynomial. L'approche de vérificateur a une complexité algorithmique plus simple que l'approche de diagnostiqueur. En théorie, cette approche permet de résoudre le problème de l'explosion combinatoire. Toutefois, la taille de vérificateur d'un système complexe peut aussi être très grande dans le pire des cas, alors cette approche n'est pas exactement efficace pour tester la diagnosticabilité des systèmes complexes.

Approches décentralisées

Afin d'en tirer une solution à l'explosion combinatoire de l'approche de diagnostiqueur, une architecture décentralisée coordonnée[8] est proposé, qui se composent de plusieurs sites. Chaque site dispose d'un diagnostiqueur sur un sous-ensemble d'événements observables pour diagnostiquer la présence de tous les types de fautes. En raison d'une observabilité locale, il n'est pas capable d'une tâche unique pour chaque site. Les informations de diagnostic générées sur les sites locaux est spécifié par le protocole. Les sites locaux utilisent les règles de communication pour échanger des informations de diagnostic et le coordinateur utilise des règles de décision pour les tests de diagnosticabilité de système.

Les hypothèses utilisées d'approches décentralisées sont les suivantes :

le langage généré est toujours vivant ;
il n'existe pas de cycle d'événements non observables ;
chaque faute est inobservable et permanente ;
la langue n'est pas diagnosticable pour chaque site et la partition de ces types de fautes ;
chaque site connaît les événements observables par d'autres sites ;
la communication entre le site local et le coordonnateur est fiable.

La partie critique de cette approche est un protocole approprié. Plusieurs protocoles sont proposés pour assurer la communication entre le site local et le coordonnateur. L'approche décentralisée construit plusieurs sites à éviter de construire le diagnostiqueur du système entier.Le problème d'explosion combinatoire est ainsi résolu en utilisant cette méthode. Cependant, il y a encore des difficultés à choisir le protocole approprié. Surtout avec la croissance du nombre de sites, le protocole pourrait être très compliquée. La conception de sites et le choix du protocole doivent être également considérés dans l'application pratique. En bref, l'approche décentralisée résout le problème de l'explosion combinatoire, mais d'autres questions complexes apparaissent.

Approche distribuée

Une architecture de diagnostic est proposée pour les systèmes distribués physiquement[9]. Un échange direct d'informations est admis à la place de coordinateur de l'approche décentralisée. Ce type de système distribué est considéré comme une combinaison de plusieurs sites séparés. Chaque site a un diagnostiqueur pour diagnostiquer un sous-ensemble de types de fautes associées au site.

Approche modulaire

Basée sur les recherches précédentes, la définition de la diagnosticabilité modulaire[10] est proposée. Un ensemble de composants est modulairement diagnosticable par rapport à l'ensemble de ses événements observables et de tous ses fautes, si chaque type de ses modules de fautes peut être diagnostiquée en utilisant uniquement les événements observables de ce module. L'idée principale de l'approche modulaire est la suivante.

Étape 1. Tester la diagnosticabilité locale de tous les composants. Si elles sont toutes diagnosticables, le système est modulairement diagnosticable. Sinon, passer à l'étape 2.
Étape 2. Découvrir tous les cycles indéterministes dans le diagnostiqueur local. Pour chaque composant non-diagnosticable, construire un module en exécutant produit synchrone avec d'autres composants qui ont événements observables commun avec ce composant. Tester la diagnosticabileté de ce module.
Étape 3. Répéter l'étape 2 jusqu'à ce que tous les modules sont diagnosticables, alors le système est modulairement diagnosticables. S'il existe un module qui ne peut jamais être diagnosticables, le système n'est pas modulairement diagnosticable.

La diagnosticabilité modulaire est un type de diagnosticabilité moins forte que la diagnosticabilité globale. Mais en pratique, la diagnosticabilité modulaire semble suffisante pour diagnostiquer les fautes. L’approche modulaire réduit le risque de problème d'explosion combinatoire en décomposant le système en des composants. De plus, il n'est pas nécessaire de construire un coordinateur pour faire la fusion d'information, donc il est plus exécutable en pratique.

Perspective

Avec le développement des recherches dans ce domaine, on s’intéresse au diagnostic des systèmes temporisés. La technique de vérification de modèles est utilisée pour tester la diagnosticabilité du système temporisé en utilisant une logique temporelle (CTL (en), LTL…) ou temporisée (TCTL). Les logiciels, par exemple KRONOS[11] et UPPAAL[12], sont développés pour traiter ces problèmes.

Ce qui concerne les notations du modèle, non seulement l'automate fini et l'automate temporisé sont utilisés, mais aussi le réseau de Petri, le réseau de Petri temporisé et le réseau de Petri temporel. Les recherches sur la diagnosticabilité du système sont vraiment enrichies et en pratique, le test de la diagnosticabilité du système peut élaborer des recommandations sur la conception du système.

Notes et références

(en) Meera Sampath, Raja Sengupta, Stéphane Lafortune et al., « Diagnosability of Discret-Event System », IEEE Transactions on Automatic Control, vol. 40, n^o 9,‎ 1995, p. 1555-1575 (lire en ligne [archive du 3 mars 2016], consulté le 24 juin 2014).
(en) Janan Zaytoon et Stéphane Lafortune, « Overview of fault diagnosis methods for Discret Event Systems », Annual Reviews in Control, vol. 37,‎ 2013, p. 308-320.
(en) Christos G. Cassandras et Stéphane Lafortune, Introduction to Discrete Event Systems, Springer, 2008, 2^e éd., 772 p. (ISBN 978-0-387-33332-8, lire en ligne).
Ramla Saddem, Diagnosticabilité modulaire appliquée au Diagnostic en ligne des Systèmes Embarqués Logiques, Ecole Doctorale Université Lille Nord-de-France, 2012, 121 p..
(en) Tae-Sic Yoo et Stéphane Lafortune, « Polynomial-Time Verification of Diagnosability of Partially Observed Discrete-Event Systems », IEEE Transactions on Automatic Control, vol. 47, n^o 9,‎ 2002, p. 1491-1495 (lire en ligne).
(en) Shengbing Jiang, Zhongdong Huang et al., « A Polynomial Algorithm for Testing Diagnosability of Discrete-Event Systems », IEEE Transactions on Automatic Control, vol. 46, n^o 8,‎ 2001, p. 1318-1321 (lire en ligne).
F. Cassez et S. Tripakis, Approches formelles des systèmes embarqués communicants, Hermès, 2008 (lire en ligne).
(en) R. Debouk, S. Lafortune et al., « Coordinated decentralized protocols for failure diagnosis of discrete events systems », Discret Event Dynamic Systems: Theory and Application, Kluwer Academic Publishers, vol. 10,‎ 2000, p. 33-86 (lire en ligne).
(en) R. Sengupta, « Diagnosis And Communication In Distributed Systems », dans 4th International Workshop on Discrete Event Systems WODES'98, Cagliari, Italie, 1998 (lire en ligne), p. 26-28.
(en) Olivier Contant, Stéphane Lafortune et al., « Diagnosability of Discrete Event Systems with Modular Structure », Discrete Event Dynamic Systems, vol. 16, n^o 1,‎ 2006, p. 9-37 (lire en ligne).
KRONOS.
UPPAAL.

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.