ECAI-2002 Conference Paper

[full paper]

Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity

Alfonso Gerevini, Bernhard Nebel

There exist a number of qualitative constraint calculi that are used to represent and reason about temporal or spatial configurations. However, there are only very few approaches aiming to create a spatio- temporal constraint calculus. Similar to Bennett et al., we start with the spatial calculus RCC-8 and Allen's interval calculus in order to construct a qualitative spatio-temporal calculus. As we will show, the basic calculus is NP-complete, even if we only permit base relations. When adding the restriction that spatial changes are continuous over time, the calculus becomes more useful, but the satisfiability problem appears to be much harder. Nevertheless, we are able to show that satisfiability is still in NP. Finally, we specify an inference algorithm making use of tractable fragments of the combined calculus.

Keywords: Spatial Reasoning, Temporal Reasoning, Constraint Satisfaction, Knowledge Representation

Citation: Alfonso Gerevini, Bernhard Nebel: Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's Interval Calculus: Computational Complexity. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.312-316.