ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

### 结合故障输出结构特征的极小冲突求解算法

1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbolic Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012)
• 出版日期: 2018-11-01
• 基金资助:
国家自然科学基金项目(61672261,61502199,61402196,61373052,61872159)

### 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.