Abstract
Model-based diagnosis is a technique for identifying malfunctioning components in systems. While it has successfully been applied to systems such as digital circuits, this paper aims to extend applicability to systems such as programs that process values from large domains, for example, term structures. In these cases, especially when multiple components may be faulty, it is challenging to identify a diagnosis that provides a consistent model with respect to the specified domain. This paper presents an Answer-Set Programming (ASP) based method for computing such diagnoses. We are particularly interested in functional circuits over domains of values, such as rational numbers and inductive data types, to diagnose faults in programming assignments in order to advance intelligent tutoring systems. This article shows how a consistent diagnosis, justified by intermediate values, can be achieved efficiently using ASP. Additionally, an adaption to Constraint Answer Set Programming with s(CASP) is presented that avoids grounding, allowing domain sizes to be handled that are too large to be grounded.
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
Similar content being viewed by others
Notes
- 1.
s(CASP) does not yet fully implement the ASP Core 2 language standard, therefore, a direct translation is not always possible [4].
- 2.
Since s(CASP) provides the option to interface with alternative constraint solvers where an integer constraint solver might be an alternative.
References
Arias, J., Carro, M., Chen, Z., Gupta, G.: Justifications for goal-directed constraint answer set programming. arXiv preprint arXiv:2009.10238 (2020)
Arias, J., Carro, M., Salazar, E., Marple, K., Gupta, G.: Constraint answer set programming without grounding. Theory Pract. Logic Program. 18(3–4), 337–354 (2018)
Brewka, G., Eiter, T., Truszczyński, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)
Calimeri, F., et al.: ASP-Core-2 input language format. Theory Pract. Logic Program. 20(2), 294–309 (2020). https://doi.org/10.1017/S1471068419000450
Clark, K.L.: Negation as failure. In: Gallaire, H., Minker, J. (eds.) Logic and Data Bases, pp. 293–322. Springer, Boston (1978). https://doi.org/10.1007/978-1-4684-3384-5_11
Console, L., Torasso, P.: A spectrum of logical definitions of model-based diagnosis. Comput. Intell. 7(3), 133–141 (1991)
Davis, R.: Diagnostic reasoning based on structure and behavior. Artif. Intell. 24(1–3), 347–410 (1984)
De Kleer, J., Williams, B.C.: Diagnosing multiple faults. Artif. Intell. 32(1), 97–130 (1987)
Dechter, R., Cohen, D., et al.: Constraint Processing. Morgan Kaufmann, Burlington (2003)
Friedrich, G., Gottlob, G., Nejdl, W.: Physical impossibility instead of fault models. In: AAAI, vol. 90, pp. 331–336 (1990)
Friedrich, G., Nejdl, W.: MOMO-model-based diagnosis for everybody. In: Sixth Conference on Artificial Intelligence for Applications, pp. 206–213. IEEE (1990)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Multi-shot ASP solving with clingo. CoRR abs/1705.09811 (2017)
Gebser, M., Schaub, T., Thiele, S.: GrinGo: a new grounder for answer set programming. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS, vol. 4483, pp. 266–271. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72200-7_24
Gupta, G., et al.: Automating commonsense reasoning with ASP and s(CASP). In: Proceedings of 2nd Workshop on Goal-directed Execution of Answer Set Programs (GDE 2022) (2022)
Janhunen, T., Nimelä, I.: The answer set programming paradigm. AI Mag. 37(3), 13–24 (2016)
Jannach, D., Schmitz, T.: Model-based diagnosis of spreadsheet programs: a constraint-based debugging approach. Autom. Softw. Eng. 23, 105–144 (2016)
Keuning, H., Jeuring, J., Heeren, B.: Towards a systematic review of automated feedback generation for programming exercises. In: Proceedings of the 2016 ACM Conference on Innovation and Technology in Computer Science Education, pp. 41–46 (2016)
de Kleer, J.: Focusing on probable diagnoses. In: AAAI, vol. 91, pp. 842–848 (1991)
Kuhlmann, I., Gessler, A., Laszlo, V., Thimm, M.: A comparison of ASP-based and SAT-based algorithms for the contension inconsistency measure. In: Dupin de Saint-Cyr, F., Öztürk-Escoffier, M., Potyka, N. (eds.) SUM 2022. LNCS, vol. 13562, pp. 139–153. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-18843-5_10
Ligeza, A.: Towards constructive abduction. In: KEOD, pp. 352–357 (2015)
Ligeza, A.: Constraint programming for constructive abduction. A case study in diagnostic model-based reasoning. In: Koscielny, J., Syfert, M., Sztyber, A. (eds.) DPS 2017. AISC, vol. 635, pp. 94–105. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-64474-5_8
Marple, K., Salazar, E., Chen, Z., Gupta, G.: The s(ASP) predicate answer set programming system. The Association for Logic Programming Newsletter (2017)
Mozetič, I., Holzbaur, C., Novak, F., Santo-Zarnik, M.: Model-Based Analogue Circuit Diagnosis with CLP(R). In: Brauer, W., Hernández, D. (eds.) Verteilte Künstliche Intelligenz und kooperatives Arbeiten. Informatik-Fachberichte, vol. 291, pp. 343–353. Springer, Heidelberg (1991). https://doi.org/10.1007/978-3-642-76980-1_31
Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57–95 (1987)
Struss, P., Dressler, O.: “Physical Negation” integrating fault models into the general diagnostic engine. In: IJCAI, vol. 89, pp. 1318–1323 (1989)
Wotawa, F.: On the use of answer set programming for model-based diagnosis. In: Fujita, H., Fournier-Viger, P., Ali, M., Sasaki, J. (eds.) IEA/AIE 2020. LNCS, vol. 12144, pp. 518–529. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-55789-8_45
Wotawa, F., Dumitru, V.A.: The Java2CSP debugging tool utilizing constraint solving and model-based diagnosis principles. In: Fujita, H., Fournier-Viger, P., Ali, M., Wang, Y. (eds.) IEA/AIE 2022. LNCS, vol. 13343, pp. 543–554. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-08530-7_46
Wotawa, F., Kaufmann, D.: Model-based reasoning using answer set programming. Appl. Intell. 1–19 (2022)
Wotawa, F., Nica, M., Moraru, I.: Automated debugging based on a constraint model of the program and a test case. J. Logic Algebraic Program. 81(4), 390–407 (2012)
Acknowledgments
This work has been carried out in the context of the VoLL-KI project (grant 16DHKBI091), funded by Bundesministeriums für Bildung und Forschung (BMBF).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bayerkuhnlein, M., Wolter, D. (2024). Model-Based Diagnosis with ASP for Non-groundable Domains. In: Meier, A., Ortiz, M. (eds) Foundations of Information and Knowledge Systems. FoIKS 2024. Lecture Notes in Computer Science, vol 14589. Springer, Cham. https://doi.org/10.1007/978-3-031-56940-1_20
Download citation
DOI: https://doi.org/10.1007/978-3-031-56940-1_20
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-56939-5
Online ISBN: 978-3-031-56940-1
eBook Packages: Computer ScienceComputer Science (R0)