Efficient Diagnosis based on Incomplete System Descriptions
Peter Fröhlich and Wolfgang Nejdl
Abstract
Fault diagnosis is an important task in technical domains. In the
model--based diagnosis literature it has mostly been assumed that
technical systems are described by complete, deterministic system
descriptions.
We show that intuitive descriptions of technical systems are often
incomplete, and need to be completed for providing correct
diagnoses. Due to the structure of the axioms of such system
descriptions completion is not straightforward, because predicate
completion is not applicable and circumscription does not yield first
order sentences. We introduce an algorithm which reduces the system
descriptions to propositional representations which are then
completed.
Furthermore, we discuss how diagnoses can be computed efficiently for
the completed system descriptions. While the original descriptions of
the system behaviour usually consist of horn clauses, their
completions are typically not horn. We provide formal results, which
allow to exploit the structure of the original horn clauses, when
reasoning with the completed clause sets.
The full report is available as a postscript file
.