| 摘要: |
| 在基于模型诊断领域中, 首先对系统描述进行编码, 利用成熟的SAT求解器获得所有极小冲突集, 最后计算极小冲突集的极小碰集, 即待诊断设备的候选诊断. 然而这种策略花费大量的时间, 相当于计算两个NP-hard问题, 即计算极小冲突集和极小碰集. 对电路系统描述重新编码, 提出一种变种碰集算法HSDiag, 该算法可以直接对编码进行计算来获得诊断. 在与目前最先进的求解冲突集再求解碰集的诊断算法相比, 效率最高提升5–100倍. 随着电路组件的增多, 编码子句呈线性增加, 诊断数量呈指数级增加. 因为求解大规模电路(ISCAS-85)的所有冲突集不切实际, 所以在设置相同的截止时间内, 提出的HSDiag算法与基于冲突集的诊断算法相比多求出1倍以上的解集. 除此之外, 提出一种专属求解诊断的等价类优化策略, 就算在初始冲突集不可分割的情况下, 利用新提出的集合分裂规则能够对冲突集进一步分解. 在标准的Polybox和Fulladder电路中, 使用等价类优化后的HSDiag算法, 效率进一步提升2倍以上. |
| 关键词: 基于模型诊断 系统描述 极小冲突集 极小碰集 等价类 |
| DOI：10.13328/j.cnki.jos.007397 |
| 分类号:TP181 |
| 基金项目:吉林省煤炭洁净燃烧技术的环境保护装备项目(3D516L921421) |
|
| HSDiag: Variant Hitting Set Algorithm for Solving Diagnosis |
|
OUYANG Ji-Hong1,2, HUANG Sen1,2
|
|
1.College of Computer Science and Technology, Jilin University, Changchun 130012, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education (Jilin University), Changchun 130012, China
|
| Abstract: |
| In the field of model-based diagnosis, the system description is first encoded, and all minimal conflict sets are obtained using a mature SAT solver. Finally, the minimal hitting set of the minimal conflict sets is computed as the candidate diagnosis for the equipment to be diagnosed. However, this strategy consumes a significant amount of time, as it is equivalent to solving two NP-hard problems: computing the minimal conflict set and the minimal hitting set. This study re-encodes the description of the circuit system and proposes a novel variant hitting set algorithm, HSDiag, which can directly compute the diagnosis from the encoding. Compared to state-of-the-art diagnosis algorithms that first solve conflict sets and then hitting sets, the efficiency improves by a factor of 5 to 100. As the number of circuit components increases, the encoding clauses increase linearly, while the number of diagnoses increases exponentially. Since solving all conflict sets of large-scale circuits (ISCAS-85) is impractical, the proposed HSDiag algorithm, within the same cutoff time, yields more than twice the number of solutions compared to conflict-set-based diagnosis algorithms. In addition, this study proposes an equivalence class optimization strategy, which further decomposes the conflict set by using the newly proposed set splitting rule, even if the initial conflict set is inseparable. The efficiency of the HSDiag algorithm optimized by equivalence class is improved by more than 2 times in standard Polybox and Fulladder circuits. |
| Key words: model-based diagnosis (MBD) system description minimal conflict set (MCS) minimal hitting set (MHS) equivalence class |
