On the computational feasibility of abductive diagnosis for practical applications

Research output: Contribution to journalArticlepeer-review


Increasing complexity of physical systems demands an accurate fault localization in order to reduce maintenance costs. Model-based diagnosis has been proposed as an Al-based method to derive root causes from a system model and observable anomalies. Though relying on a strong theoretical background, practical applications of model-based diagnosis are often prevented by the initial modeling effort and complexity of diagnosis algorithms. In this paper, we focus on both aspects and present an approach that converts the fault information available in practice into propositional Horn logic sentences to be used in abductive diagnosis. It is well known that abductive diagnosis based on propositional Horn theories has exponential complexity in general. However, in our case the obtained logical sentences belong to a subset of propositional Horn logic that is tractable, namely definite Horn theories. In particular, we show that the abduction problem in case of the obtained models can be solved in polynomial time. We present empirical results obtained using real world examples and a parametrizable artificial example class. The data indicate that the proposed approach is feasible for practical applications.

Original languageEnglish
Pages (from-to)410-415
Number of pages6
Issue number21
Publication statusPublished - 1 Sept 2015


  • Abductive diagnosis
  • ATMS
  • Failure mode effect analysis
  • Fault diagnosis
  • FMEA
  • Model-based diagnosis

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this