MPA'10 in Zurich 73 September 14th, 2010
Invited Talk
Kathleen Stewart
Department of Geography, The University of Iowa
Semantics of movement patterns
In this talk I will discuss progress in research relating to the semantics associated with
patterns of moving objects. The talk will highlight how time in particular serves as an
important foundation for extracting many different kinds of moving object semantics. I will
discuss different temporal data models and how the choice of models exposes different
moving object semantics.
MPA'10 in Zurich 74 September 14th, 2010
Patterns of Moving Objects:
Why so interesting?
Kathleen Stewart
Department of Geography
The University of Iowa
kathleen-stewart@uiowa.edu
MPA'10 in Zurich 75 September 14th, 2010
Moving objects
Major research effort by numerous researchers that
relates to analyzing and simulating different behaviors
and activities through space-time
Many of these studies involve modeling the
movement of objects (people, vehicles, animals,
natural phenomena) through a territory affording a
focus on e.g.,
The trajectory or path of movement
Movement in constrained vs. unconstrained
environments
Movement of individuals vs. groups
Uncertainty of movement
Spatiotemporal patterns of movement
MPA'10 in Zurich 76 September 14th, 2010
Today’s talk
Discuss the topic of patterns of moving objects
with a particular focus on semantics
Discuss semantics from the perspective of some of
the underlying temporal data models that are
possible for moving object applications
Spatiotemporal patterns of movement
Highlight the semantics that arise from
Modeling linear sequences
Branching
Modeling cycles
MPA'10 in Zurich 77 September 14th, 2010
Today’s talk
In addition…
Provide a critical overview of progress and
shortcomings relating to semantics that is
relevant to movement pattern analysis
MPA'10 in Zurich 78 September 14th, 2010
Modeling
movement
Many efforts to model the
movement of objects Gulf of Mexico Oil spill July 2010
Ships through harbor waters
Track that car
MPA'10 in Zurich 79 September 14th, 2010
Formalizations designed to
reveal different semantics
Here elements of a
trajectory are formalized
including Begin, End, Stop,
Move
Semantic trajectory ontology from
Yan, Macedo, Parent, Spaccapietra
Transactions in GIS, 12: 75-91.
MPA'10 in Zurich 80 September 14th, 2010
Activities and trips
Activity
Trip
Which activities, of the person
p during the day d, takes
place at a given
location of the place x ?
Sheni, Frihida, Ben Ghezala, and Claramunt (2009) ER 2009 Workshops, pp. 347-356.
MPA'10 in Zurich 81 September 14th, 2010
A common interest…stops or
stay points
http://research.microsoft.com/apps/pubs/?
id=79440 Y. Zheng and X. Xie (2009)
MPA'10 in Zurich 82 September 14th, 2010
Alternatively…
The path of the moving object
is captured through an
expression such as
MPA'10 in Zurich 83 September 14th, 2010
Event-based
model of
movement
This transit through a harbor
can be modeled as a
sequence of events
MPA'10 in Zurich 84 September 14th, 2010
This allows us to
model important
characteristics of
many different
kinds of
movements
MPA'10 in Zurich 85 September 14th, 2010
And develop typologies of
movement
MPA'10 in Zurich 86 September 14th, 2010
Relative Motion Patterns
Laube, P., and Imfeld, S. (2002) Proceedings
of GIScience 2002, 132-144.
Dodge, S., Weibel, R., and Lautenschütz,
Speed, acceleration, and A-K. (2008) Towards a taxonomy of
movement patterns, Information
movement direction Visualization, 7, 240-252
MPA'10 in Zurich 87 September 14th, 2010
Much of this work assumes one
thing...
An underlying linear model of time
l
id et
0
Useful for timeline applications
MPA'10 in Zurich 88 September 14th, 2010
Oculus’s GeoTime application
www.oculusinfo.com
MPA'10 in Zurich 89 September 14th, 2010
Another model
Let’s consider another temporal model that will
support additional semantics important for
moving object applications and
give rise to distinct patterns of movement
MPA'10 in Zurich 90 September 14th, 2010
Branching events model
Work underway with Shane Hubbard, UIowa
spatiotemporal
alternatives
l
id et
1
l
id et0
l
id et 1
0
Diverging
MPA'10 in Zurich 91 September 14th, 2010
Branching events model
Work underway with Shane Hubbard, UIowa
spatiotemporal
alternatives
l
id et0
l
id et
l
1
id e t0
0
Converging
MPA'10 in Zurich 92 September 14th, 2010
Spatiotemporal alternatives
Alt
Now possible future
ern
ativ
e 3
Alt
ern
ati
ve
2
events including
movements can be
Altern
ative
1 modeled
Useful for “what if?”
modeling
Richer set of behaviors
MPA'10 in Zurich 93 September 14th, 2010
Spatiotemporal alternatives
Altern
Can explore how
ative
3
many alternatives
Alte
rnat
ive 2
Alternative
exist for a given
1
time
How many
alternatives are
associated with a
given location over
time
MPA'10 in Zurich 94 September 14th, 2010
Sometimes something else is
needed…
The linear and branching models emphasize
sequences
Want to capture the repetitions that are
commonly present in behaviors and movements
Need to expand modeling to allow for cycles
MPA'10 in Zurich 95 September 14th, 2010
Spatiotemporal cycles are
commonplace
A ferry or ship’s movement in
and out of the harbor may be
cyclic
Repeating events, locations,
or times
Same event, same time, same
location
Same event, different time,
same location
Granularity matters…
Individual or paths,
Event times, dates,
combinations of both
Cycle times, dates
MPA'10 in Zurich 96 September 14th, 2010
In a set of events, certain events may initiate a cycle,
e.g.,
oldZone:offshore inbd _ SE _ TSS
WFG dept1
Other events will terminate a cycle, e.g.,
expectedDest:anchorage anchorage
WFG
arrt5
And an interval often exists between repetitions
(granularity again…)
Continous cycles (daily ferry service),
intermittent cycles (seasonal ferry service)
MPA'10 in Zurich 97 September 14th, 2010
Combine branching and cyclic modeling
Cyclic events might always be associated with one branch
A diverging (or converging) component might be cyclic
MPA'10 in Zurich 98 September 14th, 2010
Cycles and branching…
…
MPA'10 in Zurich 99 September 14th, 2010
Interesting cases
Interrupted cycles
Partially
completed
Initiating, no
terminating
MPA'10 in Zurich 100 September 14th, 2010
Branching events and cycles
The parameters of t and l for time and location
respectively are obviously very key here…and
granularity matters
t= time (st; et; (st,et); date; timestamp)
l = location (x,y coordinates; region; path)
Also the granularity of the entity of interest
Individual events? Several branches? Entire cycle?
MPA'10 in Zurich 101 September 14th, 2010
Duration of events
This temporal aspect is key for both branching and
cycles
Different durations will result in branches of different
lengths of time
< m
m m
…
< < s <
o
<
And in cycles of different lengths
MPA'10 in Zurich 102 September 14th, 2010
16 Cyclic Interval Relations
((Stewart) Hornsby et al. 1999)
disjoint contained_by finishes met_by
meets starts overlapped_by meets_twice
overlaps equals started_by passed_by
passes finished_by overlaps_twice contains
MPA'10 in Zurich 103 September 14th, 2010
For a single moving object, can compare 2 or
more branches and represent possible relations
between branches
Capture similarities or differences
Can compare 2 or more paths that are cyclic
and look for relations between routes
Compare paths of different objects
Maximize or minimize certain relations
dep
(e.g., to avoid gaps in route coverage)
A
dep
arr arr cze
A cze
B
cze
cze
cze
MPA'10 in Zurich 104 September 14th, 2010
Summary
A linear temporal model is most commonly used as the
basis for modeling moving objects
Additional data models are possible and reveal
additional semantics
Branching model captures semantics of spatiotemporal alternatives
and cyclic model captures semantics for repeating movements
Identify primitives for modeling
time, location, identity, diverging, converging, initiating,
terminating, stops, moves, activities
Need to account for granularity of time and location,
event durations, interruptions (branching and cyclic)
Ongoing: spatiotemporal patterns in landscapes of risk
and opportunity
MPA'10 in Zurich 105 September 14th, 2010
Contact: kathleen-stewart@uiowa.edu