收藏切换
Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis
收藏切换
Jihong Ouyang, Sen Huang*
Journal of Computer Research and Development | 2025, 62(8) : 1850 - 1861
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(8): 1850-1861
• Artificial Intelligence •
Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis
Full
Jihong Ouyang, Sen Huang*
Affiliations
  • 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
  • born in 1964. PhD, professor. Member of CCF. Her main research interests include model-based diagnosis and machine learning

    born in 1995. PhD candidate. Student member of CCF. His main research interests include model-based diagnosis and SAT problem

About Author:

born in 1964. PhD, professor. Member of CCF. Her main research interests include model-based diagnosis and machine learning

born in 1995. PhD candidate. Student member of CCF. His main research interests include model-based diagnosis and SAT problem

Published: 2025-08-01 doi: 10.7544/issn1000-1239.202440248
Outline
收藏切换

Model-based diagnosis (MBD) mainly models the behavior of the system, and once the abnormal behavior is observed, a diagnosis algorithm is run on the system model to return a possible explanation. The existing diagnosis algorithm computes a minimal hitting set (MHS) each time a conflict set is identified, and then verifies whether this MHS satisfies the system observations. While this approach reduces the generation of redundant solution sets, the difficulty of computing the MHSs of conflict sets increases exponentially with the number of conflict sets. Since computing the MHS of a partial conflict set is not necessarily a diagnosis, it is also time-consuming to check whether the MHS satisfies the system observations. We design a filtering function to remove low-quality conflict sets based on the diagnosis cardinality and quantity, while ensuring that the obtained hitting sets are as diagnosis as possible. In addition, to facilitate the rapid verification of hitting sets for diagnosis, we propose an efficient decision algorithm based on the logical relationships of the circuit. In the experimental section, we conduct a detailed analysis to compare the runtime and diagnosis yield under varying numbers of fault conditions. Compared with state-of-the-art algorithms, our approach shows efficiency improvements up to 2−40 times in runtime and diagnosis yield enhancements ranging from 5−200 times.

model-based diagnosis  /  system observation  /  minimal conflict set (MCS)  /  minimal hitting set (MHS)  /  cardinality-minimal diagnosis
欧阳继红, 黄森. 基于模型诊断中隐式碰集的获取与判断. 计算机研究与发展, 2025 , 62 (8) : 1850 -1861 . DOI: 10.7544/issn1000-1239.202440248
Jihong Ouyang, Sen Huang. Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis[J]. Journal of Computer Research and Development, 2025 , 62 (8) : 1850 -1861 . DOI: 10.7544/issn1000-1239.202440248
Year 2025 volume 62 Issue 8
95
46
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202440248
  • Receive Date:2024-04-03
  • Online Date:2026-11-10
  • Published:2025-08-01
Article Data
Affiliations
History
  • Received:2024-04-03
  • Revised:2024-12-09
  • Accepted:2025-01-09
Affiliations
    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
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440248
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT