Projects per year
Abstract
We explore the problem of step-wise explaining how to solve constraint satisfaction problems, with a use case on logic grid puzzles. More specifically, we study the problem of explaining the inference steps that one can take during propagation, in a way that is easy to interpret for a person. Thereby, we aim to give the constraint solver explainable agency, which can help in building trust in the solver by being able to understand and even learn from the explanations. The main challenge is that of finding a sequence of simple explanations, where each explanation should aim to be as cognitively easy as possible for a human to verify and understand. This contrasts with the arbitrary combination of facts and constraints that the solver may use when propagating. We propose the use of a cost function to quantify how simple an individual explanation of an inference step is, and identify the explanation-production problem of finding the best sequence of explanations of a CSP. Our approach is agnostic of the underlying constraint propagation mechanisms, and can provide explanations even for inference steps resulting from combinations of constraints. In case multiple constraints are involved, we also develop a mechanism that allows to break the most difficult steps up and thus gives the user the ability to zoom in on specific parts of the explanation. Our proposed algorithm iteratively constructs the explanation sequence by using an optimistic estimate of the cost function to guide the search for the best explanation at each step. Our experiments on logic grid puzzles show the feasibility of the approach in terms of the quality of the individual explanations and the resulting explanation sequences obtained.
Original language | English |
---|---|
Article number | 103550 |
Journal | Artificial Intelligence |
Volume | 300 |
DOIs | |
Publication status | Published - Nov 2021 |
Bibliographical note
Funding Information:This research received funding from the Flemish Government under the ‘Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen’ programme and the FWO Flanders project G070521N . We thank Jens Claes (and his master thesis supervisor Marc Denecker) for the implementation of a typed extension of the Blackburn & Bos framework as part of his master's thesis, as well as Rocsildes Canoy for his help with the NLP aspect of the information pipeline.
Publisher Copyright:
© 2021 The Authors
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
Keywords
- Artificial Intelligence
- constraint satisfaction
- explanation
- Explainable AI
- MUS
- Natural language processing
- Logic programming
- explanatory framework
Fingerprint
Dive into the research topics of 'A framework for step-wise explaining how to solve constraint satisfaction problems'. Together they form a unique fingerprint.Projects
- 2 Active
-
FWOAL1002: FRESCO: A FRamework for Explainable Solving and Constraint Optimization
1/01/21 → 31/12/24
Project: Fundamental
-
VLAAI1: Subsidie: Onderzoeksprogramma Artificiële Intelligentie (AI) Vlaanderen
1/07/19 → 31/12/23
Project: Applied
Research output
- 2 Citations
- 3 Conference paper
-
Efficiently Explaining CSPs with Unsatisfiable Subset Optimization
Gamba, E., Bogaerts, B. & Guns, T., 2021, Efficiently Explaining CSPs with Unsatisfiable Subset Optimization . Zhou, Z-H. (ed.). IJCAI, p. 1381-1388 8 p. 191. (IJCAI International Joint Conference on Artificial Intelligence).Research output: Chapter in Book/Report/Conference proceeding › Conference paper
Open AccessFile1 Citation (Scopus)63 Downloads (Pure) -
Step-wise Explanations of Constraint Satisfaction Problems
Bogaerts, B., Gamba, E., Guns, T. & Claes, J., 24 Aug 2020, ECAI 2020 - 24th European Conference on Artificial Intelligence, including 10th Conference on Prestigious Applications of Artificial Intelligence, PAIS 2020 - Proceedings. De Giacomo, G., Catala, A., Dilkina, B., Milano, M., Barro, S., Bugarin, A. & Lang, J. (eds.). IOS Press, Vol. 325. p. 640-647 8 p. (Frontiers in Artificial Intelligence and Applications; vol. 325).Research output: Chapter in Book/Report/Conference proceeding › Conference paper
Open AccessFile5 Citations (Scopus)78 Downloads (Pure) -
ZebraTutor: Explaining how to solve logic grid puzzles (demo)
Claes, J., Bogaerts, B., Canoy, R., Gamba, E. & Guns, T., 1 Jan 2019, Proceedings of the 31st Benelux Conference on Artificial Intelligence (demos). RWTH Aachen, Vol. 2491. p. 96-96 1 p. (CEUR Workshop Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Conference paper
Open AccessFile
Datasets
-
A framework for step-wise explaining how to solve constraint satisfaction problems
Gamba, E. (Creator), Bogaerts, B. (Creator), Guns, T. (Creator) & Claes, J. (Creator), Zenodo, 2021
DOI: 10.5281/zenodo.4966599, http://10.1016/j.artint.2021.103550
Dataset
Activities
- 1 Talk or presentation at a workshop/seminar
-
Step-wise Explaining How to Solve Constraint Satisfaction Problems
Bart Bogaerts (Speaker), Emilio Gamba (Contributor) & Tias Guns (Contributor)
13 Sep 2020Activity: Talk or presentation › Talk or presentation at a workshop/seminar
File