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.5
URN: urn:nbn:de:0030-drops-190957
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19095/
Go to the corresponding LIPIcs Volume Portal

Salhi, Yakoub ; Sioutis, Michael

Prime Scenarios in Qualitative Spatial and Temporal Reasoning

pdf-format:
LIPIcs-TIME-2023-5.pdf (1.0 MB)

Abstract

The concept of prime implicant is a fundamental tool in Boolean algebra, which is used in Boolean circuit design and, recently, in explainable AI. This study investigates an analogous concept in qualitative spatial and temporal reasoning, called prime scenario. Specifically, we define a prime scenario of a qualitative constraint network (QCN) as a minimal set of decisions that can uniquely determine solutions of this QCN. We propose in this paper a collection of algorithms designed to address various problems related to prime scenarios. The first three algorithms aim to generate a prime scenario from a scenario of a QCN. The main idea consists in using path consistency to identify the constraints that can be ignored to generate a prime scenario. The next two algorithms focus on generating a set of prime scenarios that cover all the scenarios of the original QCN: The first algorithm examines every branch of the search tree, while the second is based on the use of a SAT encoding. Our last algorithm is concerned with computing a minimum-size prime scenario by using a MaxSAT encoding built from countermodels of the original QCN. We show that this algorithm is particularly useful for measuring the robustness of a QCN. Finally, a preliminary experimental evaluation is performed with instances of Allen’s Interval Algebra to assess the efficiency of our algorithms and, hence, also the difficulty of the newly introduced problems here.

BibTeX - Entry

@InProceedings{salhi_et_al:LIPIcs.TIME.2023.5,
  author =	{Salhi, Yakoub and Sioutis, Michael},
  title =	{{Prime Scenarios in Qualitative Spatial and Temporal Reasoning}},
  booktitle =	{30th International Symposium on Temporal Representation and Reasoning (TIME 2023)},
  pages =	{5:1--5:14},
  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/19095},
  URN =		{urn:nbn:de:0030-drops-190957},
  doi =		{10.4230/LIPIcs.TIME.2023.5},
  annote =	{Keywords: Spatial and Temporal Reasoning, Qualitative Constraints, Prime Scenario, Prime Implicant, Robustness Measurement}
}

Keywords: Spatial and Temporal Reasoning, Qualitative Constraints, Prime Scenario, Prime Implicant, Robustness Measurement
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/9c0cbd2cd0954252ab96/

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