Efficient methods for qualitative spatial and temporal reasoning

Abstract

Qualitative aspects of spatial or temporal information such as the distance between points, duration between events, and topology between regions can be modelled by a qualitative calculus. It represent the relations between various entities in space or time by a set of base relations, and ambiguity or incomplete knowledge can be expressed as a disjunction of different possible base relations. This thesis investigates the reasoning problem of such qualitative spatial or temporal calculi, where the task is to determine whether a given set of spatial or temporal information is consistent. The main challenge is to deal with the large number of possible relations between the spatial or temporal entities, and to find the solution in an efficient manner. This thesis approaches this challenge from several directions. We first investigate if there are some relations in a qualitative calculus which could form constraint networks that make the reasoning problem difficult. This would help us to determine whether tractable reasoning is actually possible. Secondly, we investigate algebraic properties of a qualitative calculus. We present a condition of the qualitative calculus that ensures no inconsistencies can be introduced when combining two constraint networks that share information in common. Thirdly, we reverse this process to decompose a constraint network into many smaller components to decide consistency. We evaluate our results using a well known qualitative temporal calculus, Allen's Interval Algebra, and show that this leads to a significant improvement to current state of the art. Finally, we apply the network decomposition approach to large qualitative calculi such as Rectangle Algebra and Block Algebra. The latter was previously considered too large for any efficient reasoning. We show that our approach works well for most instances of these calculi, and that efficient reasoning with these highly expressive spatial calculi is indeed possible.