ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (11): 2386-2394.doi: 10.7544/issn1000-1239.2018.20170381

Previous Articles     Next Articles

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

Xu Yini, Ouyang Dantong, Liu Meng, Zhang Liming, Zhang Yonggang   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (jlxuyini@126.com)
  • Online:2018-11-01

Abstract: 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.

Key words: model-based diagnosis, minimal conflict set, SE-Tree, SAT solver, component independent of fault output

CLC Number: