This paper describes a spatio-temporal configurations building approach, which has been applied to dynamics points in 1-dimensional space. In this approach, a temporal logic, Allen's time intervals, is crossed with a new spatial logic based on topology called spatial states. These spatial states are derived from topological relationships and a new concept of degenerate topological relationships. This work is the first step of a PhD research aiming to create a generalized spatio-temporal reasoning model based on topological relationships between spatio-temporal histories .
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…) [
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 [
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 [
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 [
A logical evolution after putting so much effort in spatial and temporal reasoning was
to combine them to obtain spatio-temporal reasoning models [
Some of the most achieved realizations illustrate this duality. First, Wolter and
Zakharyaschev propose in [
Combining both approaches, Claramunt and Jiang cross topological relationships and
Allen’s time intervals in [
Our research is inspired originally by Claramunt’s and Muller’s works and considers
spatio-temporal space as a primitive space. Our main research objective is to use
topology to express relationships between spatio-temporal histories of moving
objects. Indeed, by considering a primitive space (spatial and temporal dimensions are
not differentiates) [
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 [
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. 4
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 [
time death time
born a) b)
evolving point space
space 2-Dimensionnal space 2-Dimensionnal space 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 tn{ε1, …, εn} with ε1, …, εn ∈ ε . 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 t3{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 t3{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.
space
time {¬A,e,d,d} {¬A,e,d,¬A} {¬A,e,d,¬B} {¬A,e,d,¬A ¬B} {¬A,e,¬B,¬B} {d,d,¬A,¬A} {d,d,¬A,¬A ¬B} {d,d,¬B,¬B}
{d,d,¬B,¬A ¬B} {d,d,¬A ¬B,¬A ¬B} {d,e,¬A ¬B,¬A ¬B} {d,d,e,e} {d,d,e,d} {d,d,e,¬A} {d,d,e,¬B} {d,e,e,¬B} {d,e,e,¬A ¬B} {d,e,d,e} {d,e,d,d} {d,e,d,¬A} {e,d,d,¬A} {e,d,d,¬B} {e,d,d,¬A ¬B} {e,d,¬A,¬A} {e,d,¬A,¬A ¬B} 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 [
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
[