Guaranteed Fault Detection and Isolation for Switched Affine Models

arXiv:1704.05947v2 [math.OC] 1 Oct 2017

Farshad Harirchi

Sze Zheng Yong

Abstract— This paper considers the problem of fault detection and isolation (FDI) for switched affine models. We first
study the model invalidation problem and its application to
guaranteed fault detection. Novel and intuitive optimizationbased formulations are proposed for model invalidation and
T -distinguishability problems, which we demonstrate to be
computationally more efficient than an earlier formulation
that required a complicated change of variables. Moreover, we
introduce a distinguishability index as a measure of separation
between the system and fault models, which offers a practical
method for finding the smallest receding time horizon that is
required for fault detection, and for finding potential design
recommendations for ensuring T -distinguishability. Then, we
extend our fault detection guarantees to the problem of fault
isolation with multiple fault models, i.e., the identification of
the type and location of faults, by introducing the concept of
I-isolability. An efficient way to implement the FDI scheme is
also proposed, whose run-time does not grow with the number
of fault models that are considered. Moreover, we derive bounds
on detection and isolation delays and present an adaptive
scheme for reducing isolation delays. Finally, the effectiveness
of the proposed method is illustrated using several examples,
including an HVAC system model with multiple faults.

I. I NTRODUCTION
Cyber-physical systems (CPS), i.e., systems with integrated computation, networking, and physical processes, are
becoming increasingly common in our daily lives. Such systems include critical infrastructures such as traffic, power and
water networks, as well as autonomous vehicles, aircrafts,
home appliances and manufacturing processes. However,
some major incidents involving these critical infrastructure
systems as a result of cyber-attacks and system failures
have taken place in the recent years and are a big source
of concern. Hence, the reliability and security of CPS is
paramount for their successful implementation and operation.
The detection and isolation of faults and anomalies in CPS
play an important role in enhancing the reliability of these
systems, and in understanding the vulnerability of system
components to failures and attacks.
1) Literature Review: The study of fault detection began
with the introduction of the first failure detection filter by
Beard in 1971 [1]. Since then, fault diagnosis has attracted
a great deal of attention and has become an integral part of
most, if not all system designs. Researchers have mainly
approached the fault detection and isolation problem by
This work is supported in part by DARPA grant N66001-14-1-4045 and
an Early Career Faculty grant from NASA’s Space Technology Research
Grants Program.
F. Harirchi and N. Ozay are with the Electrical Engineering and Computer
Science Department, University of Michigan, Ann Arbor, MI, 48109 (email:
{harirchi,necmiye}@umich.edu); S.Z. Yong is with the School for
Engineering in Matter, Transport and Energy, Arizona State University,
Tempe, AZ, 85281 (email: szyong@asu.edu).

Necmiye Ozay

employing either data-driven techniques or model-based approaches. These methods can, in general, be further grouped
into active and passive approaches. In active fault detection,
the system is excited by a carefully designed input [2]–[4],
while in passive methods, the behavior of the system is not
controlled or altered by the FDI scheme [5], [6].
In broad strokes, model-based fault detection and isolation
schemes in the literature can be categorized into two classes,
i.e., approaches that are based on residual generation and
on set-membership. The former approach is more common
in the fault diagnosis literature, and in this approach, the
difference between the measurements and the estimates is
defined as a residual or a symptom [7]. Two major trends
in the residual generation techniques are methods based on
observers [5], [8]–[14] and parameter estimation [15], [16].
On the other hand, set-membership based fault detection
and isolation techniques are proposed with the goal of
providing guarantees for the detection of some specific faults.
Most of these methods operate by discarding models that are
not compatible with observed data, rather than identifying
the most likely model. There is an extensive literature on setmembership based methods for active fault detection of linear
models [17]–[19]. In [20], [21], we posed set-membership
based guaranteed passive fault detection approaches for the
class of switched affine models and polynomial state space
models. These approaches are developed by utilizing ideas
from model invalidation [22], [23] and taking advantage
of recent advances in optimization. In addition, a concept
called T -distinguishability has been introduced for finding
conditions under which the fault detection scheme can be
applied in a receding horizon manner without compromising
detection guarantees. T -distinguishability is closely related
to the concept of input-distinguishability of linear systems
[24], [25] and mode discernibility in hybrid systems [26].
2) Main Contributions and Paper Structure: In this paper,
we consider a passive fault detection and isolation scheme
for switched affine systems using an optimization-based
model invalidation framework, that improves and expands
the results of [20] on fault detection. We provide novel formulations of the model invalidation and T -distinguishability
algorithms that we demonstrate to be noticeably faster than
the previous formulation in [20] and that have the added advantage of simplicity as no complicated change of variables
are needed. Furthermore, we introduce a measure of separation between models, called distinguishability index. By
reformulating the T -distinguishability optimization problem
in [20], we can compute the distinguishability index as a
byproduct. This index offers a practical way to find out if
a finite receding time horizon exists, and suggests potential

design options for ensuring T -distinguishability.
We then consider the fault isolation problem using model
invalidation and introduce the concept of I-isolability when
multiple faults are present. Similar to fault detection, we
propose a computationally efficient optimization problem to
check whether a given set of fault models is I-isolable or
not. Moreover, we propose a fault diagnosis scheme that not
only detects the occurrence of a fault, but also outputs a list
of potential faults along with their associated ‘likelihoods’ in
the form of distinguishability indices. Further, a theoretical
analysis for bounds on detection and isolation delays is
provided and an adaptive fault isolation scheme is proposed
to reduce isolation delays. The run-time of our FDI scheme
also does not grow with the number of fault models. Finally,
these results are illustrated using a numerical model of a
heating, ventilating, and air conditioning (HVAC) system.


N
−1
+
Bswa
(G) := {ut , yt }N
t=0 | ut ∈ U and ∃xt ∈ X , σt ∈ Zm ,
[ηη |t ν |t ]| ∈ E, for t = 0, . . . , N − 1 s.t. (3) holds .

Moreover, with a slight abuse of terminology, we will call
N
Bswa
(G) the behavior of the system G for conciseness.
III. M ODEL I NVALIDATION AND T -D ETECTABILITY

II. P RELIMINARIES
In this section, the notation used throughout the paper and
the modeling framework we consider are described.
A. Notation
Let x ∈ Rn denote a vector and M ∈ Rn×m represent a
.
matrix. The infinity norm of a vector x is denoted by kxk =
maxi |xi |, where xi denotes the ith element of vector x. The
set of positive integers up to n is denoted by Z+
n , and the
set of non-negative integers up to n is denoted by Z0n .
B. Modeling Framework
In this paper, we consider systems that can be represented
by discrete-time switched affine (SWA) models.
Definition 1: (SWA Model) A switched affine model is
defined by:
G = (X , E, U, {Gi }m
(1)
i=1 ),
where X ⊂ Rn is the set of states, E ⊂ Rny +np is the set
of measurement and process noise signals, U ⊂ Rnu is the
set of inputs and {Gi }m
i=1 is a collection of m modes. For
th
all i ∈ Z+
mode is an affine model:
m , the i
Gi = {Ai , Bi , Ci , Di , fi , gi }.

Definition 2 (Fault Model): A fault model for a switched
affine system G = (X , E, U, {Gi }m
i=1 ) is another switched
affine model Ḡ = (X̄ , Ē, Ū, {Ḡi }m̄
i=1 ) with the same number
of states, inputs and outputs.
Further, to describe our framework of model invalidation
and T -distinguishability for fault detection and isolation in
the next section, we define the following.
Definition 3 (Length-N behavior): The length-N behavior associated with an SWA system G is the set of all lengthN input-output trajectories compatible with G, given by the
following set:

(2)

The evolution of G is governed by:
xt+1 = Aσt xt + Bσt ut + fσt + ν t ,
(3)
yt = Cσt xt + Dσt ut + gσt + η t ,
where ν ∈ Rnp and η ∈ Rny denote the process and
measurement noise signals, respectively, and σt indicates the
active mode at time t.
Remark 1: We assume X , E, U are convex and compact
sets. In particular, we consider the following form for the
admissible sets:
X = {x | P x ≤ p}, E = {[ηη | ν | ]| | kηη k ≤ η , kνν k ≤ ν },
U = {u | kuk ≤ U },
(4)
where P ∈ Rnp ×n and p ∈ Rnp . Note that our analysis holds
true for any X , E, U that are convex sets, but for simplicity
in notation, we use the above mentioned admissible sets.
We define the fault model as follows:

A. Model Invalidation
In our previous work [20], [21], we established a theoretical framework that can be utilized in order to develop
fault detection schemes based on the achievements in model
invalidation, a framework that we will also consider in this
paper. The model invalidation problem is to check whether
some given data can be represented by a model or not. More
formally, the model invalidation problem is as follows:
Problem 1 (Model Invalidation): Given an SWA model
N −1
G and an input-output sequence ut , yt t=0 , determine
whether or not the input-output sequence is contained in the
behavior of G, i.e., whether or not the following is true:

N −1
N
ut , yt t=0 ∈ Bswa
(G).
(5)
Clearly, if the model is invalidated by data, i.e., (5) does
not hold, and the model is precise, it is equivalent to the
data representing an abnormal behavior. Hence, model invalidation can be used as a fault detection scheme. Moreover,
our previous work [20] has shown that model invalidation
problem for SWA models can be posed as a Mixed-Integer
Linear Program (MILP) feasibility check problem.
In this paper, we propose a new MILP formulation, that we
believe is much more intuitive and computationally efficient.
We obtain this novel formulation by taking advantage of
Special Ordered Set of degree 1 (SOS-1) constraints [27],
that are readily implementable in most off-the-shelf optimization softwares. In brief, an SOS-1 constraint is a set of
variables for which at most one variable in the set may be
non-zero. Our new formulation is cleaner because this type
of constraints allows us to formulate the feasibility check
problem without introducing complicated change of variables
as was previously done in [20]. Moreover, SOS-1 constraints,
which are by nature integral constraints, make the branch
and bound search procedures noticeably faster (see, e.g., [28,
Section 3.3.4] for a discussion). Our new model invalidation
problem using SOS-1 constraints is presented below, which
we will demonstrate to be much faster than an earlier
formulation [20], [29] in Section VI-A.
Proposition 1: Given an SWA model G and an inputN −1
output sequence ut , yt t=0 , the model is invalidated if

and only if the following problem is infeasible.
Find xt , η t , ν t , ai,t , si,t , ri,t for ∀t ∈ Z0N −1 , ∀i ∈ Z+
m
+
+
0
s.t. ∀j ∈ Z+
n , ∀k ∈ Zny , ∀l ∈ Znp , ∀t ∈ ZN −1 , we have:
xt+1 = Ai xt + Bi ut + fi + ν t + si,t ,
(PM I )
yt = Ci xt + Di ut + gi + η t + ri,t ,
P
ai,t = 1, kνν t k ≤ ν ,
P xt ≤ p, ai,t ∈ {0, 1},
i∈Z+
m

kηη t k ≤ η ,

(ai,t , sji,t )

: SOS-1,

(ai,t , rki,t )

: SOS-1,

where si,t and ri,t are slack variables that are free when
ai,t is zero and zero otherwise. We refer to this problem as
−1
F eas({ut , yt }N
t=0 , G).
Intuitively, the infeasibility of (PM I ) indicates that there
are no state, input and noise values that can generate the
input-output sequence from the model, and hence it is impossible that the data is generated by the model. Proposition
1 enables us to solve the model invalidation problem by
checking the feasibility of (PM I ), which is a MILP with
SOS-1 constraints that can be efficiently solved with many
off-the-shelf softwares, e.g., [30], [31].
B. T -Distinguishability
The model invalidation problem can be solved for the
input-output sequence of any given time horizon to detect
faults, but the number of variables and constraints increase
with the size of the time horizon. Thus, a few questions
naturally arise with regards to this time horizon.
First, one may ask if the smallest receding time horizon T
can be found, for which two different models are guaranteed
to be distinguishable. This question leads us to define the notion of T -distinguishability, previously presented in [20]1 . T distinguishability is defined for a pair of system and/or fault
models, which means that the trajectory generated from the
two models cannot be identical for a time horizon of length
T for any initial state and any noise signals. This notion is
very similar to the concept of input-distinguishability, which
is defined for linear time-invariant models in [24], [25]. T distinguishability is formally defined as follows:
Definition 4 (T -distinguishability): A pair of switched
affine models G and Ḡ is called T -distinguishable if
T
T
Bswa
(G) ∩ Bswa
(Ḡ) = ∅, where T is a positive integer.
Thus, given two SWA models and an integer T , the
T -distinguishability problem is to check whether the two
models are T -distinguishable or not. This problem can be addressed using a Satisfiability Modulo Theory approach [20],
or a MILP feasibility check [29]. As with model invalidation
in the previous section, we will also propose an alternative
MILP formulation for checking T -distinguishability, which
employs SOS-1 type constraints and as before, is more
intuitive and computationally superior (cf. Section VI-A).
Note that in the following T -distinguishability test, we have
added a decision variable δ that will be important in a later
discussion, which can be computed with little additional
computational cost.
1 When the pair of models consists of the nominal system model and the
fault model, this is also known as T -detectability [20], [29].

Theorem 1: A pair of switched affine models G and Ḡ is
T -distinguishable if and only if the following is infeasible.
δ̄ =
s. t.

min

η ,η̄
η ,ν
ν ,ν̄
ν ,s,s̄,r,a,δ
x,x̄,u,η

δ

∀t ∈ Z0T −1 , ∀i ∈ Z+
m,
+
∀h ∈ Z+
,
h̄
∈
Z
np
np̄ ,

+
+
∀j ∈ Z+
m̄ , ∀k ∈ Zn , ∀l ∈ Zny ,

xt+1 = Ai xt + Bi ut + fi + ν t + si,t ,
x̄t+1 = Āj x̄t + B̄j ut + f̄j + ν̄ν t + s̄j,t ,
Pxt ≤ p, P̄x̄t ≤ p̄,
(PT )
Ci xt +Di ut +gi +ηη t = C̄j x̄t + D̄j ut + ḡj +η̄η t +ri,j,t ,
P
P
ai,j,t ∈ {0, 1},
a
= 1,
i∈Z+
j∈Z+ i,j,t
m
m̄

kηη t k ≤ η , kη̄η t k ≤ η̄ , kνν t k ≤ ν , kν̄ν t k ≤ ν̄ , kut k ≤ U,
(ai,j,t , ski,t ) : SOS-1, (ai,j,t , s̄kj,t ) : SOS-1,
   
η̄η
ηt
(ai,j,t , rli,j,t ) : SOS-1,
− ν t ≤ δ.
ν̄ t
νt

We refer to the above-mentioned problem as F easT (G, Ḡ).
Proof: Except for the last constraint, this is an equivalent formulation to the MILP feasibility problem of Theorem
1 in [29]. Clearly, the last constraint does not change the
feasible set, therefore the feasibility of (PT ) is necessary and
sufficient for T -distinguishability.
While Theorem 1 enables us to solve the T distinguishability problem, if the two models are not T distinguishable, i.e., the solution to PT is feasible, it additionally delivers δ̄, which we argue is a good indication and
measure for the separability of two models. In essence, δ̄ can
be interpreted as the noise effort that is required to make the
trajectories of the two models identical. A larger value for
δ̄ indicates a larger separation between the two models that
the noise has to compensate for. Hence, we will refer to the
normalized version of δ̄ as the distinguishability index
δ̄
δ ∗ = max ,
(6)
δ
.
where δ max = min{max{η + η̄ , ν + ν̄ }, max{η , ν } +
max{η̄ , ν̄ }} is an upper bound on δ̄; hence, 0 ≤ δ ∗ ≤ 1.
Moreover, to find the smallest T for which we have T distinguishability, one could iterate with T increasing from 1
until the T -distinguishability problem in Theorem 1 becomes
infeasible. But, if δ ∗ is small for some T , then it may
make sense to consider larger increases in T to speed up
computation. Thus, δ ∗ can be used as a heuristic for choosing
the next T to solve the T -distinguishability problem. In
addition, one may also ask about when the iterations with
increasing T can be terminated with some confidence that a
finite T does not exist. Once again, we can consider the trend
of δ ∗ with increasing T and terminate the iterations when δ ∗
reaches a plateau. This will be demonstrated to be effective in
a simulation example in Section VI-C. In addition, when this
index reaches a (non-zero) plateau and the problem remains
not T -distinguishable, then it would be possible to use any
value that is smaller than the maximum δ ∗ to derive the
maximum allowed uncertainty for a system such that fault
detection is guaranteed. This may suggest possible design
remedies involving the choice of sensors with better precision
or the employment of noise isolation platforms to reduce the

amount of noise, in order to facilitate fault detection.
IV. FAULT I SOLATION
In practice, it is of special interest to identify the source
of a detected fault, as it significantly simplify the process of
fault accommodation. The process of distinguishing among
possible fault models is called fault isolation. In this section,
we utilize the tools we developed for distinguishability and
model invalidation to address the fault isolation problem for
switched affine models, i.e, to derive necessary and sufficient
conditions to guarantee the isolation of a set of possible
faults. In addition, we propose a tractable way to isolate
faults in real-time for many applications by leveraging the
recent advances in the development of mixed-integer linear
programming tools [31]. In order to ensure the isolability
of two fault models, it suffices that the two fault models
are T -distinguishable. In this case, by implementing model
invalidation for each of the two models on a time horizon
of length T , we can simply isolate the faults after detection.
Hence, we turn our attention to the multiple-fault scenario.
A. Multiple-Fault Scenario
The fault isolation problem becomes marginally more
challenging with multiple fault models. Let us assume that
there exist Nf fault models for a specific system. We
consider the following necessary and sufficient assumptions:
A1 (Detectability Assumption): We assume that ∀ j ∈
Z+
Nf , there exists a finite Tj such that the pair of nominal
system G and the fault model Ḡj is Tj -distinguishable.
A2 (Isolability Assumption): We assume that ∀ m, n ∈
Z+
Nf , m 6= n, there exists a finite Im,n such that Ḡm and
Ḡn are Im,n -distinguishable.
Now, we will define I-isolability for multiple faults.
Proposition 2 (I-isolability for multiple faults): Consider
a set of Nf fault models that satisfies Assumption 2. If a fault
occurs, it can be isolated in at most I = maxm,n, m6=n Im,n
steps after the occurrence. Such a set of fault models is
called I-isolable.
Proof: Under Assumption A2, and because I ≥ Im,n
for all possible pairs of fault models, all pairs of faults are
I-distinguishable. Therefore, if any of the faults occur persistently, by observing at most I samples, it will be isolated.
This is because the length-I behavior of the occurred fault
does not have any intersection with the length-I behavior of
any of the other faults.
V. FDI S CHEME
In this section, we propose a two-step FDI scheme:
1) Off-line step: In the off-line step, under Assumptions
A1 and A2, we calculate the following quantities:
Isolability index: I = max Im,n , m, n ∈ Z+
Nf , m 6= n,
m,n

Isolability index for fault i: I˜i = maxj∈Z+

Nf

Detectability index: T = maxj∈Z+ Tj .
Nf

Length of memory: K = max{T, I}

, j6=i

Ii,j ,

2) On-line step: In this step, we leverage Nf + 1 parallel
monitors corresponding to system and fault models. The
monitors are labeled as {M0 , M1 , . . . , MNf }, where M0
corresponds to the system model and Mi corresponds to
the ith fault model. First, only M0 is active for fault
detection. The rest of the monitors will be “off” until a fault
is detected by M0 . The inputs to each monitor at time t
are the input-output sequence of length Ki = max{I˜i , Ti },
{uk , yk }tk=t−Ki +1 , and the corresponding model Ḡi . For
instance, M0 knows G, and at each time step, it solves the
model invalidation problem, F eas({uk , yk }tk=t−T +1 , G). If
the problem is feasible, the monitor outputs 0, otherwise
it outputs 1. In the latter case, the bank of fault monitors
is activated and parallelly solves the model invalidation
problems for all fault models, i.e., to check if Mj solves
F eas({uk , yk }tk=t−Kj +1 , Ḡj ) for each j ∈ Z+
Nf . By Assumptions A1 and A2, it is guaranteed that in this case,
the problem of at most one monitor is feasible. The output
block receives the signal from all the monitors and shows
two elements, the first element is 1, which indicates that a
fault has occurred, and the second element is kf ∈ Z+
Nf if
the fault matches kf th fault model, or 0 if the fault does not
match any of the fault models.
At every time step t, this FDI scheme acts as a function:
N

f
[H, F] = ψ({uk , yk }tk=t−K+1 , G, {Ḡj }j=1
),

(7)

where H is 0 or 1 to indicate healthy or faulty behaviors,
and F either indicates the fault model that is active, or that
none of the fault models caused the faulty behavior.
Remark 2: In some practical examples, Assumptions A1
and A2 may not be satisfied, i.e., the FDI approach is not
guaranteed to detect and isolate the given fault models.
However, the FDI approach can be simply modified such
that F outputs either the set of faults that matches the data
(because some fault models may not be isolable) along with
their corresponding ‘likelihoods’ in terms of their distinguishability indices, or the empty set, if none of the models
matches the data.
A. Detection and Isolation Delays
In this section, we describe the notion of delays in detection and isolation of faults, and provide theoretical bounds
on these delays using detectability and isolability indices.
Definition 5: (Detection/Isolation
Delay)
Detection/isolation delay is the number of time samples it takes
from the occurrence of the fault to its detection/isolation.
We denote detection and isolation delays with τT and τI ,
respectively.
Proposition 3: Given a Ti -distinguishable pair of system
and fault models (G, Ḡi ), the detection delay of the proposed
fault detection scheme is bounded by Ti . In addition, the
isolation delay of a pair of Ii,j -isolable fault models (Ḡi , Ḡj )
is bounded by Ii,j .
Proof: Direct consequence of definitions.
Theorem 2: The detection delay for fault Ḡi using the FDI
scheme proposed in Section V is bounded by Ti , and the
isolation delay is bounded by Ki = max{I˜i , Ti }.

Proof: Assume fault i occurs at time t∗ . The FDI
approach implements model invalidation with a time horizon
size of T ≥ Ti . At time t∗ +Ti −1, the input-output trajectory
that is fed to the model invalidation contains a length Ti
trajectory that is in B Ti (Ḡi ). By Ti -distinguishability of Ḡi ,
this trajectory cannot be generated by G. Thus, the model
will be invalidated by observing at most Ti data points from
fault i. This concludes the proof for the bound on detection
delay. For isolation, the FDI approach requires detection first,
and in the worst case, detection will occur in Ti steps. On the
other hand, if we observe any trajectory from t∗ to t∗ + I˜i −1
˜
that is generated by fault i, it is not in B Ii (Ḡj ), j 6= i. This
˜
is because Ii ≥ Ii,j , j 6= i. Hence, the fault will be isolated
in at most I˜i observations of the fault. Considering that the
fault needs to be detected first, the isolation delay is bounded
by Ki = max{I˜i , Ti }. This concludes the proof.

A. Run-Time Comparison
In this section, we compare the run-time for the formulations proposed in this paper with the one in [29]. Consider
a hidden-mode switched affine model, G, with admissible
sets X = {x | kxk ≤ 11}, U = {u | kuk ≤ 1000} and
E = {ηη | kηη k ≤ 0.1}. We assume there is no process noise.
We also assume B = [1 0 1]| and C = [1 1 1] for all
modes. The system matrices of the modes are:

0.5
A1 =  0.1
−0.4

0.5
A3 =  0.2
−0.9


 


 
0.5 0.5
1
0.5
0.5
0.5
0
−0.2 0.5, f1 = 0, A2 = −0.3 −0.2 0.3 , f2 = 1,
0.6 0.2
0
0.1 −0.3 −0.5
0

 
0.2 0.6
0
−0.2 0.2, f3 = 0.
0.7 0.1
1

In addition, consider a fault model, G f , with:



 
 
0.8
0.7
0.6
1
1
f
f




0.1 −0.2 0.3 , B = 0 , f = 1 .
A =
−0.4 0.3 −0.2
0
1
f

The bound on isolation delays represents the worst case
scenario, where the data created by a fault model falls within
the behavior of some other models up until the very last time
step. However, this is not the case in most applications, where
the faults can be isolated much prior to this bound. Here, in
this section, we propose an adaptive fault isolation scheme
that reduces isolation delay, which is based on the idea of
validation of only one of the fault models. Since the data
prior to the time of detection will most probably invalidate
all the fault models, we propose to reduce isolation delays by
using an adaptive receding horizon that considers only the
data starting from the detection time (fixed horizon lower
bound) with increasing horizon until only one fault model
matches or validates the data. In practice, we can achieve
this by considering model invalidation problems for each of
the fault models with the adaptive receding horizon until only
one fault model remains that matches the data.
Since we assumed that the fault is among the predefined
set of models and is persistent, it is guaranteed that the fault
will be isolated with this approach. Such an approach has the
potential to significantly reduce isolation delays, as we have
observed in simulation in Section VI-B (cf. Fig. 3 (bottom)).

The implementation of the T -distinguishability approach
proves that the system and fault model pairs is 12distinguishable. We first randomly generate input-output
trajectories (5 for each time horizon length) from G f . We
then compare the model invalidation approaches that use
the proposed formulation in Prop. 1 and the one in [20],
[29]. The average run-time for each time horizon length
as well as the standard deviation of run-times for both
formulations are illustrated in Fig. 1. Clearly, the results
indicate the superiority of the proposed formulation to the
one in [20], [29]. Similar improvements were also observed
for the proposed T -distinguishability formulation in Thm. 1
when compared to [20], [29] (plots are omitted for brevity).
100
80

Time(s)

B. Adaptive Fault Isolation

SOS-1
Convex hull

60
40
20
0
0

50

100

150

200

Time Horizon(samples)

VI. I LLUSTRATIVE E XAMPLES
First, we demonstrate in Section VI-A that our new
formulations for model invalidation and T -distinguishability
in Prop. 1 and Thm. 1, respectively, are computationally
superior to the previous formulation in [20], [29]. Then,
we illustrate the performance of the proposed FDI scheme
using a numerical model for the Heating, Ventilating, and
Air Conditioning (HVAC) system that is proposed in [32] in
Section VI-B. Moreover, we provide a numerical example in
Section VI-C to illustrate the practical merits of the distinguishability index that was introduced in Section III-B. All
the simulations in this section are implemented on a 3.5 GHz
machine with 32 GB of memory that runs Ubuntu. For the
implementation of the MILP feasibility check problems, we
utilized YALMIP [33] and Gurobi [30]. All the approaches
and examples are implemented in MATLAB.

Fig. 1: Average execution time (with standard deviations) for
invalidating data generated by G f with various time horizons.
B. Fault Diagnosis in HVAC Systems

Fig. 2: Schematic of a single-zone HVAC system.
In [32], a single-zone HVAC system in cooling mode (cf.
schematic in Fig. 2) is considered. This HVAC system is

68
66

Guaranteed
isolation
for Fault 1

Fault 1
0

2

4

6

Guaranteed
isolation for
Fault 2

66
64
62
60
58

Detection

66

Fault 2
2

Detection

67

Detection
0

8

68

Fault 3

4

6

8

0

2

4

Guaranteed
isolation for
Fault 3
6

8

10 -3

10 -3

0.014

10

10

Fault 3

0.012

8
0

2

4

6

0.008

0

8

2

4

6

0

8

Detection
Flag1
Flag2
Flag3
Fault1
Fault1 (Adaptive Isolation)

2

0

2

Detection
Flag1
Flag2
Flag3
Fault 2
Fault 2 (Adaptive Isolation)

2

4

6

0

8

2

4

6

8

4

6

8

4

4

4

0

0.01

8

0

2

Detection
Flag1
Flag2
Flag3
Fault 3
Fault 3 (Adaptive Isolation)

2

0

4

6

8

0

2

Fig. 3: The outputs (top two rows) of 3 fault scenarios; Detection, isolation and adaptive isolation signals for all faults
(bottom row). Flag i is non-zero when the model invalidation problem associated with fault i using the adaptive horizon
length is validated. Adaptive isolation occurs when only one Flag is non-zero.
represented by a non-linear model as follows:




ṪT S
ẆT S 
ṪSA

hf g f


f
TT S
Cp Vs
Vs 

f



=
0
− Vs
0  WT S  +
TSA
0.75 Vf
−0.75 CfphVw
− Vf
he
he
he

h
f
− CfpgVs Ws + Cp4Vs (Qo − hf g Mo )

Mo
f


Vs Ws + ρVs
hw
f hw
gpm
f
(T
−
W
)
+
o
o
4Vhe
Cp
Cp Vhe Ws − 6000 ρCp Vhe



− Vfs

1

0.5

0.5

0



(8)


,


where f , gpm, Mo and Qo are time varying parameters. The
parameters of the model2 are defined in [32].
We leverage an augmented state-space model with additional states Q0 and M0 that is obtained in [32]. To further
simplify the model, we assume that the fan is always turned
on and the flow rate is fixed at 17000 ft3 /min and the chiller
pump is either “off” or “on” with a fixed flow rate of 58
gal/min. These assumptions along with a discretization with
a sampling time of 10 minutes convert the nonlinear system
(8) to a switched affine model parameterized by

0.98 229.63
0.001
0.94
0
 0

A1 = A2 = 0.74 −360.61 0.0008
 0
0
0
0
0
0


1 0 0 0 0
C1 = C2 =
, f1 = 0.
0 1 0 0 0

1






0 −0.0035
0.3886
0
0

 0.0001 



0 −0.0030, f2 = −22.576,



1
0
0
0
1
0

The first three states in the SWA model represent the
deviation of TT S , WT S and TSA from their equilibria and
the last two states are Q0 and M0 . In addition, the HVAC
model is represented by GH = (X , E, U, {Gi }2i=1 ), where
X = {x | [−100 − 0.05 − 50 289800 150]| ≤ x ≤
[100 0.05 50 289950 180]| }, E = {ηη | |ηη | ≤ [0.2 0.002]| }
and U = ∅. The last two bounds on the states are for
the augmented states, which are assumed to stay within a
small range of their equilibria. The first mode corresponds
to chiller being “on” and the second mode represents the
model when it is “off”. The controller keeps the temperature
in the comfort zone of 65–75◦ F by turning the chiller on and
off. Control signals are not observed by the FDI scheme.
We consider three fault scenarios:
2h
w = 180, hf g = 1078.25, Wo = 0.018, Ws = 0.007, Cp =
0.24, To = 85, Vs = 58464, Vhe = 60.75, Mo ∈ [150 180], Qo ∈
[289800 289950], ρ = 0.074, f = 17000, gpm ∈ {0, 58}.

5

10

15

0

5

10

15

Fig. 4: Distinguishability index as a function of length of
time horizon. Left: Increase in detectability index for fault
3, T3 and isolability index of faults 2 and 3, I2,3 , for the
HVAC example; Right: Nonlinear increase with a plateau at
around T = 5, for numerical example described by (9).
1) Faulty fan: The fan rotates at half of its nominal speed.
2) Faulty chiller water pump: The pump is stuck and spins
at half of its nominal speed.
3) Faulty humidity sensor: The humidity measurements
are biased by an amount of +0.005.
The proposed approach for T -distinguishability and Iisolability gives us the following results:
TABLE I: Detectability and Isolability Indices
T1 = 4

T2 = 8

T3 = 16

I1,2 = 4

I1,3 = 4

I2,3 = 16

To illustrate the growth in the distinguishability index δ ∗
as the time horizon increases, we plot its trend in Fig. 4 (left)
for T -distinguishability of fault 3 and I-isolability of faults
2 and 3. The plot shows that the distinguishability index we
introduced does indeed deliver a nice measure of how far
two models are from detectability or isolability, and at the
same time, it allows us to estimate the size of time horizon,
T or I, to achieve T -distinguishability or I-Isolability.
Next, we consider 3 scenarios, where for each scenario i
(i ∈ {1, 2, 3}), we generate data from the nominal system for
four hours and from fault i afterwards. The times at which
the faults occur and their detection times, as well as the upper
bounds on isolation delays are indicated in Fig. 3 (top and
middle rows), which show the output trajectories for each
scenario. Furthermore, we plot in Fig. 3 (bottom row) the
detection and isolation signals for all three faults to show that
only the occurred fault is isolated in all scenarios before their
upper bounds are exceeded, and that the proposed adaptive
isolation scheme reduces the isolation delay, as desired.

C. Distinguishability Index
To illustrate the practical use of the distinguishability
index, δ ∗ , we consider two synthetic SWA models G and
Ḡ subject to measurement and process noise, given by

G:



















Ḡ :























0.1
0
0.1
0
0
0.15




A1 =  0
0.1 0.2 , A2 = 0.1
0
0 ,
0.2 0.12 0
0.1 0.12 0.1
 
 
0.5
1
 
 
C1 = C2 = I, f1 = 0.2 , f2 =  0  ,
1
0.5




0.1 0 0.1
0
0 0.1




Ā1 =  0 0.1 0.2 , Ā2 = 0.1 0
0 ,
0.2 0.1 0
0.1 0.1 0.1
 
 
0.3
0.8


 
C̄1 = C̄2 = I, f¯1 =  0  , f¯2 = 0.2 ,
0.9
0.3

(9)

where the rest of the parameters are zero. The bounds
on the process and measurement noise are set to be 0.2
and 0.25, respectively. Fig. 4 (right) depicts the change of
the distinguishability index with increasing T . We observe
that the distinguishability index increases nonlinearly and
reaches a plateau at a value less than one. In this case, the
distinguishability index δ ∗ provides a practical indication that
these two models are very unlikely to be isolable for any
finite I. Moreover, if the noise levels are constrained to be
below the value of the plateau, then we can be sure that these
faults will be isolable. Hence, the distinguishability index can
also be exploited to derive the maximum allowed uncertainty
for a system such that certain faults are guaranteed to
be detectable or isolable. In turn, this suggests possible
measures for ensuring fault detection and isolation through
the reduction of noise levels, either with a better choice of
sensors or with the use of noise isolation platforms.
VII. C ONCLUSION
We considered the FDI problem for switched affine models. For fault detection, we proposed new model invalidation and T -distinguishability formulations using SOS1 constraints, that are demonstrated to be computationally
more efficient and do not require any complicated change of
variables. Further, we introduced the distinguishability index
as a measure of separation between the system and fault
models and showed that this index is also a practical tool for
finding the smallest receding time horizon that is needed for
fault detection and for recommending system design changes
for ensuring fault detection. Finally, a novel approach is
proposed for isolation of a set of faults, with proven isolation
guarantees under certain conditions. The effectiveness of the
proposed approaches is illustrated on an HVAC system.
R EFERENCES
[1] R. Beard. Failure accommodation in linear systems through selfreorganization. PhD thesis, MIT, 1971.
[2] R. Nikoukhah. Guaranteed active failure detection and isolation for
linear dynamical systems. Automatica, 34(11):1345–1358, 1998.
[3] R. Nikoukhah and S. Campbell. Auxiliary signal design for active
failure detection in uncertain linear systems with a priori information.
Automatica, 42(2):219–228, 2006.
[4] F. Harirchi, S.Z. Yong, E. Jacobsen, and N. Ozay. Active model
discrimination with applications to fraud detection in smart buildings.
In IFAC World Congress, Toulouse, France, 2017.

[5] P. Frank and X. Ding. Survey of robust residual generation and
evaluation methods in observer-based fault detection systems. Journal
of Process Control, 7(6):403–424, 1997.
[6] R. Patton and J. Chen. Observer-based fault detection and isolation:
robustness and applications. Control Eng. Prac., 5(5):671–682, 1997.
[7] S. Simani, C. Fantuzzi, and R. J Patton. Model-based fault diagnosis
in dynamic systems using identification techniques. Springer Science
& Business Media, 2003.
[8] P. Frank. Advances in observer-based fault diagnosis. In International
Conference on Fault Diagnosis: TOOLDIAG, 1993.
[9] H. Sneider and P. M. Frank. Observer-based supervision and fault
detection in robots using nonlinear and fuzzy logic residual evaluation.
IEEE Trans. on Control Systems Technology, 4(3):274–282, 1996.
[10] H. Hammouri, M. Kinnaert, and E. H. El Yaagoubi. Observer-based
approach to fault detection and isolation for nonlinear systems. IEEE
Transactions on Automatic Control, 44(10):1879–1884, 1999.
[11] S. Paoletti, A. Garulli, J. Roll, and A. Vicino. A necessary and
sufficient condition for input-output realization of switched affine state
space models. In IEEE CDC, pages 935–940, 2008.
[12] A. Abdo, S. X. Ding, J. Saijai, and W. Damlakhi. Fault detection
for switched systems based on a deterministic method. In IEEE
Conference on Decision and Control (CDC), pages 568–573, 2012.
[13] W. Pan, Y. Yuan, H. Sandberg, J. Gonçalves, and G. Stan. Online fault
diagnosis for nonlinear power systems. Automatica, 55:27–36, 2015.
[14] S. Narasimhan and G. Biswas. Model-based diagnosis of hybrid
systems. IEEE Transactions on Systems, Man, and Cybernetics, Part
A, 37(3):348–361, 2007.
[15] R. Isermann. Fault diagnosis of machines via parameter estimation
and knowledge processing–tutorial paper. Automatica, 29(4):815–835,
1993.
[16] X. Liu, H. Zhang, J. Liu, and J. Yang. Fault detection and diagnosis of
permanent-magnet dc motor based on parameter estimation and neural
network. IEEE Trans. on Ind. Electronics, 47(5):1021–1030, 2000.
[17] S. Campbell and R. Nikoukhah. Auxiliary signal design for failure
detection. Princeton University Press, 2004.
[18] J. K. Scott, R. Findeisen, R. D Braatz, and D. M. Raimondo. Input
design for guaranteed fault diagnosis using zonotopes. Automatica,
50(6):1580–1589, 2014.
[19] P. Rosa, C. Silvestre, J. S. Shamma, and M. Athans. Fault detection
and isolation of ltv systems using set-valued observers. In IEEE
Conference on Decision and Control (CDC), pages 768–773, 2010.
[20] F. Harirchi and N. Ozay. Model invalidation for switched affine
systems with applications to fault and anomaly detection. IFAC ADHS
Conference, 48(27):260–266, 2015.
[21] F. Harirchi, Z. Luo, and N. Ozay. Model (in)validation and fault detection for systems with polynomial state-space models. In American
Control Conference (ACC), pages 1017–1023, July 2016.
[22] J. Anderson and A. Papachristodoulou. On validation and invalidation
of biological models. BMC Bioinformatics, 10(1):1, 2009.
[23] N. Ozay, M. Sznaier, and C. Lagoa. Convex certificates for model
(in)validation of switched affine systems with unknown switches.
IEEE Transactions on Automatic Control, 59(11):2921–2932, 2014.
[24] H. Lou and P. Si. The distinguishability of linear control systems.
Nonlinear Analysis: Hybrid Systems, 3(1):21–38, 2009.
[25] P. Rosa and C. Silvestre. On the distinguishability of discrete linear
time-invariant dynamic systems. In IEEE CDC-ECC, pages 3356–
3361, 2011.
[26] M. Babaali and M. Egerstedt. Observability of switched linear
systems. In International Workshop on Hybrid Systems: Computation
and Control, pages 48–63. Springer, 2004.
[27] E. Beale and J. Forrest. Global optimization using special ordered
sets. Mathematical Programming, 10(1):52–69, 1976.
[28] C. Guéret, C. Prins, and M. Sevaux. Applications of optimization with
xpress-mp. contract, page 00034, 1999.
[29] F. Harirchi and N. Ozay. Guaranteed model-based fault detection in cyber-physical systems: A model invalidation approach.
arXiv:1609.05921 [math.OC], 2016.
[30] Inc. Gurobi Optimization. Gurobi optimizer reference manual, 2015.
[31] IBM ILOG CPLEX. V12. 1: User’s manual for cplex. International
Business Machines Corporation, 46(53):157, 2009.
[32] B. Argüello-Serrano and M. Vélez-Reyes. Nonlinear control of a
heating, ventilating, and air conditioning system with thermal load
estimation. IEEE Trans. on Control Systems Tech., 7(1):56–63, 1999.
[33] J. Löfberg. YALMIP: A toolbox for modeling and optimization in
MATLAB. In CACSD Conference, Taipei, Taiwan, 2004.

