• Funding : CRIL
  • Start year :
  • 2019

Context

Constraint satisfaction problems (CSP) [Lec13] provide a powerful framework for representing and solving many combinatorial problems (planning, scheduling, configuration…). When a CSP problem is consistent, we obtain an easily exploitable solution. On the contrary, when a CSP problem is inconsistent, it is more difficult to explain the reason for this inconsistency [HLSB06, GMP07, GLM14]. Even so, these explanations are important because they can help the user to understand why the formula is inconsistent. The goal of this thesis internship is to start studying a new type of explanation of inconsistency through the concept of “weak core”.

Topic

This work is situated in the framework of explainable artificial intelligence. The goal is to be able to explain to a user why a constraint network is unsatisfiable, where it does not have all the expected solutions. When the network is unsatisfiable, a well-known technique to provide this explanation is to identify a MUC (minimal inconsistent subset). Unfortunately, MUCs are not usable for a user if they are either too big, too long to obtain, or when the network is satisfiable. The notion of weak core allows to generalize the notion of MUC to obtain, depending on the case, a partial explanation, or an explanation of the absence of some solutions. A weak core can be defined as a subset of constraints having at most either a fixed number of solutions or a fixed proportion of solutions. We believe that the identification of small weak cores may allow the user to better understand the reason for a global inconsistency compared to a large minimal inconsistent subset (MUC). As an example, if an inconsistent problem admits a small weak core with only 10 solutions, it may be easy for the user to understand the reasons why this core is almost inconsistent, and to check by hand that the remaining 10 solutions cannot be expanded globally.

In order to be relevant to the user, weak cores should correspond to a cluster of constraints that are semantically related. This can be ensured by asking either to minimize the number of variables in the cores, or to label semantically related constraints with the same label and minimize the number of different labels in the weak cores. Identifying weak cores is clearly computationally hard, but the problem might sometimes prove easier in practice than proving inconsistency(computational time). Identifying interesting weak cores is likely to be even more difficult (and expensive), but approximating weak cores can probably be done efficiently because it does not require exploring the entire search space.

Another use of weak cores is to help identify why the network does not have as many solutions as one would expect. For example, for the problem of constructing a schedule, if the user obtains solutions but they are not satisfactory, the search for weak cores will make it possible to identify the most constrained sub-set which eliminates the solutions that one would like to have.

References

[BHvM09] Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009. Hans Kleine Büning and Oliver Kullmann. Handbook of satisfiability, chapter 11: Minimal Unsatisfia- bility and Autarkies. Volume 185 of [BHvM09], 2009.

[BK09] Bart Selman Carla P. Gomes, Ashish Sabharwal. Handbook of satisfiability, chapter 20: Model Counting. Volume 185 of [BHvM09], 2009.

[GLM14] Eric Grégoire, Jean-Marie Lagniez, and Bertrand Mazure. Boosting MUC extraction in unsatisfiable constraint networks. Appl. Intell., 41(4):1012–1023, 2014.

[CPG09][gmp07] Eric Grégoire, Bertrand Mazure, and Ce ́dric Piette. MUST: provide a finer-grained explanation of un- satisfiability. In Principles and Practice of Constraint Programming - CP, Proceedings, pages 317–331, 2007.

[HLSB06] Fred Hemery, Christophe Lecoutre, Lakhdar Sais, and Frédéric Boussemart. Extracting mucs from con- straint networks. In ECAI 2006, 17th European Conference on Artificial Intelligence, Proceedings, pages 113–117, 2006.

[Lec13] Christophe Lecoutre. Constraint Networks: Targeting Simplicity for Techniques and Algorithms. John Wiley & Sons, 2013.