Model-Based Diagnosis Through OBDD Compilation: A Complexity Analysis

Since it is known that Model-Based Diagnosis may suffer from a potentially exponential size of the search space, a number of techniques have been proposed for alleviating the problem. Among them, some forms of compilation of the domain model have been investigated. In the present paper we address the problem of evaluating the complexity of diagnostic problem solving when Ordered Binary Decision Diagrams are adopted for representing the normal and faulty behavior of the system to be diagnosed and the solution space. In particular we analyze the case of the diagnosis of static models that exhibit a directionality from inputs to outputs (an important example of this type of models is the class of combinatorial digital circuits). We show that the problem of determining the set of all diagnoses and of determining the minimum cardinality diagnoses can be solved in time and space polynomial with respect to the size of the OBDD encoding the domain model. These results hold regardless of the degree of system observability including whether observations are precise or uncertain. We then analyze the complexity of refining the set of diagnoses by making additional observations and by using a test vector for troubleshooting the system. In particular we show that in the latter case we lose the formal guarantee that the diagnosis can be performed in polynomial time with respect to the size of the compiled domain model.