ECAI 2004 Conference Paper

Diagnosis as Semiring-based Constraint Optimization

Martin Sachenbacher, Brian Williams

Constraint optimization is at the core of many problems in Artificial Intelligence. In this paper, we frame model-based diagnosis as a constraint optimization problem over lattices. We then show how it can be captured in a framework for "soft" constraints known as semiring-CSPs. The well-defined mathematical properties of a semiring-CSP allow to devise efficient solution methods that are based on decomposing diagnostic problems into trees and applying dynamic programming. We relate the approach to SAB and TREE*, two diagnosis algorithms for tree-structured systems, which correspond to special cases of semiring-based constraint optimization.

Keywords: Diagnosis, Model-Based Reasoning, Constraint Programming

Citation: Martin Sachenbacher, Brian Williams: Diagnosis as Semiring-based Constraint Optimization . In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.873-877.

ECAI-2004 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the Universitat Politècnica de València on behalf of Asociación Española de Inteligencia Artificial (AEPIA) and Associació Catalana d'Intel-ligència Artificial (ACIA).