Compact Diagnoses Representation in Diagnostic Problem Solving

The paper addresses the problem of finding a compact representation of the diagnoses within a model-based approach to diagnosis. To this end, we introduce the notion of scenario, a special kind of CNF formula over the component variables, which can be used to encode a large number of diagnoses using the same amount of space needed for encoding just a single diagnosis. We show how the solutions to a diagnostic problem can be computed as sets of scenarios by presenting first an exhaustive algorithm and then an efficient algorithm, which exploits probabilistic information to restrict the result set to preferred scenarios. Finally, we discuss the issue of how to efficiently extract preferred diagnoses from sets of scenarios and characterize a class of system models for which our techniques perform particularly well. Concepts and algorithms introduced in the paper have been tested within the prototype of the diagnostic agent of a space robotic arm; resulting statistics are reported and critically discussed