Proceedings

Diagnosing Tree-Decomposable Circuits

Yousri El Fattah, Rina Dechter

Download BibTeX Cite

Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence. Qualitative Reasoning and Diagnosis. Pages 1742-1748.

Abstract

This paper describes a diagnosis algorithm called structure-based abduction (SAB) which was developed in the framework of constraint networks [12]. The algorithm exploits the structure of the constraint network and is most efficient for near-tree problem domains. By analyzing the structure of the problem domain, the performance of such algorithms c~n be bounded in advance. We present empirical results comparing SAB with two modelbased algorithms, MBD1 and MBD2, for the task of finding one or all minimal-cardinality diagnoses . MBD1 uses the same computing strategy as algorithm GDE [9]. MBD2 adopts a breadth-first search strategy similar to the algorithm DIAGNOSE [24]. The main conclusion is that for nearly acyclic circuits, such as theN-bit adder, the performance of SAB being linear provides definite advantages as the size of the circuit increases.

Yousri El Fattah, and Rina Dechter. 1995. Diagnosing Tree-Decomposable Circuits. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, IJCAI-95. IJCAI, 1742–1748. https://ijcai.org/proceedings/1995/224
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards