Hierarchical diagnosis of multiple faults

Sajjad Siddiqi, Jinbo Huang

    Research output: Contribution to journalConference articlepeer-review

    60 Citations (Scopus)

    Abstract

    Due to large search spaces, diagnosis of combinational circuits is often practical for finding only single and double faults. In principle, system models can be compiled into a tractable representation (such as DNNF) on which faults of arbitrary cardinality can be found efficiently. For large circuits, however, compilation can become a bottleneck due to the large number of variables necessary to model the health of individual gates. We propose a novel method that greatly reduces this number, allowing the compilation, as well as the diagnosis, to scale to larger circuits. The basic idea is to identify regions of a circuit, called cones, that are dominated by single gates, and model the health of each cone with a single health variable. When a cone is found to be possibly faulty, we diagnose it by again identifying the cones inside it, and so on, until we reach a base case. We show that results combined from these hierarchical sessions are sound and complete with respect to minimum-cardinality diagnoses. We implement this method on top of the diagnoser developed by Huang and Darwiche in 2005, and present evidence that it significantly improves the efficiency and scalability of diagnosis on the ISCAS-85 circuits.

    Original languageEnglish
    Pages (from-to)581-586
    Number of pages6
    JournalIJCAI International Joint Conference on Artificial Intelligence
    Publication statusPublished - 2007
    Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
    Duration: 6 Jan 200712 Jan 2007

    Fingerprint

    Dive into the research topics of 'Hierarchical diagnosis of multiple faults'. Together they form a unique fingerprint.

    Cite this