摘要
基于模型诊断(model-based diagnosis,MBD)是人工智能诊断领域中著名的诊断求解方法之一,旨在识别诊断问题的根本原因.由于求解诊断解在计算上具有挑战性,一些MBD算法提出通过修改模型的编码来提高诊断效率,如面向统治者的编码(dominator-oriented encoding,DOE)方法.面向观察的编码(observation-oriented encoding,OOE)方法使用2种方法对MBD模型进行约简.首先,利用系统观测和统治组件输出的一些过滤边来约简系统描述和观测.其次,通过查找基于观测的过滤节点来过滤更多的组件,进而有效约简组件的编码规模.此外,在ISCAS85和ITC99基准测试用例上的实验结果表明,与目前最新的MBD编码方法DOE和传统的基础编码(basic encoding,BE)相比,上述2种约简方法有效减少了MBD实例的编码子句数量比,降低MaxSAT求解器求解诊断的难度,进而能在更短的时间内返回一个诊断解.
Model-based diagnosis(MBD),a well-known approach in the AI field,aims at identifying the root cause of a diagnosis problem.Since computing diagnosis is computationally challenging,some MBD algorithms by modifying the model encode are presented successively,such as Dominator-Oriented Encoding(DOE)approach.In this study,we propose a new encoding process,Observation-Oriented Encoding(OOE),which uses two ideas to simplify MBD model.Firstly,we consider more filtered edges based on observation of system and output of dominated components.This idea can reduce the number of encoded clauses for diagnosis system and observations.Secondly,more components are filtered by finding out observation-based filtered nodes.This approach reduces the number of encoded clauses for components.All of them can reduce the number of encoded clauses efficiently.Furthermore,experiment evaluations on ISCAS85 and ITC99 benchmarks,which contain well-known combinational circuits used for MBD algorithms,show that OOE approach generates less weighted conjunctive normal forms(WCNF)and makes diagnosis easier with maximum satisfiability(MaxSAT)solver,compared with DOE,the latest encoding algorithms for MBD,and Basic Encoding(BE),which is the traditional encoding approach for MBD.In addition,OOE approach returns a solution in a shorter time than DOE and BE approaches.
作者
周慧思
欧阳丹彤
田新亮
张立明
Zhou Huisi;Ouyang Dantong;Tian Xinliang;Zhang Liming(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)
出处
《计算机研究与发展》
EI
CSCD
北大核心
2023年第1期95-102,共8页
Journal of Computer Research and Development
基金
国家自然科学基金项目(62076108,61872159,61672261)。
关键词
基于模型诊断
最大可满足性问题
基于统治关系的编码
顶层诊断
极小势诊断
model-based diagnosis(MBD)
maximum satisfiability(MaxSAT)
dominator-oriented encoding(DOE)
top-level diagnosis(TLD)
cardinality-minimal diagnosis
