Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework: 11th IFIP WG 12.5 International Conference, AIAI 2015, Bayonne, France, September 14–17, 2015, Proceedings

Michael Sioutis, Jean-François Condotta, Yakoub Salhi, Bertrand Mazure, David Randell

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)
143 Downloads (Pure)

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 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 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.
Original languageEnglish
Title of host publicationArtificial Intelligence Applications and Innovations
Subtitle of host publication11th IFIP WG 12.5 International Conference, AIAI 2015, Bayonne, France, September 14–17, 2015, Proceedings
EditorsRichard Chbeir , Yannis Manolopoulos, Ilias Maglogiannis, Reda Alhajj
PublisherSpringer
Pages130-150
Number of pages20
Volume458
ISBN (Electronic)978-3-319-23868-5
ISBN (Print)978-3-319-23867-8
DOIs
Publication statusPublished - 2015
Event11th IFIP WG 12.5 International Conference, Artificial Intelligence Applications and Innovations 2015 - Bayonne, France
Duration: 14 Sept 201517 Sept 2015

Publication series

Name IFIP Advances in Information and Communication Technology
PublisherSpringer
Volume458
ISSN (Print)1868-4238

Conference

Conference11th IFIP WG 12.5 International Conference, Artificial Intelligence Applications and Innovations 2015
Country/TerritoryFrance
CityBayonne
Period14/09/1517/09/15

Fingerprint

Dive into the research topics of 'Ordering Spatio-Temporal Sequences to Meet Transition Constraints: Complexity and Framework: 11th IFIP WG 12.5 International Conference, AIAI 2015, Bayonne, France, September 14–17, 2015, Proceedings'. Together they form a unique fingerprint.

Cite this