 |
Compiling Model-Based Diagnosis to Boolean Satisfaction
Amit Metodi, Roni Stern, Meir Kalech and Michael Codish
Proceedings of AAAI 2012;
2012
Abstract:
This paper introduces an encoding of Model Based Diagnosis (MBD) to Boolean Satisfaction (SAT) focusing on minimal cardinality diagnosis. The encoding is based on a combination of sophisticated MBD preprocessing algorithms and SAT compilation techniques which together provide concise CNF formula. Experimental evidence indicates that our approach is superior to all published algorithms for minimal cardinality MBD. In particular, we can determine, for the first time, minimal cardinality diagnoses for the entire standard ISCAS-85 benchmark. Our results open the way to improve the state-of-the-art on a range of similar MBD problems.Available: bibtex entry pdf
Related sites: The SCryptoMiniSAT wrapper, The SAT based MBD diagnoser (for Windows), More details on the AAAI benchmarks
Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il