Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework

Abstract : Time and space are fundamental concepts of study in Artificial Intelligence and, in particular, Knowledge Representation. In this paper, we investigate the task of ordering a temporal sequence of qualitative spatial configurations to meet certain transition constraints. This ordering is constrained by the use of conceptual neighbourhood graphs defined on qualitative spatial constraint languages. In particular, we show that the problem of ordering a sequence of qualitative spatial configurations to meet such transition constraints is $\mathcal{NP}$-complete for the the well known languages of RCC-8, Interval Algebra, and Block Algebra. Based on this result, we also propose a framework where the temporal aspect of a sequence of qualitative spatial configurations is constrained by a Point Algebra network, and again show that the enhanced problem is in $\mathcal{NP}$ when considering the aforementioned languages. Our results lie within the area of Graph Traversal and allow for many practical and diverse applications, such as identifying optimal routes in mobile robot navigation, modelling changes of topology in biological processes, and computing sequences of segmentation steps used in image processing algorithms.
Type de document :
Communication dans un congrès
Richard Chbeir; Yannis Manolopoulos; Ilias Maglogiannis; Reda Alhajj. 11th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI 2015), Sep 2015, Bayonne, France. IFIP Advances in Information and Communication Technology, AICT-458, pp.130-150, 2015, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-23868-5_10〉
Domaine :

Littérature citée [20 références]

https://hal.inria.fr/hal-01385350
Contributeur : Hal Ifip <>
Soumis le : vendredi 21 octobre 2016 - 11:38:06
Dernière modification le : vendredi 1 décembre 2017 - 01:16:44

Fichier

978-3-319-23868-5_10_Chapter.p...
Fichiers produits par l'(les) auteur(s)

Citation

Michael Sioutis, Jean-François Condotta, Yakoub Salhi, Bertrand Mazure, David Randell. Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework. Richard Chbeir; Yannis Manolopoulos; Ilias Maglogiannis; Reda Alhajj. 11th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI 2015), Sep 2015, Bayonne, France. IFIP Advances in Information and Communication Technology, AICT-458, pp.130-150, 2015, Artificial Intelligence Applications and Innovations. 〈10.1007/978-3-319-23868-5_10〉. 〈hal-01385350〉

Métriques

Consultations de la notice