Computing Minimum-cardinality Diagnoses by Model Relaxation
Sajjad Siddiqi
It is known that all minimum-cardinality diagnoses of a (faulty) system can be computed efficiently, in a hierarchical fashion, once the system abstraction has been successfully compiled into DNNF. However, the compilation of a system with very large abstraction can become a bottleneck. We propose a novel approach, based upon model relaxation, which scales diagnosis to very large systems: If the abstraction of a system cannot be compiled, we obtain a relaxed model of the system using node-splitting and compile the abstraction of the relaxed model instead. We then use a novel two-stage branch-and-bound search to compute the abstract minimum-cardinality diagnoses of the relaxed model. First we perform search on split variables and compute the minimum-cardinality of diagnoses. Then we perform search on both the split as well as the health variables and compute minimum-cardinality diagnoses of the abstraction. The computed diagnoses are later refined hierarchically to get all minimum-cardinality diagnoses of the system. We deal with intricacies involved in computing diagnoses correctly and efficiently, and employ novel techniques to improve efficiency. Experiments on ISCAS-85 benchmark circuits show that the new approach can diagnose all circuits in the suite for the first time. On circuits that can be solved by the previous technique it also gives significant performance improvement.