Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis

Ouyang Jihong; Huang Sen

doi:10.7544/issn1000-1239.202440248

Journal of Computer Research and Development > 2025 > Accepted Manuscript > DOI: 10.7544/issn1000-1239.202440248 CSTR: 32373.14.issn1000-1239.202440248

Ouyang Jihong, Huang Sen. Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440248

Citation:

Ouyang Jihong, Huang Sen. Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440248

Citation:

Ouyang Jihong, Huang Sen. Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202440248

PDF (3203 KB)

Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis

Ouyang Jihong,
Huang Sen^,

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

More Information

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

Huang Sen: born in 1995. PhD candidate. Student member of CCF. His main research interests include model-based diagnosis and SAT problem
Received Date: April 02, 2024
Revised Date: June 23, 2024
Accepted Date: January 08, 2025
Available Online: January 08, 2025

Graphical Abstract

Abstract

Abstract

Model-based diagnosis 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 have designed 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 have proposed an efficient decision algorithm based on the logical relationships of the circuit. In the experimental section, we conducted a detailed analysis comparing the runtime and diagnosis yield under varying numbers of fault conditions. Compared to state-of-the-art algorithms, our approach showed efficiency improvements of up to 2-40 times in runtime and diagnosis yield enhancements ranging from 5-200 times.
- model-based diagnosis,
- system observation,
- minimal conflict set,
- minimal hitting set,
- cardinality-minimal diagnosis

FullText(HTML)

References (36)

References

[1]	Reiter R. A theory of diagnosis from first principles[J]. Artificial Intelligence, 1987, 32(1): 57−95 doi: 10.1016/0004-3702(87)90062-2
[2]	Zhao Xiangfu, Tong Xiangrong, Ouyang Dantong, et al. Treemerge: Efficient generation of minimal hitting-sets for conflict sets in tree structure for model-based fault diagnosis[J]. IEEE Transactions on Reliability, 2021, 70(4): 1596−1610 doi: 10.1109/TR.2021.3115130
[3]	Metodi A, Stern R, Kalech M, et al. A novel SAT-based approach to model based diagnosis[J]. Journal of Artificial Intelligence Research, 2014, 51(1): 377−411
[4]	Marques-Silva J, Janota M, Ignatiev A, et al. Efficient model based diagnosis with maximum satisfiability[C]//Proc of the 24th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2015: 1966−1972
[5]	Dekleer J, Williams BC. Diagnosing multiple faults[J]. Artificial Intelligence, 1987, 32(1): 97−130 doi: 10.1016/0004-3702(87)90063-4
[6]	Feldman A , De Castro HV, Van Gemund A, et al. Model-based diagnostic decision-support system for satellites[C/OL]//Proc of the 33rd Aerospace Conf. Piscataway, NJ: IEEE, 2013[2024-04-03]. https://ieeexplore.ieee.org/ document/6497427
[7]	Struss P, Price C. Model-based systems in the automotive industry[J]. AI Magazine, 2004, 24(4): 17−34
[8]	Jannach D, Schmitz T. Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach[J]. Automated Software Engineering, 2016, 23(1): 105−144 doi: 10.1007/s10515-014-0141-7
[9]	Palma J, Juarez J, Campos M, et al. Fuzzy theory approach for temporal model-based diagnosis: An application to medical domains[J]. Artificial Intelligence in Medicine, 2006, 38(2): 197−218 doi: 10.1016/j.artmed.2006.03.004
[10]	Mordoch A, Juba B, Stern R. Learning safe numeric action models[C]//Proc of the 37th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2023, 12079−12086
[11]	Stern R, Kalech M, Rogov S, et al. How many diagnoses do we need[J]. Artificial Intelligence, 2017, 248: 26−45 doi: 10.1016/j.artint.2017.03.002
[12]	Liffiton M, Malik A. Enumerating infeasibility: finding multiple MUSes quickly[C]//Proc of the 10th AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. Berlin: Springer, 2013: 160−175
[13]	Liffiton M, Previti A, Malik A, et al. Fast, flexible MUS enumeration[J]. Constraints, 2016, 21(2): 223−250 doi: 10.1007/s10601-015-9183-0
[14]	欧阳丹彤,高菡,田乃予,等. 基于双模型的MUS求解方法[J]. 计算机研究与发展,2019,56(12):2623−2631 doi: 10.7544/issn1000-1239.2019.20180852 Ouyang Dantong, Gao Han, Tian Naiyu, et al. MUS enumeration based on double-model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623−2631 (in Chinese) doi: 10.7544/issn1000-1239.2019.20180852
[15]	Torlak E, Chang FS, Jackson D. Finding minimal unsatisfiable cores of declarative specifications[C]//Proc of the 15th Int Symp on Formal Methods. Berlin: Springer, 2008: 326−341
[16]	Mencia, C, Previti A, Marques-Silva J. Literal based MCS extraction[C]//Proc of the 24th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2015: 1973−1979
[17]	Jannach D, Schmitz T, Shchekotykhin K. Parallelized hitting set computation for model-based diagnosis[C]//Proc of the 29th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2015: 1503−1510
[18]	Greiner R, Smith B. Wilkerson R. A correction to the algorithm in Reiter’s theory of diagnosis[J]. Artificial Intelligence, 1989, 41(1): 79−88 doi: 10.1016/0004-3702(89)90079-9
[19]	Wotawa F. A variant of Reiter’s hitting-set algorithm[J]. Information Processing Letters, 2001, 79(1): 45−51 doi: 10.1016/S0020-0190(00)00166-6
[20]	姜云飞,林笠. 用布尔代数方法计算最小碰集[J]. 计算机学报,2003,26(8):919−924 doi: 10.3321/j.issn:0254-4164.2003.08.004 Jiang Yunfei, Lin Li. The computation of hitting sets with Boolean formulas[J]. Chinese Journal of Computers, 2003, 26(8): 919−924 (in Chinese) doi: 10.3321/j.issn:0254-4164.2003.08.004
[21]	Pill I, Quaritsch T. Optimizations for the Boolean approach to computing minimal hitting sets[C]//Proc of the 20th European Conf on Artificial Intelligence. Montpellier: IOS Press, 2012, 648−653
[22]	刘思光,欧阳丹彤,张立明. 极小碰集求解中候选解极小性判定方法[J]. 软件学报,2018,29(12):3733−3746 Liu Siguang, Ouyang Dantong, Zhang Liming. Minimization of candidate solutions in minimal hitting sets solution[J]. Journal of Software, 2018, 29(12): 3733−3746 (in Chinese)
[23]	田乃予,欧阳丹彤,刘梦,等. 基于子集一致性检测的诊断解极小性判定方法[J]. 计算机研究与发展,2019,56(7):1396−1407 Tian Naiyu, Ouyang Dantong, Liu Meng, et al. A method of minimality-checking of diagnosis based on subset consistency detection[J]. Journal of Computer Research and Development. 2019, 56(7): 1396−1407 (in Chinese)
[24]	赵相福,黄森,童向荣,等. IBWIICC:结合局部独立覆盖检测策略增量求解极小碰集的算法[J]. 电子学报,2022,50(11):2722−2729 doi: 10.12263/DZXB.20211356 Zhao Xiangfu, Huang Sen, Tong Xiangrong, et al. IBWIICC: incrementally computing minimal hitting-sets combing local independence cover checking[J]. Acta Electronica Sinica, 2022, 50(11): 2722−2729 (in Chinese) doi: 10.12263/DZXB.20211356
[25]	Zhao Xiangfu, Ouyang Dantong. Deriving all minimal hitting sets based on join relation[J]. Transactions on Systems, Man, and Cybernetics: Systems, 2015, 45(7): 1063−1076 doi: 10.1109/TSMC.2015.2400423
[26]	Zhao Xiangfu. Linearmerge: Efficient computation of minimal hitting sets for conflict sets in a linear structure[J]. Engineering Applications of Artificial Intelligence, 2018, 72: 327−339 doi: 10.1016/j.engappai.2018.04.015
[27]	Wang Qiujie, Tao Jin, Wang Mengqi. A hierarchical minimum hitting set calculation method for multiple multiphase faults in power distribution networks[J]. IEEE Transactions on Industrial Electronics, 2021, 68(1): 4−14 doi: 10.1109/TIE.2020.2967691
[28]	Wang Qiujie, Tao Ji, Mohamed M. A fast and robust fault section location method for power distribution systems considering multisource information[J]. IEEE Systems Journal, 2022, 16(2): 1954−1964 doi: 10.1109/JSYST.2021.3057663
[29]	Kalech M, Stern R, Lazebnik E. Minimal cardinality diagnosis in problems with multiple observations[J]. Diagnostics, 2021, 11(5): 780 doi: 10.3390/diagnostics11050780
[30]	Siddiqi S. Computing minimum-cardinality diagnoses by model relaxation[C]//Proc of the 24th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2011: 1087−1092
[31]	Ignatiev A, Morgado A, Weissenbacher G, et al. Model-based diagnosis with multiple observations[C]//Proc of the 28th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2019: 1108−1115
[32]	Zhou Huisi, Ouyang Dantong, Zhao Xiangfu, et al. Two compacted models for efficient model-based diagnosis[C]//Proc of the 36th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 3885−3893
[33]	Ignatiev A, Morgado A, Marques-Silva J. RC2: An efficient MaxSAT solver[J]. Satisfiability Boolean Modeling and Computation, 2019, 11(1): 53−64 doi: 10.3233/SAT190116
[34]	Kochemazov S, Kondratiev V, Gribanova I. Empirical analysis of the RC2 MaxSAT algorithm[C]//Proc of the 46th MIPRO ICT and Electronics Convention. Piscataway, NJ: IEEE, 2023: 1027−1032
[35]	Gainer-Dewar A, Vera-Licona P. The minimal hitting set generation problem: Algorithms and computation[J]. Siam Journal on Discrete Mathematics, 2016, 31(1): 63−100
[36]	Siddiqi S, Huang J. Hierarchical diagnosis of multiple faults[C]//Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco, CA: Morgan Kaufmann, 2007: 581−586

[1]	Wu Huanhuan, Xie Ruilin, Qiao Yuanxin, Chen Xiang, Cui Zhanqi. Optimizing Deep Neural Network Based on Interpretability Analysis[J]. Journal of Computer Research and Development, 2024, 61(1): 209-220. DOI: 10.7544/issn1000-1239.202220803
[2]	Li Qian, Lin Chenhao, Yang Yulong, Shen Chao, Fang Liming. Adversarial Attacks and Defenses Against Deep Learning Under the Cloud-Edge-Terminal Scenes[J]. Journal of Computer Research and Development, 2022, 59(10): 2109-2129. DOI: 10.7544/issn1000-1239.20220665
[3]	Shen Zhengchen, Zhang Qianli, Zhang Chaofan, Tang Xiangyu, Wang Jilong. Location Privacy Attack Based on Deep Learning[J]. Journal of Computer Research and Development, 2022, 59(2): 390-402. DOI: 10.7544/issn1000-1239.20200843
[4]	Gu Mianxue, Sun Hongyu, Han Dan, Yang Su, Cao Wanying, Guo Zhen, Cao Chunjie, Wang Wenjie, Zhang Yuqing. Software Security Vulnerability Mining Based on Deep Learning[J]. Journal of Computer Research and Development, 2021, 58(10): 2140-2162. DOI: 10.7544/issn1000-1239.2021.20210620
[5]	Wang Huijiao, Cong Peng, Jiang Hua, Wei Yongzhuang. Security Analysis of SIMON32/64 Based on Deep Learning[J]. Journal of Computer Research and Development, 2021, 58(5): 1056-1064. DOI: 10.7544/issn1000-1239.2021.20200900
[6]	Zhou Chunyi, Chen Dawei, Wang Shang, Fu Anmin, Gao Yansong. Research and Challenge of Distributed Deep Learning Privacy and Security Attack[J]. Journal of Computer Research and Development, 2021, 58(5): 927-943. DOI: 10.7544/issn1000-1239.2021.20200966
[7]	Chen Jinyin, Chen Yipeng, Chen Yiming, Zheng Haibin, Ji Shouling, Shi Jie, Cheng Yao. Fairness Research on Deep Learning[J]. Journal of Computer Research and Development, 2021, 58(2): 264-280. DOI: 10.7544/issn1000-1239.2021.20200758
[8]	Wang Ruiqin, Wu Zongda, Jiang Yunliang, Lou Jungang. An Integrated Recommendation Model Based on Two-stage Deep Learning[J]. Journal of Computer Research and Development, 2019, 56(8): 1661-1669. DOI: 10.7544/issn1000-1239.2019.20190178
[9]	Zhou Yucong, Liu Yi, Wang Rui. Training Deep Neural Networks for Image Applications with Noisy Labels by Complementary Learning[J]. Journal of Computer Research and Development, 2017, 54(12): 2649-2659. DOI: 10.7544/issn1000-1239.2017.20170637
[10]	Zhang Lei, Zhang Yi. Big Data Analysis by Infinite Deep Neural Networks[J]. Journal of Computer Research and Development, 2016, 53(1): 68-79. DOI: 10.7544/issn1000-1239.2016.20150663