Efficient Sequential Model-Based Fault-Localization with Partial Diagnoses

Abstract

Model-Based Diagnosis is a principled approach to identify the possible causes when a system under observation behaves unexpectedly. In case the number of possible explanations for the unexpected behavior is large, sequential diagnosis approaches can be applied. The strategy of such approaches is to iteratively take additional measurements to narrow down the set of alternatives in order to find the true cause of the problem. In this paper we propose a sound and complete sequential diagnosis approach which does not require any information about the structure of the diagnosed system. The method is based on the new concept of partial diagnoses, which can be efficiently computed given a small number of minimal conflicts. As a result, the overall time needed for determining the best next measurement point can be significantly reduced. An experimental evaluation on different benchmark problems shows that our sequential diagnosis approach needs considerably less computation time when compared with an existing domain-independent approach.