Model-Based Diagnosis with Multiple Observations

Model-Based Diagnosis with Multiple Observations

Alexey Ignatiev, Antonio Morgado, Georg Weissenbacher, Joao Marques-Silva

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 1108-1115. https://doi.org/10.24963/ijcai.2019/155

Existing automated testing frameworks require multiple observations to be jointly diagnosed with the purpose of identifying common fault locations. This is the case for example with continuous integration tools. This paper shows that existing solutions fail to compute the set of minimal diagnoses, and as a result run times can increase by orders of magnitude. The paper proposes not only solutions to correct existing algorithms, but also conditions for improving their run times. Nevertheless, the diagnosis of multiple observations raises a number of important computational challenges, which even the corrected algorithms are often unable to cope with. As a result, the paper devises a novel algorithm for diagnosing multiple observations, which is shown to enable significant performance improvements in practice.
Keywords:
Constraints and SAT: MaxSAT, MinSAT
Knowledge Representation and Reasoning: Diagnosis and Abductive Reasoning
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Constraints and SAT: SAT: Applications