In this paper we present a Semantic Indoor Trajectory Model aimed at supporting the design and implementation of contextaware mobility data mining and statistical analytics methods. Motivated by a compelling museum case study, and by what we perceive as a lack in indoor trajectory research, we are interested in combining aspects of state-of-the art semantic outdoor trajectory models, with a semantically-enabled hierarchical symbolic representation of the indoor space, which abides by OGC's IndoorGML standard. We drive the discussion on those modeling issues and details that have been overlooked so far or where our approach deviates from typical practices. We illustrate the modeling part with instantiations from the Louvre Museum in an eofrt to provide a pragmatic view of what a Semantic Indoor Trajectory Model ought to represent and ideally also how.
It has long been of paramount importance for museums to “know”
their visitors, meaning to study and understand their motivations,
expectations, engagement, and satisfaction. In this regard,
multimedia guides ofering Location-Based Services (e.g. way-finding,
contextualized content delivery) are becoming an invaluable tool
for museums, since they provide them with access to an
unprecedented wealth of visitor movement data. Similar opportunities
have appeared in other domains of indoor human mobility such
as retail stores, arenas, hospitals, airports, universities [
So far, trajectory-based human mobility data analytics research
has solely focused on outdoor trajectories, driven by the fact that
Geographic Information Science (GIS) has traditionally only
supported outdoor spatial information. This type of research difers
considerably in indoor environments, mainly due to interior
architectural components constraining (or otherwise afecting) the
way people can move. For example, an indoor trajectory model
has to consider multiple ways of entering a room, floor changes,
specific locations of entrance/exit to/from the building, sensor
coverage gaps and/or sensor detection area overlaps, movement
data of varying spatial granularity, and other peculiarities. In
addition, indoor trajectory analytics may gain from avoiding
cumbersome calculations over geometric representations of space
and objects within it, that are typical of outdoor environments.
Instead, operations such as intersection, containment, and
proximity can be simplified in order to prioritize the non-geometric
aspects of movement [
Moreover, in order to reason about movement in
informationally rich domains, a trajectory model must also account for
multiple types of contextual and semantic information. As identified
by [
This has resulted in an emphasis on the enrichment of GPS data, the identification of stops and moves, the identification of transportation means, and other conceptual modeling issues that are either not interesting or not transferable in indoor settings. On the other hand, the adoption of some modeling approaches, such as the segmentation of trajectories into episodes and the use of semantic annotations, seems to be promising.
In this paper, we present a new model for spatiotemporal indoor trajectories enriched with semantic annotations. The proposed model makes use of an indoor space modeling framework, instead of assuming 2D coordinate data as is the norm. To this end, on the one hand, we identify certain limitations of stateof-the-art conceptual semantic (outdoor) trajectory models and propose ways to overcome them, and on the other hand we discuss diferent indoor space modeling approaches and the choices that we made. Equally important, the new model is developed in order to support mining and analysis tasks.
The rest of this paper is divided as follows: Section 2 presents an overview of the related work and its limitations with regards to indoors. Section 3 introduces our trajectory model. Section 4 introduces the Louvre case study and the corresponding model instantiation. Finally, Section 5 concludes with the key issues addressed in our model and a brief description of the types of analytical tasks that it supports. 2
In this section, we describe the state-of-the-art in modeling indoor spaces and (outdoor) semantic trajectories. 2.1
In order to represent movement phenomena in terms of
trajectories, first a formal spatial model is needed to provide an
abstraction of their physical environment. Every trajectory model
(TM) proposed in the literature, either explicitly or more usually
implicitly, uses a certain model of location and therefore space. In
this regard, a fundamental distinction exists between quantitative
and qualitative spatial representation approaches. The former are
preferable when precise spatial information is important, while
the latter when it is unnecessary or unavailable [
A qualitative spatial representation formalism, coupled with
qualitative relations between spatial objects and qualitative
reasoning about spatial knowledge, constitutes what is known as
Qualitative Spatial Reasoning (QSR) [
The latter focus on representing the ontological aspects of spatial
units and the topological relationships between them,
maintaining a more abstract view of indoor space [
Furthermore, a line of research works on indoor space
modeling (e.g. [
IndoorGML’s core module considers an indoor space as a set of non-overlapping cells that represent its smallest organizational/structural units: S = {c1, c2, ..., cn }, ci ∩ cj = ∅. Technically, IndoorGML describes a hybrid indoor space model and not a TM, but it can be used in support of one. More specifically, the cell space and the topological relationships between its objects are represented by one or more Node-Relation Graphs (NRGs). In particular, the Poincaré duality provides the means of mapping the physical indoor space (embedded in a 2D/3D Euclidean primal space) into an adjacency NRG (in the corresponding dual space).
Therefore, a cell (e.g. room) becomes a node and a cell boundary (e.g. a thin wall) becomes an edge. The respective formal terminology is summarized in Table 1. If cell boundary semantics are also taken into account (e.g. doors vs. walls, ramps) then a connectivity and/or an accessibility NRG may be derived as well.
Connectivity suggests that there exists an opening in the common boundary of two cells. Accessibility additionally suggests that the opening is traversable by the moving object (MO).
Moreover, IndoorGML’s Multi-Layered Space Model (MLSM)
is the description of multiple interpretations of the same physical
indoor space, through the instantiation of multiple cell
decompositions and corresponding NRGs. Each NRG is treated as a
separate graph layer. Nodes belonging to diferent layers are
connected via inter-layer “joint” edges. While intra-layer edges
represent either adjacency, connectivity, or accessibility relations
between non-overlapping cells, joint edges represent potential
locations where a physical object might actually reside. Therefore,
given that a physical object may be in only one cell of each layer
at any given point in time (called the “active” state), joint edges
express all the valid active state combinations (called “overall”
states) and are derived by pairwise cell intersection. Equivalently,
a joint edge represents any of the eight binary topological
relationships derived by the n-intersection model [
The MLSM can be used to represent spatial hierarchies but it is unclear how its flexible cell subdivision mechanism is ought to be used: each node may be split independently of the rest which favors ad-hoc hierarchical modeling approaches. For instance, in the Louvre example of Figure 1, we may want to split nodes 4 and 5 into smaller cells to take advantage of more precise localization data available there. It is however unclear, whether or not we should also split 1,2,3 correspondingly, or whether or not we should split 4 and 5 in the same layer (as depicted).
These indoor space modeling issues have been identified in [
N-intersection Primal Space (2D) Dual Space (NRG) Dual Space (Navigation) (spatial) region1 cell/“cellspace” node state (region) boundary (cell/“cellspace”) boundary (intra-layer) edge transition “overlap” / “coveredBy” / “inside” binary topological relationship (inter-layer) joint edge valid active state combination / / “covers” / “contains” / “equal” (between cells/“cellspaces”) valid overall state Table 1: Closely related terms, often used interchangeably under the context of indoor space modeling and IndoorGML. 2.2
In the last decade, accounting for the semantics of movement
has received a lot of attention in the trajectory data modeling
and analytics literature. Pivotal to this has been the proposal
to view a trajectory as “the user-defined record of
spatiotemporal evolvement of the position of a MO, during a given time
interval of its lifespan, and in order to achieve a certain goal”:
[tbeдin , tend ] → space [
More recently, in [
SeMiTri [
The conceptual semantic TM proposed by [
Finally, CONSTAnT [
More generally, in the earlier semantic TM literature,
semantics were largely exhausted in the names and types of the
geographic places of interest related to the MO’s physical stops.
Eforts have since been undertaken to integrate movement
ontologies, linked open data, information extracted from social
network platforms, or complementary case-specific datasets, with
spatiotemporal trajectory data. But they have largely concerned
outdoor contexts, as made evident by the terminology (e.g.
“traveling objects” [
In this section, we define a semantic indoor trajectory model (SITM) aimed at supporting: • all types of indoor settings; • both human and inanimate moving objects (from hereon both referred to as MOs); • mining and analysis applications using both statistical and reasoning approaches in order to provide insight both at the individual and collective level. 3.1
The proposed SITM mainly consists of a semantically enriched sequence of an individual MO’s spatiotemporal presence, but also makes use of a semantically enriched representation of indoor space.
The semantically enriched representation of indoor space that we propose is represented as a layered multigraph. Its nodes symbolically represent indoor spatial regions, and its edges represent topological relationship information between those regions. Static semantic information about the regions is represented through node classes and attributes as well as node-edge grouping into layers. The proposed representation is compatible with OGC’s IndoorGML standard and can be viewed as an extension of it. It is described in Subsection 3.2.
The semantically enriched representation of an individual MO’s trajectory that we propose is a couple consisting of a trace of consecutive presence intervals inside the indoor regions represented by the graph’s nodes, and a set of semantic annotations describing the trajectory in its entirety. It is semantically enriched and uses the above indoor space representation. It is described in Subsection 3.3. 3.2
Based on the modeling framework provided by the IndoorGML standard and in particular its Multi-Layered Space Model (MLSM), we represent a 2D multiple floor (i.e 2.5D) indoor space as a layered multigraph G = (V , E) where and
i=0
G comprises m + 1 diferent layers of nodes and edges, each constituting an accessibility Node-Relation Graph (NRG):
Gi = (Vi , Eiacc )(0 ≤ i ≤ m) that corresponds to a diferent decomposition of the indoor space. On the one hand, node v ∈ Vi represents a cell belonging to the ith layer and an edge e ∈ Eiacc ⊆ Vi ×Vi represents the accessibility between two cells of the i-th layer. On the other hand, a joint edge e ′ ∈ Etop ⊆ Vi × Vj represents a binary topological relationship between two cells of diferent layers ( i , j). Figure 2 illustrates an example of such an indoor space graph representation consisting of five hierarchical layers (detailed in Section 4), but in general G need not be strictly hierarchical.
In the proposed indoor space model, we adopt IndoorGML’s
implicit assumption that each node belongs to only one layer:
m
Ñ Vi = ∅. If a node is relevant to multiple layers then it is
esi=0
sentially replicated in each one and all the copies are connected
to each other via “equal” joint edges. Moreover, assuming that
cells represent the physical reality of planar space (instead of a
conceptual space) and that same-layer cells do not overlap at all,
an intra-layer edge e ∈ Eiacc actually presupposes the “meet”
relation between its two cells, because they need to share a common
surface for the MO to be able to physically transition between
them. At the same time, as explained in Section 2, a joint edge
e ′ ∈ Etop signifies that either one of the “overlap”, “contains”,
“insideOf”, “covers”, “coveredBy”, or “equal” topological relations
holds between the two cells that it connects. Thus, intra-layer
edges and inter-layer edges are always of a diferent type, and
therefore G can be considered as an edge-coloured multigraph
which can be mapped to a multilayer network [
An important modeling decision is whether G is directed or not. Although IndoorGML does not explicitly assume either case, m V = Ø
Vi i=0 m E = Ø Eiacc ∪ Etop it considers undirected edges in all of its examples. As far as intra-layer edges go, we can think of “adjacency” and “connectivity” as being symmetric relations. However, “accessibility” is not symmetric since often indoor movement is only unidirectionally possible due to technical, safety or other limitations. In Figure 1 for example, room 4 (“Salle des Etats”) houses the “Mona Lisa” and accommodates a vast number of visitors on a daily basis. To facilitate their flow, entering it from room 2 is often prohibited by the museum personnel while exiting it that way is allowed. Therefore, we assume directed accessibility NRGs. As far as joint edges go, while “overlap” and “equal” can be thought of as symmetric binary relations, “contains” and “covers” can not. Therefore, we also assume directed joint edges (Figure 2). If we wanted to simply model intersection non-emptiness, instead of the specific nature of the relation, then undirected joint edges would sufice.
In our model, we define a layer hierarchy as k ≥ 2 ordered
layers Gi (0 ≤ i ≤ k) of G that are only consecutively connected
by joint edges. Similar to [
It is thus evident that there can be layer hierarchies that comprise either topographic layers, or semantic layers, or both. Our core hierarchy is indeed a mixed one. The “Building” and “Floor” layers are spatially defined, since the architectural structure alone is mostly enough to determine which space constitutes a building and which space constitutes a floor. The “Room” layer is predicated both spatially and semantically: it should not contain cells of vastly diferent sizes, but it may contain cells whose boundaries are not necessarily physical (e.g. functionally independent subspaces of a big hall or of a great room).
Additionally, two optional layers are proposed for typical cases: a “Building Complex” root layer and a “Region of Interest (RoI)” leaf layer (Figure 2). We define the “Building Complex” layer to represent the indoor space of a site comprised of multiple buildings, such as a hospital spanning multiple attached wings or a university campus spanning multiple independent edifices. We define the “RoI” layer to represent navigable sub-room level spatial cells of application-specific interest, such as “you are here” map installations in a shopping mall or individual exhibit displays in a museum (Figure 4). The “Building Complex” and “RoI” layers are only relevant per case. When present, they can be properly integrated into the aforedescribed core layer hierarchy: “Building Complex” → “Building” → “Floor” → “Room” → “RoI”. Then, a “Floor” object describes a single building’s floor level (e.g. FloorA1 , FloorB1 in Figure 2). Ad-hoc refinements of the hierarchy are still possible in extremely particular cases (e.g. architectures with indistinguishable floor levels) as long as joint edges represent “contain” or “cover” relations and do not skip layers.
A static predefined layer hierarchy (e.g. Figure 2), as opposed to local ad-hoc node subdivisioning (e.g. Figure 1), allows a structured reasoning about the trajectories at multiple levels of granularity. By only allowing “proper part” types of relationships, we allow inference of a MO’s location at all levels of granularity above the detection data level. This in turn allows developing reasoning mechanisms to cope with missing or uncertain location information. It also enables the identification of certain types of movement patterns at the “room” level for instance, and at the same time of other types of patterns at the “floor” level, from the same trajectory dataset. Finally, hierarchies simplify the conceptual indoor space data model thanks to the transitivity of parthood (isomorphic to set inclusion) in classical mereology: a layer hierarchy only needs to connect to other layers or layer hierarchies at the lowest possible level, since a relation (e.g. “overlap”) between two nodes will also hold between their predecessors. 3.3
Automatically collected raw movement data typically consist
of spatiotemporal records, out of which individual trajectories
can be extracted. Depending on the application and on the type
of MO, only the evolution of its representative location may be
relevant (e.g. museum visit analysis) or perhaps also its shape
and parts’ movements (e.g. sports performance analysis). In the
former case, a trajectory is typically represented as a sequence
of timestamped spatial points, as explained in Subsection 3.2.
Due to a building’s clearly separated spaces, we consider regions
(instead of points) as our primary primitive spatial entities, in the
spirit of Qualitative Spatial Representation [
Definition 3.1 (semantic trajectory). A semantic trajectory is defined as the couple of its spatiotemporal trace and the set At r aj of semantic annotations describing it in its entirety, as given by the following equation: where I Dmo is the identifier of the MO concerned, tst ar t and tend are the trajectory’s starting and ending timestamps. Moreover, traceI Dmo,tstar t ,tend represents the spatiotemporal aspect of the trajectory defined as a sequence of timestamped semantically annotated presence periods/intervals at states of the indoor space graph G.
The second element of the couple in Def. 3.1 is a non-empty set of semantic annotations characterizing the trajectory in its entirety. A trajectory semantic annotation at r aj ∈ At r aj is not confined within specific types of information, but would typically be chosen to represent an activity, a behavior, or a goal showcased by the complete trajectory. These terms are often ambiguously used in trajectory literature. Here, we consider an “activity” to concern more targeted/conscious actions than a “behavior”, which concerns less intentional actions or reactions. Both describe the actuality of movement. A “goal” might instead concern the potentiality of movement (e.g. a disrupted activity).
Definition 3.2 (semantic trajectory trace). trace is defined as following: traceI Dmo,tstar t ,tend = (ei , vi , tist ar t , tiend , Ai )i ∈[1,n] m where ei = (vi−1, vi ) ∈ Ð Eacc is the transition, i.e. boundary i=0 i crossed, that led the MO from state vi−1 to state vi at time tist ar t , where it stayed until time tiend . Moreover, Ai is a potentially empty set of semantic annotations describing that specific stay. Given that each layer’s NRG is a multigraph, it is generally useful to know the specific transition ei (e.g. which door, staircase, or elevator was used), albeit optional2.
For example, the spatiotemporal trace of a museum visitor’s 3-hour visit (on a given day) might resemble the following: traceI Dvis,11:30:00,14:28:00 = { (_,room001,11:30:00,11:32:35,∅), (door 012,hall 003,11:32:31,11:40:00,∅), ... (door 005,room006,14:12:00,14:28:00,∅) }
We define a semantic subtrajectory as being for all practical purposes a semantic trajectory (similar to how a mathematical subsequence is itself a sequence) but necessarily referable to some other main semantic trajectory: 2For applications where individual transitions bear a dynamic semantic load (e.g. setting of an alarm with some probability), we can extend the TM with semantic transition annotations, efectively substituting ei with eisem = (ei, Aitr ans ).
jectory Given a semantic tra
TI′Dmo,ts′tar t ,te′ nd = (traceI′Dmo,ts′tar t ,te′ nd , At′r aj ) if trace ′ is a proper subsequence of trace: tst ar t ≤ ts′t ar t < te′nd < tend or tst ar t < ts′t ar t < te′nd ≤ tend .
A subtrajectory’s set of semantic annotations At′r aj may or
may not be the same as that of its main trajectory At r aj , contrary
to [
Moreover, in the following, we define an episode of a semantic trajectory as any particularly meaningful part of it.
Given a semantic trajectory
TI Dmo,tstar t ,tend = (traceI Dmo,tstar t ,tend , At r aj ) an episode of it is defined as
TI′Dmo,ts′tar t ,te′ nd = (traceI′Dmo,ts′tar t ,te′ nd , At′r aj ) if (1) TI′Dmo,ts′tar t ,te′ nd is a semantic subtrajectory of TI Dmo,tstar t ,tend , (2) At′r aj , At r aj , and (3) it satisfies a given spatiotemporal and/or semantic predicate:
Pep : TI′Dmo,ts′tar t ,te′ nd
→ {true, f alse } where Pep is domain-dependent and user-defined.
Moreover, an episodic segmentation of a semantic trajectory is simply any subset of its episodes that covers it time-wise. Contrary to typical literature practice, we allow an episodic segmentation to contain episodes that overlap in time, since the exact same movement part may have multiple meanings depending on the broader context. An example illustrative of the museum domain is given in the next Section.
Finally, the SITM is event-based in the sense that, only a change of the spatial cell that the MO is located in, or a change of the semantic information regarding the MO’s presence in that cell, needs to be accompanied by a new tuple and a corresponding timestamp. Hence, in the previous museum visit example the last presence interval could be split if the visitor changes his goal while in room006 (which hosts both exhibits and the gift shop): (door 005,room006,14:12:00,14:21:45,{goals:[“visit”]}) and (_,room006,14:21:46,14:28:00,{goals:[“visit”,“buy”]}). This modeling approach allows us to integrate diferent data sources in order to semantically enrich the trajectory.
In this section, we present a compelling trajectory dataset from the world’s most frequented museum, the Louvre Museum.
In July 2016, the Louvre launched its oficial “My Visit to the Louvre” smartphone application, which takes advantage of a large Bluetooth Low Energy (BLE) beacon infrastructure3 and the smartphone’s accelerometer and compass, in order to estimate the visitor’s (lat,long) coordinate position within the museum. This is accomplished via BLE Received Signal Strength Indicator (RSSI)-based trilateration, extended Kalman and particle filtering techniques. The app visualizes the position over a locally stored
version of the museum map for navigation purposes. The Louvre
has already been the object of visitor mobility research in the past
leading to interesting conclusions [
In the obtained dataset, raw geometric positions have already been spatially aggregated into 52 non-overlapping zones. Each zone corresponds to a large polygonal area of the museum (Figures 3 and 5) specified by the museum administration in such a way so as to reflect a single exhibition theme (e.g. Italian paintings) but also only extend within a single floor. In more detail, our dataset consists of 4,945 visits (continuously collected from 19-01-2017 to 29-05-2017, where each visit consists of a sequence of timestamped “zone detections”, i.e. detections of the visitor’s smartphone inside a certain zone. The duration of a visit ranges from 0 sec (potential error) to 7 hours, 41 min and 37 sec, whereas the duration of a zone detection ranges from 0 sec (potential error) to 5 hours, 39 min and 20 sec. The visits were performed by 3228 diferent visitors using both the iPhone and Android app versions. Out of them, 1227 were “returning” visitors who made 1717 second/third visits, although not necessarily on diferent days. The dataset includes 20,245 zone detections and 15,300 (intra-visit) zone transitions in total.
Unfortunately, the trajectories obtained from the dataset are sparse, since a visitor may delay launching the app or stop using it early in the visit for a variety of reasons, ranging from battery depletion to lack of engagement or sporadic navigation-only usage. Moreover, around 10% of the zone detections have a duration of zero value, forcing us to filter them out as detection errors.
In order to instantiate the STIM presented in Section 3 for the Louvre case, we need first to represent Louvre’s indoor spaces according to the proposed graph-based model. This is done in Figure 2. Although the Louvre’s multi-layered graph is prohibitively large to be included in this paper, we cite hereafter its correspondences with respect to Figures 3 and 5: Layer 4 is instantiated as the whole “Louvre Museum”, Layer 3 as its three wings (“Richelieu”, “Denon”, and “Sully”) as well as the “Napoleon” area (under the Pyramide), Layer 2 as a wing’s five diferent floors (-2, -1, 0, +1, +2), Layer 1 as a floor’s rooms and halls (hundreds in total), and Layer 0 as a room’s exhibits (several hundreds of the most important ones). In addition, we add a semantic layer that happens to fall right between Layer 2 and Layer 1, representing the thematic zones of our dataset as described in Subsection 4.1 (Figure 3). Layer 4 actually represents a level above any specific building, denoting whether a visitor is at the Louvre in general. Layer 3 treats each wing of the museum as a separate building because its spaces and usage are practically equivalent to that of a typical building. In Layer 0, we opted to define a RoI as the predefined spatial area of engagement with the corresponding exhibit, outside of which a visitor is certainly not paying attention to it. For simplicity, a RoI includes the area physically taken up by the exhibit itself and its display installation (i.e. no holes).
Finally, an interesting space modeling decision concerns whether
or not to assume that the spatial region represented by a node
in layer i + 1 is fully covered by the union of the spatial regions
represented by its child nodes in layer i. For example, is a floor
fully covered by the rooms it contains (Figure 2)? Although not
explicitly stated, the IndoorGML standard and related works (e.g.
[
Having instantiated the Louvre’s indoor space representation, the SITM is used to extract (from the zone detection data) the Louvre visit trajectories as sequences of presence intervals in the museum’s thematic zones. Figure 6 depicts the accessibility topology of the 30 zones present in the dataset, which was extracted by hand on site and can therefore also assist in filtering out data errors. The figure’s lower part corresponds to the −2 floor of the museum, and a short sub-visit of a random visitor in February 2017 is drawn over it: at time t1 the visitor was detected in Zone60887 (i.e. E in Figure 5) for a duration of δt1, and at time t2 he was detected in Zone60890 (i.e. S in Figure 5) for a duration of δt2. From the zone layer NRG (Figure 6) we can infer that although never detected there, the visitor must have passed from Zone60888 (i.e. P in Figure 5). In our SITM, this would be captured with the addition of an extra tuple in the sequence, e.g.: (checkpoint 002, zone60888, 17:30:21, 17:31:42, {goals:[“cloakroomPickup”,“souvenirBuy”,“museumExit”]})
The semantics of places also ofer us valuable insight about the visitor’s trajectory. For instance, we know that the visitor disappearing after Zone60890 is normal because it is one of the Louvre’s exit zones (through the Carrousel Hall). Also, Zone60887 hosts the temporary exhibition of the Louvre which requires a separate ticket to enter. Thus, we would expect that δt1 ≫ δt2. There are many such interesting examples, where cell semantics could help, not only explain the results of, but potentially even redesign, existing sequential pattern mining methods.
It is now more apparent why our SITM allows for
overlapping episodes instead of requiring mutually exclusive episode
predicates (as in [
In this work, we presented an indoor space representation based
on the IndoorGML standard [
We will next focus on developing new data mining methods
that exploit the expressiveness of the SITM, and on proposing
semantic similarity metrics for trajectories (e.g. for visitor
profiling). In the future, it would be interesting to integrate the indoor
space representation with formal ontologies of cultural heritage
information (e.g. CIDOC Conceptual Reference Model [
The authors would like to thank Anne Krebs for her cooperativity and her multifaceted help and Artus Gosselin for his contribution in developing the code for Figure 6.
This work is supported by the TRAJECTOIRES project funded by the French Heritage Science Foundation (EUR-17-EURE-0021).
Karine Zeitouni’s work in this paper has been supported by the MASTER project that has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie-Slodowska Curie grant agreement N. 777695.