Algorithm of Computing Minimal Conflict Sets Based on the Structural Feature of Fault Output

Model-based diagnosis is an important research in the field of artificial intelligence, and the diagnosis based on minimal conflict is a classical method to solve the problem of diagnosis. Therefore computing minimal conflict is an important step in model-based diagnosis. After studying the characteristics of the circuit model, this paper proposes an algorithm of computing minimal conflict sets based on the structural feature of fault output (MCS-SFFO) based on the CSRDSE algorithm. Firstly, the pruning rule of CSRDSE algorithm is improved, and it avoids the access to child leaf nodes of leaf nodes which are not conflict sets. Secondly, the concepts of component set independent of fault output and related to fault output are presented, and the method of computing component set independent of fault output is provided according to the system description and observation. Finally, a theorem about non-conflict set is proposed, that is, the component set independent of fault output and its subset are not conflict sets. MCS-SFFO algorithm that computes minimal conflict set is presented according to the non-conflict set theorem. Compared with CSRDSE algorithm, MCS-SFFO algorithm further prunes the non-solution space and reduces the number of calls to the SAT solver. Experimental evidence indicates that MCS-SFFO algorithm has better computational efficiency than CSRDSE algorithm.