Abstract: Time and space are fundamental concepts of study in Artificial Intelligence and, in particular, Knowledge Representation. In this talk, 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 neighborhood 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 study an optimization variant of the problem, and show that in certain cases this variant belongs to the class of polynomially bounded NP-optimization problems. 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.

Date: 06 January 2016