Several researchers have identified the combination of temporal and spatial constraint calculi as a research desideratum (see, e.g., [1,2,3,4]) and have started to analyze the semantic and computational properties of such temporalized spatial calculi. In particular, Nebel and Gerevini's calculus STCC [5] which allows for an explicit representation of time (cp. [6]) seems to be the most natural candidate for such a spatio-temporal calculus. We continued our analyses of this calculus, which combines RCC-8 and Allen's interval calculus. Since in this calculus satisfiability testing is NP-hard even if only basic relations and the two universal relations are permitted, the development of efficient reasoning algorithms is imperative. For this reason, we are developing a constraint propagation algorithm as well as different backtracking algorithms that allow for reasoning with STCC constraint satisfaction problems.

In addition to STCC, we analyzed the combination of the cardinal direction calculus [7,8] and Allen's interval calculus. We proved the correctness of the so-called neighborhood graph of the cardinal direction calculus by analytic means and showed how constraint satisfaction problems of the temporalized calculus can be translated into deterministic planning problems, which seems to be a promising approach for future research [9].

Reasoning techniques used for solving constraint satisfaction problems of STCC-like calculi crucially rely on the neighborhood graph of the underlying spatial calculus if objects are supposed to change spatial properties by continuous transformations [1,2,3]. We developed precise notions of continuous change for temporalized region-based calculi (such as STCC) and for temporalized point-based calculi (e.g., the temporalized cardinal direction calculus). Such precise continuity concepts are necessary to provide a well-founded semantics of temporalizations of spatial calculi that deal with continuous transformations. Moreover, we showed how such precise notions can be used to analytically prove the correctness of neighborhood graphs. Since classical neighborhood graphs, as discussed in the literature, only represent possible continuous transformations of at most two objects, we proposed a more flexible concept of neighborhood that allows for representing continuous transformations of arbitrarily many objects, in principle. We showed that for temporalized topological calculi (such as STCC) these generalized graphs can be generated from the classical neighborhood graphs and the composition tables of the spatial calculus at hand if only one object is allowed to move in each transformation step. Our results are published in two research papers in cooperation with R2-[BackSpace] [4,5].

[1]	Christian Freksa. Conceptual neighborhood and its role in temporal and spatial reasoning, Decision Support Systems and Qualitative Reasoning, 1991.
[2]	Max J. Egenhofer, Khaled K. Al-Taha. Reasoning about Gradual Changes of Topological Relationships., Spatio-Temporal Reasoning, 1992.
[3]	Antony Galton. Qualitative Spatial Change, 2000.
[4]	Marco Ragni, Stefan Wölfl. Temporalizing Spatial Calculi: On Generalized Neighborhood Graphs, Proceedings of the 28th Annual German Conference on AI (KI 2005), 2005.
[5]	Marco Ragni, Stefan Wölfl. Temporalizing Cardinal Directions: From Constraint Satisfaction to Planning, Proceedings of the Knowledge Representation Conference (KR 2006), 2006. pdf

In the domain of qualitative reasoning a large number of calculi for efficient reasoning about spatial and temporal entities have been developed. These calculi are designed for modeling specific aspects of space or time, respectively, to the effect that the class of intended models may vary widely with the calculus at hand. But from a formal point of view these calculi are often closely related to each other. For example, the spatial region connection calculus RCC-5 may be considered a coarsening of Allen's (temporal) interval calculus. And vice versa, intervals can be used to represent spatial objects that feature an internal direction. The central issue is to integrate these calculi and their semantics as well as logical dependencies between them by means of the Common Algebraic Specification Language (CASL) specifications (cf. [1]). In detail, we developed CASL libraries for

• basic topological concepts,
• the region connection calculi (the first order theory of RCC, RCC-5, and RCC-8) [2,3,4],
• Egenhofer and Franzosa's 4- and 9-intersection calculi [5,6],
• JEPD relation systems and induced relation algebras [7],
• Allen's interval algebra (based on Allen, Hayes, and Ladkin's first-order theory of intervals in linear time) [8,9,10],
• the modal-logical encoding of RCC-8 [11].

For more details see [12].

In cooperation with the R3-[QShape] project, we worked on qualitative modelling of right of way rules of sea navigation. We investigated the possibilities of several calculi resolving potential conflict situations, i.e., situations where boats are in danger of a future collision. The calculi currently considered are the Dipole Calculus and the OPRA_m calculi [1,2].

The aim of this work was to assess if formal approaches to reasoning such as the RCC theory and Allen's interval calculus mirror human reasoning (see [1,2,3,4]). This is often paraphrased with the term cognitive adequacy. Our work addressed two main issues:

1. the inferential adequacy of Allen's interval calculus and related conceptual neighborhood theories, and
2. the inferential adequacy of the RCC theory.

Regarding the Allen relations we published a set of studies [5,6] based on our previous findings that if a reasoning problem results in multiple relations, human reasoners find only a single relation -- the preferred one. In the new experiments we focused on conceptual neighborhoods and showed that other relations are reached by a revision process that starts from the preferred relation and then constructs alternative relations by local transformations. This principle is adequately mirrored in the formal approach of conceptual neighborhood (although there are some differences). From a practical point of view this is important as it shows that humans have additional problems with relations which are more difficult to reach in the neighborhood graph. They are more likely to be neglected than relations which require only minor revisions of the preferred relation.

In a second group of studies we focused on RCC calculi. In previous research we reported empirical evidence that supports the assumption that the topological relations of the RCC theory model human conceptual knowledge of spatial relationships [7]. Thus the RCC theory is conceptually adequate. In this part of the project we investigated if the RCC-8 relations are inferentially adequate. Together with Bolormaa Tseden we ran an experiment to explore preferences in reasoning with these RCC relations. In the experiment, the participants got two premises A r B , and B r C in which both r are based on RCC relations. Their task was to determine the relation A r C. Since we are interested in preferences, we explored only those combinations in which more than one relation is possible for A r C. As many researchers claim that such tasks are strongly dependent on cultural aspects we also conducted the study in Mongolia, where Bolormaa Tseden originates from. Interestingly the inter-cultural comparison of our findings suggests that basic spatial concepts are culturally-independent rather than culturally-dependent.

We conducted some initial studies on spatial concepts together with Alexander Klippel (University of Melbourne). In this work we used the grouping tool developed in our investigations on the conceptual adequacy of the RCC theory. With this tool, we collected human data on the mental representation of direction concepts and how these findings may revise formal models of spatial reasoning and navigation assistance systems. While early models were designed for unstructured space, for example, reasoning about cardinal directions, our research focused on the influence of context. Specifically, we explored how mental direction concepts in city street networks differ from those in sea or air navigation. The results are used to modify the direction concepts employed in a way-finding assistance framework. The main part of this research has been published in [1].

In previous computational work we have started to combine RCC-8 and Allen's interval calculus aiming to create a spatio-temporal constraint calculus [1]. In order to determine whether this calculus is cognitively adequate it is first necessary to understand how people reason (see, e.g., [2] about spatio-temporal relations. Due to the dearth of empirical work on this topic we implemented a task that allows us to establish a baseline for spatio-temporal reasoning in order to apply our findings to the RCC theory. This work is still in progress in collaboration with researchers from the Institut für Wissensmedien in Tübingen.

In our experimental set-up participants are required to draw a conclusion from two animated dynamic sequences. These premises show the spatial relation between two sets of two moving objects with different velocities, A and B, and B and C, respectively. Their task was to determine the spatial relation between A and C at different time points t. In order to draw such inferences they needed to combine the spatial and temporal relations of the objects. We are specifically interested in indeterminate problems, that is, problems in which different relations between A and C are possible at t. With this procedure we are able to determine which inferences were preferred and which were ignored.

In the second part of our research we have developed an aquarium scenario to represent the RCC relations, which works along similar lines to the set-up described above. This scenario allows us to present animated dynamic sequences and semi-animated dynamic sequences. Moreover, the scenario is constructed in such a way that we could readily adapt it for incorporation of multiple variables such as: the amount of objects in a scene; the consistency of movement of individual objects; and the complexity of spatial relations between the objects.