Alexander Feldman, Gregory Provan, Arjan van Gemund
Most algorithms for computing diagnoses within a model-based diagnosis framework are deterministic. Such algorithms guarantee soundness and completeness, but their hardness is in the second class of the polynomial hierarchy. 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 AlgoRIthm). 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-art deterministic algorithms, CDA* and HA*, for multiple-fault diagnoses.
Subjects: 3.3 Nonmonotonic Reasoning; 1.5 Diagnosis
Submitted: Apr 15, 2008