TY - CHAP
T1 - Approximate model-based diagnosis using greedy stochastic search
AU - Feldman, Alexander
AU - Provan, Gregory
AU - Van Gemund, Arjan
PY - 2007
Y1 - 2007
N2 - Most algorithms for computing diagnoses within a model-based diagnosis framework are deterministic. Such algorithms guarantee soundness and completeness, but are NP-hard. To overcome this complexity problem, we propose a novel approximation approach for multiplefault diagnosis, based on a greedy stochastic algorithm called SAFARI (StochAstic Fault diagnosis AlgoRIthm). SAFARI sacrifices guarantees of optimality, but for models in which component failure modes are defined solely in terms of a deviation from nominal behavior (known as weak fault models), it can compute 80-90% of all cardinality-minimal diagnoses, several orders of magnitude faster than state-of-the-art deterministic algorithms. We have applied this algorithm to the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, demonstrating order-of-magnitude speedup over a well-known deterministic algorithm, CDA*, for multiple-fault diagnoses.
AB - Most algorithms for computing diagnoses within a model-based diagnosis framework are deterministic. Such algorithms guarantee soundness and completeness, but are NP-hard. To overcome this complexity problem, we propose a novel approximation approach for multiplefault diagnosis, based on a greedy stochastic algorithm called SAFARI (StochAstic Fault diagnosis AlgoRIthm). SAFARI sacrifices guarantees of optimality, but for models in which component failure modes are defined solely in terms of a deviation from nominal behavior (known as weak fault models), it can compute 80-90% of all cardinality-minimal diagnoses, several orders of magnitude faster than state-of-the-art deterministic algorithms. We have applied this algorithm to the 74XXX and ISCAS-85 suites of benchmark combinatorial circuits, demonstrating order-of-magnitude speedup over a well-known deterministic algorithm, CDA*, for multiple-fault diagnoses.
UR - https://www.scopus.com/pages/publications/34548079043
U2 - 10.1007/978-3-540-73580-9_13
DO - 10.1007/978-3-540-73580-9_13
M3 - Chapter
AN - SCOPUS:34548079043
SN - 3540735798
SN - 9783540735793
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 139
EP - 154
BT - Abstraction, Reformulation, and Approximation - 7th International Symposium, SARA 2007 Proceedings
PB - Springer Verlag
T2 - 7th International Symposium on Abstraction, Reformulation, and Approximation , SARA 2007
Y2 - 18 July 2007 through 21 July 2007
ER -