An efficient algorithm for finding minimal overconstrained subsystems for model-based diagnosis

In model-based diagnosis, diagnostic system construction is based on a model of the technical system to be diagnosed. To handle large differential algebraic models and to achieve fault isolation, a common strategy is to pick out small overconstrained parts of the model and to test these separately against measured signals. In this paper, a new algorithm for computing all minimal overconstrained subsystems in a model is proposed. For complexity comparison, previous algorithms are recalled. It is shown that the time complexity under certain conditions is much better for the new algorithm. This is illustrated using a truck engine model.