Computing minimal diagnoses with critical set algorithms
Igor Mozetič · 1994
The paper is concerned with the time complexity of model-based diagnosis. Our experiments indicate that the time to compute minimal diagnoses is dominated by the calls to the model of the device being diagnosed. In the paper we describe an attempt to reduce the number of model calls by incorporating two critical set algorithms [ Loveland, 1987 ] into IDA [ Mozetic, 1992 ] . A critical set algorithm computes a minimal diagnosis with O(log n) model calls as opposed to O(n) model calls made by a straightforward algorithm. We performed experiments on two non-trivial domains: (a) a 1000-bit adder which has simple structure and behaviour, but large number of components (5000) and minimal diagnoses, and (b) the KARDIO model of the heart with complicated structure and behaviour, but relatively small search space and few minimal diagnoses. The reported results are negative: the straightforward algorithm outperforms more sophisticated critical set algorithms. We analyse the results and show that...