高级检索

    基于模型诊断的一种新编码方法

    A Novel Encoding for Model-Based Diagnosis

    • 摘要: 基于模型诊断(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求解器求解诊断的难度,进而能在更短的时间内返回一个诊断解.

       

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

       

    /

    返回文章
    返回