MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis

Shchekotykhin, Kostyantyn M.; Jannach, Dietmar; Schmitz, Thomas

MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis

Kostyantyn M. Shchekotykhin, Dietmar Jannach, Thomas Schmitz

Download BibTeX Cite

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Special Track on Knowledge Representation and Reasoning. Pages 3221-3227.

Abstract

The computation of minimal conflict sets is a central task when the goal is to find relaxations or explanations for overconstrained problem formulations and in particular in the context of Model-Based Diagnosis (MBD) approaches. In this paper we propose MergeXPlain, a non-intrusive conflict detection algorithm which implements a divide-and-conquer strategy to decompose a problem into a set of smaller independent subproblems. Our technique allows us to efficiently determine multiple minimal conflicts during one single problem decomposition run, which is particularly helpful in MBD problem settings. An empirical evaluation on various benchmark problems shows that our method can lead to a significant reduction of the required diagnosis times.

Kostyantyn M. Shchekotykhin, Dietmar Jannach, and Thomas Schmitz. 2015. MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15. IJCAI, 3221–3227. https://ijcai.org/proceedings/2015/454

@inproceedings{ijcai2015p454,
  title     = {MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis},
  author    = {Shchekotykhin, Kostyantyn M. and Jannach, Dietmar and Schmitz, Thomas},
  booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-15}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Qiang Yang and Michael Wooldridge},
  pages     = {3221--3227},
  year      = {2015},
  month     = {7},
  note      = {Special Track on Knowledge Representation and Reasoning},
  url       = {https://ijcai.org/proceedings/2015/454},
}

TY  - CPAPER
TI  - MergeXplain: Fast Computation of Multiple Conflicts for Diagnosis
AU  - Shchekotykhin, Kostyantyn M.
AU  - Jannach, Dietmar
AU  - Schmitz, Thomas
T2  - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2015
SP  - 3221
EP  - 3227
UR  - https://ijcai.org/proceedings/2015/454
ER  -