stic discrete-
event systems. We dene the notions of A- and AA-diagnosability
for stochastic automata; these notions are weaker than the
corresponding notion of diagnosability for logical automata
introduced by Sampath et al. [1]. Through the construction of a
stochastic diagnoser, we determine off-line conditions necessary
and sufcient to guarantee A-diagnosability and sufcient to
guarantee AA-diagnosability. We also show how the stochastic
diagnoser can be used for on-line diagnosis of failure events. We
illustrate the results through two examples from HVAC systems.
Index Terms Discrete-event systems, stochastic automata,
fault diagnosis, failure detection, probabilistic models
I. I
NTRODUCTION
I
N this paper we investigate the diagnosability of stochas-
tic discrete-event systems (DES) or stochastic automata.
Discrete-event systems are systems whose evolution is guided
by the occurrence of physical events that are separated by
regular or irregular intervals of time. Stochastic automata are a
more precise formulation of the general DES model, in which
a probabilistic structure is appended to the model to estimate
the likelihood of specic events occurring. An introduction to
the theory of stochastic automata can be found in Paz [2].
The failure diagnosis problem for DES is to detect the
occurrence of specic pre-dened failure events that may not
be directly observed by the sensors available to the system.
Roughly speaking, a system is considered to be diagnosable
if any instance of a failure event can eventually be detected
from the observations made on the system.
The problem of diagnosability of logical DES has re-
ceived a lot of attention in recent years in the contexts of
centralized systems [1], [3]-[10], decentralized systems [11],
timed systems [12], [13], modelling of systems [14]-[17], and
applications [18]-[24]. Diagnosability of stochastic automata
was investigated by Lunze and Schr ¨oder [25]. The approach
to diagnosability of stochastic automata we adopt in this paper
is similar to that of [1]; comparisons between our results and
those of [1] will be made throughout the rest of this paper.
The main differences between the results of this paper and
those on diagnosability of logical DES are the following.
Logical DES models cannot distinguish between strings or
states that are highly probable and those that are less probable.
Therefore, the notions that a state can be observed or a
Manuscript received December 23, 2003; revised November 17, 2004. This
research is supported in part by NSF Grants ECS-0080406 and CCR-0325571,
ONR Grant N00014-03-1-232, and a grant from the Xerox University Affairs
Committee.
The authors are with the Department of Electrical Engineering and Com-
puter Science, University of Michigan, Ann Arbor, MI, USA 48109-2122.
E-mail:
{dthorsle,teneketzis}@eecs.umich.edu
failure can be diagnosed after a nite delay are all-or-
nothing propositions: one possible system behavior, however
improbable, that does not allow the failure to be diagnosed is
sufcient to consider a system to be non-diagnosable. In this
paper, we present denitions of diagnosability that allow such
improbable system behaviors to be disregarded.
The main differences between are results and those of [25]
are the following. Our notions of diagnosability are distinct
from those of [25]; therefore, the conditions for diagnosability
determined in this paper are distinct from those of [25].
Lunze and Schr¨oder correctly demonstrate that, in general,
the observer or diagnoser of a stochastic automaton cannot
be itself realized by another stochastic automaton, and do not
attempt to extend the logical diagnoser approach of [1] to
stochastic systems. The stochastic diagnoser introduced in
this paper inherits the structure of the logical diagnoser of [1],
and appends to each transition a matrix that can be used to
update the probability distribution on the state estimate. The
resulting machine is not a stochastic automaton, but possesses
a structure supercially similar to one.
The main contributions of this paper are: (1) the introduction
of two notions of diagnosability that appropriately incorporate
the stochastic structure of the automaton; these notions of
diagnosability are, as expected, less stringent than those of [1];
and (2) the determination of necessary or sufcient conditions
to guarantee the aforementioned notions of diagnosability.
Preliminary versions of the results in this paper previously
appeared in [26].
Because the model under consideration here allows us
to formulate the probability distributions of various state
estimates and failures, we consider two different denitions
of what it means for a failure to be diagnosed. In the
rst situation, a failure is not said to be diagnosed until all
possible system behaviors consistent with the observations of
the system contain at least one instance of the failure event.
In the second situation, we merely require that of all the
consistent system behaviors, the subset that contains the failure
event has a probability above a pre-determined threshold.
Both notions of diagnosability display long term properties
approximating the type of diagnosability proposed in [1]. The
conditions necessary and sufcient or sufcient to ensure both
types of diagnosability can be expressed in terms of properties
of a diagnoser that is the stochastic analogue of that in [1].
This paper is organized as follows. Section II introduces the
stochastic automaton model under consideration and the con-
cepts and notation required to dene diagnosability. Section III
introduces new denitions of diagnosability motivated by the
probabilistic nature of the automaton. Section IV describes the
construction of a stochastic diagnoser used to state conditions
that ensure diagnosability. These conditions are presented in
00000000/00$00.00 c 2004 IEEE 2
Section V and illustrated using examples from HVAC systems
in Section VI. The results of the paper are summarized in
Section VII.
II. T
HE
M
ODEL
This section describes the formal model of the type of
system we will attempt to diagnose and introduces the basic
concepts and notation necessary to approach the problem.
The type of system to be diagnosed is a stochastic automa-
ton. It is a quadruple
G = (, X , p, x
0
)
(1)
where is a nite set of events X is a nite state space p(x , e | x) is a state transition probability dened for
x, x X , e x
0
X is the initial state
The system evolves through the triggering of events at discrete
points in time, forming a sequence, or string, of events. The
set of all nite strings of positive probability is the prex-
closed language
L(G), which for simplicity will be denoted
as
L. L is a subset of , the Kleene-closure of the event set
.
The system is observed through the events transitioning
the system from one state to another. The event set
is
partitioned as
=
o uo
, where o
represents the set of
observable events and uo
represents the set of unobservable
events. Observable events are events the occurrence of which
is detected by the sensors available to the system; unobservable
events are those events that the available sensors cannot detect.
When a string of events occurs in a system, the sequence of
observable events is indicated by the projection of the string,
which is dened in the usual manner [27] as Pj
: o
Pj
( ) =
Pj
() = if

o
if

uo
(2)
Pj
(s) = Pj (s)Pj () for s ,
where
denotes the empty string. The inverse projection of a
string of observable events
s
o
with respect to a language
L is
given by:
Pj
1
L
(s
o
) = {s L : Pj (s) = s
o
}
(3)
We dene a set of failure events f
. The objective of
the diagnosis problem under consideration is to determine the
likelihood of the occurrence of these failure events when only
the events in o
are observed. We can assume, without loss
of generality, that f

uo
, because it is a trivial problem
to determine when an observable failure has occurred.
To facilitate the diagnosis problem, the set of failure events
is partitioned into a set of failure types: f
=
f
1
· · ·
f
m
(4)
If a failure event f

f
i
occurs, we will say that a failure
of type
F
i
has occurred.
0
1
2 f
( ,.1)
(a,.7)
(b,.2)
(c,1)
(b,.5)
(a,.5)
Fig. 1.
A stochastic automaton.
X = {0, 1, 2}, = {a, b, c,
f
},
uo
= f
= {
f
}, x
0
= 0.
The probability transition function
p(x , e | x) denes the
probability that a certain event
e will occur and transition the
state of the machine from a given state
x to the specied state
x . For example, p(z, a | y) = 0.7 states that, if the system
is in state
y, with probability .7 the event a will occur and
transition the state of the system to
z. We will assume, for
the sake of simplicity, that
p(x , e | x) > 0 for at most one
x X . The results that follow hold without this assumption.
Under this assumption, the probability transition function
can be used to dene the partial transition function, which is
dened as
: X × X where
(x, e) = y p(y, e | x) > 0
(5)
If for some
x X and e , there does not exist y X
such that
p(y, e | x) > 0, then (x, e) is undened.
This relationship demonstrates that the stochastic model is
a more specic model than the logical nite state machine
model discussed in [1]. In the logical automaton model, the
partial transition function is dened as part of the specication
of the system, but here it is derived from the state transition
probabilities.
The partial transition function can be extended to strings of
events as follows:
(x, ) = x
(6)
(x, se) = ((x, s), e))
(7)
Figure 1 provides a pictorial representation of a stochastic
automaton. The set of states is
X = {0, 1, 2}, and the init