Focussing Abductive Diagnosis

Abstract

The aim of this paper is to present a novel approach to the problem of focusing abductive (model-based) diagnosis. The approach we propose is based on the use of compiled knowledge and, specifically, on the possibility of associating with each entity in a model a necessary condition for the presence of the entity itself. Such conditions embed the problem solving strategy and their evaluation on the data characterizing the problem to be solved allows us to prune the search space, yet preserving the completeness of the abductive process (in other words, only useless search is avoided). The use of compiled knowledge thus allows us to mitigate the problems arising from the computational complexity of the model based approach. The final part of the paper is devoted to a comparison of our approach with other ones and to a brief discussion on the role of knowledge compilation in model-based diagnosis.