Abstract
Model-based diagnosis (MBD) has been widely acknowledged to be an effective fault diagnosis paradigm for combinational circuits. Most diagnosis algorithms (DAs) return a single diagnosis, a list of diagnoses or a score for every returned diagnosis, which estimates the likelihood of each diagnosis to be correct. Roni Stern et al. recently proposed the heath state as an output of DA to provide a manageable view of which components are likely to be faulty for human operators in the circuit diagnosis area. The health state can be used widely in areas such as troubleshooting problems, among others. This paper proposes a novel approach that improves the quality of health state with difference degree (IHSD) utilizing the MBD approach with multiple observations in the circuit diagnosis area, which returns a list of possible diagnoses that explain these observations simultaneously. In addition, we also propose a multi-observation “scoring” method based on the difference degree for every returned diagnosis, where the difference degree denotes the “distance” from the multi-observations diagnosis to the relevant diagnosis that satisfies only one observation. We present evidence that shows that, compared with the state-of-the-art algorithm on health state (Stern et al., Artif Intell 248:26–45 2018), our approach improves the quality of health state.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Stern R, Kalech M, Rogov S et al (2017) How many diagnoses do we need? Artif Intell 248:26–45
Console L, Dressler O (1999) Model-based diagnosis in the real world: lessons learned and challenges remaining. In: Sixteenth International joint conference on artificial intelligence. Stockholm, pp 1393–1400
Xu K, Li W (2006) Many hard examples in exact phase transitions. Theor Comput Sci 355(3):291–302
Zhou J, Yin M, Li X, Wang J (2012) Phase transitions of expspace-complete problems: a further step. Int J Found Comput Sci 23(01):173–184
Stern R, Kalech M (2014) Model-based diagnosis techniques for Internet delay diagnosis with dynamic routing. Appl Intell 41(1):167–183
Weber J, Wotawa F (2012) Diagnosis and repair of dependent failures in the control system of a mobile autonomous robot. Appl Intell 36(3):511–528
Obeid N (2001) Model-based diagnosis and conditional logic. Appl Intell 14(2):213–230
De Kleer J, Mackworth A, Reiter R (1992) Characterizing diagnoses and systems. Artif Intell 56 (2-3):197–222
De Kleer J (2009) Minimum cardinality candidate generation. In: Proceedings of the 20th international workshop on principles of diagnosis (DX-09). Stockholm, pp 397–402
Williams B, Ragno R (2007) Conflict-directed A* and its role in model-based embedded systems. Discret Appl Math 155(12):1562–1595
Zhang J, Ma F, Zhang Z (2012) Faulty interaction identification via constraint solving and optimization. In: Theory and applications of satisfiability testing-SAT. Trento, pp 186–199
Feldman A, Provan G, De Kleer J, Robert S, Van Gemund A (2010) Solving model-based diagnosis problems with Max-SAT solvers and vice versa. In: Proceedings of the 21th international workshop on principles of diagnosis (DX-10). Portland, pp 185–192
Metodi A, Stern R, Kalech M, Codish M (2012) Compiling model-based diagnosis to Boolean satisfaction. In: Twenty-Sixth AAAI conference on artificial intelligence. Toronto, pp 793–799
Nica I, Wotawa F (2012) ConDiag - computing minimal diagnoses using a constraint solver. In: Proceedings of the 23th international workshop on principles of diagnosis (DX-12). Great Malvern, pp 185–192
Metodi A, Stern R, Kalech M, Codish M (2014) A novel sat-based approach to model based diagnosis. J Artif Intell Res 51:377–411
Darwiche A (1998) Model-based diagnosis using structured system descriptions. J Artif Intell Res 8:165–222
Siddiqi S, Huang J (2007) Hierarchical diagnosis of multiple faults. In: IJCAI. Hyderabad, pp 581–586
Stern R, Kalech M, Feldman A, Provan G (2012) Exploring the duality in conflict-directed model-based diagnosis. In: Twenty-Sixth AAAI conference on artificial intelligence. Toronto, pp 828–834
Luo C, Su K, Cai S (2014) More efficient two-mode stochastic local search for random 3-satisfiability. Appl Intell 41(3):665–680
Cai S, Luo C, Zhang H (2017) From decimation to local search and back: a new approach to MaxSAT. In: IJCAI. Melbourne, pp 571–577
Cai S, Luo C, Lin J, Su K (2016) New local search methods for partial MaxSAT. Artif Intell 240:1–18
Cai S, Su K (2012) Configuration checking with aspiration in local search for SAT. In: Twenty-Sixth AAAI conference on artificial intelligence. Toronto, pp 828–834
Menai MEB, Batouche M (2006) An effective heuristic algorithm for the maximum satisfiability problem. Appl Intell 24(3):227–239
Wang Y, Cai S, Yin M (2016) Two efficient local search algorithms for maximum weight clique problem. In: Thirtieth AAAI Conference on artificial intelligence. Arizona, pp 805– 811
Wang Y, Cai S, Yin M (2017) Local search for minimum weight dominating set with two-level configuration checking and frequency based scoring function. J Artif Intell Res 58:267–295
Smith A, Veneris A, Ali M, Viglas A (2005) Fault diagnosis and logic debugging using Boolean satisfiability. IEEE Trans CAD Integr Circ Syst 24(10):1606–1621
Bauer A, Simplifying diagnosis using LSAT (2005) A propositional approach to reasoning from first principles. In: CPAIOR. Prague, pp 49–63
Safarpour S, Mangassarian H, Veneris A, Liffiton M, Sakallah K (2007) Improved design debugging using maximum satisfiability. In: FMCAD. Texas, pp 13–19
Nica I, Pill I, Quaritsch T, Wotawa F (2013) The route to success - a performance comparison of diagnosis algorithms. In: IJCAI. Beijing, pp 1039–1045
Marques-Silva J, Janota M, Ignatiev A, Morgado A (2015) Efficient model based diagnosis with maximum satisfiability. In: IJCAI. Buenos Aires, pp 1966–1972
Roychoudhury A, Chandra S (2016) Formula-based software debugging. ACM Commun 59(7):68–77
Lamraoui S, Nakajima S (2016) A formula-based approach for automatic fault localization of multi-fault programs. JIP 24(1):88–98
Jose M, Majumdar R (2011) Cause clue clauses: error localization using maximum satisfiability. In: PLDI. San Jose, pp 437–446
Abreu R, Zoeteweij P, Van Gemund A (2008) Techniques for diagnosing software faults Technical Report TUD-SERG-2008-014. Delft University of Technology
Reiter R (1987) A theory of diagnosis from first principles. Artif Intell 32(1):57–95
De Kleer J, Williams B (1987) Diagnosing multiple faults. Artif Intell 32(1):97–130
De Oca SM, Puig V (2009) Fault diagnosis of nonlinear systems using LPV interval observers. In: DX. Stockholm, pp 275–282
Nejjari F, De Oca SM, Puig V et al (2009) Passive robust fault detection for interval LPV systems using zonotopes. In: DX. Stockholm, pp 337–344
De Oca SM, Puig V, Blesa J (2012) Robust fault detection based on adaptive threshold generation using interval LPV observers. Int J Adapt Control Signal Process 26(3):258–283
Blesa J, Nejjari F, Rotondo D et al (2013) Robust fault detection and isolation of wind turbines using interval observers. In: Control and fault-tolerant systems (SysTol). Nice, pp 353–358
Zarch MG, Puig V, Poshtan J (2017) Fault detection and isolation using viability theory and interval observers. J Phys Conf Ser 783(1):012004
Buciakowski M, Witczak M, Puig V et al (2017) A bounded-error approach to simultaneous state and actuator fault estimation for a class of nonlinear systems. J Process Control 52:14–25
Acknowledgements
The authors would like to acknowledge the anonymous referees for their constructive comments, which considerably improved the quality of the manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by the National Natural Science Foundation of China (61672261, 61502199, 61402196, 61373052)
Rights and permissions
About this article
Cite this article
Liu, M., Ouyang, D. & Zhang, L. A novel approach for improving quality of health state with difference degree in circuit diagnosis. Appl Intell 48, 4371–4381 (2018). https://doi.org/10.1007/s10489-018-1214-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-018-1214-2