Bases mínimas para a diagnose de falhas de sistemas a eventos
Transcrição
Bases mínimas para a diagnose de falhas de sistemas a eventos
XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. ISBN 978-85-61507-02-2 BASES MÍNIMAS PARA A DIAGNOSE DE FALHAS DE SISTEMAS A EVENTOS DISCRETOS. PARTE II: ALGORITMO DE BUSCA Saulo T. de Souza Lima∗, João C. Basilio∗, Stéphane Lafortune†, Marcos V. Moreira∗ ∗ COPPE - Programa de Engenharia Elétrica, Universidade Federal do Rio de Janeiro, 21949-900, Rio de Janeiro, RJ, Brasil. † Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109, USA. Emails: [email protected], [email protected], [email protected], [email protected] Abstract— In this paper, a search algorithm to find all subsets of the set of observable events (diagnosis bases) that can be used to diagnose fault occurrences is proposed. All the steps of the algorithm are theoretically justified. The efficiency of the proposed algorithm is illustrated by means of an example. Keywords— Discrete-event systems, fault diagnosis, sensor selection Resumo— Neste artigo, um algoritmo de busca para encontrar todos os subconjuntos do conjunto de eventos observáveis (bases para a diagnose) que podem ser usados para a diagnose de falhas é proposto. Todos os passos do algoritmo são justificados teoricamente. A eficácia do algoritmo proposto é ilustrada por meio de um exemplo. Palavras-chave— 1 Sistema a eventos discretos, diagnose de falhas, alocação de sensores. Introdução como levantar as ambiguidade devidas a ciclos indeterminados observados e escondidos, respectivamente. Na seção 5 é proposto um algoritmo para busca das bases mínimas para diagnose. As conclusões são apresentadas na seção 6. Na teoria desenvolvida para a diagnose de falhas de sistemas a eventos discretos SEDs (Sampath et al., 1995), todo o conjunto de eventos observáveis do SED é utilizado para se detectar as ocorrências das falhas. Esse fato leva à seguinte pergunta: é possível encontrar um subconjunto do conjunto de eventos observáveis que permite a diagnose da falha? Tal redução na cardinalidade dos conjuntos dos eventos observáveis seria bastante vantajosa, uma vez que na diagnose com observação total é necessário, pelo menos, um sensor para cada evento observável, enquanto que na diagnose com observação parcial o número de eventos observáveis seria menor. Com esse objetivo, esse artigo junta novos resultados àqueles apresentados em Lima et al. (2010a) para propor um método sistemático para a busca dos subconjuntos do conjunto de eventos observáveis que permitem a diagnose da falha. Esses subconjuntos serão referidos simplesmente como bases para a diagnose de falhas quando não possuírem eventos redundantes e como bases mínimas para a diagnose de falhas, caso todos os seus eventos sejam essencias. Além de interessante do ponto de vista econômico, as bases para a diagnose (mínimas e nãomínimas, nesse caso) podem ser usadas para melhorar a confiabilidade do sistema de diagnose de falhas quando utilizadas para construir um diagnosticador que seja robusto à perda permanente de sensores (Lima et al., 2010b). Este artigo está estruturado da seguinte forma. Na seção 2 são apresentados os fundamentos teóricos necessários para o desenvolvimento do algoritmo de busca. Nas seções 3 e 4 é descrito 2 Resultados básicos Considere um autômato G = (X, E, f, Γ, x0 , Xm ) e seja Eo , Euo e Ef ⊂ Euo , respectivamente, os conjunto dos eventos observáveis, não-observáveis e de falha de G. Suponha que a linguagem gerada por G seja diagnosticável em relação a Po : E ∗ → Eo∗ e Ef = {σf }. Seja ainda Eo0 ⊂ Eo e suponha que Gd e G0d denotem os diagnosticadores de L utilizando os conjuntos Eo e Eo0 . Finalmente, seja Gteste = G0d kGd . Considere a seguinte definição. Definição 1 (Trajetórias primas-Y e trajetórias primas-N) Uma trajetória prima-Y é uma trajetória prima de Gteste cujos estados do seu único ciclo formam um ciclo indeterminado em Gteste . Uma trajetória prima-N é uma trajetória prima de Gteste cujo único ciclo é formado por estados de Gteste cujas primeiras componentes são estados incertos de G0d , e, cujas segundas componentes são estados normais ou incertos de Gd que não sejam estados de um ciclo indeterminado. 2 Considere, inicialmente, as trajetórias de Gteste que possuem ciclos formados por estados cujas primeiras componentes formam ciclos observados indeterminados em G0d . Teorema 1 Considere a sequência s0 formada por eventos de uma trajetória prima de G0d cujo único ciclo seja observado indeterminado. Então, 4817 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. ISBN 978-85-61507-02-2 é sempre possível encontrar um par de sequências, sY e sN , formados, respectivamente, por eventos de uma trajetória prima-Y e de uma trajetória prima-N de Gteste tais que s0 ∈ Poo0 (sY ) e s0 ∈ Poo0 (sN ), sendo Poo0 : Eo∗ → Eo0∗ componente. Esse fato sugere que pode ser possível estabelecer uma correlação entre trajetórias primas-Y de Gteste e trajetórias de G0d com ciclos escondidos indeterminados inerentes. Essa correlação é estabelecida no teorema seguinte. Prova: Ver Lima (2010). ? Teorema 3 Considere x?t = (x0? d , xd ) como sendo o único estado revisitado de uma trajetória primaY de Gteste , e que a sequência sY seja formada pelos eventos dessa trajetória prima-Y. Além disso, suponha que sY = uv, em que v ∈ (Eo \ Eo0 )∗ , x?t = ft (x0t , u), e ft (x?t , v) = x?t . Então, 2 O teorema 1 estabelece que para qualquer sequência s0 formada pelos eventos de uma trajetória prima de G0d cujo único ciclo seja observado indeterminado é sempre possível encontrar, ao menos, um par de sequências sY e sN , formadas, respectivamente, pelos eventos de uma trajetória prima-Y e de uma trajetória prima-N de Gteste , tais que s0 ∈ Poo0 (sY ) and s0 ∈ Poo0 (sN ). Esse fato não implica que, para cada trajetória prima-Y de Gteste , cuja sequência associada seja sY , seja sempre possível encontrar uma sequência s0 formada pelos eventos de uma trajetória prima de G0d cujo único ciclo seja observado indeterminado, tal que, para uma sequência v ∈ sY , s0 = Poo0 (v). A mesma conclusão se estende ao caso de trajetórias primas-N de Gteste . Em vista desses fatos, o seguinte resultado será enunciado. (1) s0 = Poo0 (sY ) é uma sequência formada pelos eventos de uma trajetória com ciclos escondidos indeterminados inerentes de G0d , no 0 0 0 estado x0? d = fd (x0d , s ); (2) existe, ao menos, uma sequência sN , formada pelos eventos de uma trajetória prima de Gteste cujo único estado revisitado é x#t = (x0d# , x#d ) = ft (x0t , sN ), em que x0d# é um estado incerto ou normal de G0d e x#d é um estado normal ou incerto que não faz parte de um ciclo indeterminado de Gd , que possui um prefixo ŝN (ŝN ∈ sN ) tal que Poo0 (ŝN ) = s0 . Teorema 2 Considere a sequência s formada pelos eventos de uma trajetória prima-Y ou de uma trajetória prima-N de Gteste . Então, existe sempre uma sequência u ∈ s tal que Poo0 (u) = s0 , em que s0 é uma sequência formada pelos eventos de uma trajetória prima de G0d (formada a partir de um ciclo observado) cujo único ciclo satisfaz uma das seguintes condições: (i) é indeterminado; (ii) é formado por estados normais; (iii) é formado por estados incertos que não dão origem a um ciclo indeterminado. Prova: A prova deste teorema pode ser encontrada em Lima (2010). 2 A partir de agora, é possível identificar aquelas trajetórias primas de Gteste que estão diretamente ligadas a ciclos observados indeterminados em G0d , e aquelas que estão diretamente ligadas a ciclos escondidos indeterminados em G0d . Com isso, está estabelecida a correlação entre as trajetórias primas de Gteste e as trajetórias com ciclos indeterminados inerentes (observados e escondidos) de G0d , como se buscava. Prova: A prova deste teorema pode ser encontrada em Lima (2010). 2 3 G0d Considere agora os ciclos escondidos de (Basilio e Lafortune, 2009). De modo a obter resultados para ciclos escondidos indeterminados similares aos encontrados para ciclos observados indeterminados, considere a seguinte definição. Lidando com ciclos observados indeterminados de G0d ? Considere x?t = (x0? d , xd ) como sendo o único estado revisitado de uma trajetória prima-Y de Gteste e que sY = uv seja a sequência formada pelos eventos dessa trajetória. Suponha que u e v satisfaçam às seguintes condições: x?t = ft (x0t , u) e ft (x?t , v) = x?t . Portanto, para que essa trajetória prima-Y seja associada a um ciclo observado indeterminado em G0d , ao menos um evento de v deve pertencer à Eo0 . A mesma condição se aplica a uma trajetória prima-N de Gteste . Associando trajetórias primas-Y e trajetórias primas-N de Gteste com trajetórias de G0d , de acordo com o teorema 2, três casos são possíveis de ocorrer: 1. Existe um par (sY , sN ) associados a uma trajetória prima-Y e a uma trajetória prima-N de Gteste , respectivamente, e uma sequência s0 associada a uma trajetória prima de G0d cujo único ciclo é observado indeterminado, tais que Poo0 (sY ) = Definição 2 (Trajetória com ciclos escondidos inerentes) Uma trajetória 0 Phc = (x00d , σd0 , x01d , σd1 , . . . , x0nd ) de G0d , em que x00d é o estado inicial de G0d , é uma trajetória com ciclos escondidos inerentes se 0 existir um estado x0kd ∈ Phc que possua um ciclo escondido. 2 Como L(Gteste ) = L(Gd ) e os eventos que rotulam transições entre esses estados de um ciclo escondido pertencem à Eo \ Eo0 , os ciclos que são escondidos em G0d possuem ciclos correspondentes em Gteste , cujos estados têm a mesma primeira 4818 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. Poo0 (sN ) = s0 ; 2. Para algum sY = uv (ou sN = uv) associado a uma trajetória prima-Y (ou, respectivamente trajetória prima-N) de Gteste , existe uma sequência s0 associada a uma trajetória prima de G0d cujo único ciclo é observado indeterminado, tal que Poo0 (u) = s0 e Poo0 (v) 6= ε; 3. Para algum sY = uv (ou sN = uv) associado a uma trajetória prima-Y (ou, respectivamente trajetória prima-N) de Gteste , existe uma sequência s0 associada a uma trajetória prima de G0d cujo único ciclo não é indeterminado (i.e. é formado por estados normais ou é um ciclo de estados incertos que não indeterminado), tal que Poo0 (u) = s0 and Poo0 (v) 6= ε. Nesse trabalho somente o caso 1 será considerado. rias primas para cobertura, assim se um evento de cada par (sY , sN ) for incluído em Eies , então, ao menos, um evento de cada trajetória-Y ou N com ciclos inerentes, que possuem, respectivamente, sequências associadas ŝY e ŝN que satisfaçam Poo0 (ŝY ) = Poo0 (ŝN ), também será incluído em Eei . Considere a seguinte definição. Definição 3 (Produto ponto-cartesiano) A. Considere os conjuntos Ei ⊆ E, i = 1, 2, . . . , n. O produto ponto-cartesiano entre os conjuntos Ei , i = 1, 2, . . . , n, denotado por ˙ 2× ˙ . . . ×E ˙ n , é definido como se segue: E1 ×E ˙ 2× ˙ . . . ×E ˙ n = {Ee = Ee,1 ∪ Ee,2 ∪ E1 ×E 1 . . . ∪ Ee,n : (Ee,1 , Ee,2 , . . . , Ee,n ) ∈ 2E 1 × En 2 ×2E 1 × . . . × 21 }, Teorema 4 Suponha que a linguagem L não seja diagnosticável com relação a Po0 e Ef , e seja Eo00 = Eo0 ∪ Eei , Eei ⊆ Eo \ Eo0 . Suponha que G00d denote o diagnosticador parcial para L considerando Eo00 como conjunto de eventos observáveis. Além disso, suponha que exista um par de sequências (sY , sN ) associadas a uma trajetória prima-Y e a uma trajetória prima-N de Gteste , respectivamente, e uma sequência s0 associada a uma trajetória prima de G0d cujo único ciclo seja observado indeterminado, e que satisfaçam Poo0 (sY ) = Poo0 (sN ) = s0 . Uma condição necessária para que a trajetória prima associada a s0 não seja uma trajetória prima de G00d cujo único ciclo é observado indeterminado, é que Eei ∩ [(EsY ∪ EsN ) \ Eo0 ] 6= ∅, em que EsY e EsN denotem, respectivamente, o conjunto formado pelos eventos das sequências sY e sN . Prova: Ver Lima (2010). ISBN 978-85-61507-02-2 E em que 2E 1 = {Ee ∈ 2 : |Ee | = 1}. B. Considere os conjuntos Ei ⊆ 2E , i = 1, 2, . . . , n, e defina o seguinte conjunto: E× = {Ee = Ee,1 ∪ Ee,2 ∪ . . . ∪ Ee,n : (Ee,1 , E2 En 1 Ee,2 , . . . , Ee,n ) ∈ 2E 1 × 21 × . . . × 21 }. Considere que |E× | = p e que os elementos de E× sejam denotados por E×,i , i = 1, 2, . . . , p. O produto ponto-cartesiano entre os conjuntos Ei , i = 1, 2, . . . , n, é definido como se segue: ˙ 2× ˙ . . . ×E ˙ n = {Ẽ×,1 , Ẽ×,2 , . . . ; Ẽ×,p : E1 ×E (Ẽ×,i = ∪E∈E×,i E) ∧ (E×,i ∈ E× )}. 2 Com a definição acima, é possível apresentar o seguinte algoritmo para encontrar o conjunto Eei . 2 Algoritmo 1 Observação 1 Note que a condição estabelecida pelo Teorema 4 é somente necessária, pois se um evento comum a sY e a sN pertencer à Eei e esse conjunto for tal que Poo00 (sY ) = Poo00 (sN ) = s00 , então s00 estará associada a uma trajetória com ciclos indeterminados inerentes. 2 Passo 1 Forme os seguintes conjuntos: • S 0 = {s0 ∈ Eo0∗ : s0 é uma sequência formada com os eventos de uma trajetória prima de G0d formada a partir de um ciclo observado indeterminado. Podese escrever esse conjunto como S 0 = {s01 , s02 , . . . , s0p }, em que p = |S 0 |. De acordo com o Teorema 4, para que um par de sequências (sY , sN ), associadas a uma trajetória prima-Y e a uma trajetória prima-N de Gteste , que satisfaz Poo0 (sY ) = Poo0 (sN ) = s0 , não leve a trajetórias com ciclos indeterminados inerentes em G00d , é necessário incluir, ao menos, um evento de sY ou um evento de sN em Eies . Portanto, essa condição deve ser satisfeita para todos os pares de sequências (sY , sN ) de Gteste cujas projeções em Eo0 levam a alguma trajetória prima associada a s0 , como o caso mencionado acima. Além disso, como toda trajetória prima-Y e -N são coberturas para si próprias, e qualquer trajetóriaY e -N com ciclos inerentes possuem, respectivamente, trajetórias primas-Y e -N como trajetó- • SY = {sY ∈ Eo∗ : sY é uma sequência formada com os eventos de uma trajetória prima-Y de Gtest associada a uma trajetória com ciclos observados indeterminados inerentes de G0d }. • SN = {sN ∈ Eo∗ : sN é uma sequência formada com os eventos de uma trajetória prima-N de Gtest associada a uma trajetória com ciclos observados indeterminados inerentes de G0d }. Passo 2 Para cada s0i ∈ S 0 , i = 1, . . . , p, forme os seguintes conjuntos: 4819 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. ? ? c 1 b a σf c 6 hc(b) 1 + c s ihc(b) 9 {8Y } {9N, 10Y } O 6 6 a ihc(b) c ihc(b) w ) 8 Figura 3: Diagnosticador parcial G0d . c 9 a x0d0 c a i h c b, c c Figura 1: Autômato G. h h {Y } ? d c ? {Y } ? b- {4N, 7Y } h h {Y N} {Y } 9 {4N } Figura 4: Árvore para G0d . b a ? w {1N, 2N, 3N, 4N, 5Y, 7Y ; 1N } {8Y } {10Y } {11Y } O O O a b ? a {Y N} a d q c a {Y } R {2N, 3N, 5Y } {2N, 5Y } ? ) c b {Y N} c h {Y } {Y N} a {6N, 8Y, 9N } {Y } h {1N } c a c c c a a a 1 6 a s 11 10 c {9N } a ihc(b) {9N, 10Y, 11Y } w i c ? {6N, 8Y, 9N, 10Y } 6 c = c hc(b) c σ i a / {1N, 2N, 3N, 4N, 5Y, 7Y } ? w 7 a {6N, 8Y, 9N, 10Y, 11Y } 3 c {2N, 4N, 5Y, 7Y, 11Y } w 6 / a {11Y } c w 5 1 b c / d / σ 2 d 4 3 ISBN 978-85-61507-02-2 b, c ? {2N, 4N, 5Y, 7Y, 11Y ; 2N, 5Y } c d O Figura 2: Diagnosticador Gd . {2N, 4N, 5Y, 7Y, 11Y ; 4N, 7Y } ? ? {6N, 8Y, 9N, 10Y, 11Y ; 10Y } O c a ? O b, c c b ? {1N, 2N, 3N, 4N, 5Y, 7Y ; 4N } ? O O {2N, 4N, 5Y, 7Y, 11Y ; 11Y } b c {9N, 10Y ; 10Y } ? {9N, 10Y ; 9N } O c O b c ? c {9N, 10Y, 11Y ; 9N } {9N, 10Y, 11Y ; 10Y } Passo 3 Para cada siY,k ∈ SYi forme um conjunto i EY,k com os eventos de siY,k que não perteni forme um çam à Eo0 . Para cada siN,l ∈ SN i conjunto EN,l com os eventos de siN,l que não pertençam à Eo0 . ? O O a ? {6N, 8Y, 9N, 10Y ; 10Y } {8Y ; 8Y } c ? b i • SN = {sN ∈ SN : Poo0 (sN ) = s0i }. c a c {6N, 8Y, 9N, 10Y, 11Y ; 6N, 8Y, 9N } a O • SYi = {sY ∈ SY : Poo0 (sY ) = s0i }. ? ? ? {11Y ; 11Y } c d ? {6N, 8Y, 9N, 10Y ; 6N, 8Y, 9N } {1N, 2N, 3N, 4N, 5Y, 7Y ; 4N, 7Y } a b c c ? b {2N, 4N, 5Y, 7Y, 11Y ; 4N } {1N, 2N, 3N, 4N, 5Y, 7Y ; 2N, 3N, 5Y } ? {6N, 8Y, 9N, 10Y, 11Y ; 11Y } b, c c ? {9N, 10Y, 11Y ; 11Y } O c Figura 5: Autômato Gteste = G0d kGd . o diagnosticador Gd para L = L(G), de onde se pode verificar que L é diagnosticável em relação a Po : E ∗ → Eo∗ e Ef . Calcula-se o conjunto de eventos elementares para a diagnose (vide parte 1 deste trabalho) (Lima, 2010), que é dado por Eeed = {{a, c}, {a, b, c}}. Inicialmente, verificarse-á se Eo0 = {a, c} é uma base mínima para a diagnose de L(G) construindo-se o diagnosticador parcial G0d considerando Eo0 como conjunto de eventos observáveis e verificando se há ciclos indeterminados observados e/ou escondidos. Esse diagnosticador parcial está mostrado na figura 3. Pode-se observar que G0d possui tanto ciclos escondidos indeterminados (representados por laços próprios formados por arcos pontilhados e rotulados por ihc) quanto ciclos observados indeterminados (nos estados (9N, 10Y ) e (9N, 10Y, 11Y )). De maneira a se tentar evitar os ciclos observados indeterminados em G00d , deve-se aplicar o algoritmo 1. No passo 1, deve-se formar o conjunto S 0 com as sequências construídas com os eventos de uma trajetória prima de G0d ligada a um ci- Passo 4 Para i = 1, . . . , p, calcule: Y i i i ˙ Y,2 ˙ . . . ×E ˙ Y,k = EY,1 ×E × , em que • Eei,i i k = |SY |. N i i i ˙ N,2 ˙ . . . ×E ˙ N,l • Eei,i = EN,1 ×E × , em que i l = |SN |. Y N • Eei,i = Eies,i ∪ Eies,i . ˙ ei,2 × ˙ . . . ×E ˙ ei,p . Passo 5 Calcule Eei = Eei,1 ×E 2 O algoritmo 1 retorna um conjunto Eei que consiste de subconjuntos de Eo \ Eo0 que devem ser unidos a Eo0 de forma a criar novos candidatos a bases mínimas para a diagnose de falhas. Para ilustrar a aplicação do algoritmo 1, considere o seguinte exemplo. Exemplo 1 (Aplicação do algoritmo 1) Considere o autômato G mostrado na figura 1. Nele, Euo = {σ, σf } e Ef = {σf }. A figura 2 mostra 4820 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. ISBN 978-85-61507-02-2 xt0 b a h d h c {Y N, Y 1 } b h a c h h {Y N, N} c {Y N, Y 2 } b b h {Y N, Y 1 } c a a h h {Y N, N} c h d c c c a a c {Y N, N} h {Y N, N} b c c a b h{Y N, Y 1 } c b c h {Y N, N} {Y, Y } {Y N, N} {Y, Y } {Y, Y } {Y N, N} b c b h {Y N, Y 2 } {Y N, Y 1 } {Y N, N} h {Y N, Y } {Y N, Y 2 } {Y N, Y 2 } c h {Y N, Y 2 } {Y N, Y 2 } c {Y N, Y } Figura 6: Árvore para Gteste . Os nós {Y N, Y 1 } e {Y N, Y 2 } correspondem a estados incertos de Gteste diferentes numa mesma trajetória. que não pertençam à Eo0 . De acordo com o passo Y 1 ˙ 1 4, calcula-se Eei,1 = EY,1 ×EY,2 = {{b, d}, {d}}, Y N N Eei,2 = {{b}, {d}}, Eei,1 = ∅, Eei,2 = {{b}}, Y N Eei,1 = Eei,1 ∪ Eei,1 = {{b, d}, {d}} e Eei,2 = N Y = {{b}, {d}}. Por fim, no passo 5, ∪ Eei,2 Eei,2 ic ˙ ei,2 = {{b, d}, {d}}. calcula-se Eei = Eei,1 ×E 2 clo observado indeterminado. Para tanto, devese construir a árvore para G0d , mostrada na figura 4, e identificar as trajetórias primas que possuem como folha um estado incerto de G0d pertencente a um ciclo observado indeterminado. Pela figura 4, somente duas trajetórias satisfazem essa condição, sendo as sequências associadas a essas trajetórias s01 = accc e s02 = ccc. Logo, S 0 = {s01 , s02 } = {accc, ccc}. Para formar os conjuntos SY e SN deve-se construir a árvore para Gteste e identificar as trajetórias primas-Y e -N associadas a ciclos observados indeterminados de G0d . Através da árvore para Gteste , mostrada na figura 6, pode-se verificar que as sequências associadas a trajetórias primas-Y são as seguintes: sY,1 = adcc(c), sY,2 = adcc(b), sY,3 = adc(b), sY,4 = bdacc(c), sY,5 = bdc(b), sY,6 = bdcc(b), sY,7 = bdcc(c). Porém, somente as sequências sY,1 , sY,4 e sY,7 são associadas a trajetórias ligadas a ciclos observados indeterminados, pois, ao menos, um evento da subsequência que leva a trajetória do primeiro alcance do único estado revisitado até seu segundo alcance (destacadas entre parênteses nas sequências) pertencente à Eo0 . Logo, SY = {adccc, bdaccc, bdccc}. As sequências associadas a trajetórias primas-N são: sN,1 = adb(b), sN,2 = bcc(c), sN,3 = bdb(b) e sN,4 = acc(c). A mesma condição aplicada para o caso das trajetórias primas-Y deve ser aplicada para as trajetórias primas-N, levando ao conjunto SN = {bccc, accc}. De acordo com o passo 2, devem-se formar os conjuntos SY1 = {adccc, bdaccc}, SY2 = {bdccc}, 1 2 SN = {accc} e SN = {bccc}, em que as projeções das sequências pertencentes aos conjuntos com índices 1 e 2 em Eo0 são iguais às sequências s01 e s02 pertencentes à S 0 , respectivamente. 1 No passo 3, formam-se os conjuntos EY,1 = {d}, 1 2 1 2 EY,2 = {b, d}, EY,1 = {b, d}, EN,1 = ∅ e EN,1 = {b} com os eventos das sequências que pertencem aos conjuntos criados no passo anterior, e 4 Lidando com ciclos escondidos indeterminados de G0d Considere a sequência sY = uv, v ∈ (Eo \ Eo0 )∗ , formada com os eventos de uma trajetória primaY de Gteste cujo único estado revisitado seja x?t = ? ? ? ? (x0? d , xd ), em que xt = ft (x0t , u) e ft (xt , v) = xt . De acordo com o teorema 3, essa trajetória primaY está associada a uma trajetória com ciclos escondidos indeterminados inerentes de G0d no es0 0 0 0 tado x0? d = fd (x0d , s ), em que s = Poo0 (sY ). Uma condição necessária para que uma trajetória com ciclos escondidos indeterminados de G0d associada a uma trajetória prima-Y de Gteste não seja uma trajetória de G00d é dada pelo seguinte teorema. Teorema 5 Suponha que a linguagem L não seja diagnosticável com relação a Po0 e Ef e considere Eo00 = Eo0 ∪ Eei , Eei ⊆ Eo \ Eo0 . Seja G00d o diagnosticador parcial de L considerando Eo00 como conjunto de eventos observáveis. Além disso, suponha que exista um par (sY , sN ), em que sY é uma sequência formada pelos eventos de uma trajetória prima-Y de Gteste associada a uma trajetória com ciclos escondidos indeterminados, e sN é uma sequência formada pelos eventos de uma trajetória prima de Gteste cujo único estado revisitado é x#t = (x0d# , x#d ), com x#d sendo um estado normal ou incerto de Gd . Finalmente, suponha que para uma sequência ŝN ∈ sN , Poo0 (sY ) = Poo0 (ŝN ) = s0 . Uma condição necessária para que a trajetória com ciclos escondidos indeterminados associada a s0 não seja uma trajetória de G00d , é 4821 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. 0i 0 0 • SN h = {s ∈ SN h : si ∈ s}. que Eei ∩ [(EsY ∪ Es̃N ) \ Eo0 ] 6= ∅, em que EsY e Es̃N denotam, respectivamente, o conjunto formado pelos eventos da sequência sY e s̃N , com s̃N um prefixo de ŝN tal que Poo0 (s̃N ) = Poo0 (ŝN ) e cujo último evento s̃Nf ∈ Eo0 . Prova: Ver Lima (2010). i • SN = {sN ∈ SN h h 0i SN )[P oo0 (sN ) = s]}. h 2 (∃s ∈ Passo 5 Para cada siY,k ∈ SYi h forme o conjunto i EY,k com os eventos de siY,k que não perteni cem à Eo0 . Para cada s̃iN,q ∈ SÑ forme o h i conjunto EÑ ,q com os eventos de s̃iN,q que não pertencem à Eo0 . Y Passo 6 Para i = 1, . . . , p, calcule Eei,i = i i i Ñ i ˙ ˙ ˙ ˙ EY,1 ×EY,2 × . . . ×EY,m e Eei,i = EÑ ,1 × i i ˙ ˙ × ˙ . . . ×E ˙ , em que m e r deno×E × Ñ ,2 Ñ ,r tam, respectivamente, a cardinalidade de SYi h i e a cardinalidade de SÑ . h Y Passo 7 Para i = 1, . . . , p, calcule Eei,i = Eei,i ∪ Ñ Eei,i ,. ˙ ei,2 × ˙ . . . ×E ˙ ei,p . Passo 8 Calcule Eei = Eei,1 ×E 2 Algoritmo 2 Para ilustrar a aplicação do algoritmo 2, considere o exemplo abaixo. Passo 1 Forme os seguintes conjuntos: Exemplo 2 (Aplicação do algoritmo 2) Considere novamente o autômato G da figura 1, seu diagnosticador centralizado (figura 2), seu diagnosticador parcial considerando Eo0 = {a, c} como conjunto de eventos observáveis (figura 3) e o autômato Gteste = G0d kGd (figura 5). Segundo o passo 1 do algoritmo 2, deve-se formar os conjuntos SY h e SY0 h , respectivamente, com as sequências associadas a trajetórias primas-Y de Gteste ligadas a trajetórias com ciclos escondidos indeterminados de G0d e com as projeções em Eo0∗ das sequências de SY h . No exemplo 1, foram identificadas todas as trajetórias primas-Y associadas a ciclos observados indeterminados, de forma que as demais trajetórias primas-Y só podem estar associadas a ciclos escondidos indeterminados. Além disso, pode-se identificá-las utilizandose suas subsequências que levam a trajetória do primeiro alcance do único estado revisitado ao seu segundo alcance, em que, no caso de ciclos escondidos indeterminados, devem ser formadas somente por eventos em Eo \Eo0 . Portanto, formamse SY h = {adccb, adcb, bdcb, bdccb} e SY0 h = {s01 , s02 , s03 , s04 } = {acc, ac, c, cc}. Segundo o passo 2, para cada s0i ∈ SY0 h deve-se formar um conjunto SYi h com as sequências de SY h que possuem projeção em Eo0∗ igual à sequência s0i . Formam-se então SY1 h = {adccb}, SY2 h = {adcb}, SY3 h = {bdcb} e SY4 h = {bdccb}. No passo 3, devem-se identificar todas as sequências associadas a trajetórias primas de Gteste cujo único estado revisitado • SY h = {sY ∈ Eo∗ : sy é uma sequência formada com os eventos de uma trajetória prima-Y de Gtest associada a uma trajetória com ciclos escondidos indeterminados inerentes de G0d }. • SY0 h = {s ∈ Eo0∗ : (∃sY ∈ SY h )[Poo0 (sY ) = s]}. Considere p = |SY0 h | ≤ |SY h |. Então o conjunto SY0 h pode ser escrito por SY0 h = {s01 , s02 , . . . , s0p }. Passo 2 Para cada s0i ∈ SY0 h , i = 1, . . . , p, forme o seguinte conjunto: SYi h = {sY ∈ SY h : Poo0 (sY ) = s0i }. Passo 3 Utilizando a mesma árvore construída para se obter as trajetórias primas-Y de Gteste , forme as seguintes conjuntos: • SN h = {sN ∈ Eo∗ : sN é uma sequência formada com os eventos de uma trajetória prima de Gtest cujo único estado revisitado possui como segunda componente um estado normal ou um estado incerto de Gd }. : : i 0 i 0 • SÑ = {s ∈ SN h : (Poo (s) = si ) ∧ (sf ∈ h 0 Eo )}, em que sf denota o último evento de s. Como no caso de ciclos observados indeterminados, pode-se utilizar o conceito de cobertura para uma trajetória com ciclos inerentes para se justificar que incluir um evento de cada trajetória prima-Y é o suficiente para que a condição necessária de se incluir um evento para cada trajetóriaY seja satisfeita. Além disso, como as sequências s̃N são de tamanho finito e não estão associadas a trajetórias com ciclos inerentes em Gd , não se faz necessário o uso dos conceitos de cobertura e trajetórias primas para se justificar que somente essas sequências são necessárias para satisfazer à condição para que G00d não possua ciclos escondidos indeterminados. O algoritmo abaixo permite que se encontre o conjunto Eei , como tentativa de se evitar o aparecimento de ciclos escondidos indeterminados em G00d . 0 = {s ∈ Eo0∗ • SN h SN h )[Poo0 (sN ) = s]}. ISBN 978-85-61507-02-2 (∃sN ∈ Passo 4 Para cada s0i ∈ SY0 h , i = 1, . . . , p, forme os seguintes conjuntos: 4822 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. cerrado, pois não existem bases para a diagnose de falhas em G. seja um estado normal ou incerto de Gd . Através da árvore da figura 6, pode-se concluir que o conjunto formado pelas sequências que satisfazem às condições citadas é o conjunto SN h = {adbb, accc, bccc, bdbb}. É fácil verificar que o conjunto formado pelas projeções em Eo0∗ das sequên0 cias do conjunto SN h é SN h = {a, accc, ccc, ε}. Através do passo 4, formam-se, então, os conjun01 02 03 tos SN h = {accc}, SN h = {accc}, SN h = {ccc} 04 1 2 e SN h = {ccc}; SN h = {accc}, SN h = {accc}, 3 4 1 SN h = {bccc} e SN h = {bccc}; e SÑ h = {acc}, 4 2 3 = {bc} e SÑ = {bcc}, em que SÑ = {ac}, SÑ h h h 0i 0 SN h é formado por sequências do conjunto SN h 0 0 que possuem como prefixo a sequência si ∈ SY h ; i SN h é formado por sequências do conjunto SN h que possuem como projeção em Eo0∗ uma sequên0i i cia de SN h ; e SÑ h é formado pelos prefixos das i sequências de SN h que possuem projeções iguais a sequência s0i e cujo último evento pertence a Eo0 , para i = 1, . . . , 4. Através do passo 5, formam1 2 = {b, d}, EY,1 = {b, d}, se os conjuntos EY,1 4 3 EY,1 = {b, d} e EY,1 = {b, d}, e os conjuntos 3 4 2 1 = ∅, EÑ = {b} e EÑ = {b}, = ∅, EÑ EÑ ,1 ,1 ,1 ,1 com os eventos das sequências pertencentes aos i que não pertencem a Eo0 , conjuntos SYi h e SÑ h em que o índice superior denota que os eventos do conjunto pertencem a uma sequência do conjunto i SYi h ou do conjunto SÑ e o índice inferior se reh fere à ordem da sequência no conjunto. No passo Y 6, formam-se os conjuntos Eei,1 = {{b}, {d}}, Y Y Y = Eei,2 = {{b}, {d}}, Eei,3 = {{b}, {d}} e Eei,4 Passo 2 Encontre os Conjuntos de Eventos Elementares para a Diagnose de Falhas (Eeed ). (Vide a parte 1 deste trabalho.) Passo 3 Faça Ecbd = Eeed e Ebmd = ∅. Passo 4 Calcule Ēcbd = {Ē ∈ Ecbd : (∃Ẽ ∈ Eeed )[Ẽ ⊆ Ē]} e faça Ecbd ← Ecbd \ Ēcbd . Passo 5 Faça Eo0 = Ecbdmin , em que Ecbdmin é o subconjunto de Ecbd que possui menor cardinalidade. Passo 6 Calcule G0d . Passo 7 Se G0d não possuir ciclos indeterminados observados ou escondidos então • Ebmd ← Ebmd ∪ {Eo0 } • Ecbd ← Ecbd \ {Eo0 } Caso contrário • Ecbd ← Ecbd \ {Eo0 } ic • Aplique o algoritmo 1 e encontre Eei . ihc . • Aplique o algoritmo 2 e encontre Eei ic ˙ ihc • Calcule Eei = Eei ×Eei . • Para i = 1, . . . , n faça Ecbd ← Ecbd ∪ {Eo0 ∪ Eeii }, em que n = kEei k e Eeii denota um elemento (conjunto) de Eei . Ñ Ñ {{b}, {d}}, e os conjuntos Eei,1 = {∅}, Eei,2 = Passo 8 Calcule Êcbd = {Ē ∈ Ecbd : (∃Ẽ ∈ Ebmd )[Ẽ ⊆ Ē]} e faça Ecbd ← Ecbd \ Ēcbd . Se Ecbd = {∅} então o algoritmo está encerrado. Caso contrário, retorne ao passo 4. 2 Ñ Ñ {∅} Eei,3 = {{b}} e Eei,4 = {{b}}. Como cada i i conjunto SY h e SÑ h possui somente uma sequênY Ñ cia, os conjuntos Eies,i e Eies,i são formados por subconjuntos de um único evento. De acordo com o passo 7, formam-se os conjuntos Eei,1 = Y Ñ Y Ñ Eei,1 ∪ Eei,1 = {{b}, {d}}, Eei,2 = Eei,2 ∪ Eei,2 = Para ilustrar a aplicação do algoritmo 3 considere os dois exemplos a seguir. Y Ñ {{b}, {d}}, Eei,3 = Eei,3 ∪ Eei,3 = {{b}, {d}} e Exemplo 3 (Aplicação do algoritmo 3) Considere o autômato da figura 1. Deseja-se encontrar todas as bases mínimas para a diagnose de falhas em G. Inicialmente, é necessário verificar se L = L(G) é diagnosticável com relação a Po e Ef = {σf }. Esta análise foi realizada no exemplo 1, onde se obteve resposta afirmativa à essa questão, baseando-se no fato de que Gd (figura 2) não possui ciclos indeterminados observados ou escondidos. A tarefa a ser realizada no passo 2 do algoritmo 3, que consiste em determinar o conjunto de eventos elementares para a diagnose, foi cumprida no exemplo 1, levando a Eeed = {{a, c}, {a, b, c}}. Como {a, c} ⊂ {a, b, c}, então o conjunto {a, b, c} deve ser removido de Eeed , isto é, Ecbd = Eeed \ {{a, b, c}} = {{a, c}}. A seguir, define-se Eo0 = {a, c}, pois esse é o único conjunto de Ecbd . De acordo com o passo 6, devese calcular o diagnosticador parcial G0d , considerando Eo0 como o conjunto de eventos observáveis Y Ñ Eei,4 = Eei,4 ∪ Eei,4 = {{b}, {d}}. Finalmente, ihc seguindo o passo 8, forma-se o conjunto Eei = ˙ ˙ ˙ Eei,1 ×Eei,2 ×Eei,3 ×Eei,4 = {{b}, {d}, {b, d}}. 2 5 ISBN 978-85-61507-02-2 Procedimento para a busca das bases mínimas para a diagnose de falhas Embasado nos resultados apresentados nas seções 3 e 4, um algoritmo para a busca das bases mínimas para a diagnose centralizada de falhas em SED é apresentado a seguir. Algoritmo 3 Passo 1 Calcule Gd e verifique se há ciclos indeterminados observados ou escondidos. Se não houver ciclos indeterminados, avance ao passo 2. Caso contrário, o algoritmo está en- 4823 XVIII Congresso Brasileiro de Automática / 12 a 16 de Setembro 2010, Bonito-MS. a diagnose de falhas de um SED, permitindo assim que a diagnose de falhas de um SED seja realizada com um número mínimo de sensores, o que pode representar uma grande economia de recursos para o projeto de diagnose de falhas de um sistema real. Todos os passos do algoritmo de busca foram teoricamente justificados com base em condições necessárias. Além das contribuições já citadas, este artigo apresenta novos conceitos, definições e resultados a serem incorporados à teoria de SEDs, como, por exemplo, trajetórias primas, trajetórias com ciclos inerentes, cobertura para trajetórias com ciclos inerentes, conjuntos de eventos elementares para a diagnose, bases para a diagnose, diagnosticabilidade sob perda permanente de observabiidade de eventos etc. ? {2N, 5Y } c c 1 c {9N } ? ) {6N, 8Y, 9N } a a {1N, 2N, 3N, 5Y } d c d q ? c 6 hc(b) c ? a{11Y } {4N, 7Y } ? {8Y } {10Y } O c 6 a hc(b) Figura 7: Diagnosticador parcial G0d , para Eo0 = {a, c, d}. de G. No exemplo 1, G0d foi construído e está mostrado na figura 3. Como G0d possui tanto ciclos observados indeterminados quanto ciclos escondidos indeterminados, deve-se aplicar os alic goritmos 1 e 2. Nesse caso, encontra-se Eei = ihc {{b, d}, {d}} e Eei = {{b}, {d}, {b, d}}, como mostrado nos exemplos 1 e 2, respectivamente. ic ˙ ihc Portanto, pode-se calcular Eei = Eei ×Eei = {{b, d}, {d}}. Atualiza-se o conjunto Ecbd , que passa a ser Ecbd = {{a, c, d}, {a, b, c, d}}. De acordo com o passo 8, como Ebmd = ∅ e Ebmd 6= ∅, retorna-se ao passo 4. Nesse ponto, faz-se Ecbd = {{a, c, d}, {a, b, c, d}} \ {{a, b, c, d}} = {{a, c, d}}, dado que {a, c, d} ⊂ {a, b, c, d}. Isso faz com que, nessa iteração, Eo0 = {a, c, d}. Como descrito no passo 6, deve-se calcular G0d para o novo conjunto Eo0 , que está representado na figura 7. Note que G0d não possui nenhum ciclo indeterminado, e portanto, L é diagnosticável com relação a Po0 e Ef . De acordo com o passo 7, faz-se Ebmd = {{a, c, d}} e Ecbd = {{a, c, d}} \ {{a, c, d}} = ∅. Como Ecbd = {∅}, então o algoritmo está encerrado e o conjunto de bases mínimas para a diagnose contém somente um elemento, {a, c, d}. 2 Agradecimentos Os autores agradecem ao CNPq e ao NFS, EUA, pelo apoio financeiro que tornou possível a realização desse trabalho. Referências Basilio, J. C. e Lafortune, S. (2009). Robust codiagnosability of discrete event systems, Proceedings of the American Control Conference, St. Louis, Missouri, pp. 2202–2209. Lima, S. T. S. (2010). Diagnose centralizada de falhas de sistemas a eventos discretos robusta à perda permanente de sensores, Tese de Mestrado, UFRJ/COPPE - Programa de Engenharia Elétrica. Lima, S. T. S., Basilio, J. C., Lafortune, S. e Moreira, M. V. (2010a). Bases mínimas para a diagnose de falhas de sistemas a eventos discretos. Parte I: eventos essenciais para a diagnose e trajetórias primas, XVIII Congresso Brasileiro de Automática, Bonito, MS. Na seção 3 foi constatado que três casos eram possíveis na associação das trajetórias primas-Y e -N de Gteste com as trajetórias primas de G0d . Porém, somente o primeiro caso foi abordado. Isso porque o algoritmo de busca das bases para os outros dois casos possui características peculiares e ainda estão em fase de desenvolvimento. Entretanto, a grande maioria dos casos recai sobre o primeiro, dado que para satisfazer as condições impostas pelos outros dois casos, uma combinação de estados e sequências de eventos específica deve ser satisfeita. 6 ISBN 978-85-61507-02-2 Lima, S. T. S., Basilio, J. C., Lafortune, S. e Moreira, M. V. (2010b). Diagnose centralizada de falhas de sistemas a eventos discretos robusta à perda permanente de sensores, XVIII Congresso Brasileiro de Automática, Bonito, MS. Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K. e Teneketzis, D. (1995). Diagnosability of discrete-event systems, IEEE Trans. on Automatic Control 40: 1555–1575. Conclusão Neste trabalho foi proposto um algoritmo para a busca sistemática de todas as bases mínimas para 4824