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 deterministic 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 Safari 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 diagnosis computed. Safari also displays strong anytime behavior, and will return a diagnosis after any non-trivial inference time.