Computing Minimum-Cardinality Diagnoses by Model Relaxation
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 1087-1091.
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.
@inproceedings{ijcai2011p186,
title = {Computing Minimum-Cardinality Diagnoses by Model Relaxation},
author = {Siddiqi, Sajjad Ahmed},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {1087--1091},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-186},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-186},
}
TY - CPAPER TI - Computing Minimum-Cardinality Diagnoses by Model Relaxation AU - Siddiqi, Sajjad Ahmed T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 1087 EP - 1091 DO - 10.5591/978-1-57735-516-8/IJCAI11-186 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-186 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
