For years now, several research communities (GIS, AI, etc.) have investigated spatiotemporal representations and reasoning. It was a logical evolution after putting so much effort in (qualitative) spatial reasoning and temporal reasoning. Indeed, there is a lot of applications where spatio-temporal reasoning is or could be beneficial: movement description, monitoring objects, region evolution, trajectory calculus, epistemology, crime mapping, on board-GPS analyses, etc. In behavior and monitoring interpretation for instance, spatio-temporal reasoning could be used to reason about the interaction of people with their environment or to describe motion patterns of moving objects (peoples, animals, vehicles…) [1][2][3][4][5][6][7].
So far, different types of spatio-temporal reasoning models have been developed. Some of them combine spatial and temporal logic; they "temporalize" spatial reasoning models. Others try to create spatio-temporal mereotopology directly from the spatio-temporal histories of life-lines [8]. Following this latter approach, we aim to develop a generalised spatio-temporal calculus based on spatio-temporal histories. The underlying idea is to extract spatio-temporal information by applying topological calculi on life-lines (e.g. considering a life-line as a line in 2D geometrical space). As a preliminary mandatory study, we wish to build the entire set of a specific kind of spatio-temporal configurations mixing topological and temporal information. For this purpose, we use Allen's time interval and a new spatial logic based on topology called spatial states. We have decided to start with spatio-temporal configurations between two moving points in a 1D space. This will be extended to 2D and 3D spaces and later, extended to other spatial objects (lines, regions and bodies). Further the establishment of such exhaustive configurations, our aim is to obtain in the future a framework allowing evaluating the relevance of spatio-temporal models. In other words, checking if a given model allows or not to retrieve all the possible spatiotemporal configurations.
The paper is structured as follow. First we make a brief description of models and concepts used thereafter. Then, we expose our general research objectives. After, we develop the approach used to build the spatio-temporal configurations and finally, we conclude.
Most common spatial reasoning models are based on topology. We wish to cite in this section the 9-i model [9] and the RCC model [10,11]. The former one is based on the study of intersections between spatial objects topological primitives (see figure 1). The latter is based on the Clarke's connectivity relationship. Both of them gave equivalent sets of topological relationships for regions.
Allen's time interval reasoning is the most well-known reasoning model used in time modelling. His theory of action and time proposes a formalism based on a temporal logic which is used to represent and reason about events, action, beliefs, intentions, causality, and serve as a framework for solving problems [13]. The time primitive used by Allen is the interval. On this basis, he introduced a set of thirteen mutually exclusive binary relations between intervals (figure 2). The time is assumed to be linear, dense and consequently infinite in the past and future.
A logical evolution after putting so much effort in spatial and temporal reasoning was to combine them to obtain spatio-temporal reasoning models [15,16]. Spatio-temporal representing and reasoning can be envisaged in two different ways [8]. First one is the combination of a spatial logic with a temporal logic. Some spatial snapshots are combined in a temporal reasoning to derivate spatio-temporal information. The second one is to view the world as spatio-temporal histories and create new reasoning based on spatio-temporal entities [17]. Some of the most achieved realizations illustrate this duality. First, Wolter and Zakharyaschev propose in [15] to combine the constraints formalism RCC-8 with the Propositional Temporal Logic (PLT) [13]. Gerevini and Nebel combine the RCC-8 with Allen's Interval Calculus that is closer in spirit from RCC-8 than PLT, focusing on the computational complexity of such approach. Combining both approaches, Claramunt and Jiang cross topological relationships and Allen's time intervals in [1,18,19] to deduce spatio-temporal histories of static objects (segments and regions). They have defined a temporal region as a region of space valid for a convex temporal interval (see figure 3). This idea can be used for regions but also for points. Finally, Muller considers space-time histories of objects as primitive entities to analyse directly spatio-temporal shapes or histories. He defines a specific space-time to characterise classes of spatial changes [20], which is the first full mereotopological theory based on space-time as a primitive. More recently the works of Hazarika concern a better understanding of spatio-temporal histories continuity [8]. It is worth mentioning a new model, the QTC [6,21] dealing with direction, speed and acceleration information between moving points. Figure 4 illustrates the type of information we wish to extract from such model. In figure 4 a, the "intersect" topological relationship between the two lifelines indicates without ambiguity that there is collision between the two points (spatial and temporal meeting between the two objects), when in figure 4 b., the "disjoint" topological relationship indicates no collision. Note that studying the projections of life-lines on the temporal and spatial axis does not allow differentiating the two behaviors and therefore does not provide enough information to detect a collision.
Beyond these examples, we believe that others topological relationships might have spatio-temporal meaning and could of some use for others analyses as crime mapping or epistemology. We think also that one of the major interests of this approach could be the generalization of all the possible configurations into a smaller set of topological relationships (33 in the lines case [9]). Assuming that enough spatio-temporal meaning would be associated to these relationships, we could use existing topological models and calculi and hopefully increase speed analysis and understanding of spatiotemporal configurations.
The aim of the present paper is to build the entire set of spatio-temporal configurations between two points in a one dimensional space. Beyond the interest of getting these configurations per se, this will help us to study the relevance of different spatio-temporal models to retrieve spatio-temporal configurations. This will also be useful when studying generalisation processes.
The next sections describe our spatio-temporal configurations building approach.
This section presents an approach allowing extracting spatio-temporal configurations between two dynamic points from topological and temporal information. Considering degenerate notions of topological relationships between two points (see section 4.1) and the well-known Allen time intervals, we derive all the possible (in respect to these concepts at least) spatio-temporal configurations between two dynamic points. At this stage of our research, we have decided to start with a simple case; dynamic points in a 1D space. Points are the simplest spatial objects (0D) and they could not move in a space lower than 1D. We assume that points can not go back in the past, i.e. the temporal dimension is oriented (in accordance with Allen's theory).
Practically, with one spatial and one temporal dimension, we can plot a 2-dimensional space with one dimension attributed to each axis. This space is called a temporal space in accordance to Claramunt [18]. The existence of a point in this space will be represented by a line-segment. The beginning and the end of the line-segment correspond respectively to the "born" and the "death" of the point-life. This representation is called spatio-temporal history or life-line in the dynamic's point case. Both terms will be used in this paper. All the future representations will be plotted with the same convention and orientation axis as in figure 5 Note that we do not want to impose continuity of spatio-temporal histories. This assumption could be added for specific applications if needed.
The spatial relationships considered here are topological relationships. First, we know that they are two possible topological relationships between two points; disjoint or equal (figure 6, cases 1 and 2). To fully encompass spatio-temporal information complexity, we wish to propose degenerate cases of topological relationships between points. The underlying idea is that at certain moments in time, when considering the life-line of two points A and B, point A or point B might not exist. In such cases, binary topological relationships are no longer valid. Therefore, we propose to consider three other "states" in addition to the two topological "states" (disjoint and equal) which cover all the cases of existence or non existence of points. In this context, a "state" is a particular relationship between objects at a given time. This concept is therefore time independent. The cases 3 to 5 from figure 6 illustrate the three "non-topological" states: "¬B" when point B does not exist, "¬A" when point A does not exist and "¬A ⋀ ¬B" when none of them exist.
The set of states "d", "e", "¬A", "¬B", "¬A ⋀ ¬B" is a Jointly Exhaustive and Pairwise Disjoint (JEPD) set of topological and degenerate topological relationships.
In the decision tree (figure 7), one can find also the state "t" which means that the two points exist and have a topological relationship and the state "¬t" gathering the non topological states. We believe that such concepts correspond to a lot of real cases, just mention the analysis of moving GPS antennas with some cycle slips. A spatio-temporal configuration can be seen as a succession of different states in time. The study of spatio-temporal histories successive states transitions is out of the scope of this paper. In the following, when representing the life-line of a dynamic point A, we will join successive states where the point A exists.
The method we used to obtain the entire spatio-temporal configuration set is based on the mapping of spatial information (different states) and a temporal logic (Allen's time interval in this case). To be able to combine them, we compose states in a structure called the "tuple". A tuple is defined as a combination of n states, where n is an integer and represents the level of the tuple. Let ε be the set of possible states values: "e", "d", "¬A", "¬B" and "¬A ⋀ ¬B", a tuple of level n is denoted as t n {ε 1 ,
The major interest of this combination is that there is no order between the different states (ε 1 , …, ε n ). Indeed, if ordered the combination of different states may include temporal information, e.g. the succession of the three states "e", "d" and "¬ A " in time lead to a temporal relationship "starts" only (figure 8). The order of the states in tuple is obtained by crossing it with temporal relationships. Note that the states "¬t" and "t" could be used to provide a greater level of generalization.
Crossing spatial states tuple axis S with Allen's intervals axis T, we can map a spatiotemporal space containing spatio-temporal configurations. Figure 9 shows an example of creation. Let's consider the tuple t 3 {e,d,¬ A } combined with temporal relationships "starts". Theoretically, it corresponds to 6 possible arrangements of spatial states: {e,d, ¬ A }, {d,e, ¬ A }, {¬ A ,e,d}, {¬ A ,d,e}, {e,¬ A ,d}, {d,¬ A ,e}. By combining these states with Allen's time intervals, we need to impose continuous life-line, the last 2 cases {e, ¬ A, d}, {d, ¬ A, e} must be withdrawn. In this particular case, the combination of the tuple t 3 {e,d,¬ A } with the temporal relationships "start" lead us to select the two cases where the ¬ A state is at the end of the state's succession (squared in white on figure 9). In a similar way, we have derived all the spatio-temporal configurations (279 for level 4) for dynamic points in 1D with Allen's intervals continuity assumption. It appears that it was necessary to consider level 4 tuples and combining them with the entire set of temporal relationships. A level less than 4 cannot be combined with temporal relationships as "overlaps" or "overlapped". Working with upper levels than 4 seems to be just a combination of smaller levels, however for future analyses we believe that considering level 6 tuple would be necessary. Figure 10 presents an extract of spatial configurations derived from level 4 tuple. The non continuous histories can be derived from the continuous histories configurations. Figure 11 represents an extract of the possible non continuous histories; the all set of (625) being accessible at the following address: http://www.geo.ulg.ac.be/hallot/.
Spatio-temporal reasoning models aim to describe the real world dynamic phenomena's. They can be of two kinds: either they mix spatial or temporal reasoning model or they describe directly new spatio-temporal mereotopology [8]. In this paper, we have developed an innovative approach using known spatial (topology) and temporal (Allen's time intervals) logics to build a specific set of possible spatiotemporal configurations. Building this set of spatio-temporal configurations is the first step of a global research aiming to develop a generalized spatio-temporal reasoning model. Such model, briefly sketched in this paper, aims to extract spatio-temporal information from life-lines by considering primitive space topological calculi. We wish to end up with a set of topological relationships containing enough spatiotemporal meaning to perform relevant spatio-temporal analyses. Getting these configurations is a necessary step to study the relevance of such kind of spatiotemporal model.
We start from the definition of degenerate topological relationships between two points allowing relationships between non coexistent points. Combined with topological relationships, we obtain a JEPD set of spatial states which are particular relationships between objects at a given time. Spatio-temporal histories can be seen as a succession of states. After, we define a time free combination of states called "tuple". This new representation of two moving points spatiality is crossed with a temporal logic (Allen's time intervals) to create the entire set of spatio-temporal configurations (279 for level 4).
In the future we wish to extend the spatio-temporal configurations to higher dimensions and to other types of spatial objects. Then, we plan to develop further the generalized model and testing its relevance using real data (GPS).
Finally, we believe that our approach could be also complementary to existing qualitative spatial reasoning models. For instance, the Qualitative Trajectory Calculus [6,21,25] is based on analysis of direction, speed and acceleration between two dynamic points. Such calculus can only be used when the two points are coexisting. Our approach could be a nice preliminary analysis to select only the cases where QTC can be used.