An improved approach for generating max-fault min-cardinality diagnoses

Abstract

Most approaches to model-based diagnosis focus on isolating a defective component by performing additional measurements on the defective system. Sometimes internal measurements are expensive to make and it is much less costly to change system inputs and observe how outputs change. In digital circuits this is called test-vector generation. Of particular interest are Max-Fault Min-Cardinality (MFMC) observation vectors which result in the maximum number of faults in the minimal cardinality diagnosis. Prior approaches to MFMC generation either used sampling (which is incomplete) or exhaustively enumerate all possible observation vectors (which is computationally impossible). This paper presents a new direct approach to determining MFMC vectors which shows 4-5 orders of magnitude performance improvement over prior algorithms.