Computing Minimal Diagnoses by Greedy Stochastic Search

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.