License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2023.12
URN: urn:nbn:de:0030-drops-191020
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19102/
Go to the corresponding LIPIcs Volume Portal

Sioutis, Michael

Embarrassingly Greedy Inconsistency Resolution of Qualitative Constraint Networks

pdf-format:
LIPIcs-TIME-2023-12.pdf (0.9 MB)

Abstract

In this paper, we deal with inconsistency resolution in qualitative constraint networks (QCN). This type of networks allows one to represent and reason about spatial or temporal information in a natural, human-like manner, e.g., by expressing relations of the form x {is north of ∨ is east of} y. On the other hand, inconsistency resolution involves maximizing the amount of information that is consistent in a knowledge base; in the context of QCNs, this translates to maximizing the number of constraints that can be satisfied, via obtaining a qualitative solution (scenario) of the QCN that ignores/violates as few of the original constraints as possible. To this end, we present two novel approaches: a greedy constraint-based and an optimal Partial MaxSAT-based one, with a focus on the former due to its simplicity. Specifically, the greedy technique consists in adding the constraints of a QCN to a new, initially empty network, one by one, all the while filtering out the ones that fail the satisfiability check. What makes or breaks this technique is the ordering in which the constraints will be processed to saturate the empty QCN, and for that purpose we use many different strategies to form a portfolio-style implementation. The Partial MaxSAT-based approach is powered by Horn theory-based maximal tractable subsets of relations. Finally, we compare the greedy approach with the optimal one, commenting on the trade-off between obtaining repairs that are optimal and obtaining repairs in a manner that is fast, and make our source code available for anyone to use.

BibTeX - Entry

@InProceedings{sioutis:LIPIcs.TIME.2023.12,
  author =	{Sioutis, Michael},
  title =	{{Embarrassingly Greedy Inconsistency Resolution of Qualitative Constraint Networks}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{12:1--12:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-298-3},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{278},
  editor =	{Artikis, Alexander and Bruse, Florian and Hunsberger, Luke},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/19102},
  URN =		{urn:nbn:de:0030-drops-191020},
  doi =		{10.4230/LIPIcs.TIME.2023.12},
  annote =	{Keywords: Spatial and Temporal Reasoning, Qualitative Constraints, Inconsistency Resolution, Maximizing Satisfiability, Greedy Algorithm, Partial MaxSAT Solver}
}

Keywords: Spatial and Temporal Reasoning, Qualitative Constraints, Inconsistency Resolution, Maximizing Satisfiability, Greedy Algorithm, Partial MaxSAT Solver
Collection: 30th International Symposium on Temporal Representation and Reasoning (TIME 2023)
Issue Date: 2023
Date of publication: 18.09.2023
Supplementary Material: Software: https://seafile.lirmm.fr/d/6127423776d145bab11a/

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI