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 language | English |
---|---|
Pages | 7P |
Publication status | Published - 2008 |
Event | 10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008 - Fort Lauderdale, FL, United States Duration: 2 Jan 2008 → 4 Jan 2008 |
Conference
Conference | 10th International Symposium on Artificial Intelligence and Mathematics, ISAIM 2008 |
---|---|
Country/Territory | United States |
City | Fort Lauderdale, FL |
Period | 2/01/08 → 4/01/08 |