Projects per year
Abstract
Recently, a novel method for explaining solutions of constraint satisfaction problems was proposed.
An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.
The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.
To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms.
An explanation in that method is a sequence of simple inference steps, where the simplicity of an inference step depends on the number and types of constraints used, eventually explaining all logical consequences of the problem.
The current paper tackles two questions left in builds on these formal foundations and tackles two trailing questions: namely how to generate explanations that are provably optimal (with respect to the given cost metric) and how to generate them efficiently.
To answer these questions, we develop 1) an implicit hitting set algorithm for finding optimal unsatisfiable subsets; 2) a method to reduce multiple calls for (optimal) unsatisfiable subsets to a single call that takes constraints on the subset into account, and 3) a method for re-using relevant information over multiple calls to these algorithms.
Original language | English |
---|---|
Title of host publication | Efficiently Explaining CSPs with Unsatisfiable Subset Optimization |
Editors | Zhi-Hua Zhou |
Publisher | IJCAI |
Chapter | Main Track |
Pages | 1381-1388 |
Number of pages | 8 |
ISBN (Electronic) | 978-0-9992411-9-6 |
DOIs | |
Publication status | Published - 2021 |
Event | 30th International Joint Conference on Artificial Intelligence (IJCAI-21): IJCAI-21 - Canada, Montreal, Canada Duration: 21 Aug 2021 → 26 Aug 2021 https://ijcai-21.org/ |
Publication series
Name | IJCAI International Joint Conference on Artificial Intelligence |
---|---|
ISSN (Print) | 1045-0823 |
Conference
Conference | 30th International Joint Conference on Artificial Intelligence (IJCAI-21) |
---|---|
Abbreviated title | IJCAI 2021 |
Country | Canada |
City | Montreal |
Period | 21/08/21 → 26/08/21 |
Internet address |
Keywords
- Weighted Unsatisfiable Subsets
- constraint satisfaction
- Algorithm
- Explainable AI
- Artificial intelligence
Fingerprint
Dive into the research topics of 'Efficiently Explaining CSPs with Unsatisfiable Subset Optimization'. 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
-
A framework for step-wise explaining how to solve constraint satisfaction problems
Bogaerts, B., Gamba, E. & Guns, T., Nov 2021, In: Artificial Intelligence. 300, 103550.Research output: Contribution to journal › Article › peer-review
Open AccessFile2 Citations (Scopus)39 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)