Approximate model-based diagnosis using greedy stochastic search

We propose a StochAstic Fault diagnosis AlgoRIthm, called Safari, which trades off guarantees of computing minimal diagnoses for computational efficiency. We empirically demonstrate, using the 74XXX and ISCAS85 suites of benchmark combinatorial circuits, that Safari achieves several orders-of-magnitude speedup over two well-known determinis-tic algorithms, CDA ∗ and HA∗, for multiple-fault diagnoses; further, Safari can compute a range of multiple-fault diagnoses that CDA ∗ and HA ∗ cannot. We also prove that Safari is optimal for a range of propositional fault models, such as the widely-used weak-fault models (models with ignorance of abnormal behavior). We discuss the optimality of Sa-fari in a class of strong-fault circuit models with stuck-at failure modes. By modeling the algorithm itself as a Markov chain, we provide exact bounds on the minimality of the diag-nosis computed. Safari also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time. 1