15
^{th} European Conference on Artificial Intelligence |

July 21-26 2002 Lyon France |
||

[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.

ECAI-2002 is organised by the