Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints
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.
Cite
Text
Amaneddine et al. "Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints." International Joint Conference on Artificial Intelligence, 2013.Markdown
[Amaneddine et al. "Efficient Approach to Solve the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints." International Joint Conference on Artificial Intelligence, 2013.](https://mlanthology.org/ijcai/2013/amaneddine2013ijcai-efficient/)BibTeX
@inproceedings{amaneddine2013ijcai-efficient,
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 = {International Joint Conference on Artificial Intelligence},
year = {2013},
pages = {696-702},
url = {https://mlanthology.org/ijcai/2013/amaneddine2013ijcai-efficient/}
}