论文部分内容阅读
百度无人驾驶汽车的推出和棋圣李世石在“人机大战”中以1:4惨败于Google的AlphaGo事件的发生,使得人工智能迅速被大众所熟知。作为人工智能(Artificial Intelligence,AI)领域的一个重要分支——基于模型诊断(Model-Based Diagnosis,MBD),自从该问题被提出,就一直备受科学家的青睐,越来越多的学者参与到该问题的研究当中且成果显著。目前,基于模型诊断已经被广泛应用于航空航天诊断、芯片诊断、汽车故障诊断、电网等领域。基于模型诊断的主要思想是根据待诊断设备的内部组织架构以及相应的行为来诊断该设备,从设备的模型和实际行为出发推理出故障组件,解释设备的预期行为和实际观测之间的不同。理论上,基于模型诊断问题有两个研究方向:1)溯因诊断,该方法求解效率较高,能快速求出设备的诊断解,但如果待诊断设备不符合要求,可能会丢失诊断解;2)基于一致性诊断,和溯因诊断相比,该方法的缺点是求解效率慢,优点是能遍历整个诊断空间,求出系统所有诊断解。故在算法实现上,基于模型诊断也有两类算法:完备性算法和非完备性算法,Reiter提出的著名算法HS-Tree就是非完备算法,虽然该方法因剪枝方式不合理出现了漏解情况,但是它为基于模型诊断的后续研究提供了思路。研究发现,基于模型诊断通过预期处理可以转换成可满足问题求解,而可满足问题已被相关学者证明是NP问题,故研究基于模型诊断问题对于NP问题的求解有着良好的启发作用。近年来,很多学者对国际SAT算法竞赛热情高涨,参与竞赛者众多,这使得SAT求解器发展十分迅速,故将SAT求解器和集合枚举树结合起来求诊断解问题是一个比较好的方向。本文在对基于模型诊断问题求解方法LLBRS-Tree深入研究的基础上,根据电路组件的拓扑结构信息、系统的观测行为和预期行为之间的差异以及集合枚举树的特点,首次提出了组件静态伪故障度和动态伪故障度的概念。计算所有组件的静态伪故障度,并根据静态伪故障度从大到小对组件重新排序,生成新的枚举树;并且在遍历到新的诊断解时,更新相关组件的动态伪故障度,动态建立新的枚举树,从而能较快地搜索到极小诊断解,删除大量冗余解,较大程度地减少SAT求解器的调用次数。实验结果表明,随着诊断系统中组件个数的增多以及极小诊断解长度的增加,提出的方法较LLBRS-Tree方法效率提升明显。