Diagnosticabilité — Wikipédia

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

La traduction de cet article ou de cette section doit être revue (juin 2014).

Le contenu est difficilement compréhensible vu les erreurs de traduction, qui sont peut-être dues à l'utilisation d'un logiciel de traduction automatique. Discutez des points à améliorer en page de discussion ou modifiez l'article.

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.

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.

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^[Quoi ?] L(G) est diagnosticable qui respecte^[pas clair] la projection P et la partition ${\displaystyle \Pi _{f}}$ en ${\displaystyle \Sigma _{f}}$, si

${\displaystyle (\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^[pas clair] :

${\displaystyle \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
• ${\displaystyle \Psi (\Sigma _{fi})=\{s\sigma \in L(G)|\sigma \in \Sigma _{fi}\}}$ est l'ensemble des séquences se terminant par une faute de ${\displaystyle \Sigma _{fi}}$
• L/s est l'ensemble des séquences suffixes de s dans L(G)
• ${\displaystyle \|t\|}$ est la longueur de la séquence t
• ${\displaystyle P_{L}(G)^{-1}P(u)}$ désigne toutes les séquences ${\displaystyle v}$ dans L(G) telle que ${\displaystyle P(v)=u}$.

Cette définition signifie que pour toutes les séquences suffixes de ${\displaystyle s}$, on peut diagnostiquer d'une faute de type ${\displaystyle 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.

Aussi une autre définition :

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.

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.

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.

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.

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.

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.

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.

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.

• Portail de l'informatique théorique