15th European Conference on Artificial Intelligence
  July 21-26 2002     Lyon     France  
   

ECAI-2002 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

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.


[prev] [tofc] [next]


ECAI-2002 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the UniversitÚ Claude Bernard and INSA, Lyon, on behalf of Association Franšaise pour l'Intelligence Artificielle.