A Structural Algorithm for Finding Testable Sub-models and Multiple Fault Isolability Analysis



Mattias Krysander Jan Aslund Erik Frisk


Structural methods have previously been used to perform isolability analysis and finding testable sub-models, so called Minimal Structurally Overdetermined (MSO) sets, Analytical Redundancy Relations (ARR), or Possible Conflicts (PC). The number of MSO sets grows exponentially in the degree of redundancy making the task of computing MSO sets intractable for systems with high degree of redundancy. This paper describes an efficient graph-theoretical algorithm for computing a similar, but smaller, set of testable submodels called Test Equation Supports (TES). A key difference, compared to an MSO based approach, is that the influence of faults is taken into account and the resulting number of testable models as well as the computational complexity of finding them can be reduced significantly without reducing the possible diagnosis performance. It is shown that the TESs in a direct way characterize the complete multiple fault isolability property of a model and thus extends previous structural approaches from the single-fault case.

How to Cite

Krysander, M., Aslund, J., & Frisk, E. (2010). A Structural Algorithm for Finding Testable Sub-models and Multiple Fault Isolability Analysis. Annual Conference of the PHM Society, 2(2). https://doi.org/10.36001/phmconf.2010.v2i1.1940
Abstract 4 |



diagnosis, fault isolation, diagnosability analysis, multiple faults, structural analysis

(Armengol et al., 2009 ) J. Armengol, A. Bregon, T. Escobet, E. Gelso, M. Krysander, M. Nyberg, X. Olive, B. Pulido, and L. Trav´e-Massuy`es. Minimal Structurally Overdetermined sets for residual generation: A comparison of alternative approaches. In Proceedings of the 7th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes, SAFEPROCESS09, pages 1480–1485, Barcelona, Spain, 2009.

(Blanke et al., 2006 ) M. Blanke, M. Kinnaert, J. Lunze, and M. Staroswiecki. Diagnosis and Fault-Tolerant Control. Springer, second edition, 2006.

(de Kleer and Williams, 1987 ) J. de Kleer and B.C. Williams. Diagnosing multiple faults. Artificial Intelligence, 32(1):97–130, 1987.

(Dulmage and Mendelsohn, 1958 ) A. L. Dulmage and N. S. Mendelsohn. Coverings of bipartite graphs. Canadian Journal of Mathematics, 10:517–534, 1958.

(Frisk et al., 2009 ) E. Frisk, M. Krysander, and J. Aslund. Sensor Placement for Fault Isolation in Linear Differential-Algebraic Systems. Automatica, 45(2):364–371, 2009.

(Gelso et al., 2008 ) E.R. Gelso, S.M. Castillo, and J. Armengol. An algorithm based on structural analysis for model-based fault diagnosis. In Artificial Intelligence Research and Development. Frontiers in Artificial Intelligence and Applications, volume 184, pages 138–147. IOS Press, 2008.

(Gertler, 1998 ) J. Gertler. Fault Detection and Diagnosis in Engineering Systems. Marcel Dekker, Inc., 1998.

(Krysander and Frisk, 2008 ) M. Krysander and E. Frisk. Sensor placement for fault diagnosis. IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans, 38(6):1398–1410, 2008.

(Krysander et al., 2008 ) Mattias Krysander, Jan Aslund, and Mattias Nyberg. An efficient algorithm for finding minimal over-constrained sub-systems for model-based diagnosis. IEEE Transactions on Systems, Man, and Cybernetics – Part A: Systems and Humans, 38(1), 2008.

(Krysander, 2006 ) Mattias Krysander. Design and Analysis of Diagnosis Systems Using Structural Methods. PhD thesis, Link¨opings universitet, June 2006.

(Pucel et al., 2009 ) X. Pucel, W. Mayer, and M. Stumptner. Diagnosability analysis without fault models. In 20th International Workshop on Principles of Diagnosis (DX-09), pages 67–74, Stockholm, Sweden, 2009.

(Pulido and Alonso-Gonz´alez, 2004 ) B. Pulido and C. Alonso-Gonz´alez. Possible Conflicts: a compilation technique for consistencybased diagnosis. IEEE Trans. on Systems, Man, and Cybernetics. Part B: Cybernetics, 34(5):2192–2206, Octubre 2004.

( Reiter, 1987 ) R. Reiter. A Theory of Diagnosis from First Principles. Artificial Intelligence, 32:57–95, 1987.

(Trav´e-Massuy`es et al., 2006 ) L. Trav´e-Massuy`es, T. Escobet, and X. Olive. Diagnosability analysis based on component-supported analytical redundancy relations. IEEE Transaction on Systems, Man, and Cybernetics – Part A, 36(6):1146–1160, 2006.
Technical Papers