Probabilistic sequential diagnosis by compilation

Sajjad Siddiqi*, Jinbo Huang

*Corresponding author for this work

    Research output: Contribution to conferencePaperpeer-review

    6 Citations (Scopus)

    Abstract

    When a system behaves abnormally, a diagnosis is a set of system components whose failure explains the abnormality. It is known that compiling the system model into deterministic decomposable negation normal form (d-DNNF) allows efficient computation of the complete set of diagnoses. We extend this approach to sequential diagnosis, where a sequence of measurements is taken to narrow down the set of diagnoses until the actual faults are identified. We propose novel probabilistic heuristics to reduce the diagnostic cost, defined as the number of measurements. Our heuristics involve the posterior probabilities of component failures and the entropies of measurement points. The structure of the system is exploited so that a joint probability distribution over the faults and system variables is represented compactly as a Bayesian network, which is then compiled into d-DNNF. All posterior probabilities required are computed exactly and efficiently by traversing the d-DNNF. Finally, we scale the approach further by performing the diagnosis in a hierarchical fashion. Compared with the previous GDE framework, whose heuristic involves the entropy over the set of diagnoses and estimated posterior probabilities, we avoid the often impractical need to explicitly go through all diagnoses, and are able to compute the probabilities exactly. Experiments with ISCAS-85 circuits indicate that our approach can solve for the first time a set of multiple-fault diagnostic cases on large circuits, with good performance in terms of diagnostic cost.

    Original languageEnglish
    Pages7P
    Publication statusPublished - 2008
    Event10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008 - Fort Lauderdale, FL, United States
    Duration: 2 Jan 20084 Jan 2008

    Conference

    Conference10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008
    Country/TerritoryUnited States
    CityFort Lauderdale, FL
    Period2/01/084/01/08

    Fingerprint

    Dive into the research topics of 'Probabilistic sequential diagnosis by compilation'. Together they form a unique fingerprint.

    Cite this