=Paper=
{{Paper
|id=Vol-296/paper-6
|storemode=property
|title=Spatio-Temporal Configurations of Dynamics Points in a 1D Space
|pdfUrl=https://ceur-ws.org/Vol-296/paper06hallot.pdf
|volume=Vol-296
|dblpUrl=https://dblp.org/rec/conf/ki/HallotB07
}}
==Spatio-Temporal Configurations of Dynamics Points in a 1D Space==
https://ceur-ws.org/Vol-296/paper06hallot.pdf
Spatio-temporal configurations of dynamics points
in a 1D space
Pierre Hallot1, Roland Billen1
1
Geomatics Unit, University of Liège, Allée du 6 Août, 17 B-4000 Liège Belgium
{P.Hallot@ulg.ac.be, rbillen@ulg.ac.be}
Abstract. 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 .
Keywords: Spatio-temporal modelling, spatio-temporal relationships, lifelines,
spatio-temporal configuration, spatial states, degenerate topological
relationships.
1 Introduction
For years now, several research communities (GIS, AI, etc.) have investigated spatio-
temporal 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-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
77
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 spatio-
temporal 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.
2 Spatial, temporal and spatio-temporal reasoning
2.1 Spatial Reasoning
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.
Fig. 1. Topological relationships between two regions in conceptual neighbourhood diagram
[12].
2.2 Temporal Reasoning
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
78
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.
Fig. 2. Thirteen interval relationships defined by Allen (from [14]).
2.3 Spatio-temporal Reasoning
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.
79
Fig. 3. Visual presentation of relationships in a 2-dimensional space (from [1]).
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.
3 General research objectives
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) [17], we end up considering two lines (the life-lines) and their
topological relationships (see [22] for preliminary research objectives). In other
words, lifelines are just considered as normal lines in a 2D space. It is therefore
possible to analyse topological relationships between them (topological relationships
between lines in a 2D space). We aim to end up with a generalized spatio-temporal
calculus based on a set of topological relationships between spatio-temporal histories,
which should beneficiated of existing topological calculi
80
Fig. 4. Examples of spatio-temporal information extraction based on topological relationships
between life-lines. This space-time representation is explained in section 4.
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 spatio-
temporal 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.
4 Building of a set of spatio-temporal configurations
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
81
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].
time time
born
a) b) evolving point
death
space space
2-Dimensionnal space 2-Dimensionnal space
Fig. 5. 2-dimensionnal temporal space with the evolution of a 1-dimensional object.
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.
4.1 Topological relationships and degenerate topological relationships
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).
82
Fig. 6. Representation of the 5 different topological and degenerate topological states between
points.
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.
83
Fig. 7. Decision tree representing the JEPD set of spatial states.
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.
4.2 Combination of states: the tuple
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.
84
Fig. 8. Succession of states {e,d, ¬A} inducting temporal relationships.
Note that the states “¬t” and “t” could be used to provide a greater level of
generalization.
4.3 Spatio-temporal configuration: mapping of tuples with time
Crossing spatial states tuple axis S with Allen’s intervals axis T, we can map a spatio-
temporal 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).
Fig. 9. Possible combination of the 3-tuple t3{e,d, ¬A}, the spatio-temporal configuration
squared in white are the only two valid when crossing the tuple with temporal relationships
“starts”.
85
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.
time
{¬A,e,d,d} {¬A,e,d,¬A} {¬A,e,d,¬B} {¬A,e,d,¬A ¬B} {¬A,e,¬B,¬B}
space
{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}
Fig. 10. Extract of spatio-temporal configuration generated from tuple t4 with continuity
assumption.
86
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/.
Fig. 11. Extract of spatio-temporal configuration generated from tuple t4 without continuity
assumption.
87
5 Conclusions
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 spatio-
temporal 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 spatio-
temporal meaning to perform relevant spatio-temporal analyses. Getting these
configurations is a necessary step to study the relevance of such kind of spatio-
temporal 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.
88
6 Bibliography
1. Claramunt, C., Jiang, B.: An integrated representation of spatial and temporal relationships
between evolving regions. Journal of Geographical Systems 3 (2001) 411-428
2. Claramunt, C., Jiang, B., Bargiela, A.: A new framework for the visualisation of urban
traffic data. Transportation Research Part C 8 (2000) 167-184
3. Erwig, M., Schneider, M.: A visual language for the evolution of spatial relationships and its
translation into a spatio-temporal calculus. Journal of Visual Languages and Computing 14
(2003) 181-211
4. Sinha, G., Mark, D.M.: Measuring similarity between geospatial lifelines in studies of
environmental health. Journal of Geographical Systems 7 (2005) 115-136
5. Thériault, M., Claramunt, C., Villeneuve, P.Y.: A Spatio-temporal taxonomy for the
Representation of Spatial Set Behaviours. In: Bèohlen, M.H., Jensen, C.S., Scholl, M.O.
(eds.): Spatio-temporal database management : International Workshop STDBM'99.
Springer, Edinburgh, Scotland (1999) 18
6. Van de Weghe, N., Cohn, A.G., De Tre, G., De Maeyer, P.: A Qualitative Trajectory
Calculus as a Basis for Representing Moving Objects in Geographical Information Systems.
Control and Cybernetics 35 (2006)
7. Laube, P., Kreveld, M., Imfeld, S.: Finding REMO — Detecting Relative Motion Patterns in
Geospatial Lifelines. Developments in Spatial Data Handling (2005) 201-215
8. Hazarika, S.M.: Qualitative Spatial Change: Space-time Histories and Continuity. School of
Computing, Vol. PhD. University of Leeds, Leeds (2005) 250
9. Egenhofer, M., Herring, J.: Categorizing Binary Topological Relations Between Regions,
Lines and Points in Geographic Databases. Technical Report. Department of Surveying
Engineering, University of Maine (1990) 28
10.Cohn, A.G.: Calculi for Qualitative Spatial Reasoning. In: Clamet, J., Campell, J., Pfalzgraf,
J. (eds.): Artificial Intelligence and Symbolic Mathematical Computation. Springer-Verlag,
Berlin (1996) 124-143
11.Cohn, A.G., Bennett, B., Gooday, J.M., Gotts, N.M.: Qualitative Spatial Representation and
Reasoning with the Region Connection Calculus. Geoinformatica 1 (1997) 275-316
12.Freksa, C.: Conceptual Neighborhood and its role in temporal and spatial reasoning. In:
Singh, M., Travé-Massuyès, L. (eds.): Proceedings of the IMACS Workshop on Decision
Support System and Qualitative Reasoning, Amsterdam, Holland (1991) 181-187
13.Pani, A.K., Bhattacharjee, G.P.: Temporal representation and reasoning in artificial
intelligence: A review. Mathematical and Computer Modelling 34 (2001) 50-80
14.Allen, J.F.: Time and time again: the many ways to represent time. International Journal of
Intelligent Systems 6 (1991) 341-355
15.Wolter, F., Zakharyaschev, M.: Spatio-temporal representation and reasoning based on
RCC-8. Seventh Conference on Principles of Knowledge Representation and Reasoning,
KR2000. Morgan Kafmann, Breckenridge, USA (2000) 3-14
16.Gerevini, A., Nebel, B.: Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen's
Interval Calculus: Computational Complexity. ECAI 2002. IOS Press (2002) 312-316
17.Muller, P.: Éléments d'une théorie du mouvement pour la formalisation du raisonnement
spatio-temporel de sens commun. Institut de recherche en informatique de Toulouse.
Université Paul Sabatier, Toulouse (1998) 219
89
18.Claramunt, C., Jiang, B.: A representation of relationships in temporal spaces. In: Atkinson,
P., Martin, D. (eds.): Innovations in GIS VII: GeoComputation, Vol. 7. Taylor & Francis,
London (2000) 41-53
19.Claramunt, C., Thériault, M., Parent, C.: A qualitative representation of evolving spatial
entities in Two-dimensional Topological Spaces. In: Carver, S. (ed.): Innvation in GIS V,
Vol. 5. Taylor & Francis, London (1998) 119-129
20.Muller, P.: Topological Spatio-Temporal Reasoning and Representation. Computational
Intelligence 18 (2002) 420-450
21.Van de Weghe, N.: Representing and Reasoning about Moving Objects: A Qualitative
Approach (Volume I). Department of Geography - Faculty of Sciences. Ghent University,
Ghent (2004) 168
22.Hallot, P.: Spatio-temporal relationships in a primitive space: an attempt to simplify spatio-
temporal analysis. In: Raubal, M., Miller, H.J., Frank, A., Goodchild, M. (eds.): Fourth
International Conference Geographic Information Science, GIScience 2006, Vol. 28. IfGI
prints, Münster (2006) 277-283
23.Allen, J.F.: Towards a general theory of action and time. Artificial Intelligence 23 (1984)
123-154
24.Allen, J.F.: Maintaining Knowledge about Temporal Intervals. Communications of the
ACM - The University of Rochester 26 (1983) 832-843
25.Van de Weghe, N., Cohn, A.G., Bogaert, P., De Maeyer, P.: Representation of moving
objects along road network. 12th International Conference on Geoinformatics - Geospatial
Information Research: Bridging the Pacific and Atlantic, University of Gäve, Sweden
(2004) 187-194
90