Projects per year
Abstract
We build on a recently proposed method for stepwise explaining the solutions to Constraint Satisfaction Problems (CSPs) in a human understandable way. An explanation here is a sequence of simple inference steps where simplicity is quantified by a cost function. Explanation generation algorithms rely on extracting Minimal Unsatisfiable Subsets (MUSs) of a derived unsatisfiable formula, exploiting a one-to-one correspondence between so-called non-redindant explanations and MUSs. However, MUS extraction algorithms do not guarantee subset minimality or optimality with respect to a given cost function. Therefore, we build on these formal foundations and address the main points of improvement, namely how to generate explanations efficiently that are provably optimal (with respect to the given cost metric). To this end, we developed (1) a hitting set-based algorithm for finding the optimal constrained unsatisfiable subsets; (2) a method for reusing relevant information across multiple algorithm calls; and (3) methods for exploiting domain-specific information to speed up the generation of explanation sequences. We have experimentally validated our algorithms on a large number of CSP problems. We found that our algorithms outperform the MUS approach in terms of explanation qiality and compitational time (on average up to 56 % faster than a standard MUS approach).
Original language | English |
---|---|
Pages (from-to) | 709-746 |
Number of pages | 38 |
Journal | Journal of Artificial Intelligence Research |
Volume | 78 |
DOIs | |
Publication status | Published - 25 Nov 2023 |
Bibliographical note
Funding Information:This research received partial funding from the Flemish Government (AI Research Program); the FWO Flanders project G070521N; and funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (Grant No. 101002802, CHAT-Opt).
Publisher Copyright:
©2023 The Authors. Published by AI Access Foundation.
Keywords
- Minimal unsatisifiable Subsets
- explainable AI (XAI)
- Constraint Satisfaction Problem
- Constraint Programming
- Algorithm
- Unsatifiable Subset optimization
Fingerprint
Dive into the research topics of 'Efficiently Explaining CSPs with Unsatisfiable Subset Optimization'. Together they form a unique fingerprint.-
VLAAI1: Flanders Artificial Intelligence Research program (FAIR) – second cycle
1/01/24 → 31/12/28
Project: Applied
-
FWOAL1002: FRESCO: A FRamework for Explainable Solving and Constraint Optimization
1/01/21 → 31/12/24
Project: Fundamental
Research output
- 3 Citations
- 1 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 › Research
Open AccessFile7 Citations (Scopus)112 Downloads (Pure)