Computing Minimum-Cardinality Diagnoses by Model Relaxation
Abstract
We propose a new approach based on model relaxation to compute minimum-cardinality diagnoses of a (faulty) system: We obtain a relaxed model of the system by splitting nodes in the system and compile the abstraction of the relaxed model into DNNF. Abstraction is obtained by treating self-contained sub-systems called cones as single components. We then use a novel branch-and-bound search algorithm and compute the abstract minimum-cardinality diagnoses of the system, which are later refined hierarchically, in a careful manner, to get all minimum-cardinality diagnoses of the system. Experiments on ISCAS-85 benchmark circuits show that the new approach is faster than the previous state-of-the-art hierarchical approach, and scales to all circuits in the suite for the first time.
Cite
Text
Siddiqi. "Computing Minimum-Cardinality Diagnoses by Model Relaxation." International Joint Conference on Artificial Intelligence, 2011. doi:10.5591/978-1-57735-516-8/IJCAI11-186Markdown
[Siddiqi. "Computing Minimum-Cardinality Diagnoses by Model Relaxation." International Joint Conference on Artificial Intelligence, 2011.](https://mlanthology.org/ijcai/2011/siddiqi2011ijcai-computing/) doi:10.5591/978-1-57735-516-8/IJCAI11-186BibTeX
@inproceedings{siddiqi2011ijcai-computing,
title = {{Computing Minimum-Cardinality Diagnoses by Model Relaxation}},
author = {Siddiqi, Sajjad Ahmed},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2011},
pages = {1087-1092},
doi = {10.5591/978-1-57735-516-8/IJCAI11-186},
url = {https://mlanthology.org/ijcai/2011/siddiqi2011ijcai-computing/}
}