Projects per year
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. 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. We propose an approach that is agnostic of the underlying constraint propagation mechanisms, and that can provide explanations even for inference steps resulting from combinations of constraints. 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 sequences obtained.
|Title of host publication||ECAI 2020 - 24th European Conference on Artificial Intelligence, including 10th Conference on Prestigious Applications of Artificial Intelligence, PAIS 2020 - Proceedings|
|Editors||Giuseppe De Giacomo, Alejandro Catala, Bistra Dilkina, Michela Milano, Senen Barro, Alberto Bugarin, Jerome Lang|
|Number of pages||8|
|Publication status||Published - 24 Aug 2020|
|Event||European Conference on Artificial Intelligence (ECAI 2020) - Santiago De Compostela, Spain|
Duration: 29 Aug 2020 → 2 Sep 2020
Conference number: 24
|Name||Frontiers in Artificial Intelligence and Applications|
|Conference||European Conference on Artificial Intelligence (ECAI 2020)|
|City||Santiago De Compostela|
|Period||29/08/20 → 2/09/20|
- Hybrid AI
- Explainable AI
- First-order logic
FingerprintDive into the research topics of 'Step-wise Explanations of Constraint Satisfaction Problems'. Together they form a unique fingerprint.
- 2 Active
1/01/21 → 31/12/24
1/07/19 → 31/12/23
Bogaerts, B., Gamba, E. & Guns, T., Nov 2021, In: Artificial Intelligence. 300, 103550.
Research output: Contribution to journal › Article › peer-reviewOpen AccessFile2 Citations (Scopus)39 Downloads (Pure)
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 paperOpen AccessFile1 Citation (Scopus)63 Downloads (Pure)
Bogaerts, B., Gamba, E., Canoy, R. & Guns, T., 7 Nov 2019, (Unpublished).
Research output: Unpublished contribution to conference › PosterFile
13 Sep 2020
Activity: Talk or presentation › Talk or presentation at a workshop/seminarFile
29 Aug 2020
Activity: Talk or presentation › Talk or presentation at a conferenceFile