基于模型诊断中结合问题特征的新方法

发布时间：2018-11-05 10:43

【摘要】：基于模型诊断一直是人工智能领域中热门的研究问题.近些年来,随着SAT求解器效率的逐渐提高,基于模型的诊断也被转换成SAT问题进行求解.在对基于模型诊断求解方法 CSSE-tree深入研究基础上,结合诊断问题和SAT求解过程的特征,给出先对包含组件个数较多的候选诊断进行求解的方法,进而减小SAT求解问题的规模;在对极小诊断解和非极小诊断解剪枝方法的基础上,首次提出非诊断解定理及非诊断解空间的剪枝方法,有效地实现了对诊断的无解空间进行剪枝.根据组件个数较多的候选诊断先求解及有解无解剪枝方法特征,构建基于反向搜索的LLBRS-tree方法.实验结果表明:与CSSE-tree算法相比,LLBRS-tree算法减少了SAT求解次数、减小了求解问题规模,效率较好,尤其是求解多诊断时效率提高更为显著.
[Abstract]:Model-based diagnosis has been a hot research problem in artificial intelligence field. In recent years, with the improvement of efficiency of SAT solver, model-based diagnosis is transformed into SAT problem. On the basis of the deep research on the model based diagnosis solution method (CSSE-tree), combining the characteristics of the diagnosis problem and the SAT solution process, the method of solving the candidate diagnosis which contains a large number of components is presented, and the scale of the SAT solution problem is reduced. Based on the pruning method of minimal diagnostic solution and non-minimal diagnostic solution, the non-diagnostic solution theorem and the pruning method of non-diagnostic solution space are proposed for the first time, which can effectively prune the non-solution space of diagnosis. According to the characteristics of the candidate diagnostics with a large number of components and the characteristics of the unsolved pruning method, the LLBRS-tree method based on reverse search is constructed. The experimental results show that compared with the CSSE-tree algorithm, the LLBRS-tree algorithm reduces the number of SAT solutions, reduces the size of the problem, and is more efficient, especially in solving multiple diagnostics.
【作者单位】：吉林大学软件学院;吉林大学计算机科学与技术学院;符号计算与知识工程教育部重点实验室(吉林大学);
【基金】：国家自然科学基金项目(61672261,61502199,61402196,61272208) 浙江省自然科学基金项目(LY16F020004)~~
【分类号】：TP18

【相似文献】