Diagnóstico Baseado em Modelos

Wellington R. Pinheiro

Instituto de Matemática e Estatística - Universidade São Paulo (USP)São Paulo, SP – Brasil

wrp@ime.usp.br

Resumo. Diagnóstico Baseado em Modelos (DBM) é um método utilizado parafazer o diagnóstico de sistemas construídos pelo homem, utilizando o modelocorreto de funcionamento desses sistemas. Devido à complexidade envolvidanesse processo, um sistema computacional que automatize essa tarefa, é cer-tamente uma ferramenta de interesse. Nesse trabalho será apresentada umaabordagem para DBM, através de um sistema clássico de Inteligência Artifi-cial: o GDE. Será também apresentada uma extensão do GDE, o GDE+ queconsidera, durante a tarefa de diagnóstico, um modelo de falhas de componen-tes. Além disso, também será apresentado o Algoritmo de Reiter, que pode serutilizado para realizar uma das principais subtarefas do GDE.

1. Introdução

O processo de diagnóstico tem como objetivo descobrir as falhas em um determinadosistema1 que apresenta comportamento discrepante do esperado. Por exemplo, um enge-nheiro mede a saída de um circuito eletrônico e percebe que o valor medido é diferente doesperado. Após essa observação ele inicia um processo de diagnóstico do circuito, formu-lando hipóteses de falha que possam explicar o comportamento observado. Algumas dashipóteses possíveis são: falha em algum dos componentes, umcurto-circuito, problemana alimentação do circuito, entre outras. Para esse engenheiro formular o conjunto dehipóteses é necessário que ele tenha algum conhecimento prévio a respeito de eletrônicae sobre o circuito em questão. Quanto mais profundo for o seu conhecimento sobre essesassuntos, mais provável que ele encontre as falhas do sistema.

De uma forma geral, a tarefa de diagnostico consiste em encontrar os componentesfalhos de um sistema que são causadores das discrepâncias observadas no comportamentodesse sistema [Benjamins, 1993]. Essas discrepâncias de comportamento devem ser ob-serváveis de alguma forma. Por exemplo, um circuito analógico pode ter suas saídasmedidas por instrumentos; uma lâmpada que não acende pode ser observada através davisão. Não importa a forma como a observação é feita, mas sim ainformação sobre ocomportamento do sistema fornecido para a tarefa de diagnóstico.

A dificuldade de se fazer o diagnóstico depende basicamente da quantidade decomponentes do sistema e da dependência entre eles. Assim, sistemas com um númeroelevado de componentes torna a tarefa de diagnóstico muito complexa para ser realizadapor um ser humano, mesmo sendo um especialista. Podem existir também situações es-pecíficas, como o caso em que o especialista não está disponível ou não é possível fazer

1O termo “sistema” pode ser usado de uma forma muito ampla, podendo indicar um circuito eletrônico, robôs emuma linha de produção, um programa de computador, o corpo humano, etc.

medições no sistema, entre outras adversidades. Assim, construir um sistema computa-cional que automatiza a tarefa de diagnostico, com pouca ou até nenhuma intervençãohumana, é certamente uma ferramenta de interesse. Baseado emum conjunto de informa-ções a respeito do sistema a ser diagnosticado (que podem serreferentes à sua estrutura,ao seu comportamento, experiências de diagnósticos passados, entre outras) e observa-ções feitas durante o seu funcionamento, uma ferramenta de diagnóstico deve ser capazde raciocinar sobre essas informações e observações para identificar os componentes pos-sivelmente falhos. Espera-se que uma ferramenta de diagnóstico seja capaz de identificaros componentes responsáveis pela falha de uma forma precisae correta, caso contrário,essa ferramenta seria de pouca utilidade (assim como um médico que apresenta diagnós-ticos incorretos aos seus pacientes).

Nesse trabalho, será apresentada a abordagem de diagnóstico baseado em mo-delos, através do sistema clássico de Inteligência Artificial: GDE (General DiagnosisEngine) [de Kleer and Williams, 1987], proposto na década de 80. Será visto tambémuma extensão desse sistema, o GDE+ [Struss and Dressler, 1992], que permite considerardurante a tarefa de diagnóstico o modelo de falhas de componentes. Além disso, tam-bém será discutido o algoritmo de Reiter [Reiter, 1987b] que pode ser usado para realizarumas das principais subtarefas do GDE. Esse trabalho está dividido da seguinte forma:a Seção 2 apresenta uma visão geral da área de diagnóstico. A Seção 3 trata especifica-mente do diagnóstico baseado em modelo (DBM). Na Seção 4 é apresentado o GDE. Oalgoritmo de Reiter é apresentado na Seção 5. A utilização do algoritmo de Reiter parafazer o diagnóstico é apresentado na Seção 6. Na Seção 7 é apresentado o GDE+. Porfim, a conclusão é feita na Seção 8.

2. Visão Geral Sobre Diagnóstico

Um sistema pode ser visto como um conjunto de componentes queestão relacionados dealguma forma (normalmente uma saída de um componente é ligada à entrada de um oumais componentes), além de um conjunto de entradas e saídas que podem ser medidas(a ligação entre dois componentes também pode ser um ponto demedição). A tarefaprincipal do diagnóstico é encontrar as falhas em um determinado sistema, baseado nocomportamento observado que diverge do comportamento esperado.

Existem duas abordagens básicas para se fazer o diagnóstico:

• Diagnóstico baseado em heurísticas. Utiliza informações obtidas na experiênciaadquirida com os resultados de diagnósticos anteriores. Nesse caso, é necessá-rio que exista um especialista para fornecer essas informações. No diagnósticobaseado em heurísticas, o conhecimento do especialista é emgeral descrito porum conjunto de regras (heurísticas) que mapeiam os sintomas(veja Seção 3 paradefinição de sintomas) às causas dos sintomas de mal-comportamento. Com oconjunto de regras é possível, através de um mecanismo de inferência, encon-trar quais componentes do sistema apresentam falha ou pelo menos levanta umconjunto de hipóteses plausíveis sobre as causas dos sintomas. Esse tipo de di-agnóstico, apesar de funcionar para diversos casos, apresenta os seguintes proble-mas: (1) dependência do domínio do problema, (2) limitação ao conhecimento doespecialista e (3) dificuldade de se construir explicações apartir do processo deinferência [Benjamins, 1993].

2

• Diagnóstico baseado em modelos(DBM). É uma abordagem proposta para com-pensar as limitações da abordagem de diagnóstico baseado emheurísticas. ODBM é um método geral de diagnóstico, independente do domínio, que raciocinasobre modelos do sistema, como por exemplo: modelos funcionais e estruturais. ODBM compara as predições baseadas no comportamento correto do sistema como comportamento observado; caso seja encontrado algum conflito entre prediçõese observações então é possível reconhecer quais componentes estão envolvidosnas hipóteses de falhas do sistema. A Figura 1 mostra o relacionamento entre osistema real (sistema físico), modelo do sistema e o diagnóstico. Mais detalhessobre DBM são apresentados na Seção 3.

Figura 1. O diagnóstico é construído com base nas discrepâncias e co ncordâncias en-contradas ao se comparar as observações e as predições do comp ortamento do sistema.

O diagnóstico baseado em modelos utiliza modelos corretos de um sistema pararaciocinar. Assim, esse método de diagnóstico é aplicável somente aos sistemas cons-truídos pelo homem. Os sistemas pertencentes à essa subclasse são também conhecidoscomoartefatos2.

O DBM pode usar três tipos de descrições de modelos de sistema:

• Modelo Centrado em Componentes. Descreve o sistema como um conjunto decomponentes e suas conexões (ou relacionamentos). Alguns exemplos desse tipode modelo são:modelo estruturalemodelo comportamental. O modelo estruturalconsidera os componentes e suas conexões, enquanto o modelocomportamentaltrata as relações de entradas e saídas dos componentes. Existem dois tipos derelações de entrada e saída [Benjamins, 1993]:

– Regras de simulaçãoque predizem os valores para as saídas de umcomponente, dadas as entradas. Podem descrever o comportamento cor-reto/normal dos componentes;

2A palavra “sistema” será usada no decorrer do texto, mas quando usada para indicar o sistema sendo diagnosti-cado com método DBM deve ficar subentendido esse contexto mais restrito, no sentido de artefato, isto é, sistemasconstruídos pelo homem.

3

– Regra de inferênciaque podem não descrever o comportamento corretodo sistema (valores que se propagam da saída para a entrada),mas descre-vem conclusões válidas sobre o comportamento do sistema pois calculamas possíveis entradas do componente, dadas as saídas.

Um modelo corretodo sistema apresenta o modelo do sistema conforme ele foiprojetado para operar. A informação do modelo correto permite que sejam rea-lizadas inferências sobre o sistema, supondo não haver componentes falhos. Asobservações realizadas nesse tipo de modelo consistem basicamente de mediçõesefetuadas em entradas e saídas dos componentes;

• Modelo Causal. Descreve o sistema em termos de relação entre estados do tipocausa e efeito, isto é, estados causam outros estados como efeito.

• Modelo Funcional. Descreve o sistema em termos de funções e sub-funções.

Cada modelo traz uma visão diferente do sistema e cada uma delas pode ser essen-cial para encontrar um diagnóstico em determinados problemas e domínios de aplicação.

2.1. Subtarefas de diagnóstico

A tarefa de diagnóstico pode ser decomposta em três subtarefas [Benjamins, 1993]:de-tecção de sintomas, geração de hipótesesediscriminação de hipóteses, como apresentadona Figura 2.

Diagnóstico

Detecção de

sintomas

Geração de

hipóteses

Discriminação

de hipóteses

Busca de

contribuintes

Transf. de

contrib. em

hipóteses

Predição

baseada em

filtragem

Seleção de

hipóteses

Coleta de

dados

Interpretação

de dados

Figura 2. Decomposição da tarefa de diagnóstico e subtarefas.

As responsabilidades para cada subtarefa podem ser descritas como:

1. Detecção de sintomas. São as observações iniciais, que podem representar sin-tomas ou não. Sintomas sãoobservações anormaise serão discutidos em maisdetalhes na Seção 3.

2. Geração de hipóteses. A partir dos sintomas detectados, são geradas as possíveishipóteses de falha que expliquem aqueles sintomas. A fase degeração de hipótesespode ser dividida da seguinte forma:

4

(a) Busca dos contribuintes. O conjunto de contribuintes é um conjunto decomponentes envolvidos em uma predição inconsistente com as observa-ções e que portanto contém ao menos um componente falho;

(b) Transformação dos contribuintes em conjuntos de hipóteses. A par-tir dos conjuntos de contribuintes são gerados osconjuntos de hipóteses.Cada conjunto de hipóteses explica todas as observações iniciais, isto é,se todos os componentes de uma hipótese estiverem falhos, é possível ex-plicar as observações. Um dos princípios que se usa na construção dehipóteses é o de encontrar a explicação mais simples, isto é,um conjuntominimal de componentes que explica os sintomas;

(c) Predição baseada em filtragem. O processo de filtragem é usado paraexcluir hipóteses usando somente o conhecimento já existente sobre o sis-tema (não requerendo observações adicionais).

3. Discriminação de hipóteses. A discriminação de hipóteses é a subtarefa respon-sável por reduzir o conjunto de hipóteses com base em observações adicionais,com o objetivo de encontrar a falha que é solução para o problema.

3. Diagnóstico Baseado em Modelos

Como já foi dito na seção anterior, sistemas DBM verificam as diferenças entre as obser-vações de um sistema com o seu modelo correto. O modelo correto é uma descrição dosistema em termos dos componentes, de seus comportamentos esuas relações.

A Figura 3 apresenta um exemplo circuito3 com falha que será utilizado ao longodesse texto. Esse circuito ilustra um sistema real no qual será feito o diagnóstico e ondeexiste uma ou mais falhas.

Figura 3. Exemplo de circuito.

Esse circuito é composto por três componentes multiplicadores: M1, M2 e M3 edois adicionadores:A1 e A2. Existem5 entradas:A,B,C,D e E e duas saídas:F eG. Nas saídas dos multiplicadores são definidos ospontos de medição: X,Y e Z queserão utilizados no processo de diagnóstico. Além disso, pela figura é possível observar

3Esse é um exemplo usado em diversos artigos de diagnóstico, entre eles[Davis, 1984], [Genesereth, 1984],[de Kleer and Williams, 1987] e [Reiter, 1987b]

5

os valores definidos nas entradas:{A = 3, B = 2, C = 2, D = 3, E = 3}, e os valores dasaída que foram obtidos através de medições:{F = 10, G = 12}. Observe que caso todosos componentes do circuito estivessem funcionando corretamente, as saídas deveriam sermedidas como{F = 12, G = 12} e não{F = 10, G = 12}. Essa discrepância échamada desintoma, ou seja, “o valor observado para a saídaF é 10 mas deveria ser12” é um sintoma nesse circuito. Em um sistema podem ser detectados diversos sintomasdiferentes.

O processo de observar as entradas e inferir valores para outros pontos do sis-tema, como no exemplo para{X,Y, Z, F,G}, é chamado depredição, e permite gerarum conjunto com novas informações a respeito do sistema. Ainda no exemplo, sendoas entradas{A = 3, C = 2} (as entradas também são consideradas observações), épossível obter{X = 6} utilizando o componente{M1}, por exemplo. De uma formageral, as predições podem ser feitas com qualquer conjunto de observações. Se os valores{B = 2, D = 3, F = 10} foram observados, é possível inferir que{X = 4}, utilizandoos componentes{M2, A1} (nesse caso foi inferida uma entrada do componenteA1, dadassua saída e a outra entrada). Note que é possível obter o valorpara determinados pon-tos utilizando conjuntos de componentes diferentes (por exemplo o valor deX pode serencontrado utilizando-se os conjuntos de componentes{M1} e {M2, A1}), nesse caso,se valores iguais são encontrados para um mesmo ponto então há uma concordância devalores, caso contrário, existe uma discrepância ou conflito.

As predições são geradas com base nas observações feitas, levando em considera-ção que os componentes utilizados no processo de inferêncianão apresentam falha. Casoexista uma discrepância entre algum valor gerado na predição e as observações, então oconjunto de componentes participante durante a predição será chamado deconjunto decontribuintes.

4. GDE: Um método geral de diagnóstico

O GDE (General Diagnosis Engine) [de Kleer and Williams, 1987] é um método geralpara diagnóstico automático que tem como proposta ser independente do domínio de apli-cação. De uma forma simplificada, o GDE é capaz de encontrar umdiagnóstico atravésdos conjuntos de contribuintes, como apresentado na Seção 3. De acordo com a decompo-sição de tarefas do processo de diagnóstico (Subseção 2.1),o GDE abrange as subtarefasde geração e discriminação de hipóteses.

O Algoritmo 1 é um esboço de como funciona o GDE. Com o modelo do sis-tema e o conjunto de observações é feita a busca pelos contribuintes com a funçãoBUSCA_CONTRIBUINTES (observe a relação entre as funções e as subtarefas no quala tarefa de diagnóstico foi decomposta). Com o conjunto de contribuintes são geradas ashipóteses através da função:GERA_HIPOTESES que então são passadas para a funçãoDISCRIMINA_HIPOTESES para refinar o conjunto de hipóteses. As subseções a seguirdescrevem com mais detalhes cada uma dessas subtarefas.

No sistema GDE são feitas ainda as seguintes restrições:

1. as falhas do sistema não são intermitentes, ou seja, uma vez que um valor é me-dido, novas medições devolvem sempre o mesmo valor;

2. não é utilizado o modelo de falhas de componentes. O uso de modelo de falhas

6

Algoritmo 1 : GDE(Modelo, OBS)Entrada: Modelo: descrição do sistema (componentes e conexões);

OBS: conjunto de observações.Saída: conjunto de hipóteses que explicam as observações.

C ← BUSCA_CONTRIBUINTES(Modelo, OBS);H ← GERA_HIPOTESES(C);diagnostico ← DISCRIMINA_HIPOTESES(H);retorna diagnostico

permite um melhor refinamento de hipóteses e só foi proposto como extensão aoGDE, no GDE+ [Struss and Dressler, 1992].

Nas seções seguintes serão apresentadas cada subtarefa do GDE, e sempre quepossível, será usado o exemplo do circuito elétrico para ilustrar o funcionamento dosmétodos que realizam a tarefa em questão.

4.1. Busca de contribuintes

O conjunto de contribuintes é um conjunto de componentes no qual ao menos um compo-nente apresenta falha. Para encontrar esses conjuntos podeser utilizado um mecanismo deinferência, através do qual serão feitas as predições. Caso seja detectado algum conflitoentre um valor gerado na predição e um valor observado, entãoos componentes utilizadosnessa predição formam um conjunto de contribuintes.

No exemplo da Figura 3, supondo que são fornecidas as seguintes observações:{A = 3, B = 2, C = 2, D = 3, E = 3, F = 10}, então é possível fazer a predição que{F = 12} supondo que os componentes{M1,M2, A1} funcionam corretamente. Quandoisso acontece, é reconhecido o conflito com a observação{F = 10}, gerando o conjuntode contribuintes〈M1,M2, A1〉 (a notação〈. . .〉 é utilizada para indicar um conjunto decontribuintes). Note que passando a observação{G = 12} para a ferramenta de diag-nóstico também é gerado outro conjunto de contribuintes. Supondo que o conjunto decomponentes{M2,M3, A2} estão funcionando corretamente, o mecanismo de inferên-cia gera a predição{G = 12}, que é o mesmo valor da observação, mas baseado naobservação deF = 10, e supondo que os componentes{M1,M3, A1, A2} estão funcio-nando corretamente, é possível inferir queX = 6 por M1, Y = 4 por {M1, A1}, Z = 6por M3 e G = 10 por {M1,M3, A1, A2}, gerando um novo conjunto de contribuintes〈M1,M3, A1, A2〉.

Uma descrição mais detalhada sobre esse processo de geraçãode contribuintes éapresentada em [de Kleer and Williams, 1987].

4.2. Transformação dos contribuintes em conjuntos de hipóteses

Umahipóteseé um conjunto de componentesH, com a propriedade que caso todo compo-nentec ∈ H está falho, é possível explicar as observações. Os conjuntos de hipóteses sãoconstruídos a partir dos conjuntos de contribuintes gerados. Intuitivamente, o processopara a geração de hipóteses consiste em verificar, para cada conjunto de contribuintes, seexiste algum conjunto de hipóteses atual que não explica esse conjunto de contribuintes(a intersecção entre o conjunto de contribuintes e o conjunto de hipóteses é vazia nesse

7

caso). Caso tal conjunto de hipóteses exista, ele deve ser substituído por um ou mais deseus superconjuntos, mais um componente do conjunto de contribuintes. Ao final, todosos conjuntos de hipóteses que não são minimais devem ser removidos.

A Figura 4 é um reticulado representando as possíveis hipóteses de falha que po-dem ocorrer no circuito de exemplo da Figura 3. Na figura, cadaconjunto de componentespossui uma ligação com o seus superconjuntos na camada superior e com os subconjuntosna camada inferior. Inicialmente, antes de ser reconhecidoum conjunto de contribuintes,o conjunto de hipóteses é representado por[], informando que o sistema funciona semapresentar divergências. Suponha que o conjunto de contribuintesC1 = 〈M1,M2, A1〉seja reconhecido, então[M1], [M2] e [M3] são os conjuntos de hipóteses minimais. Todosos superconjuntos dessas hipóteses são considerados caso tenha algum outro conjunto decontribuintes. A Figura 5 mostra esse fato. Os conjuntos de hipóteses minimais apare-cem com um círculo vermelho e os conjuntos marcados com um “X”não fazem parte doespaço de busca. Reconhecido o novo conjunto de contribuintesC2 = 〈M1,M3, A1, A3〉,as hipóteses[M1] e [A1] já justificam o novo conjunto de contribuintes, e portanto, conti-nuam como estão. A hipótese[M2] não justifica o novo conjunto de contribuintes, entãosão gerados os conjuntos de hipóteses:[M1,M2], [M2,M3], [M2, A1] e [M2, A3], e aofinal, [M2] é excluído. Os conjuntos de hipóteses que não são minimais são excluídos,restando os conjuntos de hipóteses:[M1], [A1], [M2,M3], [M2, A2] (Figura 6).

Figura 4. Espaço de Busca de Hipóteses.

4.3. Discriminação de hipóteses

A discriminação de hipóteses no GDE pode ser feita através doprocesso conhecido comodiagnóstico sequencial [G. Gorry, 1968]. Esse processo consiste em fazer novas mediçõesno sistema, informando os valores obtidos à ferramenta de diagnóstico.

Para exemplificar, suponha que no circuito da Figura 3 os componentesM2 e A2

estejam falhos, fazendo com queY = B + D − 2 eG = Y + Z + 2. Observe que essas

8

Figura 5. Hipóteses considerando o conjunto de contribuintes C1 = 〈M1, M2, M3〉.

duas falhas fazem com que o valor medido emG seja igual ao esperado. A Tabela 4.3mostra os conjuntos de contribuintes e as hipóteses geradasconforme as medições sãofeitas.

Medição Contribuintes HipótesesF = 10 〈M1,M2, A1〉 {[M1], [M2], [A1]}G = 12 〈M1,M3, A1, A2〉 {[M1], [M2,M3], [M2, A2], [A1]}X = 6 〈M2, A1〉 {[M1,M2], [A1], [M2,M3], [M2, A2]}Y = 4 〈M2〉 {[M1,M2], [A1,M2], [M2,M3], [M2, A2]}

〈M3, A2〉 {[M2,M3], [M2, A2]}Z = 6 〈A2〉 {[M2, A2]}

Tabela 1. Contribuintes e hipóteses geradas a partir das medições.

O valor F = 10 é medido, apresentando um sintoma e gerando os contribuin-tes〈M1,M2, A1〉 e as hipóteses{[M1], [M2], [A1]}. Em seguida o valorG = 12 é me-dido, gerando os contribuintes〈M1,M3, A1, A2〉 e atualizando o conjunto de hipótesespara{[M1], [M2,M3], [M2, A2], [A1]}. Após medirX = 6 são gerados os contribuin-tes〈M2, A1〉 e as hipóteses são{[M1,M2], [A1], [M2,M3], [M2, A2]}. Nesse último casotambém foi gerada hipótese[M1, A1] mas que foi excluída pois não é minimal. Seguindoo processo, é medidoY = 4, gerando dois conjuntos de contribuintes〈M2〉 e 〈M3, A2〉e alterando o conjunto de hipóteses para{[M1,M2], [A1,M2], [M2,M3], [M2, A2]} como primeiro conjunto de contribuintes e{[M2,M3], [M2, A2]} com o segundo conjunto decontribuintes. Por fim, é feita a mediçãoZ = 6, gerando o contribuinte〈A2〉 e deixandosomente a hipótese[M2, A2] que contém exatamente os componentes que apresentam fa-lha.

9

Figura 6. Hipóteses considerando os conjuntos de contribuintes C1 = 〈M1, M2, M3〉 eC2 = 〈M1, M3, A1, A3〉.

5. Algoritmo de Reiter para Diagnóstico

Reiter apresentou em [Reiter, 1987b] um algoritmo eficiente que pode ser utilizado pararealizar a subtarefa do GDE de transformação dos contribuintes em conjuntos de hipó-teses. Além disso, Reiter apresentou de uma maneira formal assubtarefas executadaspelo GDE (além do GDE, também foi utilizado como base as técnicas apresentadas em[Genesereth, 1984]). Para essa abordagem mais formal da tarefa de diagnóstico é utilizadalógica de primeira ordem4 para descrição do modelo e das observações, o que permite umamaior abstração do domínio de aplicação.

Nessa seção será apresentada a formalização da tarefas de diagnóstico, da formaproposta por Reiter e na seqüência, será apresentado o Algoritmo de Reiter.

5.1. Formalização do Problema

O conceito desistema, nesse contexto formal, é definido como um par(SD,COMP )onde:

• SD é uma descrição do sistema na forma de sentenças em lógica de primeira or-dem;

• COMP é um conjunto finito de constantes representando os componentes do sis-tema.

A descrição do sistema pode ser vista como um conjunto de regras que o carac-terizam, a partir das quais é possível fazer simulações e obter informações a respeitode seu comportamento. Essas regras devem representar o comportamento correto dos

4No artigo [Reiter, 1987b] é apresentada uma discussão sobre o uso deoutros tipos de lógica que podem ser utiliza-das na tarefa de diagnóstico.

10

componentes do sistema. SejaAB(c) um predicado unário utilizado para indicar que ocomponentec ∈ COMP apresenta falha (funcionamento anormal) e, da mesma forma,¬AB(c) indica que o componentec funciona como esperado (not abnormal).

O circuito de exemplo apresentado na Figura 3 temCOMP ={M1,M2,M3, A1, A2} e pode ser descrito da seguinte forma:5:

ADD(x) ∧ ¬AB(x) → out(x) = in(1, x) + in(2, x)

MUL(x) ∧ ¬AB(x) → out(x) = in(1, x) ∗ in(2, x)

MUL(M1) MUL(M2) MUL(M3)

ADD(A1) ADD(A2)

out(M1) = in(1, A1)

out(M2) = in(2, A1)

out(M2) = in(1, A2)

out(M3) = in(2, A2)

A descrição do sistema utiliza os predicados unáriosADD e MUL para repre-sentar os componentes de adição e multiplicação.in(i, x) indica o valor dai − esimaentrada do componentex, eout(x) indica o valor obtido na saída do componentex. Essadescrição também define que os componentesM1, M2 eM3 são multiplicadores;A1 eA2

são somadores. Observe quein e out também são utilizados para identificar que a saídade uma componente está ligada em uma ou mais entradas de outros componentes.

Dado um sistema(SD,COMP ), uma observação, dada pelo conjuntoOBS,desse sistema é um conjunto de sentenças em lógica de primeira ordem informando va-lores obtidos através de medições do sistema. No exemplo da Figura 3, as observaçõesiniciais no sistema são definidas como:

in(1,M1) = 3 in(2,M1) = 2

in(1,M2) = 2 in(2,M2) = 3

in(1,M3) = 2 in(2,M3) = 3

Dada a descrição correta do sistema e supondo que todoc ∈ COMP funcionacorretamente, a fórmula:

SD ∪ {¬AB(c)|c ∈ COMP} ∪ OBS (1)5Além dessa descrição que diz respeito aos componentes e conexões dosistema, também devem ser definidos os

axiomas relacionados às operações sobre número inteiros.

11

é consistente, pois o sistema funciona corretamente (nenhum componente apresenta falha)e o que foi observado está de acordo com o que foi modelado.

Quando um sintoma é detectado, pode ser feita uma conjecturade que certos com-ponentes apresentam falha, explicando o comportamento observado. Esse fato é refletidona Fórmula 1, tornando-a inconsistente. Remover a inconsistência da fórmula significaencontrar todoc ∈ COMP tal que¬AB(c) seja falso e removê-lo dessa fórmula, restabe-lecendo a consistência. Observe que removendo¬AB(c) para todoc ∈ COMP tambémrestabelece a consistência da fórmula, mas nesse caso também faz sentido considerar oPrincípio de Parcimônia6.Definição 5.1. [Reiter, 1987b] Um diagnóstico para (SD, COMP, OBS) é um conjuntominimal∆ ⊆ COMP tal que:

SD ∪ OBS ∪ {AB(c)|c ∈ ∆} ∪ {¬AB(c)|c ∈ COMP − ∆}

é consistente. Da Definição 5.1 segue:

Proposição 5.1. [Reiter, 1987b] ∆ ⊆ COMP é um diagnóstico para(SC,COMP,OBS) se e somente se∆ é um conjunto minimal tal que:

SD ∪ OBS ∪ {¬AB(c)|c ∈ COMP − ∆}

é consistente. Definido∆ é possível formalizar o conjunto de contribuintes apresentadona Subseção 4.1.

Definição 5.2. [Reiter, 1987b] Um conjunto de contribuintes para (SD, COMP,OBS) éum conjunto{c1, . . . , ck} ⊆ COMP tal queSD ∪ OBS ∪ {¬AB(c1), . . .¬AB(ck)} éinconsistente.

Da Proposição 5.1 e da Definição 5.2 segue:

Proposição 5.2. [Reiter, 1987b] ∆ ⊆ COMP é um diagnóstico para(SC,COMP,OBS) se e somente seCOMP − ∆ não é um conjunto de contri-buintes para(SD,COMP,OBS).

Definição 5.3. [Reiter, 1987b] SejaF uma família de conjuntos. Umconjunto de corte(hitting set) é um conjuntoH ⊆

⋃s∈S

tal queH ∩ S 6= ∅ para todoS ∈ F . Um conjuntode corte é minimal se e somente se não existir subconjunto próprio dele que também sejaum conjunto de corte.

O seguinte teorema forma a base para calcular o diagnóstico:

Teorema 5.1.[Reiter, 1987b]∆ ⊆ COMP é um diagnóstico para(SD,COMP,OBS)se e somente se∆ é um conjunto de corte minimal para a coleção de conjuntos de con-tribuintes de(SD,COMP,OBS).

6O princípio de parsimônia diz que perante diversas justificativas a mais simples (aquela que requer o menor númerode deduções) deve ser escolhida. Esse princípio é chamado deOccam’s Razor.

12

O Teorema 5.1 corresponde à caracterização de diagnóstico desenvolvida em[de Kleer and Williams, 1987]. A diferença entre as duas abordagens é que essa últimasegue de uma base formal, enquanto a apresentada por de Kleere Willians é uma aborda-gem mais intuitiva.

A próxima seção apresenta o algoritmo utilizado para calcular os conjuntos decorte minimais e a Seção 6 mostra como a tarefa de fazer o diagnóstico se relaciona comesse algoritmo.

5.2. Algoritmo de Reiter: Minimal Hitting Set

O algoritmoMinimal Hitting Set, também conhecido como Algoritmo de Reiter, geratodos os conjuntos de corte minimais em uma famíliaF de conjuntos quaisquer. O algo-ritmo gera um grafo acíclico dirigido onde cada nón é rotulado por um conjuntoS ∈ Fe arcos saindo den são rotulados por ums ∈ S. SejaH(n) o conjunto formado pelos ró-tulos dos arcos no caminho da raiz até um nón. Todo nón tem como rótulo um conjuntoS tal queS ∩ H(n) = ∅ e caso talS não exista, o rótulo para den é definido como@.Ao completar o grafo, todo nón rotulado como@ tem queH(n) é um conjunto de corteparaF . Esse método não permite gerar todos os conjuntos de corte possíveis paraF , masgarante que todos os conjuntos de corte minimais estarão presentes no grafo. Algumasestratégias permitem que ao final da construção desse grafo todo nón rotulado com@apresenteH(n) como sendo um conjunto de corte minimal.

Inicialmente é escolhido um conjunto deF para rotular a raiz do grafo e a partirdesse conjunto são criados os arcos rotulados por elementosdesse conjunto. Cada novoarco deve apontar para um nó que pode ser rotulado por um novo conjunto deF oupara um nó já existente no grafo. Em determinadas condições épossível que o algoritmoexecute uma poda no grafo para garantir a minimalidade dos conjuntos de corte. O mesmoprocesso é repetido para os demais nós através de uma varredura na largura (Breadth First)enquanto houver nós que possam ser expandidos. O Algoritmo 2apresenta uma descriçãodo Algoritmo de Reiter, considerando as correções apresentadas em [Greiner et al., 1989].

A seguir são apresentados os passos executados no Algoritmode Reiter, com oobjetivo de gerar somente os conjuntos de corte minimais e minimizar o número de aces-sos à família de conjuntosF (a Seção 6 explica a importância de minimizar os acessos àF ):

• P1 (Linha 6). Supondo quen é o nó corrente (Linha 3) enovo é um nó quepossivelmente será criado e apontado por um arcos_arco, seH(novo) for iguala algum outroH(n′) para um nón′ já existente no grafo, entãonovo não deveser criado e os_arco deve apontar paran′. Essa estratégia permite que conjuntosdistintos com o mesmo conjunto de corte sejam tratados igualmente.

• P2 (Linha 8). Verifica se existe um conjunto de corte menor do que aquele queseria gerado com os_arco. Caso isso ocorras_arco aponta para um nó fechado.

• P3 (Linha 10). SeP1 e P2 não sejam aplicáveis, um novo nó (novo) será criado.Caso seja encontrado algum nó com rótuloS que também possa rotular o nónovo,então o rótuloS deve ser usado.

• P4 (Linha 13). Caso o passoP3não seja aplicável, um novo conjuntoS ′ deve serobtido deF .

13

Algoritmo 2 : MinimalHittingSet(F)Entrada: F : uma família de conjuntos.Saída: todos os conjuntos de corte minimais deF .

Escolha um conjunto deF para nomear a raiz (nível0);1

para cadanón no níveli faça2

sen tem um rótuloS então3

para cadas ∈ S façacrie ums_arco saindo den com rótulos.4

H(n) ← conjuntos de rótulos do caminho da raiz atén.5

⊲ passo P1seexiste algum nón′ tal queH(n′) = H(n) ∪{s} então6

faça os_arco den apontar paran′.7

⊲ passo P2senão seexisten′ com rótulo@ tal queH(n′) ⊂ (H(n) ∪{s}) então8

feche os_arco.9

⊲ passo P3senão seexisten′ rotulado comoS ′ tal queS ′ ∩ (H(n) ∪ {s}) = ∅10

entãofaça os_arco den apontar para um novo nó rotulado porS ′.11

⊲ passo P4senão12

faça os_arco apontar para um novo nóm e rotulem pelo primeiro13

elementoS ′ deF tal queS ′ ∩ H(m) = ∅. Se tal conjunto nãoexistir, então rotulem como@.⊲ passo P4’seexiste algum nón′ com um rótuloS1 tal queS ′ ⊂ S1 então14

renomeie o nón′ comoS ′ e remova todos os arcos saindo den′15

que foram nomeados pelos elementos deS ′\S1.Repita o passo2 parai + 1.16

retorna {H(n) | onden é um nó rotulado com@}17

• P4’ (Linha 14). Se o conjuntoS ′ obtido deF é um subconjunto estrito de outroconjuntoS1 rotulando um nón′ existente no grafo, entãon′ deve ser renome-ado paraS ′ e todos os arcos rotulados com elementos pertencentes ao conjuntoresultante deS1\S

′ devem ser eliminados.

O seguinte teorema é definido com base no Algoritmo 2:

Teorema 5.2. [Reiter, 1987b] SejaF uma família de conjuntos eG o grafo gerado peloAlgoritmo 2, vale que{H(n)| n é um nó rotulado com@} é uma família de conjuntos decorte minimais deF .

6. Diagnóstico com o Algoritmo de Reiter

O diagnóstico de sistemas pode ser feito utilizando o Algoritmo de Reiter, com basenos Teoremas 5.1 e 5.2 apresentados na Subseção 5.1. SupondoqueF é a família deconjuntos de contribuintes para(SD,COMP,OBS), o Algoritmo de Reiter executado

14

comF devolve todos os conjuntos de corte minimais, que são os conjuntos de hipótesesprocuradas.

A resolução do problema agora consiste na geração dos conjuntos de contribuin-tes que comporãoF . Cada conjunto de contribuintes é obtido chamando um provadorde teoremas para verificar a satisfazibilidade da Fórmula 1 (a função do provador de teo-remas nesse caso é a mesma que a do mecanismo de propagação de restrições usada noGDE). Caso essa fórmula seja insatisfazível então o provadorde teoremas deve devolvero conjunto de sentenças envolvidas na inconsistência. Entre essas sentenças podem estaralgumas que não dizem respeito ao funcionamento dos componentes mas sim às conexõesexistentes entre eles, sendo que estas devem ser descartadas7.

Quando um nón é criado, ele deve ser rotulado com um conjunto de contribuintesS. Esse rótulo ou é obtido no próprio grafo (passosP1, P2ou P3 do Algoritmo 2) ouno conjunto de contribuintes (através do provador de teoremas no passoP4 do mesmoalgoritmo). Nos dois casos existe a restrição queS ∩ H(n) = ∅. Para garantir que essarestrição seja satisfeita quando chamando o provador de teoremas, a Fórmula 1 deve seralterada para essa chamada. SejaC ⊆ COMP e I as inconsistências encontradas peloprovador de teoremas na fórmulaSD∪{¬AB(c)|c ∈ COMP −C}∪OBS, dessa formaé claro queI ∩ C = ∅. Sendo assim, caso o rótulo para um nón tenha que ser geradoatravés do provador de teoremas, a fórmulaSD ∪ {¬AB(c)|COMP − H(n)} ∪ OBSdeve ser usada.

No início do algoritmo é feita uma chamada ao provador de teoremas para devol-ver o rótuloS da raiz (nesse casoH(n) = ∅). Se nada for devolvido, então nenhumacontradição foi encontrada nas observações do sistema e o algoritmo é finalizado. Su-pondo queS 6= ∅, então é criado um arco de saída a partir do nó (a raiz nesse caso) paracada elementos ∈ S. Antes de gerar os nós para os quais os arcos de saída apontarão,deve ser verificado se esses arcos podem apontar para algum outro nó na árvore (passosP1 a P3), caso contrário será necessário fazer a novamente a chamada ao provador deteoremas para cada sucessorn′, usando a fórmulaSD ∪ {¬AB(c)|COMP −H(n′)}. Oalgoritmo executa dessa mesma forma para todo nó do grafo. Para cada iteração onde égerado um novo rótulo para algum nó é feita uma consistência necessária para garantir aminimalidade dos conjuntos de corte (passoP4’).

É importante observar que usando os passos definidos no algoritmo, o conjuntoF pode ser definido implicitamente, ou seja, os conjuntos deF são encontrados somentequando necessário, evitando que isso seja feito antes de iniciar o algoritmo. Dessa forma,é uma preocupação do algoritmo tentar minimizar o acesso ao conjunto F , pois cadaacesso a esse conjunto representa uma chamada ao provador deteoremas, que é umatarefa com alto custo computacional.

6.1. Exemplo de Diagnóstico com o Algoritmo de Reiter

O circuito de exemplo apresentado na Figura 3 será utilizadopara encontrar um diagnós-tico utilizando o Algoritmo de Reiter. A descrição do sistemae as observações iniciais(valores de entrada) são apresentadas na Subseção 5.1. Suponha que as saídas dos com-ponentesA1 e A2 sejam medidas, obtendo os valores10 e 12 respectivamente. Essas

7Artigos recentes como [de Kleer, 2007] tratam do problema de falhas emconexões.

15

informações são adicionadas ao conjunto de observações iniciais gerando um novo con-junto: OBS1 = OBS ∪ {out(A1) = 10, out(A1) = 12}. Essas novas observaçõesindicam que há uma discrepância de comportamento no sistemae a ferramenta de diag-nóstico será chamado para(SD,COMP,OBS1). O provador de teoremas é chamado noinício para devolver o conjunto de contribuintes que será usado como rótulo da raiz dografo: {M1,M2, A1} (Figura 7(a)). Para cada elemento desse conjunto é criado umarco.Como os passosP1 a P3 não são aplicáveis em nenhum dos três casos,P4 é executadoe o provador de teoremas será chamado para os três novos casos(para nenhum dos ca-sosP4’ é aplicável). Chamando o provador de teoremas para a Fórmula 1considerandoCOMP −{M1} eCOMP −{A1} nada é devolvido, então os arcos rotulados comoM1

eA1 apontam para um nó rotulado com@. ParaCOMP − {M2} é devolvido o conjuntode contribuintes{M2,M3, A1, A2} que rotulará o nó apontado pelo arco rotulado comM2

(Figura 7(b)). Os arcos partindo de{M2,M3, A1, A2} com rótulosM1 eA1 satisfazem ascondições do passoP2 e apontam para nós fechados, e para os arcos rotulados comoM3

eA2 o passoP4é executado, fazendo-os apontar para um nó rotulado com@. Ao final daexecução do algoritmo o diagnóstico obtido é:

∆1 = {{M1}, {A1}, {M2,M3}, {M2, A2}}

como apresentado na Figura 7(c).

{M1,M2, A1}

(a) Rotulando a raiz do grafo com os contribuintes{M1, M2, A1}.

{M1,M2, A1}

@ {M1,M3, A1, A2} @

M1 M2 A1

(b) Conjuntos de corte minimais reconhecidos e o novo contribuinte{M1, M3, A1, A2} adicionado (passoP4).

{M1,M2, A1}

@ {M1,M3, A1, A2} @

X @ X @

M1 M2 A1

M1 M3 A1 A2

(c) Grafo ao final da execução do algoritmo.

Figura 7. Grafo gerado pelo Algoritmo de Reiter durante o diagnóstic o.

16

6.2. Discriminação de Hipóteses

A idéia para a discriminação de hipóteses apresentada na Subseção 4.3 pode ser aplicadada mesma forma quando utilizando o Algoritmo de Reiter. As hipóteses obtidas em umprocesso de diagnóstico indicam possíveis pontos onde podem ser feitas novas medições,adicionando mais informações ao conjunto de observações que podem ser utilizadas parafazer um novo diagnóstico.

Baseado nas observações do comportamento do sistema apresentadas na Subse-ção 6.1, seOBS1 = OBS ∪ {out(A1) = 10, out(A2) = 12} então o seguinte diag-nóstico é encontrado∆1 = {{M1}, {A1}, {M2,M3}, {M2, A2}} (Figura 7(c)). Supo-nha que seja feita a observaçãoout(M1) = 6, gerando o novo conjunto de observa-çõesOBS2 = OBS1 ∪ {out(M1) = 6}. Executando a ferramenta de diagnóstico para(SD,COMP,OBS2), é obtido:

∆2 = {{M1,M2}, {A1}, {M2,M3}, {M2, A2}}

Na seqüência é medida a saída deM2, e gerada a nova observaçãoout(M2) = 4. SendoOBS3 = OBS2 ∪ {out(M2) = 4}, o diagnóstico para(SD,COMP,OBS3) é:

∆3 = {{M1,M2}, {A1,M2}, {M2,M3}, {M2, A2}}

E por fim, medindo a saída deM3 é geradoOBS4 = OBS3 ∪ {out(M3) = 6},que submetido ao sistema de diagnóstico gera:

∆4 = {{M2, A2}}

A Figura 8 apresenta como a resposta é obtida para o diagnóstico(SD,COMP,OBS4). O conjunto de contribuintes{M1,M2, A1} é devolvido pelo pro-vador de teoremas para rotular a raiz. Para cada arco saindo da raiz é executado o passoP4 (Figura 8(a)). Para o arco rotulado comA1 é devolvido o conjunto{M2}. Como{M2} ⊂ {M1,M2, A1}, então o rótulo do nó raiz é substituído por{M2} e são elimi-nados todos os arcos com rótulos diferentes deM2 (passoP4’), restando somente umarco que leva até o nó rotulado por{M1,M3, A1, A2} (Figura 8(b)). São criados os ar-cos saindo de{M1,M3, A1, A2}. Com o arco rotulado comoM1 é executado o provadorde teoremas que devolve o conjunto de contribuintes{A2} (Figura 8(c)). O passoP4’ éexecutado e o nó rotulado como{M1,M3, A1, A2} é substituído por{A2}. A Figura 8(d)apresenta o estado final do grafo. Quando o provador de teoremas é chamado excluindoos componentes{M2, A2} nada é devolvido e o arco rotulado comoA2 aponta para umnó marcado como@. Ao final da execução resta somente uma conjunto de corte minimal,ou seja, o diagnóstico{M2, A2}.

7. GDE+: Incorporando falhas no GDE

O GDE+ [Struss and Dressler, 1992] é uma extensão do GDE, que durante a tarefa dediagnóstico considera, além do modelo correto do sistema, um modelo de falhas de com-ponentes. O uso do modelo de falhas de componentes permite que o diagnóstico seja maispreciso, pois as hipóteses consideradas não plausíveis sãoexcluídas durante a tarefa dediagnóstico.

17

{M1,M2, A1}

{M2, A1} {M1,M3, A1, A2} {M2}

M1 M2 A1

(a) Situação do grafo antes da raiz ter seu rótulo trocado por{M2} (passoP4’ do algoritmo).

{M2}

{M1,M3, A1, A2}

M2

(b) Grafo resultante após a troca do rótulo da raiz e poda das arestas.

{M2}

{M1,M3, A1, A2}

{A2}

M2

M1 M3 A1 A2

(c) Adicionado ao grafo o conjuntoA2, que fará com que uma nova poda seja feita.

{M2}

{A2}

@

M2

A2

(d) Grafo resultante da poda e após a última chamada ao provador de teoremas.

Figura 8. Exemplo do grafo gerado pelo Algoritmo de Reiter contendo informações dediversas medições.

18

A Figura 9 apresenta um circuito com uma bateriaS, os componentes{W1, . . . ,W6} (representando os cabos) e as lâmpadas{B1, B2, B3}. Observandoque somente a lâmpadaB3 está acessa, um diagnóstico encontrado pelo GDE inclui:{{S,B3}, {W1,W5}, {B1, B2}}, entre outras. A hipótese que realmente justifica a falhaé {B1, B2}, indicando que as lâmpadasB1 e B2 estão queimadas. As demais hipótesesnão são plausíveis, pois{S,B3} indica que a bateria não está produzindo energia eB3

está acesa mas deveria estar apagada e{W1,W5} considera que a bateria funciona corre-tamente mas as lâmpadasB1 e B2 estão apagadas por uma falha emW1 e W5 apresentaoutra falha que faz com que energia seja produzida. Este diagnóstico justifica as observa-ções feitas, portanto está correto, mas devido à falta de mais informações (sobre falhas,por exemplo) não é possível obter nada mais refinado nesse momento.

Figura 9. Circuito de Exemplo.

Quando o componente de um sistema apresenta falha, é possível perceber que eleainda apresenta um comportamento determinístico. Essa informação é importante poispermite justificar a falha em um componente ou negar a falha emoutro componente. Umcomponente que apresenta falha assume ummodo de falha, podendo haver diversos mo-dos de falha para um único componente. Esses modos de falha são chamados demodelosde falha. No exemplo da Figura 9, poderia ser informado que quando a bateria apresentafalha não há corrente em nenhum ponto do circuito, o que descartaria as hipóteses citadasque não são plausíveis.

O GDE+ apresenta uma forma de usar esses modelos de falhas de componentes,criando uma extensão do GDE.

7.1. Integrando o Modelo de Falhas

O modelo de falhas é uma extensão do modelo de funcionamento correto, descrevendoo comportamento de um componente quando ele apresenta falha. Um componente podeapresentar diversas falhas que fazem com que o seu comportamento seja divergente emrelação ao modelo correto. Quando todas as falhas possíveispara um componente sãoconhecidas e estão modeladas, tem-se ummodelo de falhas completo. Supondo que umcomponenteC tenhanc modos distintos de apresentar falha,¬ABi(C) indica que o queo componente está correto em relação aoi− esimo modelo de falha. Isso significa que o

19

componente não apresenta aquela falha. Com as seguintes definições é possível exploraro modelo de falhas:Definição 7.1.Se um componenteC não apresenta falha, entãoC está correto em relaçãoà cada um dosnc modelos de falha possíveis:

{¬AB(C) → ¬ABi(C)|i ≤ nc}

Definição 7.2.Se o componenteC está correto em relação à todos os modelos de falhaentãoC está funcionando corretamente:

¬AB1(C) ∧ ¬AB2(C) ∧ . . .¬ABnc(C) → ¬AB(C)

A Definição 7.2 impõe que o modelo de falhas é completo (o uso demodelos nãocompletos pode fazer com que o diagnóstico devolvido pelo GDE+ não seja correto).

Quando a ferramenta de diagnóstico raciocina sobre o modelocorreto do sistema,dizer que um componente está correto em relação a um modelo defalha significa que ocomponente não apresenta a falha. Por outro lado, quando raciocinando sobre o modelode falhas, um componente é falho se apresenta alguma de suas possíveis falhas. Parapermitir que esse comportamento seja representado, é necessário que o mecanismo deinferência seja capaz de confrontar cada uma das possíveis falhas (descritas no modelode falhas) de um componente com as observações. Se for geradauma inconsistência paracada uma das falhas, então o componente não apresenta falha (pois o modelo de falhas écompleto). Oi − esimo modelo de falha de um componenteC é inconsistente com asobservações se existe um conjunto (possivelmente vazio)K de componentes comC /∈ K,onde oi− esimo modelo de falha seja inconsistente com qualquer combinaçãodo modelode falhas e do modelo correto de cada componente deK.

Voltando ao exemplo da Figura 9, onde foram encontradas as hipóteses:{{S,B3}, {W1,W5}, {B1, B2}} para a observação feita: somente a lâmpada 3 está acesa;suponha que sejam incluídas as seguintes informações de falha para bateria, lâmpada ecabos:

F1: Bateria Descarregadaout(1, S) = 0F2: LâmpadaBi Danificadaout(Bi) = 0F3: CaboWi Quebradoout(Wi) = 0

ComoB3 aparece em uma hipótese (e conseqüentemente em um ou mais conjun-tos de contribuintes), será feita a análise de falha. O modelo de falha para a lâmpada(F2) contradiz a observação (lâmpada está acesa) como esse é o único modelo de falhapara o componente, então é inferido que a lâmpada funciona corretamente, removendo asuposição de todos os conjuntos de contribuintes (e conseqüentemente do diagnóstico).ComoB3 não apresenta falha, então existe corrente passando pelos cabos, e pela falhaF3,{W1,W5} é excluído. Como existe corrente, então a bateria funciona e junto da falhaF1,S também é excluído dos conjuntos de contribuintes. Ao final resta somente o conjunto{B1, B2}} que é efetivamente o prolema real.

O uso do GDE+ na tarefa de diagnóstico implica em conhecer todas as formas pos-síveis de falhas dos componentes do sistema, o que pode ser uma tarefa muito complexa,

20

além de necessitar de um mecanismo de inferência mais complicado. Mas por outro lado,o uso do modelo de falhas permite que o número de hipóteses obtidas no diagnóstico sejamuito reduzida, o que é essencial para sistemas muito complexos.

8. Conclusão

Este trabalho apresentou um método importante para fazer o diagnóstico baseado em mo-delos: o GDE. Esse método geral permite que seja feito o diagnóstico de sistemas cons-truídos pelo homem (artefatos) utilizando somente o modelocorreto de funcionamentodo sistema e um conjunto de observações. Esse método é muito importante na área de In-teligência Artificial, pois a partir dele foram desenvolvidas algumas extensões, entre elaso GDE+ [Struss and Dressler, 1992], que considera um modelo de falhas durante a tarefade diagnóstico; ou mesmo a aplicação em outras áreas, como por exemplo a depuração deprogramas [Delgado, 2005].

O Algoritmo de Reiter [Reiter, 1987b] pode ser utilizado em umasubtarefa doGDE: a transformação dos conjuntos de contribuintes em conjuntos de hipóteses. OAlgoritmo de Reiter é um algoritmo de propósito geral que permite gerar todos osconjuntos de corte minimais em uma família de conjuntos, podendo ser utilizado tam-bém em outras áreas de Inteligência Artificial como por exemplo em revisão de crenças[Wassermann, 2000]. Reiter também apresentou uma formalização da tarefa de diagnós-tico, utilizando lógica de primeira ordem.

Apesar do GDE ser capaz de encontrar múltiplas falhas em um sistema, ele tam-bém gera hipóteses que são consideradas como não plausíveis, ou seja, falhas que naprática não podem acontecer. Isso deve-se ao fato dele não usar um modelo de falhas decomponentes. O GDE+ permite usar esse modelo de falhas de componentes durante odiagnóstico e, dessa forma, ele consegue podar hipóteses não plausíveis. Apesar de me-lhorar o resultado do diagnóstico, o GDE+ necessita que os modelos de falhas de todos oscomponentes sejam completos, caso contrário, o GDE+ pode devolver hipóteses que nãocondizem com a realidade.

O estudo do GDE, do Algoritmo de Reiter e do GDE+ formam uma basepara apesquisa na área de diagnóstico baseado em modelos. A compreensão desses algoritmospermite aplicá-los em outras áreas, como por exemplo em depuração de programas, alémde permitir uma melhor compreensão sobre a evolução e as limitações dessa abordagens.

9. Apêndice A - Sistemas de Manutenção de Verdade

Um sistema de manutenção de verdade (TMS -Truth Maintenance System) [Doyle, 1987]tem como objetivo manter a coerência de uma base de dados ou deuma base de conhe-cimento. A informação que é mantida na base pode ser vista como um conjunto de sen-tenças a partir das quais podem ser obtidas conclusões a respeito da verdade de um fato,junto das justificativas para essas conclusões.

A arquitetura básica de um TMS envolve um solucionador de problemas que geraas inferências, informando os resultados ao sistema de manutenção de verdade, que éresponsável por mantê-las de forma consistente. O TMS deve tratar questões relacionadasas mudanças na base, como por exemplo quando o solucionador de problemas obtémalguma informação que pode invalidar a base, necessitando que outras informações sejamdescartadas.

21

No TMS é definido o conceito decontexto. Um contexto é um conjunto de premis-sas que são verdadeiras, junto de toda informação que essas premissas permitem justificar.Uma aplicação desse conceito é na tarefa de diagnóstico. Porexemplo, para fazer o di-agnóstico de um circuito é necessário fazer predições, supondo que certos conjuntos decomponentes estão corretos. A variável e o valor gerados na predição, junto do conjuntode componentes usados nessa predição definem o contexto (a variável e o valor são jus-tificadas pelo conjunto de componentes - as premissas). Também podem ser utilizadosresultados de predições anteriores para justificarem novaspredições.

O ATMS (Assumption Truth Maintenance System) [de Kleer, 1986] é uma evolu-ção no TMS, que permite o uso de múltiplos contextos simultaneamente. O fator maisinteressante nessa evolução é que a base não precisa mais serconsistente (como era o casodo TMS).

Quando uma inconsistência é descoberta, toda informação derivada a partir dassentenças que causam essa inconsistência não é mais confiável. Mas note que caso o con-junto de sentenças que gerou a inconsistência seja divididoem dois subconjuntos (con-textualização), de forma que cada subconjunto de sentençasnão seja inconsistente, entãoesses subconjuntos ainda servem para justificar outras informações da base. Desse forma,se ora um subconjunto, ora outro (mas não ambos simultaneamente) são assumidos comoverdadeiro, então não há mais a inconsistência. Esse tipo deabordagem faz todo sentidona tarefa de diagnóstico, pois permite, por exemplo, encontrar os componentes que fo-ram utilizados na predição de um determinado valor para uma variável, permitindo queexistam diversos valores distintos para essa mesma variável (contextos distintos).

Referências

Benjamins, R. (1993).Problem Solving Methods for Diagnosis. PhD thesis, Universityof Amsterdam.

Davis, R. (1984). Diagnostic reasoning based on structure and behavior. Artif. Intell.,24(1-3):347–410.

de Kleer, J. (1986). An assumption-based tms.Artif. Intell., 28(2):127–162.

de Kleer, J. (2007). Modeling when connections are the problem. In Proceedings ofthe Twentieth International Joint Conference on Artificial Intelligence IJCAI-07, pages310–317. AAAI Press.

de Kleer, J. and Williams, B. C. (1987). Diagnosing multiple faults. Artif. Intell.,32(1):97–130.

Delgado, K. V. (2005). Diagnóstico baseado em modelos num sistema tutor inteligentepara programaçãoo com padrões pedagógicos. Dissertação demestrado, Instituto deMatemática e Estatística.

Doyle, J. (1987). A truth maintenance system. pages 259–279.

G. Gorry, G. B. (1968). Experience with a model of sequential diagnosis.Computers andBiomedical Research, 1:490–507.

Genesereth, M. R. (1984). The use of design descriptions in automated diagnosis.Artif.Intell., 24(1-3):411–436.

22

Greiner, R., Smith, B. A., and Wilkerson, R. W. (1989). A correction to the algorithm inreiter’s theory of diagnosis.Artif. Intell., 41(1):79–88.

Pearl, J. (1979). Entropy, information and rational decisions, policy analysis and infor-mation systems.Special Issue on Mathematical Foundations, 3(1):93–109.

Reiter, R. (1987a). A logic for default reasoning. pages 68–93.

Reiter, R. (1987b). A theory of diagnosis from first principles. Artif. Intell., 32(1):57–95.

Struss, P. and Dressler, O. (1992). Physical negation – integrating fault models into thegeneral diagnostic engine. pages 153–158.

Wassermann, R. (2000).Resource-Bounded Belief Revision. PhD thesis, University ofAmsterdam, Amsterdam, Holanda.

23