Nowadays, a large number of practical systems in aerospace and industrial environments are best represented as hybrid systems that consist of discrete modes of behavior, each defined by a set of continuous dynamics. These hybrid dynamics make the on-line fault diagnosis task very challenging. In this work, we present a new modeling and diagnosis framework for hybrid systems. Models are composed from sets of user-defined components using a compositional modeling approach. Submodels for residual generation are then generated for a given mode, and reconfigured efficiently when the mode changes. Efficient reconfiguration is established by exploiting causality information within the hybrid system models. The submodels can then be used for fault diagnosis based on residual generation and analysis. We demonstrate the efficient causality reassignment, submodel reconfiguration, and residual generation for fault diagnosis using an electrical circuit case study.
Robust and efficient fault diagnosis plays an important role in ensuring the safe, correct, and efficient operation of complex engineering systems. Many engineering systems are modeled as hybrid systems that have both continuous and discreteevent dynamics, and for such systems, the complexity of fault diagnosis methodologies increases significantly. In this paper, we develop a new modeling framework and structural model decomposition approach that enable efficient online fault diagnosis of hybrid systems.
During the last few years, different proposals have been
made for hybrid systems diagnosis, focusing on either
hybrid modeling, such as hybrid automata [
One solution to the mode pre-enumeration problem is to
build hybrid system models in a compositional way, where
discrete modes are defined at a local level (e.g., at the
component level), in which the system-level mode is defined
implicitly by the local component-level modes. Since this
allows the modeler to focus on the discrete behavior only at
the component level, the pre-enumeration of all the
systemlevel modes can be avoided [
In a system model, the effects of mode changes in
individual components may force other components to reconfigure
their computational structures, or causality, during the
simulation process, which requires developing efficient online
causality reassignment procedures. As an example of this
kind of approach, Hybrid Bond Graphs (HBGs) [
In this work, we propose a compositional modeling
approach for hybrid systems, where models are made up of
sets of user-defined components. Here, a component is
constructed by defining a set of discrete modes, with a different
set of mathematical constraints describing the continuous
dynamics in each mode. Then, we borrow ideas for efficient
causality reassignment in HBGs [
The paper is organized as follows. Section 2 presents the modeling approach and introduces the case study. Section 3 presents the overall approach for hybrid systems fault diagnosis based on structural model decomposition. Section 4 develops the causality analysis and assignment algorithms.
Section 5 presents the structural model decomposition apSw1
C1
R1
Sw2
R2 C2 i11 v(t) proach. Section 6 describes efficient causality reassignment. Section 7 demonstrates the approach for the electrical case study. Section 8 reviews the related work and current approaches for hybrid systems fault diagnosis. Finally, Section 9 concludes the paper. 2
We define hybrid system dynamics in a general compositional way, where the system is made up of a set of components. Each component is defined by a set of discrete modes, with a different set of constraints describing the continuous dynamics of the component in each mode. Here, system-level modes are defined implicitly through the composition of the component-level modes. Because the number of system-level modes is exponential in the number of switching components, we want to avoid generating and reasoning over the system-level hybrid model, instead working directly with the component models.
To illustrate our proposal, throughout the paper we will use a circuit example, shown in Fig. 1. The components of the circuit are a voltage source, V, two capacitors, C1 and C2, two inductors, L1 and L2, two resistors, R1 and R2, and two switches, Sw1 and Sw2, as well as components for series and parallel connections. Sensors measure the current or voltage in different locations (i3, v8, and i11, as indicated in Fig. 1). Because each switch has two modes (on and off), there are four total modes in the system.
In the following, we present the main details of our
hybrid system modeling framework, which may be viewed as
an extension of our modeling approach described in [
At the basic level, the continuous dynamics of a component in each mode are modeled using a set of variables and a set of constraints. A constraint is defined as follows: Definition 1 (Constraint). A constraint c is a tuple (εc, Vc), where εc is an equation involving variables Vc.
A component is defined by a set of constraints over a set of variables. The constraints are partitioned into different sets, one for each component mode. A component is then defined as follows: Definition 2 (Component). A component δ with n discrete modes is a tuple δ = (Vδ, Cδ), where Vδ is a set of variables and Cδ is a set of constraints sets, where Cδ is defined as Cδ = {C1, Cδ2, . . . , Cδn}, with a constraint set, Cδm, defined δ for each mode m = {1, . . . , n}.
The components of the circuit are defined in Table 1 (first three columns).
Example 1. Consider the component R1 (δ6). It has only a single mode with a single constraint v5 = i5 ∗ R1 over variables {v5, i5, R1}.
Example 2. Consider the component Sw2 (δ10). It has two modes: on and off. In the off mode, it has three constraints setting each of its currents (i9, i10, i11) to 0. In the on mode, it has also three constraints, setting the three currents equal to each other and establishing that the voltages sum up (it acts like a series connection when in the on mode).
We can define a system model by composing components: Definition 3 (Model). A model M = {δ1, δ2, . . . , δd} is a finite set ofd components for d ∈ N.
Example 3. The model of the electrical system is made up of the components detailed in Table 1, i.e., M = {δ1, δ2, . . . , δ15}. For each component, the variables and constraints are defined for each component mode (third column).
Note that the set of variables for a model does not change with the mode, hence we need only a variable set in a component and not a set of variable sets as with constraints. The set of variables for a model, VM, is simply the union of all the component variable sets, i.e., for d components, VM = Vδ1 ∪ Vδ2 ∪ . . . ∪ Vδd . The interconnection structure of the model is captured using shared variables between components, i.e., we say that two components are connected if they share a variable, i.e., components δi and δj are connected if Vδi ∩ Vδj 6= ∅. VM consists of five disjoint sets, namely, the set of state variables, XM; the set of parameters, ΘM; the set of inputs (variables not computed by any constraint), UM; the set of outputs (variables not used to compute any other variables), YM; and the set of auxiliary variables, AM. Parameters, ΘM, include explicit model parameters that are used in the model constraints (e.g., fault parameters). Auxiliary variables, AM, are additional variables that are algebraically related to the state, parameter, and input variables, and are used to simplify the structure of the equations.
Example 4. In the circuit model, we have XM = {i3, v6, i8, v11}, ΘM = {L1, R1, C1, L2, R2, C2}, UM = {uv}, and YM = {i3∗, i1∗1, v8∗}. Remaining variables belong to AM. Here, the ∗ superscript is used to denote a measured value of a physical variable, e.g., i3 ∈ XM is the current and i3∗ ∈ YM is the measured current. Since i3 is used to compute other variables, like i2, it cannot belong to YM and a separation of the variables is required. Connected components are known by shared variables, e.g., R1 and Series Connection1 are connected because they share i5 and v5.
The model constraints, CM, are a union of the component constraints over all modes, i.e., CM = Cδ1 ∪ Cδ2 ∪ . . . ∪ Cδd , where Cδi = Cδ1i ∪ Cδ2i ∪ . . . ∪ Cδni for n modes. Constraints are exclusive to components, that is, a constraint c ∈ CM belongs to exactly one Cδ for δ ∈ M.
To refer to a particular mode of a model we use the concept of a mode vector. A mode vector m specifies the current mode of each of the components of a model. So, the constraints for a mode m are denoted as Cm .
M
Example 5. Consider a model with five components, then
if m = [
i2 v8∗ i11 i1∗1 δ3: Parallel Connection1 1 δ4: L1 δ5: Series Connection1 δ8: Parallel Connection2 1
For shorthand, we will refer to the modes only of the
components with multiple modes. So, for the circuit, we will
refer only to components δ2 and δ10, and we will have four
possible mode vectors, [
The switching behavior of each component can be
defined using a finite state machine or a similar type of control
specification. The state transitions may be attributed to
controlled or autonomous events. However, for the purposes of
this paper, we view the switching behavior as a black box
where the mode change event is given, and refer the reader
to many of the approaches already proposed in the literature
for modeling the switching behavior [
Given a constraint c, which belongs to a specific mode of a specific component, the notion of acausal assignment is used to specify a possible computational direction, or causality, for the constraint c. This is done by defining whichv ∈ Vc is the dependent variable in equation εc.
Definition 4 (Causal Assignment). A causal assignment αc to a constraint c = (εc, Vc) is a tuple αc = (c, vcout), where vcout ∈ Vc is assigned as the dependent variable in εc. We wusheeVrecinVction d=enVocte−th{eviconudte}p.endent variables in the constraint,
In general, the set of possible causal assignments for a constraint c is as big as Vc, because each variable in Vc can act as vout. However, in some cases some causal assignc ments may not be possible, e.g., if we have noninvertible nonlinear constraints. Also, if we assume integral causality, then state variables must always be computed via integration, and so the derivative causality is not allowed. Further, when placed in the context of a model, additional causalities may not be applicable, because the causal assignments of other constraints may limit the potential causal assignments. To denote this concept, we use Ac to refer to the set of permissible causal assignments of a constraint c.
For a given mode, we have the set of (specific) causal assignments over the entire model in its mode, denoted using Am. So, some α ∈ Am would refer to the causal assignment of some constraint in some component of the model in its correct mode. The consistency of the causal assignments Am is defined as follows, Definition 5 (Consistent Causal Assignments). Given a mode m, we say that a set of causal assignments Am, for a model M is consistent if (i) for all v ∈ UM ∪ ΘM, Am does not contain any α such that α = (c, v), i.e., input or parameter variables cannot be the dependent variables in the causal assignment; (ii) for all v ∈ YM, Am does not contain any α = (c, vcout) where v ∈ Vcin, i.e., an output variable can only be used as the dependent variable; and (iii) for all v ∈ VM − UM − ΘM, Am contains exactly one α = (c, v), i.e., every variable that is not an input or parameter is computed by only one (causal) constraint.
With causality information, we can efficiently derive a set
of submodels for residual generation [
We propose a hybrid systems diagnosis approach based on structural model decomposition. In this approach, we generate submodels for the purpose of computing residuals. Residuals can then be used for diagnosis.
For hybrid systems, however, the problem is that these
submodels may change as the result of a mode change. That is,
we may obtain two different submodels when decomposing
the model in two different modes. There are two approaches
to this problem. One is to find a set of submodels that work
for all modes, and can be easily reconfigured by executing
only local mode changes within the submodels [
In order to execute this type of approach, however, we must be able to efficiently reconfigure submodels online. In order to do this, we take advantage of causality in two ways. First, we perform an offline model analysis to determine which causalities of the hybrid system model are not permissible, i.e., they will never be used in any mode of the system (determine AM for a model). Second, we use an efficient causality reassignment algorithm, so that the causality of a hybrid systems model is updated incrementally when a mode changes (given A for the previous mode, compute it for the new mode). Since causal changes usually only propagate in a local area in the model, causality does not need to be reassigned at the global model level. Together, these algorithms reduce the number of potential causalities to search within the model decomposition algorithm and allow efficient submodel reconfiguration. 4
In order to compute minimal submodels for residual generation, we need a model M with a valid causal assignment Am. As described in Section 2, causality assignment can only be defined for a given mode. However, there are some causal assignments that are independent of the system mode, i.e., they are valid for all system modes. We capture this through the notion of permissible causal assignments, introduced as AM in Section 2.
Given a model with a number of modes, some constraints will always have the same causal assignment in all modes, and we say these constraints are in fixed causality . Definition 6 (Fixed Causality). A constraint cδ is in fixed causality if (i) component δ has only a single mode, i.e., |Cδ| = 1, and (ii) for cδ in the single C ∈ Cδ, it always has the same causal assignment in all system modes.
If a constraint is in fixed causality, then |Ac| = 1, i.e., there is only one permissible causal assignment. For example, if we make the integral causality assumption, then constraints computing state variables will always be in the integral causality, and thus they are in fixed causality.
Additionally, when the constraint is viewed in the context of the model, the concept of fixed causality can be propagated from one constraint to the related constraints (those sharing a variable with the fixed causality constraint). This will help to reduce the number of permissible causal assignments. For example, if we again assume integral causality, then any constraint involving a state variable cannot be in a causal assignment where the state variable is the dependent/output variable, because the integration constraint is the one that must compute it. For such a constraint, 1 < |Ac| < |Vc|.
Given a system model and a set of outputs, Algorithm 1 searches over the model constraints to reduce the set of permissible causal constraints based on system-level information.1 First, it determines which constraints are mode-variant, i.e, they can appear/disappear from the model depending on the mode (so belong to components with multiple modes), and which are mode-invariant, i.e., they are present in all system modes (so belong to components with a single mode). It is only the mode-invariant constraints for which causal assignments can be removed. We then construct a queue of variables from which to propagate. This queue contains the inputs and parameters (which must always be independent/input variables in constraints), and the outputs (which must always be dependent/output variables in constraints). We create a variable set V that refers to the variables that are resolved, i.e., either they are inputs/parameters or there is a constraint with a single causal assignment that will compute the variable. So, V is initially set to include UM and ΘM. Further, for any mode-invariant constraints that only has a single causal assignment, the output variable is added to V , and all variables of the constraint added to the queue.
The main idea is to analyze the causality restrictions imposed by variables in the queue, which will be propagated throughout the model. While the queue is nonempty, we pop a variable v off the queue. We then count the number of constraints involving v that have no set causal assignment yet, including constraints that are both mode-variant and modeinvariant. We then go through all mode-invariant constraints involving v, and remove causal assignments that will never be possible. There are three conditions in which this holds: a causal assignment is not possible in any system mode if (i) the output variable is already computed by another constraint, or is an input/parameter (i.e., in V ), (ii) any of the input variables are in the model outputs (i.e., in Y ), or (iii) v is not yet computed by any constraint (i.e., not in V ), there is only one noncausal constraint involving v remaining, and v is not the output in this causality (in this case, v needs to be computed by some constraint and there is only one option left, so this constraint must only be in the causality computing v). These causal assignments are removed. If only one is left, then we add the output for that causal assignment to V , and add the constraint’s variables to the queue. The algorithm stops when causalities can no longer be removed, i.e., there are not enough restrictions imposed by the current permissible causalities to reduce AM further.
Example 6. For the circuit, we assume integral causality, so all constraints with the state variables are limited to causal assignments in which the states are computed via integration. Further, the constraint with uV is also fixed so thatuV is the independent variable. For any specified outputs,AM is also 1For structural model decomposition, some output variables may become input variables and so the causal assignments permitting that must be retained. Therefore, the algorithm only reduces the permissible set of causal assignments for a given set of outputs Y ⊆ YM. Algorithm 1 AM
← ReduceCausality(M, AM, Y ) 1: Cinvariant ← ∅ 2: Cvariant ← ∅ 3: for all δ ∈ M do 4: if |Cδ| = 1 then 5: Cinvariant ← Cinvariant ∪ Cδ1
7: reduced so that they can appear only as dependent variables.
With AM defined, we can perform causality assignment
for a given mode, m. Because AM was reduced as much as
possible, causality assignment (and, later, reassignment) will
be more efficient than otherwise. Algorithm 2 describes the
causality assignment process for a model given a mode. Here,
the model is assumed to not have an initial causal
assignment. Causal assignment works by propagating causal
restrictions throughout the model. The process starts at inputs,
which must always be independent variables in constraints;
outputs, which must always be the dependent variables in
constraints; and variables for involved in fixed causality
constraints. From these variables, we should be able to propagate
throughout the model and compute a valid causal assignment
for the model in the given mode. For the purposes of this
paper, we assume integral causality and that the model
possesses no algebraic loops.2 In this case, there is only one
valid causal assignment (this is a familiar concept within
bond graphs) [
Specifically, the algorithm works as follows. Similar to Algorithm 1, we keep a queue of variables to propagate causality restrictions, Q, and a set of variables that are computed in the current causality, V . Initially, V is set to U and Θ, because these variables are not to be computed by any constraint. Q is set to U , Θ, and Y , since the causality of 2If algebraic loops exist, the algorithm will terminate before all constraints have been assigned a causality. Extending the algorithm to handle algebraic loops is similar to that for bond graphs; a constraint without a causality assignment is assigned one arbitrarily, and then effects of this assignment are propagated until nothing more is forced. This process repeats until all constraints have been assigned causality.
Algorithm 2 A ← AssignCausality(M, m, A) 1: A ← ∅ 2: V ← UM ∪ ΘM 3: Q 4: for ←all UcM∈ C∪MΘmMd∪o YM 5: if |Ac| = 1 then 6: (c, v) ← Ac(1) 7: Q ← Q ∪ v 8: while |Q| > 0 do 9: v ← pop(Q) 10: for all c ∈ CMm (v) do 11: if c ∈/ {c : (c, v) ∈ A} then 12: α∗ ← ∅ 13: for all α ∈ Ac do 14: if Vc − {vα∗ } ∪ V 6= ∅ then 15: α∗ ← α 16: else if αv ∈ Y then 17: α∗ ← α 18: else if vα∗ = v and |CMm (v)|−|{c0 : (c0, v0) ∈ A∧v ∈ vc}| = 1 then 19: α∗ ← α 20: if α∗ 6= ∅ then 21: A ← A ∪ {α∗} 22: Q ← Q ∪ (Vc − V ) 23: V ← V ∪ {vα∗ } constraints is restricted to U and Θ variables being independent variables and Y variables being dependent variables. We add also to Q any variables involved in constraints that have only one permissible causal assignment, because this will also restrict other causal assignments. The set of causal assignments is maintained in A.
The algorithm goes through the queue, inspecting
variables. For a given variable, we obtain all constraints it is
involved in, and for each one that does not yet have a causal
assignment (in A), we go through all permissible causal
assignments, and determine if the causality is forced into one
particular causal assignment, α∗. If so, we assign that
causality and propagate by adding the involved variables to the
queue. A causal assignment α = (c, v) is forced in one of
three cases: (i) v is in Y , (ii) all variables other than v of the
constraint are already in V , and (iii) v is not yet in V , and
all but one of the constraints involving v have an assigned
causality, in which case no constraint is computing v and
there is only one remaining constraint that must compute v.
Example 7. Consider the mode m = [
Example 8. Consider the mode m = [
3Note that this particular circuit was carefully chosen so that causality does propagate across much of the circuit, in order to demonstrate the causality reassignment algorithm. 5
For a given causal model in a given mode, we have the
equivalent of a continuous systems model for the purpose of
structural model decomposition, and we can compute
minimal submodels using the GenerateSubmodel algorithm
described in our previous work [
In the context of residual generation, we set the local output set to a single measured value, and the local inputs to all other measured values and the (known) system inputs. That is, we exploit the analytical redundancy provided by the sensors in order to find minimal submodels to compute estimated values of sensor outputs. In this framework, we consider one submodel per sensor, each producing estimated values for that sensor.
Assuming that the set of sensors does not change from mode to mode, then for a hybrid system we have one submodel for each sensor.4 However, since the set of constraints changes from mode to mode, the result of the GenerateSubmodel algorithm will also change. When a mode changes, we first reassign causality to the model for the new mode. Then, we generate new updated submodels for that mode using GenerateSubmodel. In order to reduce the work performed by this algorithm when a mode changes, we use an efficient causality reassignment algorithm. That, coupled with the reduced set AM, significantly reduces the work of the algorithm compared to a naive approach, where the submodels are completely regenerated for a new mode. Additionally, when the system transitions to a new mode, the causal assignments for the previous mode can be stored, so that when the system changes to a mode that has already been visited, it just takes the causal assignments that were stored previously. Similarly, submodels generated in previously visited modes can be saved and reused when the mode reappears.
Example 9. The causal assignments for the submodels in the
different modes are shown in Table 1. For example, consider
the submodel for i1∗1 in m = [
Note that a submodel for an output may have different
states in two different modes (e.g., in moving from m = [
5If this is not the case, then a state is not observable in some ←
ReassignCausality(M, m,AAm, A) a submodel that gets a state added in a new mode can initialize using the estimated value from another submodel in the previous mode. 6
As we mentioned before, from the initial mode in the system
with a valid set of causal assignments, we compute minimal
submodels. However, when the system transitions to a
different mode, any submodel containing constraints of a
switching component will no longer be consistent, and must be
recomputed. In order to do this, we need to know the causal
assignments for the new mode. We can reassign causality in
an efficient incremental process to avoid having to reassign
causality to the whole model, as causal changes typically
propagate only to a small local area in the model [
Algorithm 3 presents the causality reassignment procedure.
The main ideas are based on the hybrid sequential causality
assignment procedure (HSCAP) developed for hybrid bond
graphs in [
10 8 6 ) A ∗i(3 4 2 0 2 0 0 )-2 V ∗ (8 v-4 -6 -8
0 2 0 ) A (-2 ∗i11 -4 -6 5 5 10 10
15
Time (s) (a) i3∗.
15
Time (s) (b) v8∗
15
Time (s) (c) i1∗1 The algorithm works similarly to Algorithm 2. It maintains a queue of variables to inspect and a set V of variables that are known to be computed in the causality for the new mode (so includes only variables from new assignments or confirmed assignments made in the new mode). In this case, we initialize the queue only to variables involved in the constraints of the switching components. If no components are switching, the queue will be empty and no work will be done. The main idea is that the required causal changes from the variables placed in the queue will, on average, be limited to a very small area. The causal assignments for the new mode are initialized to those for the previous mode, for any constraints that still exist in the new mode. Some of these may conflict with the new mode and will be removed and replaced with different assignments.
As in all the other causality algorithms, we go through the queue and propagate the restrictions we find on causality. We pop a variable off the queue, and look at all involved constraints. If the constraint is not causal, then we need to assign causality. We do the same analysis as before to find if a causality is forced, but checking things only with respect to V that includes only variables with confirmed causal assignments computing it in the new mode. If we find a constraint that is forced into a particular causal assignment for the new mode, we make the assignment. If it conflicts with one already in the set of causal assignments (copied from the old mode), then we remove the old assignment and add the new one, adding the involved variables to the queue so that changes are propagated. 7
For the circuit example, we consider two modes: one where
Sw1 is on and Sw2 is off (i.e., m = [
Fig. 2 shows the measured and submodel-estimated values
for the sensors. Up through the first mode change, the outputs
are correctly tracked by the submodels. At the first mode
change at 10 s, the submodels reconfigure and track correctly
up to 15 s, when the fault is injected, and a discrepancy
is observed in the i3∗ submodel. Specifically, the current
increases above what is expected. The other submodels in
this mode are independent of the fault, and so continue to
track correctly. When the second mode change occurs, i1∗1
can still be tracked correctly, since its estimation remains
independent of the fault. However, we now see a discrepancy
in v8∗, as the measurement increases above what is expected.
This transient occurs because we switch from a mode in
which the submodel is independent of the fault to one where
it is dependent on the fault. Fault isolation can be performed
by using the information that in m = [
Modeling and diagnosis for hybrid systems have been an important focus of study for researchers from both the FDI and DX communities during the last 15 years. In the FDI community, several hybrid system diagnosis approaches have been Measured Estimated Measured Estimated Measured
Estimated 20 25
30
20
25
30
0
5
10
20
25
30
developed. In [
In the DX community, some approaches have used
different kind of automata to model the complete set of modes and
transitions between them. In those cases, the main research
topic has been hybrid system state estimation, which has has
been done using probabilistic (e.g., some kind of filter [
Another solution has been to use an automaton to track the
system mode, and then use a different technique to diagnose
the continuous behavior (for example, using a set of ARRs
for each mode [
Regarding hybrid systems modeling, there are several
proposals. For HBGs [
In this work, we have developed a compositional modeling
framework for hybrid systems. Using computational
causality, we developed efficient causality assignment algorithms.
Given this causal information, submodels computed using
structural model decomposition can be computed and
reconfigured efficiently. The approach was demonstrated with a
circuit system. In future work, we will further develop the
hybrid systems diagnosis approach for the single and
multiple fault cases, and we will approach the diagnosis task in
a distributed manner. The assumption of one submodel per
sensor can also be dropped, using the extended framework
developed in [
This work has been funded by the Spanish MINECO DPI2013-45414-R grant and the NASA SMART-NAS project in the Airspace Operations and Safety Program of the Aeronautics Mission Directorate.