Computationally Efficient Tiered Inference for Multiple Fault Diagnosis



Published Mar 26, 2021
Juan Liu Lukas Kuhn Johan de Kleer


Diagnosing multiple-component systems is difficult and computationally expensive, as the number of fault hypotheses grows exponentially with the number of components in the system. This paper describes an efficient computational framework for statistical diagnosis featuring two main ideas: (1) structuring fault hypotheses into tiers, starting from low cardinality fault assumptions (e.g., single fault) and gradually escalating to higher cardinality (e.g., double faults, triple faults) when necessary; (2) at each tier, dynamically partitioning the overall system into subsystems, within which there is likely to be a single fault. The partition is based on correlation between the system components and is dynamic: when a particular partition is ruled out, a new one is constructed based on the updated belief. When no viable partition remains, the search proceeds to the next tier. This approach enables the use of single-fault diagnosis, which has only linear complexity, to the subsystems avoiding exponential hypothesis explosion. We demonstrate the concepts and implementation via examples and simulation. We analyze the performance and show that for practical systems where most components are functioning properly, the proposed scheme achieves a desirable tradeoff between computational cost and diagnosis accuracy.

How to Cite

Liu, J., Kuhn, L., & de Kleer, J. (2021). Computationally Efficient Tiered Inference for Multiple Fault Diagnosis. Annual Conference of the PHM Society, 1(1). Retrieved from
Abstract 142 | PDF Downloads 116



statistical model

(Berger, 1995) J. O. Berger. Statistical Decision Theory and Bayesian Analysis. Springer Verlay, New York, 1995.
(de Kleer and Williams, 1987) J. de Kleer and B. C. Williams. Diagnosing multiple faults. Artificial Intelligence, (32):97–130, 1987.
(Korf, 1995) Richard Korf. Optimal number partitioning. Technical report, also available at reports/, 1995.
(Kuhn and de Kleer, 2008) Lukas Kuhn and Johan de Kleer. An integrated approach to qualitative model-based diagnosis. In Qualitative Reasoning Workshop (QR 2008), Boulder, Colorado, USA, 2008.
(Pravan, 2001) G. Pravan. Hierarchical model-based diagnosis. In Proc. International Workshop on Principles of Diagnosis (DX), 2001.
(Reiter, 1987) R. Reiter. A theory of diagnosis from first principles. Artificial Intelligence, 32(1):57–96, 1987.
(Siddiqi and Huang, 2007) S. Siddiqi and J. Huang. Hierarchical diagnosis of multiple faults. In Proceedings of IJCAI, 2007.
(Srinivas, 1994) S. Srinivas. A probabilistic approach to hierarchical model-based diagnosis. In Proc.
Conference on Uncertainty in AI (UAI), pages 538– 545, 1994.
(Thiebuax et al., 1996) S. Thiebuax, M. Cordier, O. Jehl, and J. Krivine. Supply restoration in power distribution systems – a case study in integrating model-based diagnosis and repair planning. In Prof.8th International Workshop on Principles of Diagnosis (DX), 1996.
Technical Research Papers

Most read articles by the same author(s)