Computing minimal diagnoses by greedy stochastic search

Most algorithms for computing diagnoses within a model-based diagnosis framework are deterministic. Such algorithms guarantee soundness and completeness, but are Σ^P₂ hard. To overcome this complexity problem, which prohibits the computation of high-cardinality diagnoses for large systems, we propose a novel approximation approach for multiple-fault diagnosis, based on a greedy stochastic algorithm called SAFARI (StochAstic Fault diagnosis Algo-Rlthm). We prove that SAFARI can be configured to compute diagnoses which are of guaranteed minimality under subsumption. We analytically model SAFARI search as a Markov chain, and show a probabilistic bound on the minimality of its minimal diagnosis approximations. We have applied this algorithm to the 74XXX and ISCAS85 suites of benchmark combinatorial circuits, demonstrating order-of-magnitude speedups over two state-of-the-an: deterministic algorithms, CDA and HA, for multiple-fault diagnoses.