Bases mínimas para a diagnose de falhas de sistemas a eventos

Transcrição

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
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 ŝN (ŝN ∈ sN ) tal que Poo0 (ŝ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
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 ŝY e ŝN que satisfaçam Poo0 (ŝY ) = Poo0 (ŝ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 .
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 = {Ẽ×,1 , Ẽ×,2 , . . . ; Ẽ×,p :
E1 ×E
(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
?
?
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
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 ŝN ∈ sN , Poo0 (sY ) =
Poo0 (ŝ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
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 ŝN tal que Poo0 (s̃N ) = Poo0 (ŝN ) e
cujo último evento s̃Nf ∈ Eo0 .
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 ∈ SÑ
forme o
h
i
conjunto EÑ ,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
Ñ
i
˙
˙
˙
˙
EY,1 ×EY,2 × . . . ×EY,m e Eei,i = EÑ ,1 ×
i
i
˙
˙ ×
˙ . . . ×E
˙
, em que m e r deno×E
×
Ñ ,2
Ñ ,r
tam, respectivamente, a cardinalidade de SYi h
i
e a cardinalidade de SÑ
.
h
Y
Passo 7 Para i = 1, . . . , p, calcule Eei,i = Eei,i
∪
Ñ
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
• SÑ
= {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
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 SÑ h = {acc},
4
2
3
= {bc} e SÑ
= {bcc}, em que
SÑ
= {ac}, SÑ
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 SÑ 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
= ∅, EÑ
= {b} e EÑ
= {b},
= ∅, EÑ
EÑ
,1
,1
,1
,1
com os eventos das sequências pertencentes aos
i
que não pertencem a Eo0 ,
conjuntos SYi h e SÑ
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 SÑ
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 Ēcbd = {Ē ∈ Ecbd : (∃Ẽ ∈
Eeed )[Ẽ ⊆ Ē]} e faça Ecbd ← Ecbd \ Ē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 .
Ñ
Ñ
{{b}, {d}}, e os conjuntos Eei,1
= {∅}, Eei,2
=
Passo 8 Calcule Êcbd = {Ē ∈ Ecbd : (∃Ẽ ∈
Ebmd )[Ẽ ⊆ Ē]} e faça Ecbd ← Ecbd \ Ēcbd .
Se Ecbd = {∅} então o algoritmo está encerrado. Caso contrário, retorne ao passo 4. 2
Ñ
Ñ
{∅} Eei,3
= {{b}} e Eei,4
= {{b}}. Como cada
i
i
conjunto SY h e SÑ h possui somente uma sequênY
Ñ
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
Ñ
Y
Ñ
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
Ñ
{{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
Ñ
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
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

Bases mínimas para a diagnose de falhas de sistemas a eventos

Transcrição

Documentos relacionados

FT_14 Ficheiro - Agrupamento Escolas João da Silva Correia

Resolucao Area Saude - Fisica

Calor, Temperatura, Primeira e Segunda Lei da

ÓLEO DIESEL

Casal de SP fez roupa que será usada por astronauta brasileiro

Tipos de empresas de bens de consumo no Brasil

- CITA-A

EN388 Riscos Mecânicos

Sistema de Estacionamento Automático para um Veículo Autônomo

ficha técnica