ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (7): 1472-1480.doi: 10.7544/issn1000-1239.2020.20190338

Previous Articles     Next Articles

Minimal Conflict Set Solving Method Combined with Fault Logic Relationship

Ouyang Dantong1,2,3, Gao Han1,3, Xu Yini2,3, Zhang Liming1,2,3   

  1. 1(College of Software Engineering, Jilin University, Changchun 130012);2(College of Computer Science and Technology, Jilin University, Changchun 130012);3(Key Laboratory of Symbolic Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun 130012)
  • Online:2020-07-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (61872159, 61672261, 61502199).

Abstract: Model-based diagnosis is an important research direction in the field of artificial intelligence, and solving the MCS (minimal conflict set) is an important step to solve the diagnosis problem. The MCS-SFFO(minimal conflict set-structural feature of fault output) method searches the set enumeration tree (SE-Tree) by a reverse depth-first way and then prunes the combination of fault output-independent components. Based on the MCS-SFFO method, a further pruning method for solving the minimal conflict set MCS-FLR(minimal conflict set-fault logic relationship) is proposed based on the fault logic relationship of the circuit. The non-conflict theorem of the single-component is proposed, which prunes the single component, to avoid the solution-free space. Secondly, the non-minimum conflict set theorem is proposed, that is, the supersets of the fault output related is all conflict sets, and the non-minimum conflict set can be further pruned in the solution space. Based on the MCS-SFFO method, the MCS-FLR method further prunes both the solution space as well as the solution-free space, which reduces the number of times the solution space and part of the solution-free space call SAT solver, saving the solution times. The experimental results show that compared with the MCS-SFFO method, the efficiency of the MCS-FLR method is significantly improved.

Key words: model-based diagnosis, non-minimum conflict, set enumeration tree (SE-Tree), fault output related components, pruning in solution space

CLC Number: