Diagnosing multiple-component systems is difficult and computationally expensive, as the amount of fault hypotheses grows exponentially with the number of components in the system. This paper proposes an efficient computation structure 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) partitioning the overall system into subsystems, within which there is likely to be a single fault. This partitioning enables applying single-fault diagnosis, which has only linear complexity, to the subsystems without the need to handle the 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.
Liu, J. J.; de Kleer, J.; Kuhn, L. Computationally efficient tiered inference for multiple fault diagnosis. Proceedings of the Eighth Symposium on Abstraction, Reformulation and Approximation (SARA 2009); 2009 July 7-10; Lake Arrowhead, CA. Menlo Park, CA: AAAI Press; 2009.