Abstract
Model-Based Diagnosis (MBD) is a general-purpose computational approach to determine why a system under observation, e.g., an electronic circuit or a software program, does not behave as expected. MBD approaches utilize knowledge about the system’s expected behavior if all of its components work correctly. In case of an unexpected behavior they systematically explore the possible reasons, i.e., diagnoses, for the misbehavior. Such diagnoses are determined through systematic or heuristic search procedures which often use MBD-specific rules to prune the search space. In this chapter we review approaches that rely on parallel or distributed computations to speed up the diagnostic reasoning process. Specifically, we focus on recent parallelization strategies that exploit the capabilities of modern multi-core computer architectures and report results from experimental evaluations to shed light on the speedups that can be achieved by parallelization for various MBD applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
de Kleer, J., Mackworth, A.K., Reiter, R.: Characterizing Diagnoses and Systems. Artificial Intelligence 56(2-3) (1992) 197–222
de Kleer, J., Williams, B.C.: Diagnosing Multiple Faults. Artificial Intelligence 32(1) (April 1987) 97–130
Reiter, R.: A Theory of Diagnosis from First Principles. Artificial Intelligence 32(1) (1987) 57–95
Felfernig, A., Friedrich, G., Jannach, D., Stumptner, M.: Consistency-based Diagnosis of Configuration Knowledge Bases. Artificial Intelligence 152(2) (2004) 213–234
Mateis, C., Stumptner, M., Wieland, D., Wotawa, F.: Model-Based Debugging of Java Programs. In: AADEBUG’00. (2000)
Jannach, D., Schmitz, T.: Model-based Diagnosis of Spreadsheet Programs: A Constraint-based Debugging Approach. Automated Software Engineering 23(1) (2016) 105–144
Wotawa, F.: Debugging Hardware Designs Using a Value-Based Model. Applied Intelligence 16(1) (2001) 71–92
Felfernig, A., Friedrich, G., Isak, K., Shchekotykhin, K.M., Teppan, E., Jannach, D.: Automated Debugging of Recommender User Interface Descriptions. Applied Intelligence 31(1) (2009) 1–14
Console, L., Friedrich, G., Dupré, D.T.: Model-Based Diagnosis Meets Error Diagnosis in Logic Programs. In: IJCAI’93. (1993) 1494–1501
Friedrich, G., Shchekotykhin, K.M.: A General Diagnosis Method for Ontologies. In: ISWC’05. (2005) 232–246
Stumptner, M., Wotawa, F.: Debugging Functional Programs. In: IJCAI’99. (1999) 1074–1079
Friedrich, G., Stumptner, M., Wotawa, F.: Model-Based Diagnosis of Hardware Designs. Artificial Intelligence 111(1-2) (1999) 3–39
White, J., Benavides, D., Schmidt, D.C., Trinidad, P., Dougherty, B., Cortés, A.R.: Automated Diagnosis of Feature Model Configurations. Journal of Systems and Software 83(7) (2010) 1094–1107
Friedrich, G., Fugini, M., Mussi, E., Pernici, B., Tagni, G.: Exception Handling for Repair in Service-Based Processes. IEEE Transactions on Software Engineering 36(2) (2010) 198–215
Junker, U.: QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems. In: AAAI’04. (2004) 167–172
Marques-Silva, J., Janota, M., Belov, A.: Minimal Sets over Monotone Predicates in Boolean Formulae. In: Computer Aided Verification. (2013) 592–607
Shchekotykhin, K., Jannach, D., Schmitz, T.: MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis. In: IJCAI’15. (2015) 3221–3228
Greiner, R., Smith, B.,Wilkerson, R.: A Correction to the Algorithm in Reiter’s Theory of Diagnosis. Artificial Intelligence 41(1) (1989) 79–88
Jannach, D., Schmitz, T., Shchekotykhin, K.: Parallel Model-Based Diagnosis On Multi-Core Computers. Journal of Artificial Intelligence Research (JAIR) 55 (2016) 835–887
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. (1979)
Eiter, T., Gottlob, G.: The Complexity of Logic-Based Abduction. Journal of the ACM 42(1) (1995) 3–42
de Kleer, J.: Hitting Set Algorithms for Model-based Diagnosis. In: DX’11. (2011) 100–105
Stern, R., Kalech, M., Feldman, A., Provan, G.: Exploring the Duality in Conflict-Directed Model-Based Diagnosis. In: AAAI’12. (2012) 828–834
Marques-Silva, J., Janota, M., Ignatiev, A., Morgado, A.: Efficient Model Based Diagnosis with Maximum Satisfiability. In: IJCAI’15. (2015) 1966–1972
de Kleer, J., Williams, B.C.: Diagnosing Multiple Faults. Artif. Intell. 32(1) (apr 1987) 97–130
Williams, B.C., Ragno, R.J.: Conflict-directed A* and its Role in Model-based Embedded Eystems. Discrete Applied Mathematics 155(12) (2007) 1562–1595
Darwiche, A.: Model-Based Diagnosis using Structured System Descriptions. Journal of Artificial Intelligence Research 8 (1998) 165–222
Siddiqi, S., Huang, J.: Sequential Diagnosis by Abstraction. Journal of Artificial Intelligence Research 41 (2011) 329–365
Darwiche, A.: A Differential Approach to Inference in Bayesian Networks. Journal of the ACM 50(3) (May 2003) 280–305
Pill, I., Quaritsch, T.: Optimizations for the Boolean Approach to Computing Minimal Hitting Sets. In: ECAI’12. (2012) 648–653
Feldman, A., Provan, G., de Kleer, J., Robert, S., van Gemund, A.: Solving Model-Based Diagnosis Problems with Max-SAT Solvers and Vice Versa. In: DX’10. (2010) 185–192
Metodi, A., Stern, R., Kalech, M., Codish, M.: A Novel SAT-Based Approach to Model Based Diagnosis. Journal of Artificial Intelligence Research 51 (2014) 377–411
Mencia, C., Marques-Silva, J.: Efficient Relaxations of Over-constrained CSPs. In: ICTAI’14. (2014) 725–732
Mencía, C., Previti, A., Marques-Silva, J.: Literal-Based MCS Extraction. In: IJCAI’15. (2015) 1973–1979
Nica, I., Pill, I., Quaritsch, T.,Wotawa, F.: The Route to Success: A Performance Comparison of Diagnosis Algorithms. In: IJCAI’13. (2013) 1039–1045
Shchekotykhin, K., Friedrich, G., Fleiss, P., Rodler, P.: Interactive Ontology Debugging: Two Query Strategies for Efficient Fault Localization. Journal of Web Semantics 12–13 (2012) 88–103
Feldman, A., Provan, G., van Gemund, A.: Approximate Model-Based Diagnosis Using Greedy Stochastic Search. Journal of Artifcial Intelligence Research 38 (2010) 371–413
Li, L., Yunfei, J.: Computing Minimal Hitting Sets with Genetic Algorithm. In: DX’02. (2002) 1–4
Ram, D.J., Sreenivas, T.H., Subramaniam, K.G.: Parallel Simulated Annealing Algorithms. Journal of Parallel and Distributed Computing 37(2) (1996) 207 – 212
Burns, E., Lemons, S., Ruml, W., Zhou, R.: Best-First Heuristic Search for Multicore Machines. Journal of Artificial Intelligence Research 39 (2010) 689–743
Ferguson, C., Korf, R.E.: Distributed Tree Search and its Application to alphabeta Pruning. In: AAAI’88. (1988) 128–132
Brüngger, A., Marzetta, A., Fukuda, K., Nievergelt, J.: The Parallel Search Bench ZRAM and its Applications. Annals of Operations Research 90(0) (1999) 45–63
Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding All Justifications of OWL DL Entailments. In: ISWC 2007 + ASWC 2007. (2007) 267–280
Previti, A., Ignatiev, A., Morgado, A., Marques-Silva, J.: Prime Compilation of Non-Clausal Formulae. In: IJCAI’15. (2015) 1980–1987
Powley, C., Korf, R.E.: Single-agent Parallel Window Search. IEEE Transactions on Pattern Analysis and Machine Intelligence 13(5) (1991) 466–477
Anglano, C., Portinale, L.: Parallel Model-based Diagnosis using PVM. In: EuroPVM’96. (1996) 331–334
Wotawa, F.: A Variant of Reiter’s Hitting-set Algorithm. Information Processing Letters 79(1) (2001) 45–51
Phillips, M., Likhachev, M., Koenig, S.: PA*SE: Parallel A* for Slow Expansions. In: ICAPS’14. (2014)
Korf, R.E., Schultze, P.: Large-scale Parallel Breadth-first Search. In: AAAI’05. (2005) 1380–1385
Shchekotykhin, K.M., Friedrich, G., Rodler, P., Fleiss, P.: Sequential Diagnosis of High Cardinality Faults in Knowledge-Bases by Direct Diagnosis Generation. In: ECAI’14. (2014) 813–818
Kurtoglu, T., Feldman, A.: Third International Diagnostic Competition (DXC 11). https://sites.google.com/site/dxcompetition2011 (2011) Accessed: 2016-03-15.
Prud’homme, C., Fages, J.G., Lorca, X.: Choco Documentation. (2015) http://www.choco-solver.org.
Cardoso, N., Abreu, R.: A Distributed Approach to Diagnosis Candidate Generation. In: EPIA’13. (2013) 175–186
Abreu, R., van Gemund, A.J.C.: A Low-Cost Approximate Minimal Hitting Set Algorithm and its Application to Model-Based Diagnosis. In: SARA’09. (2009) 2–9
Dean, J., Ghemawat, S.: MapReduce: Simplified Data Processing on Large Clusters. Communications of the ACM 51(1) (2008) 107–113
Zhao, X., Ouyang, D.: Deriving All Minimal Hitting Sets Based on Join Relation. IEEE Transactions on Systems, Man, and Cybernetics: Systems 45(7) (2015) 1063–1076
Lin, L., Jiang, Y.: The computation of Hitting Sets: Review and New Algorithms. Information Processing Letters 86(4) (2003) 177–184
Acknowledgements
The authors were supported by the Carinthian Science Fund (KWF) under contract KWF-3520/26767/38701, the Austrian Science Fund (FWF) and the German Research Foundation (DFG) under contract numbers I 2144 N-15 and JA 2095/4-1 (Project “Debugging of Spreadsheet Programs”).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Shchekotykhin, K., Jannach, D., Schmitz, T. (2018). Parallel Model-Based Diagnosis. In: Hamadi, Y., Sais, L. (eds) Handbook of Parallel Constraint Reasoning. Springer, Cham. https://doi.org/10.1007/978-3-319-63516-3_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-63516-3_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-63515-6
Online ISBN: 978-3-319-63516-3
eBook Packages: Computer ScienceComputer Science (R0)