Du diagnostic au diagnostic distribué : algorithmes, structure et challenge

Télécharger le fichier pdf d’un mémoire de fin d’études

Le diagnostic `a base de coh´erence

Les travaux pionniers de Mackworth et al [dKMR92] d´efinissent diff´erents types de diag-nostics `a base de coh´erence. Dans notre ´etude nous nous int´eressons plus particuli`erement au diagnostics minimaux. Ici nous pr´esentons quelques types de diagnostics les plus utilis´es et mo-tivons notre choix.
Bien que la port´ee du diagnostic `a base coh´erence s’´etend `a diff´erents domaines, les travaux de de Kleer et al ont et´ essentiellement appliqu´es `a la d´etection de pannes dans les circuits ´electroniques.
D´efinition 2.12 (Syst`eme observ´ [dKMR92]) Un syst`eme observ´ est alors d´efini comme un triplet DS,COM P S,OBS o`u
– DS est une formule de la logique du premier ordre d´ecrivant le comportement du syst`eme
– OBS est une formule d´ecrivant les observations (revenant dans la plupart des cas a` une assignation de valeurs aux variables observables)
– COM P S est l’ensemble des composants surveill´es. Chacun de ces composants apparaˆıt en tant qu’argument de ¬ok() dans DS (ex : ¬ok(Ci) signifie que Ci est anormal).

Le langage propositionnel pour le diagnostic a` base de coh´erence

Nous notons par M od− l’ensemble des fautes ¬ok(Ci). Un diagnostic a` base de coh´erence est une explication, par des hypoth`eses de fonctionnement de composants, d’un ´ecart entre le comportement attendu et le comportement observ´ d’un syst`eme. En logique propositionnelle, cette explication prend la forme d’une conjonction de litt´eraux de modes coh´erente avec la description du syst`eme observ´. Elle traduit une hypoth`ese sur le mode de fonctionnement de tous les composants du syst`eme.
D´efinition 2.13 (Diagnostic coh´erent [dKMR92]) Soit un syst`eme observ´ DS, COM P S, OBS et M od− = {¬ok(Ci) : Ci ∈ COM P S} les propositions repr´esentant les comportements anor-maux. Soit Δ ∈ M od−, (Δ, {M od− \ Δ}) est un diagnostic coh´erent ssi Δ ∧ {M od− \ Δ} ∧ DS ∧ OBS = ⊥
Un diagnostic coh´erent est une explication coh´erente du comportement attendu d’un syst`eme, avec ses observations. Nous donnons l’exemple d’un raisonnement conduisant a` un diagnostic coh´erent expliquant l’´ecart entre le comportement attendu du processus de validation de com-mandes par internet et le sc´enario 1. Nous illustrons ce diagnostic par la Figure : 2.3
Exemple. 2.4 (diagnostic coh´erent du processus de validation de commande) Nous avons vu pr´ec´edemment que l’hypoth`ese supposant que tous les services se comportaient normalement n’expliquait pas le comportement observ´ du service de validation de commande. Supposons les modes de fonctionnement suivants : le service de la banque et de l’agence fonctionnent norma-lement (okBq, okAg) alors que le service d’ e-shopping lui est anormal (¬okEs).
1. Si le service de la banque fonctionne normalement (okBq), ´etant comparable a` une porte ET et ayant observ´ en entr´ee : la carte bleue est valide (v = V rai) et le client est solvable (s = V rai) on s’attend a` ce qu’il donne son accord (b = V rai).
2. De mˆeme si le comportement de l’agence de cr´edit fonctionne normalement (okAg), ´etant comparable a` la composition d’une porte NON et d’une porte ET, ayant observ´ que le client n’est pas endett´ (e = F aux) et sa carte bleue est valide (v = V rai) on s’attend a` ce que le service donne son accord (a).
3. Par contre si l’on suppose que le service d’e-shopping est anormal ¬okEs, on ne s’attend plus a` ce qu’il se comporte comme une porte OU comme il ´etait pr´evu. Il peut donc invalider la commande (c = F aux) alors qu’il a peut ˆetre re¸cu des avis positifs de la banque (b) et de l’agence de cr´edit (a).
Ainsi les hypoth`eses ({¬okEs}, {okBq, okAg} ) forment un diagnostic coh´erent avec la description du syst`eme de validation de commande et le sc´enario 1.
Nous remarquons que si le syst`eme observ´ est insatisfiable, il n’y a pas de diagnostics. Ainsi, la satisfiabilit´e du syst`eme observ´ est une condition n´ecessaire a` la probl´ematique de diagnos-tic. Cette remarque est tr`es utile pour la g´en´eration d’instances de syst`emes a` diagnostiquer. D’autre part, pour simplifier les d´efinitions suivantes, nous appelons diagnostic les hypoth`eses de fonctionnement anormales Δ uniquement constitu´ees de litt´eraux de mode n´egatifs. Pour revenir a` la d´efinition originale, il suffira de calculer M od− \ Δ en fonction de Δ.
´ |VM od| diagnostics
Etant donn´e un syst`eme observ´ satisfiable, il peut y avoir au maximum 2 possibles. Dans un souci d’une repr´esentation succincte on cherche soit `a repr´esenter tous les diagnostics de fa¸con compacte, soit `a conserver les plus int´eressants d’entre eux. Par exemple supposer que tous les composants d’un syst`eme sont d´efaillants en mˆeme temps n’est pas une hypoth`ese r´ealiste. Inversement supposer que seuls quelques composants d’un syst`eme sont en panne en mˆeme temps est plus r´ealiste. Ainsi nous nous int´eresserons aux diagnostics faisant l’hypoth`ese d’un nombre ou d’un ensemble minimal de composants d´efaillants.
D´efinition 2.14 (Diagnostic minimal) Etant donn´e un syst`eme observ´ satisfiable DS, COM P S, OBS et un ensemble de litt´eraux de mode n´egatifs : M od− = {¬okCi : Ci ∈ COM P S}, un diagnostic coh´erent Δ ⊆ M od− est un diagnostic coh´erent minimal ssi aucun sous-ensemble propre Δ′ t.q. Δ′ ⊂ Δ, est un diagnostic coh´erent.
Exemple. 2.5 (Diagnostics minimaux du processus de validation de commande) Dans un premier temps, nous avons vu que l’on ne pouvait pas supposer que tous les services se com-portent normalement, ainsi Δ = {} n’est pas un diagnostic. D’autre part nous avons vu que {¬okEs} ´etait un diagnostic. Puisqu’il n’existe pas de sous-ensemble de {¬okEs} qui soit un diagnostic, {¬okEs} est un diagnostic minimal. De mˆeme on peut v´erifier que l’autre diagnostic minimal est {¬okBq, ¬okAg}.
La fa¸con classique de calculer les diagnostics minimaux consiste, dans un premier temps, a` d´etecter les conflits. Un conflit peut ˆetre vu comme un symptˆome d´eclencheur de la recherche de diagnostic. Intuitivement, un conflit est un ensemble d’hypoth`eses de bon fonctionnement du syst`eme qui ne peuvent ˆetre toutes suppos´ees vraies a` la fois. Plus formellement :
D´efinition 2.15 (Conflit, conflit minimal, conflit positif ) Etant donn´e un syst`eme observ´ satisfiable DS, COM P S, OBS et un ensemble de variables de mode M od = {okCi : Ci ∈ COMP S},
– un conflit est une clause E form´ee sur les variables de modes t.q. DS ∧ OBS |= E
– un conflit E est minimal s’il n’existe pas de conflit E′ t.q. E′ |= E.
– Un conflit est dit positif (sous-entendu en termes de litt´eraux d’anormalit´es, ici ¬okCi) s’il est une disjonction de litt´eraux de M od−.
Un conflit est une cons´equence de l’´ecart entre le comportement attendu et le comportement observ´ du syst`eme. C’est un impliqu´e de DS ∧OBS. Un conflit minimal est un impliqu´e premier de DS ∧ OBS.
Dans l’exemple suivant illustr´e Figure 2.4 nous expliquons un raisonnement permettant d’in-f´erer de nouveaux conflits a` partir de la description observ´ee de notre exemple jouet. Le rai-sonnement que nous d´ecrivons reprend les principes de l’ATMS [dK86] (syst`eme de maintien de v´erit´ par hypoth`eses).
Exemple. 2.6 (Conflits minimaux du processus de validation de commande) Nous avons vu que compte tenu du sc´enario 1 nous ne pouvions pas supposer que tous les services fonc-tionnent correctement, ainsi ¬okAG ∨ ¬okEs ∨ ¬okBq est un conflit.
Supposons que le service de la banque okBq et celui d’e-shopping okEs fonctionnent correctement. Etant donn´e que le service de la banque se comporte comme une porte ET, en observant que le client est solvable (s = V rai) et que sa carte bleue est valide (v = V rai) en entr´ees, on s’attend a` ce que la banque donne son accord (b = V rai). De mˆeme, ´etant donn´e que le service d’e-shopping se comporte comme une porte OU, en observant une commande invalide en sortie (c = F aux), on s’attend a` ce que ni la banque ni l’agence de cr´edit n’ait donn´e leur accord (b = F aux), (a = F aux). Or l`a, il y a un conflit entre la valeur attendue a` la sortie du service de la banque (b = V rai) et celle attendue a` l’entr´ee du service d’e-shopping (b = F aux). On peut supposer que les services de la banque et de l’e-shopping fonctionnent correctement ensemble, ¬okBq ∨ ¬okEs est un conflit minimal. Par un raisonnement similaire nous pouvons d´eduire que ¬okBq ∨ ¬okEs est un autre conflit minimal. Par contre on ne peut pas d´eduire que seul l’un de ces services ne fonctionne pas correctement.
Le th´eor`eme suivant de de Kleer et al [dKMR92] permet de calculer tous les diagnostics minimaux d’un syst`eme a` partir de ses conflits minimaux.
Th´eor`eme 2.1 (Caract´erisation des diagnostics minimaux [dKMR92]) Etant donn´e un syst`eme observ´ satisfiable DS, COM P S, OBS et M od− un ensemble de litt´eraux de mode n´e-gatif, Δ ⊆ M od− est un diagnostic minimal de (DS, COM P S, OBS) ssi Δ est un impliquant premier de l’ensemble des conflits minimaux positifs de (DS, COM P S, OBS).
Nous illustrons ce th´eor`eme en revenant a` notre exemple de validation de commande.
Exemple. 2.7 (D´etermination des diagnostics minimaux par les conflits) Nous avons vu pr´ec´edemment que les conflits minimaux (qui, ici sont positifs) peuvent s’encoder par la
formule Σconf lits : (¬okBq ∨ ¬okEs) ∧ (¬okAg ∨ ¬okEs). Les impliquants premiers de Σconf lits sont ¬okES et ¬okBq ∧ ¬okAg. Ils sont simplement obtenus en r´esolvant les conflits. Ce sont
aussi les diagnostics minimaux du processus de validation de commande observ´ par le sc´enario 1.
Par le th´eor`eme pr´ec´edent on comprend que si l’on d´esire obtenir un diagnostic minimal par le calcul pr´ealable des conflits, avant d’obtenir le premier diagnostic minimal, il faudrait tout d’abord compiler l’ensemble des conflits minimaux. D’autre part, sans pour autant avoir l’ensemble des conflits minimaux on peut tout de mˆeme avoir des diagnostics minimaux par la remarque suivante.
Remarque 2.1 (Diagnostic minimal inclus dans un diagnostic) Etant donn´e un syst`eme observ´ DS, COM P S, OBS et un ensemble de litt´eraux de mode n´egatifs M od− = {¬okCi : Ci ∈ COM P S}, si Δ ∈ M od− est un diagnostic, alors il existe un diagnostic minimal Δ′ ⊆ Δ.
Ainsi, lors de la recherche des diagnostics, r´eduire successivement la taille d’un diagnostic quel-conque en inversant une hypoth`ese de panne par une hypoth`ese de bon fonctionnement tout en restant coh´erent, conduit a` la formation de diagnostics minimaux. Inversement, nous noterons que tout sur-ensemble d’un diagnostic minimal n’est pas forc´ement un diagnostic coh´erent. Exemple. 2.8 Supposons que l’on ajoute une r`egle d’exclusion entre les mod`ele de bon fonc-tionnement du service d’e-shopping et de la banque : (¬okBq ⇒ okEs), autrement dit, le service d’e-shopping et le service de la banque ne peuvent ˆetre tous les deux d´efaillants en mˆeme temps. Avec cette nouvelle r`egle, on constate que Δall = {¬okBq, ¬okEs, ¬okAg} n’est plus une conjonction coh´erente et donc n’est plus un diagnostic. Par contre ΔEs = {¬okEs} et ΔAg,Bq = {¬okBq, ¬okAg} qui sont des sous-ensembles de Δall, restent des diagnostics.
Par cette derni`ere remarque nous constatons que les diagnostics minimaux ne caract´erisent pas l’ensemble des diagnostic coh´erents d’un syst`eme observ´. En effet, tout prolongement d’un diagnostic minimal par un litt´eral de mode n´egatif, ne conduit pas forc´ement `a la construction d’un diagnostic coh´erent.
Dans le but d’avoir `a la fois les diagnostics int´eressants et caract´eristiques de l’ensemble de tous diagnostics de mˆeme type, de Kleer et al ont introduit les diagnostics partiels et noyaux.
D´efinition 2.16 (Diagnostics partiels et diagnostics noyaux) Etant donn´e un syst`eme ob-serv´ DS, COM P S, OBS et un ensemble de litt´eraux de mode n´egatifs M od− = {¬okCi : Ci ∈ COM P S},
– Δ ⊆ M od− ∪ M od− est un diagnostic partiel ssi toute extension de Δ (par des litt´eraux de modes positifs et n´egatifs) a` tout COM P S est un diagnostic coh´erent. Δ est un diagnostic et pour tout sur-ensemble Δ′ de Δ, Δ′ est un diagnostic coh´erent.
– Δ ⊆ M od− ∪ M od− est un diagnostic noyau ssi Δ est un diagnostic partiel et il n’existe pas de sous-ensemble Δ′ ⊂ Δ t.q. Δ′ soit un diagnostic partiel.
Implicitement, on comprend que tout prolongement d’un diagnostic partiel par un litt´eral de mode positif ou n´egatif est aussi un diagnostic partiel. Etant donn´e qu’un diagnostic noyau est un diagnostic partiel minimal, l’ensemble des diagnostics noyaux caract´erisent tous les diagnostics partiels du syst`eme observ´ et ainsi tous les diagnostics.

Le langage propositionnel pour le diagnostic a` base de coh´erence

Toujours dans la volont´e d’avoir une repr´esentation de l’ensemble des diagnostics significatifs d’un syst`eme, les travaux de Reiter [Rei87] caract´erisent a` travers les diagnostics abductifs les explications coh´erentes d’un syst`eme observ´ qui sont directement impliqu´ees (logiquement) par les observations. Un diagnostic abductif est plus pr´ecis qu’un diagnostic coh´erent dans la mesure o`u ce dernier se contente d’ˆetre coh´erent avec les observations et n’est pas n´ecessairement impliqu´e par les observations.
D´efinition 2.17 (Diagnostic abductif ) Etant donn´e un syst`eme observ´ DS, COM P S, OBS et un ensemble de litt´eraux de mode n´egatifs M od− = {¬okCi : Ci ∈ COM P S}, Δ ⊆ M od− est un diagnostic abductif du syst`eme observ´ ssi Δ ∧ DS = ⊥ et Δ ∧ DS |= OBS
Un diagnostic coh´erent est une assignation de variables de modes coh´erente avec la description du syst`eme observ´. Dans le cas g´en´eral, la recherche de diagnostics coh´erents peut s’apparenter `a le recherche des mod`eles de la formule d´ecrivant le syst`eme observ´. Dans le cas des diagnostics abductifs, Inoue [Ino92] a montr´e que les diagnostics abductifs correspondaient `a la n´egation de formules impliqu´ees par le syst`eme muni de la n´egation des observations (c-`a-d Δ ∧ DS |= OBS implique ∧DS ∧ ¬OBS |= ¬Δ ). Cette remarque permet `a tout syst`eme d’inf´erence de pouvoir compiler les diagnostics abductifs par un ensemble d’impliqu´es, cons´equence du syst`eme observ´. Dans un contexte distribu´e, un syst`eme d’inf´erence distribu´e comme Somewhere [ACG+06]serait en mesure de retourner les diagnostics abductifs minimaux.

Table des matières

1 Introduction
2 Du diagnostic au diagnostic distribu´e : algorithmes, structure et challenge
2.1 Le langage propositionnel pour le diagnostic `a base de coh´erence
2.1.1 La logique propositionnelle
2.1.2 D´ecrire et analyser un syst`eme de validation de commande
2.1.3 Le diagnostic `a base de coh´erence
2.1.4 Probl`emes autour du diagnostic `a base de coh´erence
2.2 Les structures arborescentes au coeur des approches pour le diagnostic
2.2.1 D´ecomposer pour mieux diagnostiquer
2.2.2 Les approches interpr´et´ees ou compil´ees pour le diagnostic
2.3 Probl´ematique et travaux li´es au diagnostic distribu´e
2.3.1 Probl´ematique informelle du diagnostic distribu´e avec contrˆole d’acc`es
2.3.2 Travaux li´es au diagnostic distribu´e
3 Cadre du diagnostic distribu´e de syst`emes avec contrˆole d’acc`es
3.1 Syst`eme de pairs diagnostiqueurs avec contrˆole d’acc`es
3.1.1 Le graphe d’accointances
3.1.2 Le contrˆole d’acc`es
3.1.3 Les descriptions locales des pairs diagnostiqueurs
3.1.4 Syst`eme de pairs diagnostiqueurs
3.2 Formalisation de la probl´ematique de diagnostic distribu´e avec contrˆole d’acc`es
3.2.1 Un pair diagnostiqueur, `a quoi a-t-il acc`es ?
3.2.2 Que peut expliquer un pair `a partir d’une description accessible ?
3.2.3 Probl´ematique : Comment expliquer le comportement global d’un syst`eme par les diagnostics accessibles localement coh´erents des pairs ?
4 Caract´erisation graphique des syst`emes garantissant un diagnostic distribu´e correct
4.1 Du diagnostic `a la coh´erence distribu´ee et vice versa
4.1.1 D’un diagnostic distribu´e correct `a la coh´erence globale des diagnostics locaux
4.1.2 De diagnostics locaux globalement coh´erents `a la coh´erence distribu´ee
4.2 Propri´et´es graphiques des syst`emes garantissant la coh´erence distribu´ee
4.3 Un sch´ema structur´e suffit `a garantir la coh´erence distribu´ee
4.4 La coh´erence distribu´ee n´ecessite un sch´ema joint
4.5 Pour les syst`emes d’interactions, seul un sch´ema structur´e garantit la coh´erence distribu´ee
5 D´ecomposition d’un syst`eme distribu´e vers un r´eseau structur´e respectant sa confidentialit´e
5.1 D´ecomposition Arborescente Distribu´ee (DAD)
5.1.1 La d´ecomposition arborescente en centralis´e
5.1.2 La d´ecomposition arborescente distribu´e avec confidentialit´e
5.2 D´ecomposer `a travers un arbre couvrant distribu´e
5.2.1 Construction d’un arbre couvrant distribu´e
5.2.2 De l’arbre couvrant distribu´e `a l’arbre joint distribu´e
5.3 Les bonnes propri´et´es de la d´ecomposition par ´elimination
5.3.1 D´ecomposer `a l’aide d’un ordre d’´elimination
5.3.2 D’un ordre d’´elimination `a l’arbre joint
5.4 Pourquoi des ´eliminations concurrentes nous ´eloignent de l’optimal ?
5.5 ´Elimination distribu´ee guid´ee par des ´elections locales et le passage jeton (TE)
5.5.1 D´eroulement de l’algorithme TE
5.5.2 Structures de donn´ees et notations
5.5.3 L’algorithme distribu´e d’´elimination par passage d’un jeton
5.5.4 Les ´elections locales
5.5.5 ´E limination du pair ´elu
5.5.6 Passer le jeton
5.5.7 ´E tape finale : reconnexions des clusters orphelins
5.5.8 Analyse de complexit´e
5.6 ´Evaluation de la largeur arborescente sur les graphes petit monde
5.6.1 Qualit´e des d´ecompositions arborescentes
5.6.2 Rapidit´e des d´ecompositions arborescentes
5.6.3 Conclusion
6 Diagnostic distribu´e d’un r´eseau structur´e de FNDs
6.1 Un r´eseau de FNDs est-ce raisonnable ?
6.2 Garantir un diagnostic distribu´e correct par un r´eseau structur´e de FNDs globalement coh´erentes
6.3 Un syst`eme structur´e de FNDs globalement coh´erentes est un syst`eme compil´e pour le diagnostic distribu´e
6.3.1 Un r´eseau de FNDs repr´esente tous les diagnostics minimaux d’un syst`eme
6.3.2 V´erifier qu’un diagnostic local appartient `a un diagnostic distribu´e minimal
6.3.3 R´esum´e du chapitre
Conclusion

Télécharger le rapport complet