The issue of residual generation using structural analysis has been studied by several authors. Structural analysis does not permit to generate the analytical expressions of residuals since the model of the system is abstracted by its structure. However, it determines the set of constraints from which residuals can be generated and it provides the computation sequence to be used. This paper presents and compares four recently proposed algorithms that solve this problem.

The problem of adding a residual component to an MSS set to gain a solvable model is studied. Two main approaches can be found, the dynamic and the static approach.

A common approach to design diagnostic systems is to use residual generators. These generators are usually constructed considering all the model equations. However, there are several advantages of instead consider small subsets of model equations, so called minimal structurally singular (MSS) sets of equations. This paper presents a new method for finding residual generators for MSS sets. A special property of the MSS set, namely that it is minimally over determined, is utilized. Two approaches are considered, one which is based on the use of a dynamic numerical equation solver, and another which uses a static numerical equation solver. The approaches are demonstrated on a non-linear point-mass satellite system.

In fault diagnosis, the set of minimal diagnoses is commonly calculated. However, due to for example limited computation resources, the search for the set of minimal diagnoses is in some applications focused on to the smaller set of diagnoses with minimal cardinality. The key contribution in this paper is an algorithm that calculates the diagnoses with minimal cardinality in a distributed system. The algorithm is constructed such that the computationally intensive tasks are distributed to the different units in the distributed system, and thereby reduces the need for a powerful central diagnostic unit. © 2007 Elsevier Ltd. All rights reserved.

In systems using only single-component tests, the fault status of a component is ready if a test only supervising the component has been evaluated. However, if plausibility tests that supervise multiple components are used, then a component can be ready before all tests supervising the component have been evaluated. Based on test results, this paper contributes with conditions on when a component is ready. The conditions on readiness are given for both centralized and distributed systems and are here applied to the distributed diagnostic system in an automotive vehicle.

Requirement verification is an important part of the development process, and the increasing system complexity has exacerbated the need for integrating this step into a formalized model driven development process, providing a dedicated methodology as well as tool support. In this paper the authors propose an extension for Modelica, an equation-based language for system modeling, that will allow to represent system requirements in the same formalism as the design model, thus reducing the need for transformations between different specialized formalisms, lowering maintenance and modification costs, and benefitting from the expression and simulation capabilities, as well as extensive tool support of Modelica. The object-oriented nature of the approach provides the advantages of modular design and hierarchical structuring of the requirement model. This paper also illustrates, with the help of an example, how requirement verification can be used alongside the simulation process to trace the components responsible for requirement violations. To this end, we introduce a formalism for expressing relationships between components and requirements, as well as a tracing algorithm.

Design of diagnosis systems is a complex task that involves many different steps. Full understanding of all different parts of the design procedure requires deep knowledge on theory from a wide variety of subjects. Thus, to encourage the use of results from diagnosis research it is highly desirable to have software support in the design process. This paper describes ongoing work for determining an architecture for such a toolbox. The paper also describes software solutions in the toolbox. In industry as well as in universities, Matlab is probably the most widespread tool used by control engineers. Therefore the toolbox is primarily based upon Matlab but also some computer algebraic tools such as Mathematica and Maple are used.

A fundamental part of a fault diagnosis system is the residual generator. Here a new method, the minimal polynomial basis approach, for design of residual generators for linear systems, is presented. The residual generation problem is transformed into a problem of finding polynomial bases for null-spaces of polynomial matrices. This is a standard problem in established linear systems theory, which means that numerically efficient computational tools are generally available. It is shown that the minimal polynomial basis approach can find all possible residual generators and explicitly those of minimal order. © 2001 Elsevier Science Ltd. All rights reserved.

Linear residual generation for DAE systems has been considered. In all results derived, no distinction between input and output signals is done. A complete characterization and parameterization of all residual generators is presented. Further, a condition for fault detectability in DAE systems is given. Based on the characterization of all residual generators, a design strategy for residual generators for DAE systems is presented. Given that a set of faults are detectable, the design strategy will result in a residual generator sensitive to all the detectable faults. Further the residual generator is guaranteed to be of lowest possible order. Special care has been devoted to assure this property also for non-controllable systems.

This document is a demonstration document, demonstrating the use of the Polynomial Toolbox for Matlab when designing residual generators for fault diagnosis. A brief introduction to the residual generation problem for fault diagnosis in linear systems is given and a solution based on polynomial methods are outlined. Also, a design example, complete with \sc Matlab code illustrates how the Polynomial Toolbox can be used in the design of residual generators.

When designing model-based fault-diagnosis systems, the use of consistency relations (also called e.g. parity relations) is a common choice. Different subsets are sensitive to different subsets of faults, and thereby isolation can be achieved. This paper presents an algorithm for finding a small set of submodels that can be used to derive consistency relations with highest possible diagnosis capability. The algorithm handles differential algebraic models and is based on graph theoretical reasoning about structure of the model. An important step, towards finding these submodels and therefore also towards finding consistency relations, is to find all minimal structurally singular (MSS) sets of equations. These sets characterize the fault diagnosability.

Fault isolability plays a significant role and could be critical with respect to many aspects such as safety and maintenance for a process to be diagnosed. In the development of processes including diagnosis, design decisions are taken, e.g. sensor configuration selection, which affects the fault isolability possibilities. In this paper an algorithm for predicting fault isolability possibilities using a structural model describing the process is proposed. Since only a structural model is needed as input, the algorithm can easily predict fault isolability possibilities of different design concepts. In contrast to previous algorithms using structural models no assumption is imposed on the model. The algorithm computes faults that cannot be distinguished from other faults, which can be used to exclude design alternatives with insufficient isolability possibility.

Fault diagnosis in the presence of noise and model errors is of fundamental importance. In the paper, the meaning of fault isolation performance is formalized by using the established notion of coverage and false coverage from the field of statistics. Then formal relations describing the relationship between fault isolation performance and the residual related design parameters are derived. For small faults, the measures coverage and false coverage are not applicable so therefore, a different performance criteria, called sub-coverage, is proposed. The performance of different AI-based fault isolation schemes is evaluated and it is notably shown that the well known principle of minimal cardinality diagnosis gives a bad performance. Finally, some general design guidelines that guarantee and maximize the fault isolation performance are proposed.

When designing model-based fault-diagnostic systems, the use of consistency relations (also called e.g. parity relations) is a common choice. Different consistency relations are sensitive to different subsets of faults, and thereby isolation can be achieved. This report presents an algorithm for finding a small set of submodels that can be used to derive consistency relations with highest possible diagnosis capability. The algorithm handles differential-algebraic models and is based on graph theoretical reasoning about the structure of the model. An important step towards finding these submodels, and therefore also towards finding consistency relations, is to find all minimal structurally singular (MSS) sets of equations. These sets characterize the fault diagnosability. The algorithm is applied to a large nonlinear industrial example, a part of a paper plant. In spite of the complexity of this process, a small set of consistency relations with high diagnosis capability is successfully derived.

When designing model-based fault-diagnosis systems, the use of consistency relations (also called e.g. parity relations) is a common choice. Different subsets are sensitive to different subsets of faults, and thereby isolation can be achieved. This paper presents an algorithm for finding a small set of submodels that can be used to derive consistency relations with highest possible diagnosis capability. The algorithm handles differential algebraic models and is based on graph theoretical reasoning about structure of the model. An important step, towards finding these submodels and therefore also towards finding consistency relations, is to find all minimal structurally singular (MSS) sets of equations. These sets characterize the fault diagnosability. The algorithm is successfully applied to a large nonlinear industrial example, a paper plant.

When designing model-based fault-diagnosis systems, the use of consistency relations (also called e.g. parity relations) is a common choice. Different subsets are sensitive to different subsets of faults, and thereby isolation can be achieved. This paper presents an algorithm for finding a small set of submodels that can be used to derive consistency relations with highest possible diagnosis capability. The algorithm handles differential-algebraic models and is based on graph theoretical reasoning about the structure of the model. An important step, towards finding these submodels and therefore also towards finding consistency relations, is to find all minimal structurally singular (MSS) sets of equations. These sets characterize the fault diagnosability. The algorithm is applied to a large nonlinear industrial example, a part of a paper plant. In spite of the complexity of this process, a small set of consistency relations with high diagnosis capability is successfully derived.

In model based diagnosis, the diagnostic system construction is based on a model of the technical system to be diagnosed. To handle large differential algebraic models and to achieve fault isolation, a common strategy is to pick out small over-constrained parts of the model and to test these separately against measured signals. A new algorithm for computing all minimal over-constrained sub-systems in a model is proposed. For complexity comparison, previous algorithms are recalled. It is shown that the time complexity under certain conditions is much better for the new algorithm. This is illustrated using a truck engine model.

In this paper, a new algorithm for computing all minimal over-constrained sub-systems in a structural model is proposed. To handle large differential algebraic models in diagnosis, systematic structural approaches to find testable sub-systems have been suggested. It is shown how the algorithm can be incorporated and improve some of them. Previous algorithms are recalled and it is shown that the new algorithm is 14000 times faster when applied to a Scania truck engine model.

Issues concerning diagnosis, supervision and saftey are found in many technologically advanced products. There is now a trend to extend the functionality of diagnosis and supervision systems to handle more advanced situations. This report collects some of the initiatives taking place in research and some of the developments taking place in the industry.

Given a number of thresholded residuals, an algorithm for finding the diagnoses, i.e. possible faults, is presented. The algorithm is based on ideas used in diagnosis algorithms from the field of AI. It is capable of handling the case of multiple faults and multiple fault-types per component. The number of multiple faults is exponential in the number of components. To handle this complexity problem, logical formulas are used to efficiently represent diagnoses. The formulas obtained can easily be used to derive the set of all diagnoses or the set of most probable diagnoses.

A framework for fault diagnosis, called structured hypothesis tests, is presented. It has earlier been developed within the area of automatic control, but is in fact very much inspired by the ideas developed in the AI area. The motivation was originally to handle dynamic systems with noise. However, it is here shown that also the noise-free case can be perfectly handled. The system to be diagnosed, and also the different faults, are described by differential equations, algebraic equations, and probability distribution functions. By using the framework, it is in the isolation possible to utilize all such modeled knowledge about the faults. The diagnosis system is constructed by combining a set of different hypothesis tests. In this way, the task of diagnosis is transferred to the task of validating a set of different models with respect to the measured data.

A Generalization of the GDE Minimal Hitting-Set Algorithm to Handle Behavioral Modes Mattias Nyberg A generalization of the minimal hitting-set algorithm given by deKleer and Williams is presented. The original algorithm handles only one faulty mode per component and only positive conflicts. In contrast, the new algorithm presented here handles more than two modes per component and also non-positive conflicts. The algorithm computes a logical formula that characterizes all diagnoses. Instead of minimal diagnoses, or kernel diagnoses, some specific conjunctions in the logical formula are used to characterize the diagnoses. These conjunctions are a generalization of both minimal and kernel diagnoses. From the logical formulas, it is also easy to derive the set of preferred diagnoses.

To handle diagnosis with behavioral modes, a new generalized minimal hitting-set algorithm is presented. The key properties in comparison with that of the original minimal hitting-set algorithm given by de Kleer and Williams are that it can handle more than two modes per component and also nonpositive conflicts. The algorithm computes a logical formula that characterizes all diagnoses. Instead of minimal or kernel diagnoses, some specific conjunctions in the logical formula are used to characterize the diagnoses. These conjunctions are a generalization of both minimal and kernel diagnoses. From the logical formulas, it is also easy to derive the set of preferred diagnoses. One usage of the algorithm is fault isolation in the sense of fault detection and isolation (FDI). The algorithm is experimentally shown to provide significantly better performance compared to the fault isolation approach based on structured residuals, which is commonly used in FDI.

It is highly desirable to systematize and automate the process of designing diagnosis systems. The reason is that in many applications, high diagnosis performance is required, and at the same time, the time-consuming engineering work of designing diagnosis systems must be minimized. Here, model-based diagnosis based on structured hypothesis tests is considered. Principles for evaluating diagnosis systems are developed, and a systematic and automatic design procedure is proposed. The procedure is successfully applied to the problem of designing a diagnosis system for the air-intake system of an automotive engine. The resulting diagnosis system is then experimentally validated using a real engine.

A strategy for automatic optimal fuzzy system design is proposed and investgated. The fuzzy system chosen has been shown to be an universal approximator. The optimization technique is the algorithm Guided Evolutionary Simulated Annealing (GESA). It has strong similarities with a parallel simulated annealing algorithm which has been shown to be able to find any global optimum. The proposed design strategy is applied to two different problems: general function estimation in the form of the "generalized parity-2 problem" and control of an inverted pendulum. Good results are obtained and in the function estimation problem, it is shown experimentally that the approximation error decreases when the fuzzy partition increases. However parts of the design strategy are very computationally intensive. Because of the complexity of the GESA algorithm, it is suggested that more experience with GESA needs to be acquired and it would be desirable to make a simplification of GESA.

A fault is (strongly) detectable if it is possible to construct a residual generator that is sensitive to the (constant) fault while decoupling all disturbances. Existing fault detectability criterions are reviewed and in two cases, improved versions are derived. For strong fault detectability, three new criterions are presented. To prove all criterions, a framework of polynomial bases is utilized. With these new and improved criterions, there exists now a criterion for models given both on transfer function form and state-space form, and for both fault detectability and strong fault detectability investigations. Recommendations are given on what criterion to use in different situations.

Assuming residual generators are already available, there are still several choices to be made when a complete FDI system is to be designed. This is a time-consuming engineering work so for this purpose, a systematic procedure is proposed. The procedure is phrased as an optimization problem. The goal is to minimize a new probability based performance index, which is derived from measurements on the real process. To increase the robustness of the FDI system, a don’t care option is introduced in the residual structure. The procedure is successfully applied to the problem of FDI design for the air intake system of an SI-engine.

Two different methods for diagnosing leakage in the air-path of an automotive engine are investigated. The first is based on a comparison between measured and estimated air flows. The second is based on an estimation of the leakage area. The two methods are compared by using a framework of hypothesis testing and especially the power function. The investigation is made first in theory and then also on a real engine. The conclusion is that the principle based on the estimated leakage area, gives a better power function and is therefore the best choice if only leakage detection is considered. However, if also other faults need to be diagnosed, it is shown that the sensitivity to these other faults may be better with the principle based on comparison of estimated and measured air flow.

A general framework and a method for model based diagnosis are suggested. In the framework, faults and modeling of faults are formally described. Then the method is used to construct a diagnosis system based on a structure of hypothesis tests. Using these principles, it is possible to diagnose a large variety of different types of faults. The framework and the method are applied to the design of a diagnosis system for an automotive engine. This application clearly shows the strength of these principles because several different types of sensor faults and leakage need to be diagnosed. The resulting diagnosis system is demonstrated using experiments on a real automotive engine.

Many model based solutions to diagnosis problems in SI-engines have been discussed in literature. However most presented methods are useful only for a specific class of faults. Here a systematic and more general method is presented. With this method, which is based on a structure of hypothesis tests, it is possible to diagnose a large variety of different types of faults. The method is applied to the diagnosis of sensor-faults and leakage in the air-intake system of an SI-engine. The features of the method are demonstrated by using experiments on a real SI-engine. The experiments show that the method is capable to diagnose both leakage and different types of sensor faults. Both detection and isolation are considered. It is for example possible to distinguish between a manifold leak and a manifold pressure sensor fault.

A new framework for fault diagnosis, called structured hypothesis tests, is proposed. The basic idea is to construct the diagnosis system by combining a set of hypothesis tests. In this way, the task of diagnosis is transferred to the task of validating a set of different models with respect to the measured data. Arbitrary types of faults, including multiple faults, can be handled. That means that one single diagnosis system can diagnose faults of many different types. When using structured hypothesis tests, existing diagnosis methods such as residual generation, parameter estimation, and statistical methods, become parts of one common framework.

Model based fault diagnosis is to perform fault diagnosis by means of models. An important question is how to use the models to construct a diagnosis system. To develop a general theory for this, useful in real applications, is the topic of the first part of this thesis. The second part deals with design of linear residual generators and fault detectability analysis.

A general framework, for describing and analyzing diagnosis problems, is proposed. Within this framework a diagnosis method structured hypothesis tests is developed. It is based on general hypothesis testing and the task of diagnosis is transferred to the task of validating a set of different models with respect to the measured data. The procedure of deriving the diagnosis statement, i.e. the output from the diagnosis system, is in this method formalized and described by logic.

Arbitrary types of faults, including multiple faults, can be handled, both in the general framework and also in the method structured hypothesis tests. It is shown how well known methods for fault diagnosis fit into the general framework. Common methods such as residual generation, parameter estimation, and statistically based methods can be seen as different methods to generate test quantities within the method structured hypothesis tests.

Based on the general framework, a method for evaluating and comparing diagnosis systems is developed. Concepts from decision theory and statistics are used to define a performance measure, which reflects the probability of e.g. false alarm and missed detection. Based on the evaluation method, a procedure for automatic design of diagnosis systems is developed.

Within the framework, diagnosis systems for the air-intake system of automotive engines are designed. In one case, the procedure for automatic design is used. Also the methods for evaluation of diagnosis systems are applied. The whole design chain is described, including the modeling of the engine. All diagnosis systems are validated in experiments using data from a real engine. This application highlights the strengths of the method structured hypothesis tests, since a large variety of different faults need to be diagnosed. To the authors knowledge, the same problem can not be solved using previous methods.

In the second part of the thesis, linear residual generation is investigated by using a notion of polynomial bases for residual generators. It is shown that the order of such a basis doesn't need to be larger than the system order. Fault detectability, seen as a system property, is investigated. New criterions for fault detectability, and especially strong fault detectability, are given.

A new design method, the minimal polynomial basis approach, is presented. This method is capable of generating all residual generators, explicitly those of minimal order. Since the method is based on established theory for polynomial matrices, standard numerically efficient design tools are available. Also, the link to the well known Chow-Willsky scheme is investigated. It is concluded that in its original version, it has not the nice properties of the minimal polynomial basis approach.

Automotive engines is an important application for model-based diagnosis because of legislative regulations. A diagnosis system for the air-intake system of a turbo-charged engine is constructed. The design is made in a systematic way and follows a framework of hypothesis testing. Different types of sensor faults and leakages are considered. It is shown how many different types of fault models, e.g., additive and multiplicative faults, can be used within one common diagnosis system, and using the same underlying design principle. The diagnosis system is experimentally validated on a real engine using industry-standard dynamic test-cycles.

An important issue in diagnosis research is design methods for residual generation. One method is the Chow-Willsky scheme. Here an extension to the Chow-Willsky scheme, called the ULPE scheme is presented. It is shown that previous extensions to the Chow-Willsky scheme can not generate all possible parity equations for some linear systems. This is the case when there are dynamics controllable from fault but not from the inputs or disturbances. The ULPE scheme is able to handle also this case since it is, for both discrete and continuous linear systems, shown to be a universal design method for perfectly decoupling residual generators. Also included are two new straightforward conditions on the process for fault detectability and strong fault detectability respectively. A general condition for strong fault detectability has not been presented elsewhere. It is shown that fault detectability and strong fault detectability can be seen as system properties rather than properties of the residual generator.

Because of environmentally based legislative regulations, diagnosis of automotive engines has become increasingly important. In the design of diagnosis systems, it is important to strive for optimum performance and at the same time, minimize the amount of engineering work required. Therefore, it is desirable to have a highly automated design procedure, in which diagnosis performance is optimized. It is discussed how a diagnosis system for the air-intake system of an SI-engine, can be constructed with the help of automated tools. In particular the problem of residual and threshold selection is addressed. For this a fully automatic algorithm is proposed and it is experimentally shown that the algorithm successfully manage to generate a well functioning diagnosis system.

The POLYBOX example is a standard example within the AI-field of model-based diagnosis research. Here, this example is discussed in the perspective of structured hypothesis tests (SHT). Even though the SHT framework was primarily developed for handling systems with noise, it has here been shown that it can perform very well in also noise-free systems. In the POLYBOX example, it manage to always give a complete and logically sound diagnosis statement, i.e. a complete and correct list of the possible fault modes. On the contrary, the established FDI framework (i.e. structured residuals) only manage to give a subset of the possible fault modes.

Two different methods for diagnosing leakages in the air path of an automotive engine are investigated. The first is based on a comparison between measured and estimated air flows. The second is based on an estimation of the leakage area. The two methods are compared by using a framework of hypothesis testing and especially the power function. The investigation is made first in theory and then also on a real engine. The conclusion is that the principle based on the estimated leakage area, gives a better power function and is therefore the best choice if only leakage detection is considered. However, if also other faults need to be diagnosed, it is shown that the sensitivity to these other faults may be better with the principle based on comparison of estimated and measured air flow. © 2003 Elsevier Ltd. All rights reserved.

A fundamental part of a fault diagnosis system is the residual generator. Here a new method, the minimal polynomial basis approach, for design of residual generators for linear systems, is presented. The residual generation problem is transformed into a problem of finding polynomial bases for null-spaces of polynomial matrices. This is a standard problem in established linear systems theory, which means that numerically efficient computational tools are generally available. It is shown that the minimal polynomial basis approach can find all possible residual generators and explicitly those of minimal order.

Linear residual generation for differential-algebraic equation (DAE) systems is considered within a polynomial framework where a complete characterization and parameterization of all residual generators is presented. Further, a condition for fault detectability in DAE systems is given. Based on the characterization of all residual generators, a design strategy for residual generators for DAE systems is presented. The design strategy guarantees that the resulting residual generator is sensitive to all the detectable faults and also that the residual generator is of lowest possible order. In all results derived, no assumption about observability or controllability is needed. In particular, special care has been devoted to assure the lowest-order property also for non-controllable systems. © 2006 IEEE.