Computing Observation Vectors for Max-Fault Min-Cardinality Diagnoses

Abstract

Model-Based Diagnosis (MBD) typically focuses on diag-noses, minimal under some minimality criterion, e.g., the minimal-cardinality set of faulty components that explain an observation α. However, for different α there may be mini-mal-cardinality diagnoses of differing cardinalities, and sev-eral applications (such as test pattern generation and bench-mark model analysis) need to identify the α leading to the max-cardinality diagnosis amongst them. We denote this problem as a Max-Fault Min-Cardinality (MFMC) problem. This paper considers the generation of observations that lead to MFMC diagnoses. We present a near-optimal, stochastic algorithm, called MIRANDA (Max-fault mIn-caRdinAlity ob-servatioN Deduction Algorithm), that computes MFMC ob-servations. Compared to optimal, deterministic approaches such as ATPG, the algorithm has very low cost, allowing us to generate observations corresponding to high-cardinality faults. Experiments show that MIRANDA delivers optimal re-sults on the 74XXX circuits, as well as good MFMC cardi-nality estimates on the larger ISCAS85 circuits.