Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
FAILURE DIAGNOSIS OF TIME-WEIGHTED DISCRETE-EVENT SYSTEMS
Gustavo S. Viana∗, João Carlos Basilio∗, Marcos Vicente Moreira∗
∗
COPPE - Programa de Engenharia Elétrica, Universidade Federal do Rio de Janeiro (UFRJ)
Rio de Janeiro-RJ, Brasil
Emails: [email protected], [email protected], [email protected]
Abstract— Although the theory of failure diagnosis of discrete-event systems (DES) has been proved effective,
one question remains open: assuming that the generated language is diagnosable, how long does the diagnosis
system take to detect the failure occurrence? In this paper, although we still consider the DES as a dynamic
system whose evolution is determined by the asynchronous occurrence of events, we add to each transition
a weight that corresponds to the maximum time that takes for the event to occur since the moment it fires
(the so-called time-weighted model), to propose an effective algorithm to determining the maximum time for
failure diagnosis. This result was only possible because we present a new necessary and sufficient condition for
diagnosability verification that replaces the search for cycles with the search for strongly connected components
and by the use max-plus algebra to obtain a matrix representation for time-weighted automata.
Keywords—
Discrete-event systems, failure diagnosis, automata, max-plus algebra.
Resumo— Embora a teoria de diagnose de falhas de sistemas a eventos discretos (SED) esteja consolidade,
uma pergunta ainda não foi respondida: supondo que a linguagem gerada seja diagnosticável, quanto tempo o
sistema de diagnose leva para detectar a ocorrência da falha? Neste artigo, embora SEDs sejam ainda considerados
como sistemas dinâmicos cuja evolução se dá pela ocorrência, em geral assı́ncrona de eventos, será acrescentado
a cada transição um peso que corresponde ao tempo máximo que o evento leva para ocorrer, desde o instante
em que ele dispara (o chamado modelo ponderado no tempo), para propor um algoritmo eficaz para determinar
o tempo máximo para o diagnóstico da falha. Esse resultado somente foi possı́vel porque foi apresentada uma
nova condição necessária e suficiente para a diagnosticabilidade que substitui a busca por ciclos pela busca de
componentes fortemente conectadas e pelo uso da álgebra max-plus, que permite obter representações matriciais
para autômatos ponderados no tempo.
Palavras-chave—
1
Sistemas a eventos discretos, diagnose de falhas, autômatos, álgebra max-plus.
Introduction
the failure occurrence in a finite number of events
occurrences. Another aspect that is not analysed
and is equally important is that, given that a language is diagnosable, how long it takes the diagnoser to reach a certain failure state; or better still,
what is the maximum time required for the system
to make sure that the failure has occurred? In a
real system, a failure can impair an entire production line. But just to make sure that the failure
has occurred is not enough; for example, components may burn or parts may misalign before the
failure occurrence is detected. So, it is important
to analyse the detection time as a parameter to
characterize the diagnosability; possibly based on
this parameter, you can set a safety measures. In
this paper, we will present a method for calculating the maximum time for diagnosis. However,
simply model of SED as a finite state automaton
does not possess this information. Such information can be obtained by using time-weighted systems (Su et al., 2012), which together with maxplus algebra (Heidergott et al., 2006) provide the
necessary tools for the calculation of the maximum
time for diagnosis.
One approach to fault diagnosis is by constructing a discrete-event model of the system whose
fault occurrence must be diagnosed (Sampath
et al., 1995). In practice, this is usually carried
out by means of a deterministic automaton called
diagnoser, whose states are sets formed with the
states of the system plant automaton together
with labels that indicate if the trace occurred
so far possesses or not the fault event, and the
decision on the failure occurrence (diagnosis) is
taken based on observed events only, i.e., those
events whose occurrence can be recorded by sensors. Diagnosers are also used offline for diagnosability verification, whose verification process requires the search for cycles formed with certain
type of states (Sampath et al., 1995; Carvalho
et al., 2012). It is well known that the search for
cycles has computational complexity that is worse
than exponential (Cormen et al., 2007). With the
view to overcoming this problem, this paper proposes a new test automaton to verify the language
diagnosability and present new necessary and sufficient conditions for language diagnosability that
require the search for strongly connected component, which is polynomial time.
In the design of a failure diagnosis systems
for DES, the first step is to check whether the
language generated by an automaton is diagnosable, i.e., whether the system is able to diagnose
This paper is structured as follows. In Section 2, we present the necessary background on
DES, failure diagnosis of DES, max-plus algebra,
time-weighted systems and max-plus representation of time-weighted automata. In Section 3, we
present a new necessary and sufficient condition
3519
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
automaton G with unobservable events can
be described by a deterministic automaton
called observer, here denoted as Obs(G) =
(Xobs , Σo , fobs , Γobs , x0obs , Xmobs ). The states of
Xobs indicate where automaton G can be after the
recording of the observable events, and for this
reason Xobs ∈ 2X (2X denotes the power set of
X). An algorithm for computing all the states and
transitions of Obs(G) can be seen in (Cassandras
and Lafortune, 2008, p. 89).
for diagnosability of discrete-event systems and
a test based on the search of strongly connected
components. In Section 4 we present an algorithm
for computing the maximum time the diagnosis
system takes to detect the failure occurrence; assuming, of course, language diagnosability. An
example is presented in Section 5 to illustrate the
results of the paper. Finally, conclusions and outline of future works are presented in Section 6.
2
Background
2.1
Let G = (X, Σ, f, Γ, x0 , Xm ) denote a deterministic automaton, where X is the finite state space,
Σ is the set of events, f is the transition function,
assumed here to be partially defined in the event
set, Γ is the active event set, i. e., Γ(x) = {σ ∈ Σ :
(∃y ∈ X)[f (x, σ) = y]}, x0 is the initial state, and
Xm is the set of marked states. We will assume
˙ uo ,
that the event set is partitioned as Σ = Σo ∪Σ
where Σo (resp. Σuo ) denotes the set of observable (resp. unobservable) events. The languages
generated and marked by G will be denoted as
= L(G) = L and Lm (G) = Lm , respectively.
Given a trace s ∈ L, we define the post-language
of L after s as L/s = {t ∈ Σ∗ : st ∈ L}. The assumption usually made in the literature (Sampath
et al., 1995; Debouk et al., 2000) that G does not
possess and cyclic path formed with unobservable
events only are not required here. As a consequence, we can assume that the language generated by G is always live, since any non-live language can be made live by adding a self-loop at
the states x, for which Γ(x) = ∅, labeled by unobservable events.
The natural projection (Ramadge and Wonham, 1989) Po : Σ∗ → Σ∗o is defined in the usual
way as Po (σ) = σ, if σ ∈ Σo , and , if σ ∈ Σuo , and
Po (sσ) = Po (s)Po (σ) for s ∈ Σ∗ and σ ∈ Σ. Its extension to a language L is carried out in a straightforward way by applying Po to all traces of L, i.e.,
Po (L) = {t ∈ Σ∗o : (∃s ∈ L)[Po (s) = t]}. The in∗
verse projection is the mapping Po−1 : Σ∗ → 2Σ ,
where, for any s ∈ Σ∗o , Po−1 (s) = {t ∈ Σ∗ : Po (t) =
s}.
Let G1 = (X1 , Σ1 , f1 , Γ1 , x01 , Xm1 ) and
G2 = (X2 , Σ2 , f2 , Γ2 , x02 , Xm2 ) denote two
automata whose generated languages are L1
and L2 , respectively. The parallel composition
between G1 and G2 is defined as (Cassandras and
Lafortune, 2008): G1 kG2 = Ac(X1 × X2 , Σ1 ∪
Σ2 , f1k2 , Γ1k2 , (x01 , x02 ), Xm1 × Xm2 ,
where
f1k2 [(x1 , x2 ), σ] = (f1 (x1 , σ), f2 (x2 , σ)), if σ ∈
Γ1 (x1 ) ∩ Γ2 (x2 ), f1k2 [(x1 , x2 ), σ] = (f1 (x1 , σ), x2 ),
if σ ∈ Γ1 (x1 ) \ Σ2 , f1k2 [(x1 , x2 ), σ] =
(x1 , f2 (x2 , σ)), if σ ∈ Γ2 (x2 ) \ Σ1 , and undefined otherwise. If we define Σ = Σ1 ∪ Σ2 ,
Po1 : Σ∗ → Σ1 and Po2 : Σ∗ → Σ2 , then, it is not
(L1 ) ∩ Po−1
(L2 ).
difficult to prove that L1k2 = Po−1
1
2
The dynamic behavior of a deterministic
Failure diagnosis of DES
Let Σf = {σf } ⊆ Σuo denote the set of failure
events of G and assume that the occurrence of σf
must be diagnosed, i.e, we must somehow be sure,
after a finite number of steps of the occurrence of
σf that it has actually occurred. This language
property is called diagnosability.
Let us assume that Ψ(Σf denote the set of all
traces of L that ends with the failure event σf .
With a slight abuse of notation, we use Σf ∈ s
to denote that s ∩ Ψ(Σf ) 6= ∅. Therefore, s ∈ L
is a trace that has the failure event σf if Σf ∈ s.
Language diagnosability can be formally defined
as follows (Sampath et al., 1995).
Definição 1 A live and prefix-closed language L
is diagnosable with respect to Po : Σ∗ → Σ∗o and
Σf if
(∃n ∈ N)(∀s ∈ Ψ(Σf ))(∀t ∈ L/s, |t| ≥ n) ⇒ D,
where the diagnosability condition D is expressed
as follows:
(∀ω ∈ Po−1 [Po (st)] ∩ L)(Σf ∈ ω).
One way to verify diagnosability is by means
of an automaton called diagnoser (Sampath et al.,
1995; Carvalho et al., 2012) given by
Gd = (Xd , Σo , fd , Γd , x0d ) = Obs(GkA` ),
where A` = (X` , Σ` , f` , Γ` , x0` ) is the so-called label automaton, with X` = {N, Y }, x0` = N , and
f` (N, σf ) = f` (Y, σf ) = Y . It is not difficult to
see that L(Gd ) = Po (GkA` ) = Po (L).
The states of Gd not only provide information
on the possible states of G after the occurrence of
the observed trace (formed only with observable
events) but also provide information on the occurrence or not of the failure event. In this regard,
a state xd ∈ Xd is called certain (or faulty), if
` = Y for all (x, `) ∈ xd , and normal (or nonfaulty) if ` = N for all (x, `) ∈ xd . If there exist
˜ ∈ xd , x not necessarily distinct from
(x, `), (y, `)
y such that ` = Y and `˜ = N , then xd is an uncertain state of Gd . When the diagnoser is in a
certain (normal) state, it is certain that a fault
has (resp. has not) occurred. However, if the diagnoser is in an uncertain state, it is not sure if
3520
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
the fault event has occurred or not. As a consequence, if there exists a cycle formed with uncertain states, only, where the diagnoser can remain
forever, then it will never be able to diagnose the
fault occurrence; on the other hand if somehow it
always leaves this cycle of uncertain states, then
this cycle is not indeterminate. Therefore, it is important to distinguish between cycles of uncertain
states that are indeterminate (in the sense that
the diagnoser is not able to determine if the fault
has occurred) and those cycles of uncertain states
that are not indeterminate.
when it reaches the corresponding normal, faulty
and uncertain states, in spite of the plant evolution. We say, in this case, that there exists hidden
cycles in the above states.
Definição 3 (Hidden
cycles
determinate hidden cycles of
xd = {x1 `1 , x2 `2 , . . . , xn `n } be
Gd . There exists a hidden cycle
some {i1 , i2 , . . . , ik } ⊆ {1, 2, . . . , n},
conditions hold true:
and
inGd ) Let
a state of
in xd if for
the following
HC.1) xi1 , xi2 , . . . , xik form a cycle in G;
Definição 2 (Sampath et al., 1995) (Indeterminate observed cycles of Gd ) A set of uncertain
states {xd1 , xd2 , . . . , xdp } ⊂ Xd forms an indeterminate observed cycle if the following conditions
hold true:
HC.2) {σi1 , σi2 , . . . , σik }
⊆
Σuo , where
σi1 , σi2 , . . . , σik are such that f (xij , σij ) =
xij+1 , j
=
1, 2, . . . , k − 1, and
f (xik , σik ) = xi1 .
If xd is an uncertain state of Gd and besides conditions HC.1) and HC.2), the following condition
is also satisfied,
IOC.1) xd1 , xd2 , . . . , xdp form a cycle in Gd ;
IOC.2) ∃(xkl l , Y ), (x̃rl l , N ) ∈ xdl , xkl l not necessarily distinct from x̃rl l , l = 1, 2, . . . , p,
kl = 1, 2, . . . , ml , and rl = 1, 2, . . . , m̃l in
such a way that the sequence of states {xkl l },
l = 1, 2, . . . , p, kl = 1, 2, . . . , ml and {x̃rl l },
l = 1, 2, . . . , p, rl = 1, 2, . . . , m̃l form cycles
in G;
HC.3) `ij = Y , j = 1, 2, . . . , k,
then xd has an indeterminate hidden cycle.
In accordance with Definition 3, there exist
Y
hidden cycles in states xN
d and xd of Gd and an
YN
indeterminate hidden cycle in xd . Notice that
in the verification of language diagnosability, state
xYd (xN
d ) ensures that the fault has (resp. has not)
occurred, and so, the existence of hidden cycles in
normal or certain states of Gd does not affect the
language diagnosability. On the other hand, the
existence of indeterminate hidden cycles implies
that the language is not diagnosable since there
exist two traces, a faulty one, s, and a normal
one, s00 , such that Po (s) = Po (s00 ).
The necessary and sufficient condition for diagnosability proposed in (Sampath et al., 1995)
has been extended in (Carvalho et al., 2012) to
take into account hidden cycles as follows.
IOC.3) there exist s = s1 s2 . . . sp ∈ Σ∗ and
s̃ = s̃1 s̃2 . . . s̃p ∈ Σ∗ such that Po : Σ∗ →
Σ∗o (s) = Po : Σ∗ → Σ∗o (s̃) 6= , where
sl = σl,1 σl,2 . . . σl,ml −1 , f (xjl , σl,j ) = xj+1
,
l
1
l
j = 1, 2, . . . , ml − 1, f (xm
l , σl+1,0 ) = xl+1 ,
m
and f (xp p , σ1,0 ) = x11 , and similarly for s˜l .
Assume now that there exists a set of states
{xi1 , xi2 , . . . , xik } ⊂ X that form a cycle of states
connected with unobservable events. Consider a
trace s = so (σi1 , σi2 , . . . , σik )n ∈ L (n ∈ N), where
(σi1 , σi2 , . . . , σik )n ∈ Σ∗uo and assume, without
loss of generality, that the last event of so is observable. Let us suppose, initially, that σf ∈
/ s and
that there is no faulty trace1 s0 such that Po (s) =
Po (s0 ). In this case there will exist in Gd a state
N
xN
d such that {xi1 N, xi2 N, . . . , xik N } ⊆ xd . On
the other hand, if Σf ∈ so and f` (x0,` , so ) = xY` ,
where f` is the transition function of G` = GkA` ,
x0,` and xY` are, respectively, the initial and a
certain state of G` , and if there is no normal
trace s00 such that Po (s) = Po (s00 ). Therefore,
there will exist a certain state xYd of Gd such that
(xY` ∪ {xi1 Y, xi2 Y, . . . , xik Y }) ⊆ xYd . It is still possible that a normal trace s00 (bounded length or
N
not) such that f` (x0,` , so ) = xN
` , where x` is a
00
normal state of G` , and Po (s) = Po (s ), exists. In
this case, there will exist an uncertain state xYd N
in Gd such that (xY` ∪ {xi1 Y, xi2 Y, . . . , xik Y } ∪
YN
xN
` ) ⊆ xd . In all the above cases, Gd halts
Theorem 1 (Sampath et al., 1995; Carvalho
et al., 2012) The language L generated by automaton G is diagnosable with respect to projection Po : Σ∗ → Σ∗o and Σf = {σf } if, and only if,
its diagnoser Gd has no indeterminate (observed
or hidden) cycles.
2.2
Max-plus algebra
Let us define ε := −∞, e := 0 and Rmax = R∪{ε},
where R denotes the set of real numbers. For two
elements a, b ∈ Rmax , the ⊕ e ⊗ operations are
defined as follows:
a ⊕ b := max(a, b) and a ⊗ b := a + b.
(1)
It is not difficult to see that a ⊕ ε = ε ⊕ a = a and
a⊗ε = ε⊗a = ε. The four-tuple (Rmax , ⊕, ⊗, ε, e)
1 A trace s is said to be faulty (normal) if Σ ∈ s (resp.
f
Σf ∈
/ s).
3521
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
is called max-plus algebra2 . As in the conventional algebra, ⊗ operation has priority over ⊕
and distributes over ⊕. Powers are defined in maxplus algebra in the usual way as follows:
x⊗n := x ⊗ x ⊗ x . . . ⊗ x = n × x.
{z
}
|
A finite-weighted automaton is a two-tuple
(G, w), where G = (X, Σ, f, Γ, x0 , Xm ) and w :
X × Σ → R+ is the weighting function, which assigns a positive weight to each transition of G and
is defined over a pair (x, σ) ∈ X × Σ if and only if
the transition f (x, σ) is defined. The weights denote the duration required for the corresponding
transition to be completed. A time-weighted automaton is a three-tuple G = ((G, w), h) where
(G, w) is a finite-weighted automaton and h ⊆
Σ × Σ is a reflexive and symmetric binary relation called intrinsic mutual exclusion relation. A
pair (σ, σ 0 ) ∈ h if the firings of σ and σ 0 are mutually exclusive, i.e., if one event is under execution,
the other event will not be initiated; otherwise,
(σ, σ 0 ) ∈
/ h. The term “intrinsic´´ means that
the mutual exclusion relation imposed by h is a
property of the system. In each automaton G,
the order of events in a string s ∈ L(G) denotes
the order of the corresponding starting moments
of event firings, and it is possible that the starting moments of two consecutive firings in are s
identical. For example, suppose s = ab ∈ L(G)
and let ta , tb ∈ R+ ∪ {0} be their corresponding starting moments of events a and b. Thus,
ta ≤ tb . However, if (a, b) ∈ h, then necessarily,
tb ≥ ta + w(x0 , a). As in the definition of ordinary finite-state automata, if an event σ is shared
by several component automata, then the starting
moments of the firings of σ in different automata
must be synchronized.
The global behavior of a time-weighted system can be obtained by composing appropriately
the individual weighted automata. This is carried out by extending the usual parallel composition rule. Given two finite-state weighted automata ((Gi = Xi , Σi , fi , xi,0 , Xi,m ), wi )(i = 1, 2),
the parallel composition of (G1 , w1 ) and (G2 , w2 ),
denoted as (G1 , w1 )||(G2 , w2 ), is a weighted automaton ((G = X, Σ, f, x0 , Xm ), w), where X =
X1 × X2 , Σ := Σ1 ∪ Σ2 , x0 := (x1,0 , x2,0 ),Xm =
X1,m ×X2,m , e w : X1 ×X2 ×(Σ1 ∪Σ2 ) → X1 ×X2
is defined as follows: (i) f ((x1 , x2 ), σ) is defined
according to the parallel composition rules presented at the beginning of this section; (ii) w :
X1 × X2 × (Σ1 ∪ Σ2 ) → R+ is defined as follow:

w(x1 , σ), if σ ∈ Γ1 \ Σ2 ,




 w(x2 , σ), if σ ∈ Γ2 \ Σ1 ,
w(x1 , σ) ⊕ w(x2 , σ),
w((x1 , x2 ), σ) =


if σ ∈ Γ1 ∩ Γ2 ,



undefined, otherwise.
(2)
n times
The set of m×n max-plus matrices is denoted
as Rm×n
max . The element aij of a matrix A ∈ Rmax
is sometimes denoted as [A]ij . The sum of two
matrices A, B ∈ Rm×n
max is denoted as [A ⊕ B]ij =
aij ⊕ bij = max(aij , bij ). Clearly, A ⊕ B = B ⊕ A.
In addition, for α ∈ Rmax , then [α⊗A]ij = α⊗aij .
l×n
For two matrices C ∈ Rm×l
max and B ∈ Rmax the
product matrix A ⊗ B is defined as follows:
[A ⊗ B]ik =
l
M
aij ⊗ bjk
j=1
= max{aij + bjk }, i ∈ m, k ∈ n, (3)
j∈l
where m = {1, 2, . . . , m} and n = {1, 2, . . . , n}.
This definition is similar to that of the conventional algebra, and is obtained by replacing +
with max and × with +. The m × n matrices
ε(m, n) and E(n, m) whose elements as defined as
[E(m, n)]ij = e, if i = j and ε, satisfy the following relationships: A ⊕ ε(n, m) = A = ε(m, n) ⊕ A
and A ⊗ E(n, n) = A = E(m, m) ⊗ A. In addition, for k ≥ 1, we have that A ⊗ ε(n, k) = ε(m, k)
and ε(k, m) ⊗ A = ε(k, n). For Rm×n
max , the matrix
addition ⊕ is associative, commutative, and has
zero element ε(m, n) and the matrix product ⊗
is associative, distributive with respect to ⊕, possesses the unit element E(n, n), and is absorbing
for ε(n, n). As in the conventional algebra, ⊗ is
not, in general, commutative. As in the addition
and multiplication of scalars, the matrix product
⊗ has priority over ⊕. For a matrix A ∈ Rn×n
max , a
k-th power of A is defined as:
A⊗k := A ⊗ A ⊗ ... ⊗ A .
|
{z
}
(4)
k times
By definition, A⊗0 := E(n, n). It is worth remarking that [A⊗k ]ij should be distinguished from
[a⊗k
ij ]; the former corresponds to element (i, j) of
the k-th power of A and the latter is the k-th
power of element (i, j) of A.
2.3
Time-weighted systems
In this section, we will review the main concepts
of time-weighted systems. For a more complete
treatment, the reader is refer to the seminal paper
by Su et al. (Su et al., 2012).
2.4
Max-plus matrix representation of timeweighted automata
Let G denote a time-weighted automaton with n
states and assume that the states of G have been
renamed in a such way that X = {1, 2, . . . , n}.
The max-plus matrix that represents G is a square
matrix A(n, n) whose i, j-th element is defined as
2 We will present here only the results relevant to our
work. The interested reader is referred to (Heidergott
et al., 2006) for a more complete treatment on max-plus
algebra.
3522
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
follows:
 L

σk ∈Γ(j) w(j, σk ),
[A(n, n)]ij =
if f (j, i) is defined,

ε, otherwise.
3 A new necessary and sufficient
condition for diagnosability of discrete
event system
(5)
The necessary and sufficient condition given in
Theorem 1 requires the search for indeterminate
(observed or hidden) cycles in Gd which is, in
the worst case, worse than exponential (Cormen
et al., 2007). In this section, we will present a
different approach to the verification of language
diagnosability that leads to a new necessary and
sufficient condition. The idea behind the proposed
approach is motivated by the following reasons:
(i) Gd does not carry enough information to determine if an observed cycle of uncertain states is
an indeterminate cycle; (ii) in order to determine
the nature of a hidden cycle in G, it is necessary
to search for cycles of states connected with unobservable events in G.
Let us define Gscc = Gd ||G` , where G` =
G||A` , and, according to Section 2, Gd = Obs(G` ).
We may state the following result.
As an illustration, consider the time-weighted automaton G be depicted in Figure 1, where the label
“a/2” over the transition f (1, a) = 2 means that
w(1, a) = 2 , and the remaining labels are interpreted similarly. Using Equation (5), we obtain
a/2
1
b/1, c/3
2
3
d/1
a/2
4
Figure 1: A time-weighted automaton G.
the following max-plus matrix A that corresponds
to G:


ε ε ε ε
 2 ε ε ε 

A=
 ε 3 ε ε 
ε 1 2 ε
Lemma 3 L(Gscc ) = L(G` ) = L(G).
Proof. The proof is straightforward and comes
from the fact that L(Gd ) = Po (L) and L(G` ) = L.
Notice that, since automaton Gscc is obtained by
performing a parallel composition between Gd and
G` , its states are of the type (xd , x` ). Moreover,
there exists the following inclusion relationship between x` and xd .
Notice that element a32 = 3, because we must
choose the maximum weight among all transitions
from state 2 to state 3.
Lemma 2 (Heidergott et al., 2006) Let A ∈
Rn×n
max be the matrix associated with an automaton G = ((X, Σ, f, Γ, x0 , Xm ), w), where X =
{1, 2, . . . , n}. Define the following matrix:
+
A :=
∞
M
⊗k
A
⊗2
=A⊕A
⊗3
⊕A
⊕ ···
Lemma 4 All states (xd , x` ) of Gscc satisfies the
following condition: x` ⊆ xd .
Proof. The proof is straightforward and is based
on the fact that Gd = Obs(G` ) which implies
that Gscc = Obs(G` )kG` . Since the observer construction is performed by calculating unobservable
reaches, it is immediate to see that x` ⊆ xd .
We will now present a necessary and sufficient
condition for language diagnosability that replace
the search for cycles with the search for strongly
connected components, that has linear complexity
(Tarjan, 1972). For completeness, we will present
first the definition of strongly connected components.
(6)
k=1
Then, the maximum weight sum of all paths from
state j to state i is equal to element [A+ ]ij .
([A+ ]ij = +∞ is possible)
Matrix A+ is called maximal weight matrix.
If we truncate the above sum to p, then
⊗k
[A+
]ij
p ]ij = maxk∈{1,2,...,p} [A
will represent [A⊗k ]ij the maximum weight of all
paths from j to i of length p (Heidergott et al.,
2006). Indeed, the maximum weight matrix A+
corresponding to automaton shown in Figure 1, is
given by


ε ε ε ε
 2 ε ε ε 

A+ = 
 5 3 ε ε 
7 5 2 ε
Definição 4 (Strongly connected component). A
set of states U of an automaton G =
(X, Σ, f, Γ, x0 , Xm ), such that U ⊆ X form a
strongly connected component if the following conditions hold true:
1. For all pair of states x, y ∈ U , there exists a
path from x to y and a path from y to x.
Notice that element a41 = 7, which is equal to the
maximum weight of the paths from initial state 1
to marked state 4.
2. The set U is maximal with respect to item 1),
i.e., ∀z ∈ X \ U , U ∪ {z} is not a strongly
connected component.
3523
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
We may now state the following result.
to diagnosis a fault occurrence. In order to do so,
we make two assumptions.
A1. The language L, generated by the automaton, is diagnosable with respect to projection Po
and Σf .
A2.
The time-weighted automaton G =
((G, w), h) is such that h = Σ × Σ.
Assumption A1. is necessary since the problem addressed here would not make sense if L were
not diagnosable. Assumption A2. implies that
any event cannot start firing if there is another one
that is under execution, which makes sense since
we are interested in computing the maximum time
for diagnosis.
Let G denote the time-weighted automaton
that models the plant and A` the time-weighted
label automaton. In addition, let us denote G` =
GkA` and Gd = Obs(G` ) with respect to Po . We
start by calculating a new automaton Gfi according to the following algorithm.
Theorem 5 The language L generated by automaton G is diagnosable with respect to projection Po : Σ∗ → Σ∗o and Σf = {σf } if, and only if,
Gscc has no strongly connected components formed
with states (xd , x` ), such that xd is uncertain and
x` certain.
Proof.
(⇒) Assume that there exists a
strongly connected component formed with states
(xd1 , x`1 ), (xd2 , x`2 ), . . . , (xdn , x`n ) such that xdi ,
i = 1, . . . , n, x` are, respectively, uncertain and
certain states.
Two possibilities arise:
(i) xd1 = xd2 = xd3 = . . . = xdn = xd .
This means that states (xd1 , x`1 ), (xd2 , x`2 ),
. . . , (xdn , x`n ) are connected by unobservable
events since these events are private events of
G` . In addition, due to Lemma 4, x`i ∈ xd ,
i = 1, 2, . . . , n, which, together with the fact
that x`i are certain states, implies that there
exists an indeterminate hidden cycle in xd .
Algorithm 1
Input Time-weighted automata G, G` , and Gd .
Output Automaton Gfi .
(ii) There exists {i1 , i2 , . . . , ip } ⊆ {1, . . . , n} such
that xdik 6= xdil , k 6= l, k, l ∈ {1, 2, . . . , p}.
Since x`i , i = 1, 2, . . . , n are certain, and
L(Gscc ) = L, then, there exists an unbounded trace sY = st ∈ L such that s ∈
Ψ(Σf ) and |t| ≥ n, for all n ∈ N. In addition, since xdik i = 1, 2, . . . , p, are uncertain states, then, as proved in (Sampath
et al., 1995), there exists a trace sN ∈ L
such that Po (sY ) = Po (sN ), which implies
that L is not diagnosable with respect to
Po : Σ∗ → Σ∗o and Σf .
Step 1. Compute G`m from G` by marking all
states of G` that have only labeled Y.
Step 2. Compute Gdm from Gd by marking all certain states Gd .
m
= Gdm kG`m .
Step 3. Compute Gscc
Step 4. Set Γ(xm ) = ∅ for all marked states
m
xm of Gscc
, i.e., remove all output transitions from the marked states xm of
m
m
m
) =
= trim(Gscc
, and compute Gscc,t
Gscc
m
m
m
m
m
m
(Xscc,t , Σscc,t , fscc,t , Γscc,t , xscc,t,0 , Xscc,t,m )
(⇐) Assume, now, that L is not diagnosable
with respect to Po and Σf . Thus, there exist two
traces: an unbounded trace sY = st, s ∈ Ψ(Σf ),
and |t| > n for all n ∈ N and a not necessarily unbounded trace sN , such that Σf ∈
/ sN , which satisfy Po (sY ) = Po (sN ). Let the |Xd ||X` | = q and
set n > q. Then fscc (xscc0 , sY ) = (xd , x` ), x` certain, and (xd , x` ) already exists in Gscc , therefore,
forming a cycle, and, as a consequence, a strongly
connected component in Gscc . Assume, now that
xd is certain. Since, after entering in a cycle,
a certain state cannot become uncertain again,
then, any trace s ∈ L such that Po (s) = Po (sY )
will be certain, which, contradicts the assumption that there exists sN , Σf ∈
/ sN such that
Po (sY ) = Po (sN ). Therefore, the component xd
must be uncertain for all states in the strongly
connected component.
4
m
Step 5. Find all states xi of Gscc,t
that satisty
σf ∈ Γ(xi ). Suppose that there exists p states
that satisfy this requirement. For each i =
1, 2, . . . , p:
Step 5.1 Construct an automaton Gscc,i =
i
i
i
),
, Γiscc , xiscc,0 , Xm,scc
(Xscc
, Σiscc , fscc
i
m
i
such that Xscc = Xscc,t , Σscc = Σm
scc,t ,
i
m
fscc
=
fscc,t
, Γiscc
=
Γm
scc,t ,
i
m
i
m
xscc,0 = fscc,t (xi , σf ) e Xm,scc = Xscc,t
.
Step 5.2 Gfi = trim(Gscci )
We may state the following results.
Lemma 6 Let L(Gfi ) denote the language generated by Gfi , i = 1, 2, . . . , p. Then
m
∪pi=1 L(Gfi ) = {t ∈ Σ∗ : (∃s ∈ Ψ(Σf ) ∩ L(Gscc
)∧
m
m
(∃xm ∈ Xm,scc
)[(st ∈ L(Gscc
))∧
m
(fscc
(xi0,scc , t) = xm )]}
Failure diagnosis of DES modeled by
time weighted automata
In this section we will address the problem of finding the maximum time the diagnosis system takes
Proof. The proof is straightforward and comes
from the construction of L(Gfi ).
3524
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
Lemma 7 Automaton Gfi , i = 1, 2, . . . , p does
not have strongly connected components.
11
1
b/3
g/1
a/9
12
Proof. Since the language generated by G is diagnosable with respect to projection Po and Σf =
{σf }, then, according to Theorem 5, Gscc , thus
Gfi , i = 1, 2, . . . , p, does not have strongly connected components formed with states (xd , x` ),
such that xd uncertain and x` certain. However,
we still need to consider the possibility of strongly
connected components in Gfi formed with the following pair of states: (i) xd certain and x` certain, (ii) xd certain and x` normal, (iii) xd normal and x` normal. A strongly connected component formed with xd certain and x` certain is not
possible, because of the way Gfi is constructed;
all transitions leaving marked states are removed.
Also by construction, we can say that possibilities
(ii) and (iii) can be excluded too, since the initial
state of Gfi is always a state after the occurrence of
the failure event, and thus, all of the states of Gfi
are of the form (xd , x` ), where x` certain, which
concludes the proof.
Lemma 6 shows that all language continuation
of all traces of G that end with a failure event that
leads to the first certain state of Gd are covered by
automaton Gfi , i = 1, 2, . . . , p, whereas Lemmas 7
ensures that Gfi , i = 1, 2, . . . , p has no strongly
connected components. Therefore, the maximum
time necessary to diagnose the fault occurrence
can be calculated according to the following result.
d/4
σf /1
8
g/1
10
3
d/4
4
t/2
b/3
g/1
5
d/4
t/2
6
t/2
Figure 2: Time-weighted automaton G.
Σuo = {σf }. The first step is to compute the timeweighted diagnoser Gdm = Obs(G m kG`m ) shown in
Figure 3. The next step is to compute Gm
scc =
{2Y, 1N}
a/9
{3Y, 8Y, 7N}
b/3
d/4
g/1
d/4
{10Y, 12N, 5Y}
t/2
{6Y}
t/2
Figure 3: Time-weighted diagnoser automaton
Gdm .
(a) The time tfi that Gd fi takes to diagnose the
failure occurrence is
M
tfi =
[A+
i ]i,1 ⊗ tσf ,i
Gdm kG`m k, depicted in Figure 4. Notice that the
language is diagnosable with respect to Po e Σf
since Gm
scc has no strongly connected components
formed with states (xd , x` ), xd uncertain and x`
certain.
Proceeding according to Algorithm 1, two automata Gfi are obtained. For conciseness reasons,
only automaton Gf1 , depicted in Figure 5, will be
analysed here.
The max-plus matrix A1 that corresponds to
Gf1 , as well as its maximal weight matrix A+
1 are
given by:


ε ε ε ε ε ε ε
 3 ε ε ε ε ε ε 


 ε 1 ε ε ε ε ε 



A1 = 
 ε ε 4 ε ε ε ε ,
 ε ε ε 3 ε ε ε 


 ε ε ε ε 1 ε ε 
ε ε 2 ε 4 2 ε
i∈{i1 ,i2 ,...,iki }
where tσf ,i is the weight associated with the
failure event that formed Gd fi
(b) The maximum time tf to diagnose the failure
occurrence is
tfi .
i=1
Proof. The proof is a direct consequence of Lemmas 2, 6, and 7.
5
a/9
9
Theorem 8 Let the states of Gfi , i = 1, 2, . . . , m
be renamed such that Xfi = {1, 2, . . . , qi },
where qi = |Xfi |, x0,fi = 1 and Xm,fi =
{i1 , i2 , . . . , iki } ⊆ {1, 2, . . . , qi }. Let Ai denote
the max-plus matrix associated with Gfi , i =
1, 2, . . . , m. Let A+
i be obtained according to Equation (6). Then
m
M
2
b/3
{11N, 9Y, 4Y}
tf =
σf /1
7
Example
In order to illustrate the results of the paper, let us
consider automaton G depicted in Figure 2, where
3525
Anais do XX Congresso Brasileiro de Automática
Belo Horizonte, MG, 20 a 24 de Setembro de 2014
({2Y, 1N}, 1N)
σf /1
a/9
({2Y, 1N}, 2Y)
systems against intermittent loss of observations, Automatica 48(9): 2068–2078.
({3N, 4N, 6Y}, 4N)
d/4
({3Y, 8Y, 7N}, 7N)
g/1
b/3
Cassandras, C. G. and Lafortune, S. (2008). Introduction to Discrete Events Systems, 2nd
edn, Springer, New York, NY : USA.
({11N, 9Y, 4Y}, 11N)
σf /1
({3Y, 8Y, 7N}, 8Y)
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and
Stein, C. (2007). Introduction to Algorithms,
MIT Press, Cambridge, MA.
b/3
a/9
({11N, 9Y, 4Y}, 9Y)
Debouk, R., Lafortune, S. and Teneketzis, D.
(2000). Coordinated decentralized protocols
for failure diagnosis of discrete event systems,
Discrete Event Dynamic Systems: Theory
and Applications 10(1): 33–86.
g/1
({3Y, 8Y, 7N}, 3Y)
d/4
({10Y, 12N, 5Y}, 10Y)
b/3
t/2
({11N, 9Y, 4Y}, 4Y)
Heidergott, B., Olsder, G. J., and van der Woude,
J. W. (2006). Max Plus at Work, Princeton
University Press, New Jersey, NJ.
d/4
g/1
t/2
({10Y, 12N, 5Y}, 5Y)
({ 6Y}, 6Y)
t/2
Ramadge, P. J. and Wonham, W. M. (1989). The
control of discrete-event systems, Proceedings
of the IEEE 77(1): 81–98.
Figure 4: Time-weighted test diagnoser automam
ton Gscc
.
Sampath, M., Sengupta, R., Lafortune, S., Sinnamohideen, K. and Teneketzis, D. (1995).
Diagnosability of discrete-event systems,
IEEE Transactions on Automatic Control
40(9): 1555–1575.
and






A+
=
1




ε
3
4
8
11
12
15
ε
ε
1
5
8
9
12
ε ε ε
ε ε ε
ε ε ε
4 ε ε
7 3 ε
8 4 1
11 7 4
ε
ε
ε
ε
ε
ε
2
ε
ε
ε
ε
ε
ε
ε





,




Su, R., van Schuppen, J. and Rooda., J. E. (2012).
The synthesis of time optimal supervisors by
using heaps-of-pieces, IEEE Transactions on
Automatic Control 57(1): 105–118.
where index 1 represents the initial state and index 7 represents the marked state in maxplus
matrix A1 . Note that element a71 = 15, and
thus, is the maximal weight from initial state
({3Y, 8Y, 7N }, 8Y ) to marked state ({6Y }, 6Y ).
Since the failure weight is ts = 1, then tf1 =
15 + 1 = 16. Proceeding the same way, the maximum time to diagnose σf following the paths
given in Gf2 is tf2 = 17. Therefore, the maximal time to diagnose the occurrence of σf is
tf = tf1 ⊕ tf2 = max(tf1 , tf2 ) = 17.
6
Tarjan, R. (1972). Depth first search and linear graph algorithms, SIAM Journal of Computer 1(2): 146–160.
({3Y, 8Y, 7N}, 8Y)
b/3
Conclusions
({11N, 9Y, 4Y}, 9Y)
A new test for verification of language diagnosability of discrete event system that relies on
the search for strongly connected components has
been proposed in this paper. Besides its importance as a diagnosability test, this result also provided the bases for a new approach to compute the
maximal time for diagnosing failure occurrences.
The key to this approach is the use of a recently
introduced time-weighted automaton model and
its max-plus representation.
g/1
({3Y, 8Y, 7N}, 3Y)
d/4
({10Y, 12N, 5Y}, 10Y)
b/3
t/2
({11N, 9Y, 4Y}, 4Y)
d/4
g/1
({10Y, 12N, 5Y}, 5Y)
t/2
({ 6Y}, 6Y)
References
Figure 5: Time-weighted automaton Gf1 .
Carvalho, L. K., Basilio, J. C. and Moreira, M. V.
(2012). Robust diagnosis of discrete event
3526