ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (7): 1396-1407.doi: 10.7544/issn1000-1239.2019.20180192

• 人工智能 • 上一篇    下一篇

基于子集一致性检测的诊断解极小性判定方法

田乃予,欧阳丹彤,刘梦,张立明   

  1. (吉林大学计算机科学与技术学院 长春 130012) (符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012) (naiyutian@126.com)
  • 出版日期: 2019-07-01
  • 基金资助: 
    国家自然科学基金项目(61672261,61502199,61402196,61373052)

A Method of Minimality-Checking of Diagnosis Based on Subset Consistency Detection

Tian Naiyu, Ouyang Dantong, Liu Meng, Zhang Liming   

  1. (College of Computer Science and Technology, Jilin University, Changchun 130012) (Key Laboratory of Symbol Computation and Knowledge Engineering(Jilin University), Ministry of Education, Changchun 130012)
  • Online: 2019-07-01

摘要: 基于模型诊断作为克服第1代诊断系统的缺陷而出现的智能诊断推理技术,现已成为十分活跃的人工智能研究分支,随着相关技术的不断发展,应用愈加广泛.其中,大多数研究集中于诊断求解过程,而诊断解的极小性检测方法保证了最终求得诊断解的极小性,也是问题求解过程中至关重要的一步.传统诊断解的极小性判定过程是将新求得的诊断解与已有诊断集合中的诊断解依次比较,检查是否有新得诊断解的超集或子集来判定极小性,这种方法随着求解过程中得到的诊断解数量增多,检测难度逐渐提高,耗时也随之增大.为解决此问题,提出了一种基于子集一致性检测的诊断解极小性判定的新方法:子集一致性(subset consistency detection, SCD)方法.通过对诊断解少数几个子集的一致性检测来给出该诊断解的极小性判定,避免了求解过程中诊断解集合增大对效率的影响.SCD方法可应用于许多高效的诊断方法,如GD(grouped diagnosis)和ACDIAG(abstract circuit diagnosis)方法,算法效率均有所提高.

关键词: 基于模型诊断, 子集一致性, 诊断解极小性, 可满足性, 合取范式

Abstract: Model-based diagnosis is an intelligent inference technology in order to overcome the serious defects of the first generation of diagnostic system. With the consistent development of relevant work, it is a significant branch of AI at present. However, most of the researches focus on the process of finding out the diagnosis. The process of detecting the diagnosis ensures the minimality of the final solution. It is also a crucial step in the problem. The traditional process of minimality-checking of diagnosis is to compare the new diagnosis with the ones in the existing diagnosis set, checking whether there is a superset or subset of the new diagnosis. The disadvantage of the traditional process is that as the number of diagnosis increases, the difficulty of detection increases gradually, and the time-consuming increases. To solve the problem, we propose a new method of minimality-checking of diagnosis based on subset consistency detection: subset consistency detection (SCD) method. Avoiding the influence of increasing the diagnosis set size, we determine the minimality of diagnosis through the consistency detection of a few subsets of the diagnosis. Our method can be applied to many efficient diagnostic algorithms such as grouped diagnosis (GD) and abstract circuit diagnosis (ACDIAG), and the efficiency of the algorithms is improved by SCD method.

Key words: model-based diagnosis, subset consistency, minimal diagnosis, SAT, conjunctive normal form

中图分类号: