DIAGNOSTICADOR REDE DE PETRI PARA UM SED MODELADO

Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
DIAGNOSTICADOR REDE DE PETRI PARA UM SED MODELADO POR UM
AUTÔMATO FINITO
Marcos V. Moreira∗, Felipe G. Cabral†, Oumar Diene†
∗
†
COPPE-Programa de Engenharia Elétrica, Universidade Federal do Rio de Janeiro, Cidade
Universitária, Ilha do Fundão, Rio de Janeiro, 21.945-970, RJ, Brasil
Departamento de Engenharia Elétrica, Universidade Federal do Rio de Janeiro, Cidade Universitária,
Ilha do Fundão, Rio de Janeiro, 21.945-970, RJ, Brasil
Emails: [email protected], [email protected], [email protected]
Abstract— Fault detection and isolation is an essential task in automated manufacturing systems, and thus,
several works in the literature address this problem. We propose in this paper a Petri net approach to online
diagnosis of a discrete event system (DES) modeled as a finite state automaton. The diagnosis method requires
less memory than other methods proposed in the literature and relies on the computation of a Petri net diagnoser
(PND).
Keywords—
Petri net, Automaton, Fault diagnosis, Discrete event systems.
Resumo— Detecção e isolamento de falhas é uma tarefa essencial em sistemas de automação e, portanto,
vários trabalhos têm sido publicados sobre este assunto. Neste artigo, é proposta uma abordagem por redes
de Petri para diagnose online de falhas em um sistema a eventos discreto modelado por um autômato finito.
O método de diagnose requer menos memória do que outros métodos propostos na literatura e é baseado na
obtenção de um diagnosticador rede de Petri (DRP).
Palavras-chave—
1
Rede de Petri, Autômato, Diagnóstico de falhas, Sistemas a eventos discretos.
INTRODUÇÃO
Detecção e isolamento de falhas é uma tarefa essencial em sistemas de automação e, por isso,
muitos trabalhos têm sido publicados sobre esse
assunto (Lin, 1994; Sampath et al., 1995; Qiu
and Kumar, 2006; Carvalho et al., 2011; Basilio
et al., 2012).
Em Sampath et al. (1995), é apresentada uma
abordagem para diagnose de falhas utilizando sistemas a eventos discretos (SEDs) modelados por
autômatos finitos. O método de diagnose proposto em Sampath et al. (1995) consiste de três
etapas: (i) construção de um autômato rotulado
Gℓ obtido a partir do autômato G que modela o
sistema, cujos estados são (x, ℓ), em que x é um
estado de G e ℓ ∈ {Y, N }. Se x é um estado alcançado em G após a ocorrência de uma sequência sY que contém o evento de falha, então um
estado (x, Y ) é alcançado em Gℓ após a ocorrência da mesma sequência sY , e se x é alcançado
em G após uma sequência normal sN , então o estado (x, N ) é alcançado após sN 1 ; (ii) obtenção
do autômato diagnosticador Gdiag calculando-se o
observador de estados do autômato rotulado Gℓ ;
(iii) identificação dos eventos de falha baseado no
estado alcançado de Gdiag após a observação de
uma sequência executada pelo sistema.
O diagnosticador proposto em Sampath et al.
(1995) pode ser usado para detectar e isolar falhas
1 Note que o comportamento normal e o de falha do
sistema são separados em Gℓ , i.e., um estado (x, Y ) é alcançado em Gℓ após a ocorrência de uma sequência s se e
somente se s possui um evento de falha.
ISBN: 978-85-8001-069-5
online e ainda para verificação off-line da diagnosticabilidade da linguagem gerada pelo sistema.
Embora esse diagnosticador possa ser implementado de forma direta em um computador, em geral isso é evitado, uma vez que, no pior caso, o
espaço de estados do diagnosticador Gdiag cresce
exponencialmente com a cardinalidade do espaço
de estados do modelo do sistema G (Sampath
et al., 1995; Qiu and Kumar, 2006).
Em Qiu and Kumar (2006), um método de
diagnose online que evita a construção e o armazenamento do autômato Gdiag é proposto. Para
tanto, um autômato não determinı́stico Gnd
ℓ é calculado substituindo-se cada transição de Gl associada a um evento não observável por uma transição ε. Nesse método apenas o estado atual do diagnosticador Gdiag e o autômato Gnd
ℓ precisam ser
armazenados para diagnose online. Após a ocorrência de um evento observável, o próximo estado
de Gdiag pode ser obtido em tempo polinomial
conhecendo-se o estado atual de Gdiag e o autômato Gnd
ℓ .
Neste artigo, é apresentada uma abordagem
por redes de Petri para diagnose online de falhas
em um SED. A definição de diagnosticabilidade é
a mesma apresentada em Sampath et al. (1995). É
suposto também que o sistema é descrito por um
autômato finito G e que o conjunto de eventos de
falha Σf pode ser particionado em diferentes conjuntos de eventos de falha Σfk , k = 1, . . . , r, em
que r denota o número de tipos de falha. O método é baseado no cálculo de um autômato GC que
modela a composição dos comportamentos normais do sistema, obtido a partir de G e autômatos
3723
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
GNk , para k = 1, . . . , r, em que o autômato GNk
modela o comportamento normal de G com relação ao conjunto de eventos de falha Σfk . Em
geral, GNk possui um número menor de estados
do que G, levando a uma redução na complexidade computacional da diagnose online em comparação com o método proposto em Qiu and Kumar (2006), que usa os comportamento normais e
de falha do sistema descritos por Gℓk = G∥Aℓk ,
para k = 1, . . . , r, em que Aℓk denota o autômato
rotulador com relação à falha do tipo Fk .
A técnica de diagnose proposta neste trabalho consiste em encontrar os estados alcançáveis
de GC após a observação de uma sequência de
eventos e, baseado no conjunto de estados alcançáveis de GC , verificar se a falha ocorreu. Para
tanto, um diagnosticador rede de Petri (DRP) é
proposto. O DRP é obtido a partir de uma rede
de Petri binária que é capaz de encontrar os estados alcançáveis de GC após a observação de uma
sequência de eventos.
Este artigo está organizado da seguinte forma:
na seção 2 são apresentados conceitos preliminares de autômatos e de redes de Petri; na seção 3 é
apresentada a definição de diagnosticabilidade de
uma linguagem; na seção 4 é proposto um método
para a obtenção do autômato GC calculado a partir dos comportamentos normais do sistema GNk ,
k = 1, . . . , r; na seção 5 o diagnosticador rede de
Petri (DRP) é apresentado; finalmente, as conclusões são apresentadas na seção 6. Um exemplo
é usado para ilustrar os resultados ao longo do
texto.
2
FUNDAMENTOS TEÓRICOS
Seja G = (Q, Σ, Γ, f, q0 ) um autômato determinı́stico que modela um SED, em que Q é o espaço de estados finito, Σ é o conjunto de eventos, Γ : Q → 2Σ é a função de eventos ativos,
f : Q × Σ → Q é a função de transição de estados
e q0 é o estado inicial do sistema. Por simplicidade, a função de eventos ativos será omitida a
menos que seja necessária.
A parte acessı́vel de G, denotada por Ac(G),
é a operação que elimina todos os estados de
G que não são alcançáveis a partir do estado inicial q0 e suas transições relacionadas,
i.e., Ac(G) = (Qac , Σ, fac , q0 ), em que Qac =
{q ∈ Q : (∃s ∈ Σ⋆ )[f (q0 , s) = q]} e fac : Qac ×Σ →
Qac é a nova função de transição de estados.
A operação de projeção Ps : Σ⋆l → Σ⋆s , em
que Σs ⊂ Σl é definida como Ps (ε) = ε, Ps (σ) =
σ, se σ ∈ Σs ou Ps (σ) = ε, se σ ∈ Σl \ Σs , e
Ps (sσ) = Ps (s)Ps (σ), para todo s ∈ Σ⋆l , e σ ∈ Σl .
A operação de projeção pode ainda ser aplicada à
linguagem gerada por G, L(G), executando essas
regras a todas as sequências s ∈ L(G).
Sejam G1 e G2 dois autômatos. Então, G1 ×
G2 e G1 ∥G2 denotam o produto e a composição
ISBN: 978-85-8001-069-5
paralela de G1 e G2 , respectivamente (Cassandras
and Lafortune, 2008).
Suponha agora que o conjunto de eventos de
˙ uo , em que Σo e
G seja particionado em Σ = Σo ∪Σ
Σuo denotam os conjuntos de eventos observáveis
e não observáveis, respectivamente. O alcance não
observável do estado q ∈ Q com relação ao conjunto Σuo , denotado por U R(q), é definido como
U R(q) = {y ∈ Q : (∃t ∈ Σ⋆uo )(f (q, t) = y)}. (1)
Essa definição é estendida a um subconjunto de
estados B ⊆ Q da seguinte forma:
∪
U R(B) =
U R(q).
(2)
q∈B
Uma rede de Petri (RP) é outro formalismo comumente usado para modelar um SED
(Cassandras and Lafortune, 2008; Davi and Alla,
2005). A principal vantagem em usar redes de Petri para descrever SEDs em comparação com os
autômatos finitos, é a natureza distribuı́da do estado da RP, o que permite a obtenção de grafos
compactos para descrever SEDs. Para definir formalmente uma RP primeiramente a estrutura de
uma rede de Petri será definida.
Definição 1 A estrutura de uma rede de Petri é
um grafo bipartido ponderado (P, T, P re, P ost, w),
em que P é o conjunto finito de lugares, T é o
conjunto finito de transições, P re ⊆ (P × T ) é o
conjunto de arcos que ligam lugares a transições,
P ost ⊆ (T × P ) é o conjunto de arcos que ligam
transições a lugares, e w : (P × T ) ∪ (T × P ) → N
é a função de pesos dos arcos, com w(pi , tj ) = 0
e w(tj , pi ) = 0 se e somente se (pi , tj ) ̸∈ P re e
(tj , pi ) ̸∈ P ost, respectivamente.
O conjunto de lugares é representado neste
artigo por P = {p1 , p2 , . . . , pn } e o conjunto de
transições por T = {t1 , t2 , . . . , tm }. Logo, |P | = n
e |T | = m, em que |.| denota cardinalidade.
A indicação de que as condições para o disparo das transições são satisfeitas é obtida através da atribuição de fichas aos lugares. O número de fichas atribuı́das a um lugar pi é representado por x(pi ), em que x : P → N. Logo, uma
marcação de uma rede de Petri é o vetor coluna
T
x = [x(p1 ) x(p2 ) . . . x(pn )] , formado pelo número de fichas em cada lugar pi , para i = 1, . . . , n.
Definição 2 Uma rede de Petri N é uma sêxtupla N = (P, T, P re, P ost, w, x0 ), em que
(P, T, P re, P ost, w) é, de acordo com a definição
1, a estrutura de uma rede de Petri e x0 é a marcação inicial do conjunto de lugares.
Em uma rede de Petri, normalmente eventos
são associados a transições e lugares são associados às condições que precisam ser satisfeitas para
a ocorrência desses eventos. Isso leva à seguinte
definição de redes de Petri rotuladas.
3724
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
Definição 3 Uma rede de Petri rotulada N é
uma óctupla N = (P, T, P re, P ost, w, x0 , Σ, l), em
que (P, T, P re, P ost, w, x0 ) é, de acordo com a definição 2, uma rede de Petri, Σ é o conjunto de
eventos utilizados para rotulação das transições e
l : T → 2Σ é a função de rotulação que associa a
cada transição um subconjunto de eventos do conjunto Σ.
Uma transição tj é dita estar habilitada
quando o número de fichas em cada um dos seus
lugares de entrada é maior ou igual ao peso dos
arcos que conectam os lugares à transição tj , i.e.,
tj é dita estar habilitada se e somente se
x(pi ) ≥ w(pi , tj ), for all pi ∈ I(tj ),
(3)
sendo I(tj ) o conjunto de lugares de entrada de
tj . Se a transição tj está habilitada para uma
marcação x e o evento associado a tj ocorre, então
a transição tj dispara e uma nova marcação x̄ é
alcançada. A evolução das marcações é dada por:
x̄(pi ) = x(pi ) − w(pi , tj ) + w(tj , pi ), i = 1, . . . , n.
(4)
Uma classe particular de redes de Petri é a
chamada rede de Petri máquina de estados. Em
uma rede de Petri máquina de estados cada transição possui exatamente um lugar de entrada e um
lugar de saı́da. Se, aliado a isso, essa rede de Petri possuir apenas uma ficha, então a rede de Petri
máquina de estados se comporta exatamente como
um autômato, em que cada lugar é associado a um
estado em seu autômato correspondente.
3
Σ⋆o . Então L é dita ser diagnosticável com relação
à projeção Po e com relação à partição Πf em Σf
se
(∀k ∈ Πf )(∃nk ∈ N)(∀s ∈ L \ LNk )(∀st ∈ L \ LNk )
(∥t∥ ≥ nk ) ⇒ (∀ω ∈ Po−1 (Po (st)) ∩ L, ω ∈ L \ LNk ),
em que ∥.∥ denota o comprimento de uma sequência.
De acordo com a definição 4, L é diagnosticável com relação a Po e Πf se e somente se para
todas as sequências st de comprimento arbitrariamente longo após a ocorrência de um evento de
falha do conjunto Σfk , não existirem sequências
sNk ∈ LNk , de tal forma que Po (sNk ) = Po (st)
para todo k ∈ Ir = {1, 2, . . . , r}. Portanto, se L é
diagnosticável então sempre é possı́vel identificar
unicamente o tipo de falha que ocorreu após um
número finito de observações de eventos.
O primeiro passo para implementar um diagnosticador online é verificar se todos os tipos de falha podem ser diagnosticados após a ocorrência da
falha em um número limitado de observações. Em
Moreira et al. (2011) um algoritmo em tempo polinomial para identificar se uma linguagem L é diagnosticável é apresentado. O algoritmo proposto
em Moreira et al. (2011) é baseado na construção de um autômato verificador determinı́stico e a
verificação tem complexidade computacional inferior comparada com outros métodos na literatura
(Qiu and Kumar, 2006; Yoo and Lafortune, 2002).
Neste artigo é suposto que a linguagem gerada
pelo sistema é diagnosticável com relação a Po e
Πf .
DIAGNOSTICABILIDADE DE SED
4
Seja G o autômato que modela o sistema e seja
Σf ⊆ Σuo o conjunto de eventos de falha. Além
disso, suponha que o conjunto de eventos de falha
possa ser particionado como
Σf =
r
∪
Σfk ,
(5)
k=1
em que Σfk representa um conjunto de eventos de
falha do mesmo tipo e Πf denota essa partição.
Seja L(G) = L a linguagem gerada por G e
GNk o subautômato de G que representa o comportamento normal do sistema com relação ao
conjunto de eventos de falha Σfk , i.e., supondo
que L(GNk ) = LNk , então LNk é a linguagem
prefixo-fechada formada por todas as sequências
de L que não contém nenhum evento de falha
do conjunto Σfk . A seguinte definição de diagnosticabilidade pode ser formulada (Sampath
et al., 1995).
Definição 4 Sejam L e LNk ⊂ L as linguagens
prefixo-fechadas geradas por G e GNk , respectivamente, e defina a operação de projeção Po : Σ⋆ →
ISBN: 978-85-8001-069-5
OBTENÇÃO DO AUTÔMATO GC
Nesta seção, é mostrado como obter o autômato
GC utilizado no processo de diagnose online. Diferente do autômato diagnosticador introduzido em
Qiu and Kumar (2006), que usa o comportamento
normal e de falha do sistema descrito por Gℓk , o
autômato GC é construı́do a partir dos autômatos GNk , que modelam o comportamento normal
de G com relação aos eventos de falha de Σfk , e
que, em geral, tem um número menor de estados
e transições do que Gℓk .
Algoritmo 1
• Passo 1: Calcule o autômato GNk , para cada
k ∈ Πf , que modela o comportamento normal
de G com relação ao conjunto de eventos de
falha Σfk , da seguinte forma:
– Passo 1.1: Defina ΣNk = Σ \ Σfk .
– Passo 1.2: Construa o autômato ANk
composto de um único estado Nk (também seu estado inicial) com um autolaço
rotulado com todos os eventos de ΣNk .
3725
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
– Passo 1.3: Faça GNk = G × ANk =
(QNk , Σ, fNk , ΓNk , q0,Nk ).
• Passo 2: Construa o autômato estendido
GaNk , para cada k ∈ Πf , adicionando um
novo estado Fk , que indica que um evento
de falha do conjunto Σfk ocorreu. Uma nova
transição rotulada com um evento σfk ∈ Σfk
é adicionada, conectando o estado (q, Nk ) de
GNk ao estado de falha Fk , se σfk ∈ Γ(q).
Adicione um autolaço rotulado com todos os
eventos σ ∈ Σ ao estado de falha Fk .
• Passo 3:
Calcule o autômato GC =
(QC , Σ, fC , ΓC , q0,C ) = GaN1 ∥GaN2 ∥ . . . ∥GaNr .
Note que, para cada GaNk , o comportamento
de falha do sistema com relação ao conjunto de
eventos de falha Σfk é representado pelo estado de
falha Fk , com um autolaço rotulado com todos os
eventos do conjunto Σ, o que indica que uma falha
do conjunto Σfk ocorreu. É importante mencionar
que essa representação não preserva a linguagem
gerada pelo sistema após a ocorrência do evento
de falha. Entretanto, como o diagnosticador é um
dispositivo passivo, essa representação não altera
a observação dos eventos do sistema e, portanto,
não interfere na diagnose de falhas.
Para mostrar como o autômato GC pode ser
usado na diagnose online de falhas é preciso primeiro definir uma função que fornece os possı́veis
estados atuais de GC após a ocorrência de um
evento observável. Essa estimativa é denotada
neste artigo por Reach(ν), em que ν = vσo =
Po (s) é a sequência observada pelo diagnosticador
após a execução de uma sequência s ∈ L cujo último evento observável é σo , e pode ser calculada
recursivamente como (Qiu and Kumar, 2006)
Reach(ε)
=
Reach(vσo )
=
U R(q0,C ),
(6)
U R(δ(Reach(v), σo )), (7)
∪κ
em que δ(Reach(v), σo ) =
i=1 δC (qCi , σo ),
com qCi ∈ Reach(v), κ = |Reach(v)|, e
δC (qCi , σo ) = fC (qCi , σo ) se fC (qCi , σo ) é definida
e δC (qCi , σo ) = ∅, caso contrário.
Após a observação de uma sequência ν, o
conjunto dos possı́veis estados atuais de GC ,
Reach(ν), pode ser calculado e seus estados podem ser usados para identificar a ocorrência de
um evento de falha. O teorema a seguir apresenta
a base para o método de diagnose proposto neste
artigo.
Teorema 1 Seja L a linguagem gerada por G e
suponha que L é diagnosticável com relação a Po
e Πf . Seja s ∈ L \ LNk tal que ∀ω ∈ L, com
Po (ω) = Po (s), ω ∈ L \ LNk . Então, a k-ésima
coordenada de todos os possı́veis estados atuais de
GC , alcançados após a ocorrência de s, dados por
Reach(Po (s)), é igual a Fk .
ISBN: 978-85-8001-069-5
0
a
σu
1
b
2
σf
σf
1
5
σu
3
4
c
2
σf
7
1
σu
a
6
a
8
a
9
b
Figura 1: Autômato G do Exemplo 1.
Nk
Σ\{σfk }
Figura 2: Autômato ANk do Exemplo 1.
Prova: A prova do teorema 1 segue diretamente
da construção do autômato GC e será, portanto,
omitida.
2
De acordo com o teorema 1, se L é diagnosticável com relação a Po e Πf , então sempre é possı́vel identificar a ocorrência de uma falha do tipo
Fk com um número limitado de observações verificando os possı́veis estados atuais de GC . Se após
a ocorrência de uma sequência s, todos os estados de Reach(ν), em que ν = Po (s), não possuem
uma coordenada (q, Nk ), então não é possı́vel que
uma sequência normal com relação ao conjunto de
eventos de falha Σfk , com a mesma projeção que
ν, tenha sido executada, o que implica que uma
falha do tipo Fk ocorreu, ou seja, s contém um
evento de falha σfk ∈ Σfk . Logo, a diagnose de
uma falha do tipo Fk pode ser feita verificando-se
se um estado do comportamento normal descrito
por GNk é uma coordenada de um possı́vel estado
atual de GC .
Observação 1 O número de estados de GC é, no
pior caso, igual a [(2r − 1) × |Q|] + 1, em que r é
o número de tipos de falha do sistema. Logo, a
complexidade computacional da construção de um
autômato GC é O(2r ×|Q|×|Σ|), o que mostra que
a complexidade é linear com o número de estados
e eventos do autômato do sistema e exponencial
com o número de tipos de falhas. A complexidade computacional pode ser linear com relação
ao número de tipos de falha se cada comportamento normal com relação a um tipo de falha é
considerado separadamente. Nesse caso, ao invés
de um único autômato GC , tem-se r autômatos
GaNk , em que cada um leva em consideração apenas a falha do tipo Fk , e a complexidade computacional é O(r×|Q|×|Σ|). Embora a análise de pior
caso sugira que é vantajoso considerar os autômatos GaNk , para k = 1, . . . , r, ao invés de GC , é importante observar que o número de estados de GC
pode ser menor que a soma do número de estados
de GaNk para k = 1, . . . , r, levando a um código
de programação menor para a implementação do
diagnosticador.
3726
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
Σ
0N1 ,0N2
F1
σf
σf
1
ON1
a
1N1
b
2N1
σu
3N1
4N1
F1 ,6N2
c
a
σf
F1 ,8N2
F1 ,9N2
7N1
σu
0N2
1N2
σf
b
2N2
σu
3N2
4N2
c
σf
1
2
5N2
Σ
F2
σf
1
a
6N2
a
8N2
a
9N2
b
Figura 4: Autômato aumentado GaN2 do Exemplo
1.
Exemplo 1 Seja G o autômato do sistema apresentado na figura 1, em que
Σ = {a, b, c, σu , σf1 , σf2 }, Σo = {a, b, c},
Σuo = {σu , σf1 , σf2 }, e Σf = {σf1 , σf2 }. Suponha
que o conjunto de eventos de falha possa ser
˙ f2 com Σf1 = {σf1 }
particionado em Σf = Σf1 ∪Σ
e Σf2 = {σf2 }, e suponha que se queira calcular
o autômato GC . De acordo com o algoritmo
1, o primeiro passo é obter os autômatos ANk ,
para k = 1, 2, mostrados na figura 2, e os
autômatos que modelam os comportamentos
normais GNk = G × ANk . O próximo passo é
a construção dos autômatos aumentados GaN1 e
GaN2 , mostrados nas figuras 3 e 4, respectivamente, obtidos adicionando-se os estados de falha
F1 e F2 aos autômatos GN1 e GN2 . O passo
final do algoritmo 1 é o cálculo do autômato
GC = GaN1 ∥GaN2 , ilustrado na figura 5.
A partir de agora será apresentado como o
autômato GC pode ser usado no processo de diagnose online. Suponha que uma sequência de falha s = aσf1 aa ∈ L \ LN1 tenha sido executada
pelo sistema. Então, a sequência observada é ν =
Po (s) = aaa. De acordo com o teorema 1, se não
existir uma sequência ω ∈ LN1 tal que Po (ω) = ν
então todos os estados no conjunto de estados alcançáveis Reach(ν) possuem a primeira coordenada igual a F1 . O conjunto de estados alcançáveis Reach(ν) pode ser obtido recursivamente
de acordo com as equações (6) e (7), da seguinte
forma: Reach(ε) = {(0N1 , 0N2 )}, Reach(a) =
{(1N1 , 1N2 ), (2N1 , 2N2 ), (F1 , 5N2 ), (7N1 , F2 ),
ISBN: 978-85-8001-069-5
b
3N1 ,3N2
σu
4N1 ,4N2
c
a
9N1 ,F2
σf
1
b
b
9N1
Figura 3: Autômato aumentado GaN1 do Exemplo
1.
σu
2N1 ,2N2
σ f2
7N1 ,F2
σu
8N1 ,F2
b
a
8N1
σu
a
2
a
1N1 ,1N2
σf1
F1 ,5N2
a
1
σu
a
Figura 5: Autômato GC = GaN1 ∥GaN2 do Exemplo
1.
(8N1 , F2 )}, Reach(aa) = {(F1 , 6N2 ), (9N1 , F2 )},
e Reach(aaa) = {(F1 , 8N2 )}.
Uma vez que o estado alcançado após a observação de ν = aaa possui a primeira coordenada
igual a F1 , então é possı́vel garantir que o evento
de falha σf1 ocorreu.
Com relação à complexidade computacional
para construção de GC , pode ser visto que GC
possui 12 estados e GaN1 e GaN2 possuem 9 e 10
estados, respectivamente. Logo GC possui um número menor de estados do que a soma de estados
de GaN1 e GaN2 . Portando, como mostrado na observação 1, a diagnose online pode ser executada,
neste caso, com um custo computacional menor
usando GC ao invés de GaNk , para k = 1, 2.
Na Seção 5, uma rede de Petri é usada para
fornecer um diagnosticador online capaz de encontrar os estados alcançáveis de GC após a observação de uma sequência de eventos para a identificação da ocorrência de um evento de falha.
5
DIAGNOSTICADOR REDE DE
PETRI
Considere o problema de encontrar os possı́veis estados de GC após a observação de uma sequência
ν ∈ Σ⋆o . Para resolver esse problema um observador online que armazena os estados estimados
atuais de GC após a ocorrência de um evento observável precisa ser calculado. Esse observador
online de estados pode ser construı́do usando o
formalismo de redes de Petri, explorando a natureza distribuı́da do estado de uma rede de Petri,
levando a um observador de estados rede de Petri.
O primeiro passo para a construção de um
observador rede de Petri é a obtenção de uma
rede de Petri máquina de estados, NC , a partir
do autômato GC . Isso pode ser feito associandose um lugar pCi em NC a cada estado qCi de
GC e associando-se a cada arco direcionado em
GC , (qCi , σ, q̄Ci ), em que q̄Ci = fC (qCi , σ) e σ ∈
ΓC (qCi ), uma transição tCj , rotulada com σ, em
NC (Cassandras and Lafortune, 2008). Para ligar
lugares e transições em NC , dois arcos com peso
3727
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
igual a um precisam ser criados para cada transição: um arco (pCi , tCj ) e um arco (tCj , p̄Ci ), em
que p̄Ci é o lugar de NC associado ao estado q̄Ci . O
estado inicial de NC é definido atribuindo-se uma
ficha ao lugar de NC associado ao estado inicial
de GC e atribuindo-se zero aos outros lugares.
Após NC ter sido obtida, o próximo passo
para o cálculo do observador de estados rede de
Petri de GC é a criação de novos arcos, conectando cada transição rotulada com um evento observável a lugares especı́ficos que correspondem ao
alcance não observável de lugares. Para isso, seja
TCo o conjunto de todas as transições de NC rotuladas com eventos observáveis e defina a função
ReachT : TCo → 2PC , em que PC é o conjunto
finito de lugares de NC . O conjunto de lugares
ReachT (tCj ), em que tCj ∈ TCo , pode ser calculado de acordo com o seguinte algoritmo.
Algoritmo 2 Sejam O(t) e O(p) o conjunto de
todos os lugares de saı́da de t e o conjunto de todas
as transições de saı́da
de p, respectivamente.
Seja
∪
∪
também O(P ) = p∈P O(p) e O(T ) = t∈T O(t).
• Passo 1: Defina pout = O(tCj ), Pr′ = {pout }
e Pr = Pr′ .
• Passo 2: Forme o conjunto Tu′ com todas as
transições de O(Pr′ ) associadas a eventos não
observáveis. Se Tu′ = ∅, ReachT (tCj ) = Pr e
pare.
• Passo 3: Faça Pr′ = O(Tu′ ), Pr ← Pr ∪ Pr′ , e
retorne ao Passo 2.
Para implementar o alcance não observável
após o disparo de cada transição observável, um
arco com peso um, conectando cada transição
tCj ∈ TCo a cada lugar pCi ∈ ReachT (tCj ), precisa ser adicionado a NC , gerando uma nova rede
de Petri NC′ . Após isso, todas as transições rotuladas com eventos não observáveis de NC′ , e seus arcos relacionados, precisam ser removidos levando
a uma nova rede de Petri NCo , cujas transições
são todas rotuladas com eventos observáveis pertencentes a Σo .
Note que para a estimação dos estados de GC ,
apenas os lugares que são associados aos possı́veis
estados atuais de GC devem ter fichas e, após a
ocorrência de um novo evento observável, o número de fichas nos lugares que não são mais possı́veis deve ser igual a zero. Isso implica que o número de fichas em cada lugar do observador rede
de Petri precisa ser igual a um ou zero, mesmo
que o disparo de uma transição tCj ∈ TCo resulte,
de acordo com a equação (4), em uma marcação
com duas ou mais fichas. Portanto, lugares são
forçados a ter marcações binárias e a equação (4)
não é mais válida. Esse requisito pode ser satisfeito usando-se redes de Petri binárias (Alayan
and Newcomb, 1987). Uma rede de Petri binária pode ser definida como uma rede de Petri com
ISBN: 978-85-8001-069-5
uma regra de evolução diferente para a marcação
de lugares alcançados após o disparo de uma transição tj , dada por:
{
0, se x(pi )− w(pi , tj )+ w(tj , pi ) = 0
,
x̄(pi ) =
1, se x(pi )− w(pi , tj )+ w(tj , pi ) > 0
(8)
para i = 1, . . . , n.
É importante observar que definir NCo como
uma rede de Petri binária não é suficiente para
garantir que NCo possa ser usada como um observador de estados. Suponha, por exemplo, que pCi
é um lugar de NCo que possui uma ficha e não tem
uma transição de saı́da rotulada com um evento
observável σo ∈ Σo . Suponha ainda que pCi não
possui uma transição de entrada habilitada rotulada com σo . Então, se σo ocorrer, pCi permanece
com uma ficha. Considerando que um lugar pCi
com uma ficha representa um possı́vel estado atual
qCi de GC , pode-se verificar que, neste exemplo,
pCi não deveria ter permanecido com uma ficha, o
que mostra que o estado da rede de Petri binária
NCo não corresponde aos possı́veis estados atuais
de GC após a ocorrência de σo .
Para se obter o observador rede de Petri, NSO ,
é necessário adicionar um arco conectando cada
lugar pCi de NCo a uma nova transição, rotulada
com os eventos observáveis de Σo que não estão
no conjunto de eventos ativos do estado qCi de
GC associado a pCi . Essa modificação e o fato
do observador rede de Petri ser uma rede de Petri
binária garantem que se o lugar pCi não está associado com um possı́vel estado atual de GC após o
disparo de uma transição observável, então o número de fichas de pCi é igual a zero. Finalmente,
para definir o estado inicial de NSO , uma ficha é
atribuı́da a cada lugar associado a um estado de
U R(q0,C ) e o número de fichas dos demais lugares
é igual a zero.
Após NSO ter sido obtida, o diagnosticador rede de Petri NDiag pode ser calculado
adicionando-se a NSO transições tfk , para k =
1, . . . , r, com um lugar de entrada pNk e um lugar
de saı́da pFk . Cada transição tfk está associada
à verificação da ocorrência de um tipo de falha.
Arcos inibidores (Davi and Alla, 2005) de peso
igual a um são usados para conectar cada lugar
associado a um estado de GC que tem uma coordenada (q, Nk ) à transição tfk . Como o arco
inibidor de peso um habilita a transição apenas
quando o número de fichas do lugar de entrada
é igual a zero, então tfk será habilitada apenas
quando o comportamento normal do sistema com
relação à falha do tipo Fk não for possı́vel, o que
implica que uma falha do conjunto Σfk ocorreu.
Um arco inibidor é representado por um arco cuja
extremidade final possui um pequeno cı́rculo. A
transição tfk será rotulada com o evento sempre
ocorrente λ (Davi and Alla, 2005) para representar que tfk dispara imediatamente após ter sido
3728
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
habilitada, removendo-se a ficha do lugar pNk e
adicionando-se uma ficha ao lugar pFk , o que indica que uma falha do tipo Fk ocorreu.
O algoritmo 3 resume os passos necessários
para a obtenção do diagnosticador rede de Petri
NDiag a partir do autômato GC .
0N1 0N2
1N1 1N2
•
a
• Passo 4: Calcule NSO = (PC , TSO , P reSO ,
P ostSO , wSO , x0,SO , Σo , lSO ) da seguinte
forma:
1
σf
3N1 3N2
4N1 4N2
σu
b
c
2
7N1 F2
a
F1 6N2
σu
8N1 F2
a
F1 8N2
• Passo 1: Calcule a rede de Petri máquina de estados NC = (PC , TC , P reC ,
P ostC , wC , x0,C , Σ, lC ) a partir de GC .
• Passo 3:
Elimine todas as transições
de NC′ rotuladas com eventos não observáveis e seus arcos relacionados, gerando a rede de Petri binária NCo =
(PC , TCo , P reCo , P ostCo , wCo , x0,C , Σo , lCo ).
σu
σf
F1 5N2
Algoritmo 3
• Passo 2: Adicione a NC arcos conectando
cada transição observável tCj ∈ TCo aos
lugares em ReachT (tCj ), gerando a rede
′
,
de Petri NC′ = (PC , TC , P reC , P ost′C , wC
x0,C , Σ, lC ).
2N1 2N2
a
9N1 F2
a
b
σf
F1 9N2
1
b
Figura 6: Rede de Petri máquina de estados NC .
0N1 0N2
1N1 1N2
•
2N1 2N2
3N1 3N2
a
b
F1 5N2
7N1 F2
4N1 4N2
c
a
F1 6N2
8N1 F2
a
F1 8N2
a
9N1 F2
a
b
F1 9N2
– Passo 4.1: Adicione à NCo transições
rotuladas com eventos observáveis de Σo
que não estão no conjunto de eventos
ativos do estado qCi de GC associado a
pCi .
– Passo 4.2: Defina o estado inicial de
NSO atribuindo uma ficha a cada lugar
associado a um estado de U R(q0,C ) e nenhuma ficha aos outros lugares.
• Passo 5: Calcule o diagnosticador rede de
Petri NDiag = (PDiag , TSO ∪ Tf , P reDiag ,
P ostDiag , InDiag , wDiag , x0,Diag∪, Σo ∪ {λ},
r
lDiag ), em que Tf
=
k=1 {tfk } e
InDiag ⊆ PDiag × Tf denota o conjunto
de arcos inibidores, como segue:
– Passo 5.1: Adicione à NSO transições
tfk , para k = 1, . . . , r, rotuladas com o
evento sempre ocorrente λ.
– Passo 5.2: Adicione a cada transição tfk
um lugar de entrada pNk e um lugar de
saı́da pFk , ambos conectados à tfk por
arcos com peso igual a um.
– Passo 5.3: Conecte cada lugar associado
a um estado de GC que tem uma coordenada (q, Nk ) à transição tfk com um
arco inibidor.
– Passo 5.4: A marcação inicial dos lugares pNk é igual a um e dos lugares pFk
é igual a zero. Os outros lugares possuem a mesma condição inicial definida
por x0,SO .
ISBN: 978-85-8001-069-5
b
Figura 7: Rede de Petri binária NCo .
Observação 2 Considerando a construção de
um diagnosticador rede de Petri para um único
tipo de falha, é possı́vel ver que no pior caso o número de lugares da rede é igual a |Q| + 2 e o número de transições é (|Q| + 2) × (|Σo | + 1). Assim,
a complexidade computacional do diagnosticador
considerando um tipo de falha é O(|Q| × |Σo |).
Note que isso é uma grande vantagem com relação ao diagnosticador proposto por Sampath et al.
(1995) cuja complexidade é exponencial no número de estados do sistema.
O exemplo a seguir ilustra os passos para a
obtenção da rede de Petri NDiag e o processo de
diagnose online.
Exemplo 2 Considere o autômato diagnosticador GC mostrado na figura 5, e considere o problema de obter o diagnosticador rede de Petri
NDiag a partir de GC . De acordo com o algoritmo 3 o primeiro passo é o cálculo da rede de
Petri máquina de estados NC , mostrada na figura
6. Seguindo os Passos 2 e 3, a rede de Petri binária NCo , apresentada na figura 7, é obtida. Em
seguida, de acordo com o Passo 4, o observador
rede de Petri NSO , mostrado na figura 8, é obtido
a partir de NCo . Finalmente, seguindo o Passo
5 do algoritmo 3, o diagnosticador rede de Petri
NDiag , apresentado na figura 9, é calculado.
3729
Anais do XIX Congresso Brasileiro de Automática, CBA 2012.
a, c
0N1 0N2
2N1 2N2
1N1 1N2
•
b
a , b, c
a
c
a , b, c
7N1 F2
F1 5N2 a , b , c
b, c
onando uma ficha ao lugar pF1 , indicando a ocorrência do evento de falha σf1 .
a, b
3N1 3N2 4N1 4N2
6
a
F1 6N2
b, c
8N1 F2
b, c
a
a
F1 8N2
b, c
9N1 F2
a, c
a
b
F1 9N2
a, c
b
Figura 8: Observador rede de Petri NSO .
a, c
tSO2
a
•
tSO3
tSO4
a , b, c
tSO1
b
a, b
a , b, c
tSO5
AGRADECIMENTOS
tSO7
PN1
a , b, c
•
tSO16
b, c
a
tSO10
tSO9
tSO17
b, c
tf1
b, c
a
tSO12
tSO11
tSO19
a
Referências
tSO18
PN2
a, c
tSO14
tSO13
tSO20
•
b
Este trabalho foi parcialmente financiado pela Petrobras, convênio no. 6000.0069294.11.4, PFRH no.19, e
pela FAPERJ, processo 110.728/2011.
PF1
b, c
a
Neste artigo foi apresentado um diagnosticador
rede de Petri que pode ser usado para a detecção e isolamento de falhas online de sistemas a
eventos discretos. Esse procedimento de diagnose
online utiliza menos memória do que outros métodos propostos na literatura. Como um trabalho
futuro, visando a implementação do diagnosticador em controladores lógicos programáveis, é sugerido o desenvolvimento de um método de conversão de diagnosticadores redes de Petri em uma
linguagem de programação adequada.
tSO6
c
tSO8
CONCLUSÃO
Alayan, H. and Newcomb, R. W. (1987). Binary petrinet relationships, IEEE transactions on circuits
and systems CAS-34: 565–568.
a, c
b
tSO15
PF2
tf2
Figura 9: Diagnosticador rede de Petri NDiag .
Será mostrado agora como utilizar a rede
de Petri NDiag no processo de diagnose online.
Para tanto, suponha que uma sequência de falha s = aσf1 aa ∈ L \ LN1 tenha sido executada pelo sistema. Então, a sequência observada é
ν = Po (s) = aaa. Como o estado inicial de NDiag
possui uma ficha apenas no lugar (0N1 , 0N2 ), associado ao estado inicial de GC , então, após a
ocorrência do primeiro evento a, a transição tSO1
dispara e o conjunto de lugares associados com os
possı́veis estados de GC que possuem uma ficha
é dado por {(1N1 , 1N2 ), (2N1 , 2N2 ), (7N1 , F2 ),
(8N1 , F2 ), (F1 , 5N2 )}. Então, quando o segundo
evento a é observado, as transições tSO2 , tSO3 ,
tSO9 , tSO16 , tSO18 disparam simultaneamente e o
conjunto de lugares com uma ficha é dado por
{(F1 , 6N2 ), (9N1 , F2 )}. Note que as transições
tSO2 , tSO3 , tSO16 removem as fichas dos lugares que não estão associados aos possı́veis estados atuais de GC após a observação da sequência aa. Após a ocorrência do terceiro evento a,
as transições tSO11 , tSO19 disparam e o único lugar de NDiag que continua com uma ficha é dado
por (F1 , 8N2 ). Como todos os lugares associados
a um estado de GC com uma coordenada (q, N1 )
não possuem fichas, então a transição tf1 , rotulada com o evento sempre ocorrente, é habilitada
e dispara, removendo a ficha do lugar pN1 e adici-
ISBN: 978-85-8001-069-5
Basilio, J. C., Lima, S. T. S., Lafortune, S. and Moreira, M. V. (2012). Computation of minimal
event bases that ensure diagnosability, Discrete
Event Dynamic Systems: Theory And Applications . to appear.
Carvalho, L. K., Moreira, M. V. and Basilio, J. C.
(2011). Generalized robust diagnosability of discrete event systems, 18th IFAC World Congress,
Milano, Italy, pp. 8737–8742.
Cassandras, C. G. and Lafortune, S. (2008). Introduction to Discrete Event System, Springer-Verlag
New York, Inc., Secaucus, NJ.
Davi, R. and Alla, H. (2005). Discrete, Continuous
and Hybrid Petri Nets, Springer.
Lin, F. (1994). Diagnosability of discrete event systems and its applications, Journal of Discrete
Event Dynamic Systems 4(2): 197–212.
Moreira, M. V., Jesus, T. C. and Basilio, J. C. (2011).
Polynomial time verification of decentralized diagnosability of discrete event systems, IEEE
Transactions on Automatic Control pp. 1679–
1684.
Qiu, W. and Kumar, R. (2006). Decentralized failure
diagnosis of discrete event systems, IEEE Transactions on Systems, Man, and Cybernetics Part
A:Systems and Humans 36(2).
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K. and Teneketzis, D. (1995). Diagnosability of discrete-event systems, IEEE Trans. on
Automatic Control 40(9): 1555–1575.
Yoo, T.-S. and Lafortune, S. (2002). Polynomial-time
verification of diagnosability of partially observed discrete-event systems, IEEE Transactions
on Automatic Control 47(9).
3730