Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

Amaneddine, Nouhad; Condotta, Jean-François; Sioutis, Michael

Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

Nouhad Amaneddine, Jean-François Condotta, Michael Sioutis

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 696-701.

Abstract

The Interval Algebra (IA) and a subset of the Region Connection Calculus (RCC), namely RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. Such qualitative information can be formulated as a Qualitative Constraint Network (QCN). In this paper, we focus on the minimal labeling problem (MLP) and we propose an algorithm to efficiently derive all the feasible base relations of a QCN. Our algorithm considers chordal QCNs and a new form of partial consistency. Further, the proposed algorithm uses tractable subclasses of relations having a specific patchwork property for which closure under weak composition implies the consistency of the input QCN. Experimentations with QCNs of IA and RCC-8 show the importance and efficiency of this new approach.

Nouhad Amaneddine, Jean-François Condotta, and Michael Sioutis. 2013. Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13. IJCAI, 696–701. https://ijcai.org/proceedings/2013/110

@inproceedings{ijcai2013p110,
  title     = {Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints},
  author    = {Amaneddine, Nouhad and Condotta, Jean-François and Sioutis, Michael},
  booktitle = {Proceedings of the Twenty-Third International Joint Conference on
               Artificial Intelligence, {IJCAI-13}},
  publisher = {AAAI Press / International Joint Conferences on Artificial Intelligence},
  editor    = {Francesca Rossi},
  pages     = {696--701},
  year      = {2013},
  month     = {8},
  url       = {https://ijcai.org/proceedings/2013/110},
}

TY  - CPAPER
TI  - Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints
AU  - Amaneddine, Nouhad
AU  - Condotta, Jean-François
AU  - Sioutis, Michael
T2  - Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, IJCAI-13
PB  - AAAI Press / International Joint Conferences on Artificial Intelligence
PY  - 2013
SP  - 696
EP  - 701
UR  - https://ijcai.org/proceedings/2013/110
ER  -