Computationally efficient tiered inference for multiple fault diagnosis


Event SARA 2009


Liu, Juan J.
Kuhn, Lukas
Technical Publications
July 7th 2009
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.

Additional information

Focus Areas

Our work is centered around a series of Focus Areas that we believe are the future of science and technology.

Licensing & Commercialization Opportunities

We’re continually developing new technologies, many of which are available for¬†Commercialization.


PARC scientists and staffers are active members and contributors to the science and technology communities.