Embed Size (px)
Citation preview
DIAGRAMAS ESPIRAIS: MÉTODO AUXILIAR PARA A RESOLUÇÃO ÓTIMA DE ÁRVORES DE FALHAS VIA OBDD
Paulo Renato Alves Firmino
UFPE, Av. Acadêmico Helio Ramos, s/n, Cidade Universitária, Recife-PE, Cep: 50740-530, [email protected]
Pedro Igor Carvalho Moreira
UFPE, Av. Acadêmico Helio Ramos, s/n, Cidade Universitária, Recife-PE, Cep: 50740-530, [email protected]
Rohgi Toshio Meneses Chikushi
UFPE, Av. Prof. Luiz Freire, s/n, Cidade Universitária, Recife-PE, Cep: 50740-540, [email protected]
Enrique López Droguett
UFPE, Av. Acadêmico Helio Ramos, s/n, Cidade Universitária, Recife-PE, Cep: 50740-530, [email protected]
Resumo
A análise da confiabilidade é uma importante ferramenta, tanto para o desenvolvimento de novos produtos, quanto para a melhor prática de manutenção de produtos em uso. Uma das suas intenções é evitar surpresas desagradáveis e, assim, garantir a satisfação dos clientes em relação à qualidade do produto. Uma das maneiras de se fazer inferência sobre as medidas de confiabilidade refere-se à análise de árvores de falhas, que são estruturas lógicas, montadas postulando-se os eventos que podem levar a conseqüências indesejáveis do produto. Muitos são os métodos propostos para a resolução da árvore; porém, o de BDDs (Diagramas de Decisão Binária) tem sido citado como uma alternativa às técnicas convencionais, que alia tanto maior precisão quanto menor esforço computacional. O grande problema para a aplicação de BDDs reside na necessidade de conversão da árvore de falhas para o seu formato. Atualmente, muitos pesquisadores tentam encontrar uma maneira robusta de conversão que garanta um BDD ordenado (OBDD); isto é, com o menor número de variáveis possível. Este artigo apresenta um novo método de resolução, denominado de diagramas espirais. Os diagramas espirais solucionam este problema, fazendo o papel de conversores da árvore de falhas a OBDDs e garantindo robustêz para árvores de falhas que têm, a princípio, a característica de coerência.
Palavras chave: Árvores de Falhas, Diagramas de Decisão Binária Ordenados(OBDDs), Diagramas Espirais.
Abstract
Reliability is an important analysis tool, not only in the context of new products development; but, also, to determine better maintenance practices of products already in use. One of the reliability goals is to avoid undesirable surprises and, therefore, keep customers satisfied regarding the product’s quality. One of the possible techniques to perform inferences about reliability measures is through fault tree analysis, which are logic structures built from events that can lead to undesirable consequences. Several solution methods have been proposed for fault tree resolution. One of these is the binary decision diagram (BDD). BDD has been employed as an alternative to the conventional approaches that has both advantages of increased precision and less computational effort. One problem, however, with BDD usage is the requirement of converting the fault tree into a BDD format. Current research effort is under way in order to develop robust methods that guarantee an ordered BDD (OBDD); i. e., with the minimum number of variables. This article presents a new solution
1713
method, called spiral diagrams. The spiral diagrams tackle this problem, by converting fault trees into BDD with the assurance of robustness for coherent fault trees.
Keywords: Fault Trees, Ordered Binary Decision Diagrams (OBDDs), Spiral Diagrams.
1. Introdução
A análise da confiabilidade é uma ferramenta de suporte técnico-científico que justifica tomadas de decisão, melhorias de produto, estratégias de manutenção, entre outras. Ela busca garantir o bom funcionamento do produto, respeitando suas características físicas, o seu tempo de uso e os fatores que influenciam o seu desempenho. A utilização de análises de árvores de falhas permite a obtenção das medidas de confiabilidade do produto em relação aos eventos indesejáveis inerentemente ligados a ele.
O estudo de uma árvore de falhas deduz todas as possíveis combinações de eventos que levam à falha do produto, são os chamados cortes da árvore. Entre os cortes da árvore pode-se separar aqueles que são mínimos; excluindo-se os cortes que contêm outros cortes (para mais detalhes ver MODARRES et al. 1999). Os métodos tradicionais adotados para a obtenção dos cortes mínimos limitam-se a pequenas árvores, devido ao desgaste computacional que requerem e à perda de precisão decorrente de artifícios necessários, à medida que o nível de detalhamento das árvores aumenta. Diante disto, uma forma auternativa é a utilização de métodos de BDDs. Vários autores (BEDFORD & COOKE, 2001; BARLETT & ANDREWS, 1999 e 2000; DUTUIT & RAUZY, 2001; WEGNER, 2004, REAY & ANDREWS, 2002 e JUNG et al. 2004) citam BDDs como a melhor alternativa para a análise de árvores de falhas. Porém, todos se deparam com a dificuldade de encontrar um procedimento de conversão robusto, que garanta uma ordenação das variáveis (eventos básicos da árvore) e leve a um OBDD. O método dos diagramas espirais aquí apresentado, exaustivamente testado em uma grande quantidade de árvores de falhas coerentes, surge como uma maneira robusta, eficiente e dedutivamente comprovada, de realizar o trabalho de conversão.
Na seção 2 o artigo introduz algumas definições freqüentmente utilizadas no decorrer do texto. Em seguida, traz uma breve apresentação de BDDs (seção 3), propõe o raciocínio recursivo utilizado no método dos diagramas espirais (seção 4), extendendo-se à noção de subsistemas (seção 5), expõe os diagramas espirais como uma otimização combinatória e relata a preparação da árvore para a construção do diagrama espiral (seção 6), mostra como converter o diagrama espiral em um OBDD (seção 7), fala sobre alternativas de solução para a presença de redundâncias (seção 8) e conclui-se na seção 9.
2. Definições
O método dos diagramas espirais utiliza alguns termos próprios, e outros já apresentados pela literatura, que são definidos a seguir:
Conexão (ramificação): ligação de um evento básico, ou subsistema, a outro evento básico ou subsistema.
Subsistema: cada porta lógica da árvore de falhas constitue um subsistema, cujos elementos são as suas ramificações, sejam eles eventos básicos ou outros subsistemas.
Tamanho de um subsistema: é dado pelo seu número de ramificações e pelo tamanho dos seus subsistemas. Este tamanho se define prioritariamente pelo número de ramificações dos subsistemas cujas portas lógicas são um OU e secundariamente pelo número de ramificações dos subsistemas cujas portas lógicas são um E. Como o tamanho em relação ao OU lógico é prioridade, um subsistema cuja porta lógica é um E, com k eventos básicos ramificados, terá um tamanho menor que o de um outro subsistema cuja porta lógica é um OU e possui apenas dois eventos básicos, mesmo que k seja maior que 2. Naturalmente, um evento básico terá o tamanho nulo em relação a ambos os tipos de porta lógica.
Conector (topo): evento básico, ou subsistema, mais próximo da raíz da árvore de falhas, em relação àquele que é uma ramificação sua.
1714
Diagrama Espiral: grafo, cujas arestas (conexões ou ramificações) são direcionados para os topos.
Observando a figura 1 tem-se que, G0, G1, G2, G3, G4, e mesmo o topo da árvore, são subsistemas que constituem a árvore de falhas. O tamanho de G1, por exemplo, é 2 em relação à porta lógica OU e 2 em relação à porta lógica E, enquanto que G0 tem tamanho 4 em relação à porta lógica OU e 6 em relação à porta lógica E; sendo assim G1 é menor que G0. A importância da definição dos tamanhos dos subsistemas reside na necessidade de a árvore de falhas estar ordenada, neste sentido, para que o método de diagramas espirais possa ser aplicado. Isto será detalhadamente explicado na seção 6. O topo da árvore é topo do evento básico G e do subsistema G0, enquanto que G0 é topo dos subsistemas G1 e G2.
3. BDDs
A noção de diagramas de decisão é tão natural que não é possível se saber qual foi a primeira vez que esse tipo de representação foi usado. Sistemas de classificação utilizados pelo botânico Carl von Linné, no século 18, podem ser considerados como diagramas de decisão. A primeira pessoa a usar diagramas de decisão como representação ou estrutura de dados para funções booleanas foi Lee e Bryant os popularizou, ao aplicá-los a sistemas digitais; porém, Coudert & Madre e Rauzy introduziram, de fato, BDDs na análise da confiabilidade (JUNG et al. 2004).
Um BDD é construído a partir de dois tipos de módulos ou componentes. Nós terminais, que são nós não-conectores, rotulados por uma constante booleana v, pertencendo ao conjunto {0, 1} e nós internos de decisão (conectores), que representam os eventos básicos, rotulados por uma variável do conjunto X = { x1, x2,... ,xn } e possuem uma conexão rotulada por 0 e outra rotulada por 1. Considerando o rótulo xi e os conectores ou terminais xi
0 e xi1, se xi = 1 então o diagrama segue para
xi1, se não, o diagrama segue para xi
0. Esta declaração é também conhecida como decomposição de Shannon ou, simplesmente, conectiva ITE (if-then-else), observe a figura 2, e pode ser aplicada a árvores coerentes e incoerentes. De acordo com Jung et al. (2004), considerando a função booleana representada de forma linear para qualquer xi, ,cbxxaf iixi
++⋅= onde a, b e c, são funções booleanas
das variáveis conectoras ou terminais de xi e ix é o evento complementar a xi, a árvore de falhas é dita coerente se a função booleana a é sempre vazia; isto é, a pode ser descartada, e é este tipo de árvore de falhas que está sendo tratado neste artigo. Com isto, cbxf ixi
+= .
Um BDD é um grafo acíclico e direcionado, onde o número de conexões a um nó não é restrito. O tamanho de um BDD é definido como o número de nós conectores que ele possui e está diretamente ligado à ordenação das variáveis. Quando tem-se uma ordenação ótima, o BDD compacta toda a
Figura 1: Árvore de falhas.
+
*
GG0
G1
+
G2
+
F
Topo
BA
*G3
*
G4
EDC
1715
estrutura lógica da árvore de falhas, permitindo uma análise dos cortes mínimos e de suas probabilidades bem mais precisa e eficiente. Cada nó xi representa uma função booleana
ixf : {0,
1}n→{0, 1}, se o conjunto de variáveis X contem n variáveis. De forma a avaliar )z(fix , z � {0, 1}n,
ixf é analisado a partir de z e segue as instruções dos nós percorridos na chamada computação de
caminhos para ixf e z.
Na figura 3, a função 1xf tem o valor 1 para X={1, 0, 0, 1}, como pode ser visto seguindo o caminho
computado tracejado. O caminho indicado por linhas pontilhadas é a representação de um caminho possível graficamente, mas impossível matematicamente, se a intenção é chegar ao terminal 1. O motivo é que no primeiro momento x3 assume o valor 1 e no segundo momento ele assume o valor 0. Tais caminhos são chamados de caminhos inconsistentes e causam muitos problemas em algoritmos que tratam de BDDs. Para maior compreensão, ver WEGNER (2004).
4. Recursividade
Recursão é o processo pelo qual uma função chama a si própria repetidamente, um número finito de vezes, até que uma solução simples possa ser aplicada ao problema. Este recurso é muito útil em alguns tipos de algoritmos, chamados de algoritmos recursivos. Um algoritmo recursivo requer que o problema possua a propriedade recursiva, que consiste na característica de que, a partir de um problema cuja solução não se conhece, resolve-se as suas menores partes, aquelas cuja resposta é conhecida, obtendo-se, assim, a resposta do próprio problema. Assim, uma árvore de falhas pode ser manipulada através de algoritmos recursivos, já que, por maior que seja, ela será sempre finita e possuirá subsistemas dos quais todas as ramificações serão eventos básicos. Ora, nesse momento, tornarar-se-á óbvio que se tal subsistema possuir uma porta lógica OU, cada um dos seus eventos básicos, se ocorrido, levará à sua falha, e se ele possuir uma porta lógica E, somente a ocorrência simultânea de todos os seus eventos básicos levará à sua falha. O método dos diagramas espirais é melhor compreendido através do raciocínio recursivo que pode ser aplicado desde a leitura da árvore de falhas até a obtenção do OBDD que a representa.
5.Subsistemas
A estruturação dos subsistemas é fundamental para o sucesso tanto da construção do diagrama quanto do método dos diagramas espirais. Como foi dito anteriormente, o que define quais serão os subsistemas são as portas lógicas presentes na árvore de falhas. Observando a figura 4, os subsistemas
xi0 xi
1
xi 1 0
Figura 2: Representação grafo-binária da declaração ITE.
x1
x3 x2
x3 x2
x4
0 1
10
1 0 1
0
1
0
01 0
1
Figura 3: Representação grafo-binária de caminhos consistentes e inconsistentes.
1716
G1 e G2 comporiam os dois maiores subsistemas da árvore de falhas, os quais poderiam ser compostos por outros subsistemas, e assim por diante. Como os subsistemas formam a árvore de falhas, o topo é, também, um subsistema com a particularidade de não ser uma ramificação de um outro subsistema. Da figura 4, é simples perceber que, caso G1 e G2 sejam eventos básicos, a solução para a árvore de falhas é imediata. Na figura 4(a) haverá apenas um corte mínimo, G1*G2, enquanto que na figura 4(b) haverá dois cortes mínimos, G1 e G2. Porém, caso eles sejam subsistemas bem detalhados, isto é, grandes, a solução para a árvore de falhas exigirá bastante esforço dedutivo ou computacional.
Até este momento, nenhum cuidado é tomado de forma a eliminar os erros provenientes da árvore de falhas, sejam de característica redundante ou inconsistente. Estes dois tipos de problema são detalhadamente comentados na seção 8.
6. Diagramas Espirais
A combinatória estuda o número de combinações de eventos que levam à ocorrência de um evento final, assim como a constituição de tais combinações. A análise de árvores de falhas pode ser vista como uma extensão da combinatória, onde o evento de interesse é o evento topo da árvore de falhas e as combinações de eventos que levam à ocorrência do evento topo são os cortes da árvore.
Por exemplo, considerando o estudo das possíveis maneiras de ocorrência da falha de um sistema composto por dois subsistemas em paralelo, S1 e S2, onde o primeiro é composto por dois componentes em série e o segundo, por sua vez, por três componentes em série (veja a figura 5). Sendo Ei o evento básico referente à falha do componente Ci, do sistema, tem-se a árvore de falhas apresentada na figura 6.
Utilizando as regras de adição e multiplicação do método de enumeração da combinatória, todas as maneiras de ocorrência da falha do sistema apresentam-se na figura 7. Para maiores detalhes, ver Meyer (1974).
A proposta do diagrama espiral é otimizar a representação esquemática da combinatória, de forma a condensá-la, ou seja, repetir os nós o mínimo possível. Retornando à figura 7, onde E3, E4 e E5 se repetem, a presença de uma conexão alternativa, isto é, uma conexão que represente o OU lógico, de
Figura 6: Árvore de falhas referente ao diagrama de blocos do sistema proposto.
*
Falha do sistema
Falha do S1
E1 E2 E3 E4
+ +
E5
Falha do S2
Figura 5: Diagrama de blocos do sistemaproposto.
S2
C1 C2
C3 C4 C5
S1
(a) (b)G1 G2
Topo
G1 G2
*
Topo
+
Figura 4: Subsistemas de uma árvore defalhas.
1717
E1 para E2 pode eliminar a presença da repetição dos nós sem que haja alteração da estrutura lógica do diagrama. Como esta nova conexão representa o OU lógico, é pertinente que ela esteja presente, também, nos nós E3 e E4, já que, de fato, tem-se como opções E3, E4 ou E5, seguidos de E1 ou E2. O diagrama da figura 8 mostra a representação esquemática da figura 7 reestruturada fisicamente como um diagrama espiral, onde as setas com linhas pontilhadas representam as conexões do tipo OU.
O nome diagrama espiral se dá justamente pela presença das conexões OU, que aparecem sequencialmente no diagrama, da periferia para o centro e no sentido horário, dando a idéia de um espiral (arcos pontilhados da figura 8). As duas principais diferenças entre os diagramas espirais e as árvores de falhas são que os primeiros não possuem portas lógicas e que, assim como os BDDs, os eventos se conectam, porém com uma particularidade, os eventos se conectam de forma ordenada. Eles são uma evolução das árvores de falhas. Desta forma, pode-se dizer que os diagramas espirais estão a um passo dos OBDDs. O topo da árvore é considerado como sendo um terminal e as ramificações do terminal são os eventos básicos da árvore de falhas, conectados através de uma lógica combinatória adequada à porta lógica do subsistema do qual faziam parte na árvore de falhas.
Antes da aplicação da lógica combinatória, alguns cuidados devem ser tomados em relação à arvore de falhas, tais como:
C1. Verificação de subsistemas que possuem subsistemas caracterizados por portas lógicas iguais à sua:
Caso um subsistema seja ramificação de um outro subsistema cuja porta lógica é igual à sua, tal subsistema pode ser removido e suas ramificações podem ser ramificações diretas do seu topo. Na figura 9, os eventos A, B, C e D podem ser ramificações diretas do topo de G0 e G1, já que estes possuem portas lógicas iguais às dos seus topos. Este tratamento é a etapa de contração da redução de Faunet (REAY & ANDREWS, 2002).
C2. Subsistemas com, no máximo, uma ramificação:
Figura 7: Representação esquemática detodos as possíveis maneiras de ocorrer afalha do sistema proposto.
Falha do sistema
E1
E2
E3
E5
E4
E3
E5
E4
Figura 8: Diagrama espiral referente à árvore de falhas do sistema proposto.
Falha do sistema
E1
E3
E5
E4
E2
*
* *
Topo
G0 G1
A B C D
Figura 9: Árvore de falhas com subsistemascujas portas lógicas são iguais às dos seustopos.
1718
Quando um subsistema possui, no máximo, uma ramificação, não há motivos para que ele permaneça na árvore de falhas. Isto porquê não há a necessidade da aplicação de álegbra booleana para solucioná-lo. Caso isto ocorra, sua ramificação, se existir, pode passar a ser uma ramificação direta do seu topo e ele pode ser excluído da árvore sem que haja qualquer alteração na estrutura lógica da árvore de falhas.
C3.Ordenação dos subsistemas:
Os subsistemas são ordenados de acordo com seus tamanhos, de maneira crescente, isto é, são dispostos da esquerda para a direita na árvore de falhas. Como dito anteriormente, o tamanho de um subsistema é dado prioritariamente pelo seu tamanho em relação ao número de ramificações dos seus subsistemas cujas portas lógicas são do tipo OU e secundariamente pelo número de ramificações dos seus subsistemas cujas portas lógicas são do tipo E, incluindo nesses tamanhos o seu próprio número de ramificações. Após a ordenação, a árvore de falhas apresenta a mesma estrutura lógica, porém, com as portas lógicas ordenadas.
A lógica combinatória para a construção do diagrama espiral é dada da seguinte forma. Caso um evento possua como topo um subsistema cuja porta lógica é um OU, duas análises devem ser feitas:
1. Se o topo em questão pertence a um outro subsistema, este outro subsistema possui uma porta lógica E (devido ao tratamento C1). Assim, todas as ramificações do topo em questão tornar-se-ão ramificações do último evento básico da última ramificação do subsistema à sua esquerda. Verificando a figura 10, os eventos C e D passaram a ser ramificações do evento B, e G1 poderá ser descartado (figura 11). Se ao invés do evento B, a última ramificação de G0 fosse um outro subsistema, esta mesma condição seria aplicada ao mesmo, até que o último evento básico de G0 fosse encontrado.
2. Se o subsistema em questão não possui um topo, este é o topo da própria árvore. Assim, as suas ramificações farão, na verdade, parte dos caminhos para se chegar à falha do sistema, isto é, ao terminal do diagrama espiral. Se ele é a única ramificação do seu topo, recai-se no tipo de caso em que C2 se aplica. Voltando à figura 10, dado que C e D já passaram a ser ramificações de B, tem-se que A e B se conectarão ao topo, já que G0 se tornará a sua única ramificação. A figura 11 ilustra este procedimento, onde as setas indicam a intenção de se chegar ao topo ou terminal 1.
Caso um evento pertença a um subsistema cuja porta lógica é um E, é necessário que este se conecte ao evento mais próximo à sua esquerda, dentro do subsistema, e que depois seja removido do subsistema. Na figura 12, os eventos D e B, se tornarão ramificações de C e A, respectivamente.
A lógica combinatória, de uma forma geral, faz as seguintes conexões no diagrama espiral: as ramificações de subsistemas cujas portals lógicas são do tipo E, dado que estão ordenadas de forma crescente, são conectadas entre sí, da direita para a esquerda, e postas no diagrama espiral. Estas conexões representarão a ocorrência simultânea dos eventos básicos. As ramificações de subsistemas cujas portas lógicas são do tipo OU não são conectadas entre sí. Ou elas fazem parte da lógica combinatória dos subsistemas cujas portas lógicas são um E ou se conectam ao terminal 1. Desta maneira, a árvore descrita na figura 12 assume o diagrama espiral apresentado na figura 13, que tem uma analogia muito forte com um BDD, onde as conexões representariam a ocorrência simultânea dos eventos, isto é, das falhas. Assim, caso ocorram A “E” B “OU” C “E” D, o sistema representado pela
Figura 11: Conexão dos eventos básicosda árvore de falhas.
1
A B
C D
Figura 10: Árvore de falhas com subsistemascujas portas lógicas são do tipo OU.
*
Topo
G0 G1
A B C D
+ +
1719
figura 12 falha. Falta, apenas, realizar as conexões do tipo OU para que o diagrama espiral seja o prório BDD.
A conexão OU obedece, também, a uma lógica combinatória, porém, menos simples que a das conexões E. Para cada subsistema cuja porta lógica é um OU, cada evento ou subsistema se conecta ao evento ou subsistema mais próximo à sua esquerda dentro do subsistema. Esta conexão representa a presença de uma outra opção de se chegar ao terminal 1 do diagrama. Isto é, tal conexão expressa o OU lógico do diagrama espiral. Sendo assim, na árvore representada na figura 12, G1 tem uma conexão OU com G0. Para realizar a conexão OU entre subsistemas, deles são capturados os eventos básicos que realizarão a conexão. Do subsistema receptor da conexão OU, extrai-se o último evento básico do seu último subsistema descendente, e do subsistema a realizar a conexão OU extrai-se o primeiro evento básico do seu último subsistema descendente cuja porta lógica é também OU. Quando não existir qualquer subsistema cuja porta lógica é do tipo OU, selecina-se o último evento básico do último subsistema descendente, que será ou um subsistema cuja porta lógica é um E ou o último evento básico do subsistema em questão. Retornando à figura 12, como tanto G0 quanto G1 são subsistemas que possuem portas lógicas do tipo E, os seus representantes serão B e D, respectivamente. Assim, D possuirá uma conexão OU com B, isto é, se não ocorrer G0 ainda é possível que o sistema falhe, ou que se chegue ao terminal 1, por G1 (ver a figura 13).
7.Método dos Diagramas Espirais
O método dos diagramas espirais tem a função de converter o diagrama espiral em um BDD. A ordenação dos eventos básicos é dada pela distância entre o evento básico e o terminal 1. Percorrendo o diagrama espiral, os eventos básicos são incluídos no BDD onde à direita se conectam ao seu conector no espiral ou ao terminal 1 caso não possua um conector, e à esquerda utilizam a conexão OU realizada na construção do diagrama espiral, que representa uma opção para se chegar ao terminal 1. Sendo assim, o que é de fato necessário para se transformar o diagrama espiral em um OBDD é invertê-lo, onde o topo do OBDD será o último evento básico da última ramificação do diagrama espiral. Voltando à árvore de falhas apresenatada na figura 12, cujo diagrama espiral está apresentado na figura 13, o OBDD teria a estrutura da figura 14. É importante salientar que, neste caso, haverá eventos sem conexões do tipo OU. Estes eventos, caso possuissem tais conexões, apontariam para o terminal 0, aquele que representa o funcionamento sem falhas do sistema. Isto não chega a ser um problema já que o diferencial aquí é a substituição do terminal 0 pela ausência de uma conexão OU.
*
Topo
G0 G1
A B C D
+
*
Figura 13: Diagrama espiral da árvore de falhas apresentada na figura 12.
1
A C
D B
Figura 14: OBDD da árvore de falhasapresentada na figura 12.
1
D
B C
A
Figura 12: Árvore de falhas comsubsistemas cujas portas lógicas são do tipoE.
1720
8. Incoerência, Inconsistência e Redundância
Dois problemas são considerados críticos para o sucesso do método dos diagramas espirais em relação a árvores coerentes: A inconsistência e a redundância da árvore de falhas. Os caminhos inconsistentes são provenientes de árvores de falhas inconsistentes, às vezes pela falta de conhecimento do analista sobre o sistema ou pela falta de experiência do profissional responsável por sua construção. Existem algumas maneiras de se evitar tais inconsistências. Duas delas são avaliar a função booleana da árvore de falhas antes ou durante a construção do diagrama espiral. Em geral, a inconsistência se apresenta quando existem subsistemas compostos por eventos básicos que representam a não-falha dos seus componentes. Neste trabalho, têm sido tratados apenas os casos em que não se verifica a presença de inconsistência, já que são tratadas somente árvores coerentes, como citado na seção 3.
A redundância (ou repetição desnecessária) de eventos básicos é mais freqüente em grandes árvores de falhas. Torna-se cada vez mais difícil evitá-la à medida em que o nível de detalhamento do sistema aumenta. O método dos diagramas espirais só é, de fato, útil e preciso quando todos os problemas de redundância são corrigidos.
Apresenta-se a seguir como o problema da presença de redundâncias é tratado pelo método aquí proposto.
Seja o topo da ocorrência da redundância a raíz da qual o evento original e o redundante são descendentes imediatos. Isto é, a porta lógica descendente do topo da árvore, que representa o subsistema que possui como descendentes os eventos original e redundantes. Seja o evento original da redundância aquele mais próximo do topo da ocorrência da redundância e sejam os eventos redundantes aqueles mais distantes do topo da ocorrência da redundância. Cinco tipos de ocorrência da redundância são analisados:
1. Redundância trivial (o evento original e os redundantes pertencem à primeira geração do topo da ocorrência da redundância): Nesse caso a solução para a redundância é simples. Basta excluir todas as redundâncias e manter o evento original, pois em álgebra booleana A+A = A. A = A. Considerando, na figura 4, que G1 e G2 são o mesmo evento básico, este tipo de ocorrência de redundância se verifica.
2. Redundância de geração I (Apenas o evento original pertence à primeira geração do topo da ocorrência da redundância): Aquí ocorrem duas lógicas de matemática combinatória. Se os topos dos eventos redundantes possuirem portas lógicas diferentes da do topo do evento original (que é também o topo da ocorrência da redundância), o topo das redundâncias deve ser eliminado da árvore (observar a figura 15). Porém, se os topos dos eventos redundantes possuirem portas lógicas iguais à do topo do evento original, apenas os eventos redundantes devem ser eliminados dos seus topos (observar a figura 16). É importante que se perceba a utilização do tratamento C2, seção 6, tanto na árvore representada na figura 15 quanto na da figura 16.
1721
Este tipo de redução utiliza-se do seguinte fato: seja f a função booleana referente à árvore de falhas apresentada na figura 16(a), em álgebra booleana DBADABAf ⋅+=+⋅+= )( , e, em se tratando da árvore de falhas referente à figura 15(a), ADABAAf =⋅+⋅+= .
3. Redundância de geração II (Tanto o evento orginal quanto os eventos redundantes pertencem à segunda geração de ramificações do topo da ocorrência da redundância): Neste tipo de ocorrência de redundâncias o método de redução de Faunet (REAY & ANDREWS, 2002) é aplicado. Utilizando álgebra booleana, tem-se CBACABA ⋅+=+⋅+ )()( , assim como )( CBACABA +⋅=⋅+⋅ , onde, do lado direito destas duas igualdades a redundância é eliminada, como pode ser visto na figura 17.
4. Redundância de geração III (Ao menos o evento original ou os redundantes pertencem à terceira geração de ramificações do topo da ocorrência da redundância e a porta lógica do topo da ocorrência das redundâncias é do tipo E): Para este tipo de ocorrência de redundâncias o método de resolução utilizado é o método espiral de eliminação de cortes não-mínimos (MEEC), proposto também por este artigo. O MEEC utiliza-se, do fato de que
)GG(G)GG(G)GG()GG( lkjlkilkji +++=++ [4.1],
onde Gi, Gj, Gk, Gl são subsistemas da árvore de falhas. Considerando que a primeira parcela do lado direito da igualdade em [4.1] não contém o evento original, e que, conseqüentemente, a segunda parcela o contém, esta lógica de igualdade é aplicada recursivamente na segunda parcela, de forma a expandí-la e aproximar o evento original do topo da ocorrência da redundância. Quando o evento original torna-se uma ramificação do topo da ocorrência da redundância, tem-se a redundância de geração I, chegando-se assim à solução possível. Antes da utilização do MEEC é preciso a seguinte precaução: quando o evento redundante pertencer à terceira geração do topo da ocorrência da
Topo
G1
A
+
*G0
A
*
B C
Figura 17: Ocorrência de redundâncias, onde tanto oevento orginal, quanto os eventos redundantes, pertencemà segunda geração de ramificações do topo da ocorrênciada redundância.
Topo
G1’
B
+
*
A
C
Figura 15: Ocorrência de redundâncias, ondeapenas o evento original pertence à primeirageração do topo da ocorrência da redundância.
*
Topo
G0 G1
A B A D
+
*
A
Topo
A
(a) (b)
Figura 16: Ocorrência de redundâncias, onde apenas o evento original pertence à primeira geração do topo da ocorrência da redundância.
Topo
G0
B
+
*A
A D
+
G1
Topo
G0
B
+
*A
D
(a) (b)
1722
redundância, este deve passar a ser considerado como o evento original, a não ser que o evento original também possua esta característica.
5. Redundância de geração elevada (Não há qualquer das relações de parentesco citadas anteriormente e a porta lógica do topo da ocorrência das redundâncias é do tipo E): Aquí o método utilizado é, também, o MEEC, porém com uma singularidade. O MEEC finaliza-se aplicando a lógica inversa à primeira parcela do lado direito da igualdade de [4.1], correspondente à última chamada da recursividade. Esta lógica inversa remove o topo do evento repetido da primeira parcela do lado direito da igualdade de [4.1] quando apenas o evento repetido é removido da segunda parcela, e remove apenas o evento repetido da primeira parcela do lado direito de [4.1] quando o topo do evento repetido é removido da segunda parcela.
Para o tipo de ocorrência de redundâncias onde o MEEC se aplica, não é possível obter-se uma árvore de falhas sem repetições, mas é garantido que o método de diagramas espirais gere um OBDD cujos caminhos (cortes) são mínimos e os eventos são otimamente ordenados.
O MEEC pode ser melhor compreendido verificando-se a figura 18, onde a sua lógica elimina todos os cortes não-mínimos que certamente serão gerados devido o topo da ocorrência da repetição ser uma porta lógica do tipo E. Como o evento básico B está presente em dois subsistemas distintos e tanto o evento original quanto o evento redundante pertencem à terceira geração do topo da ocorrência da redundância (que por conhecidência é o topo da árvore), a redundância é classificada como de geração III e apenas o MEEC pode solucioná-la. Neste caso específico o evento original poderia ser qualquer uma das ocorrências do evento básico B. O que o MEEC está fazendo de (1) para (2), na figura 18, é considerando que )()( lj GDGA +⋅+ = )()( ll GDCBGDA +⋅⋅++⋅ . Como )( lGDCB +⋅⋅ é o subsistema que possui a ocorrência da redundância, e como o evento original pertence à primeira geração do topo de tal ocorrência, G’l, e ainda considerando que o evento básico original e o redundante são ramificações de subsistemas cujas portas lógicas são do mesmo tipo, tem-se que apenas o evento básico redundante deve ser excluído do seu topo, em G’1. Observando a figura 18(3), percebe-se que agora os eventos básicos D, E, e o prórpio B possuem uma repetição. Estas repetições são inevitáveis, devido às características da árvore proposta. Porém, são necessárias para que seja garantida a geração de todos os cortes mínimos. Como os seus topos são subsistemas cujas portas lógicas são do tipo OU, não haverá problemas com suas permanências na árvore de falhas e suas repetições não devem ser consideradas como redundâncias. O maior problema ao se tratar de árvores de falhas que possuem esta característica de redundância ou de repetição, é que é impossível que se gere um OBDD mínimo idealmente, ou seja, o OBDD sempre possuirá eventos básicos repetidos.
1723
Há ainda um tipo de ocorrência de redundâncias em que o MEEC se aplica. Quando há redundância de geração III ou elevada referente a subsistemas ao invés de eventos, o MEEC é usado, porém com alguns cuidados adicionais que fogem ao escopo deste artigo. Estes casos serão trabalhados em outra oportunidade.
Faz-se necessário salientar que apenas após todos os cuidados aquí mencionados, tanto de redução quanto de reestruturação da árvore de falhas, o método dos diagramas espirais pode ser aplicado. Caso isto não ocorra, os seus resultados serão comprometidos. O método dos diagramas espirais, que é responsável direto pela construção do OBDD, requer que a árvore esteja ordenada em relação aos tamanhos dos seus subsistemas e isenta da presença de redundâncias.
9.Conclusões
De acordo com os testes dedutivos realizados, o método dos diagramas espirais promove um OBDD ótimo para uma grande malha de árvores de falhas. Já que trata de sistemas k de n que são coerentes por defnição. A sua lógica recursiva é uma maneira elegante e robusta de solucionar o problema de conversão da árvore de falhas em um OBDD ótimo e a sua lógica combinatória é totalmente implementável. Os diagramas espirais, assim como o seu método, eliminam uma das grandes dificuldades (se não a maior delas) de se utilizar OBDDs na resolução de árvores de falhas atualmente: construí-los e, a depender da arquitetura aplicada para a construção da árvore de falhas, requer o mínimo de esforço computacional possível.
Moreira et al. (2004), trata de um problema prático onde deseja-se encontrar os cortes mínimos de um sistema de controle de prospecção de gás natural e óleo de poços offshore com o auxílio do método dos diagramas espirais.
Topo
G1= Gk+ Gl
+
*
Gj
B
+
*
C
G0
A Gl
B
*
E
D
Gi Gk
1 Topo
+
G’0
A
*
G1
B
+
*D
E
Gk+ Gl
G’1
B
*
C
G1
B
+
*D
E
Gk+ Gl
2
Topo
+
G’0
A
*G’1
B
*
C+
D
(Gk+Gl)’
3
E
G1
B
+
*D
E
Figura 18: Presença de redundâncias de geração III.
1724
Desafios futuros são a análise do método dos diagramas espirais para árvores de falhas incoerentes.
Referências
BARLETT, L. M. & ANDREWS, J. D. (1999)- Efficient Basic Event Ordering Schemes for Fault Tree Analysis. Quality and Reliability Enginnering International. Vol. 15, p. 95-101.
BARLETT, L.M. & ANDREWS, J. D. (2000)- An ordering heuristic to develop the binary decision diagram based on structural importance. Reliability Engineering and System Safety. Vol. 72, p. 31-38.
BEDFORD, T. & COOKE, R. (2001)- Probabilistic Risk Analysis: Foundations and Methods. Cambridge University Press. Cambridge.
BRYANT, R. E. (1992)- Symbolic Boolean Manipulation with Ordered Binary-Decision Diagrams. ACM Computing Surveys. vol. 24, n. 3, p. 293-318.
DUTUIT, Y. & RAUZY, A. (2001)- Efficient algorithms to assess component and gate importance in fault tree analysis. Reliability Engineering and System Safety. Vol. 72, p. 213-222.
JUNG, W. S.; HAN, S. H. & HA J. (2004)- A fast BDD algorithm for large coherent fault trees analysis. Reliability Engineering and System Safety. Vol. 83, p. 369-374.
MEYER, P. (1974)- Probabilidade. Aplicações à Estatística. Ao livro técnico S. A.. Rio de Janeiro.
MODARRES, M.; KAMINSKIY, M. & KRIVTSOV, V. (1999)- Reliability engineering and risk analyses. Primeira edição. Marel Dekker. New York.
MOREIRA, P. I.; FIRMINO, P. R. & DROGUETT, E. L., (2004)- Aplicação do método dos diagramas espirais no auxílio para a resolução de árvores de falhas via OBDD. Artigo submetido para este simpósio.
REAY, K. A. & ANDREWS, J. D. (2002)- A fault tree analysis strategy using binary decision diagrams. Reliability Engineering and System Safety. Vol. 78, p. 45-56.
WEGNER, I. (2004)- BDDs-design, analysis, complexity, and applications. Discrete Applied Mathematics. Vol. 138, p. 229-251.
