=Paper=
{{Paper
|id=Vol-396/paper-4
|storemode=property
|title=Modeling Ontological Concepts of Motions with Two Projection-Based Spatial Models
|pdfUrl=https://ceur-ws.org/Vol-396/paper04shi.pdf
|volume=Vol-396
|dblpUrl=https://dblp.org/rec/conf/ki/ShiK08
}}
==Modeling Ontological Concepts of Motions with Two Projection-Based Spatial Models==
https://ceur-ws.org/Vol-396/paper04shi.pdf
Modeling Ontological Concepts of Motions
with Two Projection-Based Spatial Models
Hui Shi1 and Yohei Kurata
Safe and Secure Cognitive Systems, DFKI Bremen
SFB/TR 8 Spatial Cognition, Universität Bremen
Abstract. To model human concepts of motions is essential for the development
of the systems and machines that collaborate with ordinary people on spatio-
dynamic tasks. This paper applies two projection-based spatial models, Double
Cross and RfDL3-12, to the modeling of human concepts of motions on a plane,
making use of the ability of these two models to illustrate where and how a
landmark extends around/on a path. For generalization, we adopt a set of formal
motion concepts defined in an existing spatial ontology called GUM. These motion
concepts are associated with the motion patterns modeled by Double Cross and
RfDL3-12, considering two scenarios where the landmarks are represented by points
and regions, respectively. For the latter scenario, we identify the motion patterns
whose characterization cannot be clearly determined. In addition, we find that the
knowledge of landmarks’ convexity is useful for characterizing motion patterns.
Keywords. motion concepts, route descriptions, projection-based spatial models,
Double Cross, RfDL, GUM, spatial ontology
Introduction
To model how ordinary people conceptualize motions in their living environments is
essential for the development of the systems and machines that collaborate with those
people on spatio-dynamic tasks, such as intelligent vehicles, mobile robots, and
security monitoring systems, especially if they equip with natural language interfaces.
Traditionally, many researchers have discussed a number of expressions and notions
that people use for describing motions, such as into, across, and over [1-5], past and
along [6, 7], and turn before/after/at [8]. This paper adds another speculation on such
human concepts of motions with the aid of two spatial models—Double Cross [9, 10]
and RfDL3-12 [11]. These models can be used for illustrating where and how a landmark
extends around/over a path and, accordingly, they may cover such expressions in
behavioral descriptions as “go toward”, “pass … on the right”, “go into”, and “go
across”. Indeed, based on the analysis of human route instructions to an intelligent
semi-autonomous wheelchair in buildings [12], Krieg-Brückner and Shi [13] insist that
Double Cross nicely captures the semantics of human route instructions in combination
with Route Graph [14, 15]. Route Graph is a graph-based model of navigational
knowledge that consists of landmarks, decision points, and route segments. These
landmarks are conceptualized as points within the framework of Double Cross. On the
1
Corresponding Author: SFB/TR 8 Spatial Cognition, Universität Bremen, Postfach 330 440, 28334
Bremen, Germany; shi@informatik.uni-bremen.de
42
other hand, the corpus in [16], which collects the route instructions given to a small
robot traveling in a miniature town, observes the subjects’ use of expressions that
presume spatial extent of landmarks, such as “follow it around” and “keep going until
you hit the end of the train station”. This motivated us to develop a spatial model
called RfDL3-12 [11], which captures the characteristics of spatial arrangements between
a path and a region-like landmark using a similar framework.
The aim of this paper is to analyze the applicability of Double Cross and RfDL3-12
to model a number of human concepts of motions on a plane in a comparative way. In
our previous work, we studied several concrete expressions in behavioral descriptions,
such as approach, go toward, and pass by [11]. However, in natural dialogues, people
use thousands of expressions for describing motions. Thus, in this work, we consider
more generic concepts of motions that underlie such individual expressions. For
instance, the expressions “go across …” and “pass through …”, as well as “gehen über
…” in German and “…-wo toorinukeru” in Japanese, are mapped to the same motion
concept if their slight nuance is neglected. Such generalization is definitely useful to
expand the coverage of our approach. For this purpose, we adopt the motion concepts
defined in an existing spatial ontology, called Generalized Upper Model extended with
space components (GUM) [17].
The remainder of this paper is organized as follows: Section 1 reviews Double
Cross and RfDL3-12, highlighting their potential for characterizing motion patterns.
Section 2 gives an overview of the ontological specifications of motion concepts
defined in GUM. Sections 3 and 4 associate the motion concepts in GUM with the
motion patterns modeled by Double Cross and RfDL3-12, respectively. Finally, Section 5
concludes with a discussion of future problems.
1. Double Cross and RfDL3-12
When an agent moves stepwise on a plane with the aid of landmarks, each step of
movement is mapped to a spatial arrangement between a directed line (DLine) and
another spatial object (a point, a line, or a region) in a two-dimensional Euclidean space
R2. The DLine represents the route segment [14, 15] (i.e., the course of movement in
each step), while the second object represents the landmark.
In the last two decades, a number of spatial models of DLine-object arrangements
have been developed; for instance, Double Cross [9, 10] and Orientation Calculi [13]
capture the directional and topological characteristics of DLine-point arrangements, the
9+-intersection for DLine-region relations [18] captures the topological characteristics
of DLine-region arrangements, and RfDL3-12 [11] captures the directional characteristics
of DLine-region arrangements, as well as a certain degree of topological information
(Section 4.2). Finally, Goyal and Egenhofer [19] discuss cardinal directions between
arbitrary objects, which may include DLine-point, DLine-region, and DLine-line pairs.
The 9+-intersection for DLine-region relations [18] illustrates where the DLine
starts, passes, and ends with respect to the region’s interior, boundary, and exterior.
Accordingly, this model can be used for capturing such topology-relevant concepts as
“go into” and “go across” [18]. However, if the DLine does not intersect with the
region, any DLine-region arrangement is mapped to a single topological pattern (i.e.,
disjoint relation), even though people can distinguish such arrangements in more detail,
describing them as “go toward …”, “pass … on the left”, “go until … comes to the left”,
and so forth. These expressions typically refer to the landmark’s direction as seen from
43
the route segment. This motivated us to examine the spatial models that emphasize the
directional characteristics of DLine-object arrangements as a foundation for modeling
human concepts of motions.
Typically, directional characteristics of spatial arrangements are captured with the
aid of a frame of spatial reference [20]. The frame of spatial reference is projected onto
the space with its center on one object (called relatum), such that the space around/on
the relatum is partitioned into a set of fields. Then, the arrangement between the
relatum and another object (called referent) is characterized by the field or the set of
fields where the referent takes place. The frames of spatial reference are categorized
into the following three types [20]:
• absolute frame, whose orientation is determined extrinsically by the
environment (e.g., the frame of cardinal directions in [19]);
• intrinsic frame, whose orientation is determined by the intrinsic orientation of
the relatum (typically represented by a DLine or a directed point); and
• relative frame, whose orientation is determined by the direction from the third
object (viewer) to the relatum.
The models of spatial arrangements that adopt a frame of spatial reference is
generally called projection-based models [21]. For modeling motion concepts, two
types of projection-based models are potentially useful [22]. One is the projection-
based models whose relatum is represented by a DLine (e.g., Double Cross [9, 10],
Bipartite Arrangements [23], Orientation Calculi [13], and RfDL [11]). This type may
illustrate where and how the landmark (referent) extends around/over the route segment
(relatum). Thus, they can capture such mover-centric concepts as “go toward” and
“pass … on the right”. Another useful type is the projection-based models whose
referent is represented by a point (e.g., Single Cross [9], Ternary Point Configuration
Calculus [24]). This type may illustrate the relative location of the end-point of the
route segment (referent) with respect to the landmark (relatum). Thus, they can capture
such goal-oriented concepts as “walk to the front of” and “go to the north of”. Note
these concepts are essentially the combination of a motion verb and an expression of
the goal location accompanied by a preposition “to”, and the goal expression itself is
static. On the other hand, the mover-centric concepts are motion-oriented by nature.
This is why we focus on the first type of spatial models in this paper.
Double Cross [9, 10] is viewed as a projection-based model whose relatum and
referent are represented by a DLine and a point, respectively [10]. It adopts a ‡-shaped
intrinsic frame that distinguishes three fields on the DLine and twelve fields around it.
We call the former three fields En (entry), I (interior), and Ex (exit), and the latter
twelve fields LB (left back), SB (straight back), RB (right back), LEn (left at entry),
REn (right at entry), LI (left of interior), RI (right of interior), LEx (left at exit), REx
(right at exit), LF (left front), SF (straight front), and RF (right front) (Figure 1a).
Naturally, Double Cross distinguishes fifteen patterns of DLine-point arrangements
based on which field contains the point.
RfDL (Region-in-the-frame-of-Directed-Line) [11] is a series of projection-based
models whose relatum and referent are represented by a DLine and a simple region,
respectively. Simple regions are single-component regions without disconnected
interior, holes, spikes, punctuating points, or cuts [25]. For simplification, simple
regions are called regions from now. Following Orientation Calculi [13], RfDL considers
eight types of intrinsic frames based on the combinatorial use/non-use of left-right,
front-side-back, and entry-interior-exit distinctions with respect to the DLine (Figure
1b). Each frame partitions the space around/on the DLine into two to fifteen fields,
44
including zero- and one-dimensional fields that fill the gap between two-dimensional
ones. These eight frames naturally yield eight models with different levels of
granularities, since the patterns of DLine-region arrangements are distinguished by the
set of fields over which the region extends. Each model is called RfDLm-n, where m/n
indicates the number of fields on/around the DLine. The finest model RfDL3-12 adopts a
‡-shaped intrinsic frame that distinguishes three fields on the DLine and twelve fields
around the DLine. This frame is actually equivalent to the frame adopted by Double
Cross (Figure 1a). As a result, RfDL3-12 has a strong correspondence with Double Cross.
Even though a region can take place more than one field, RfDL3-12 distinguishes not
23+12 = 32768 patterns, but only 1772 patterns, due to the following two constraints:
• the region must extend over one or more two-dimensional fields; and
• the set of fields over which the region extends must be connected, even if En
and Ex are removed from this set.
We also identified that RfDL1-1, RfDL1-4, RfDL1-8, RfDL1-12, RfDL3-1, RfDL3-4, and RfDL3-8
distinguish 2, 23, 142, 479, 8, 92, and 520 patterns, respectively. Such coarser models
are potentially useful for the prevention of overspecification, although it is out of the
scope of this paper.
For simplification, patterns of DLine-point arrangements modeled by Double
Cross are called DC patterns, while patterns of DLine-region arrangements modeled by
RfDL3-12 are called RfDL3-12 patterns. Both DC patterns and RfDL3-12 patterns are
represented by icons with 3×5 cells (Figure 1c). The icons’ fifteen cells geometrically
correspond to the fifteen fields that each model considers. The marked cells indicate the
fields over which the referent extends.
1 2 2 1 2
1 1 1 1
1 2 2 1 2 2 1 2 2 1 2
LF SF RF 1 1 1 1
1 2 2 1 2
LEx Ex REx
RfDL1-1 RfDL1-12 RfDL1-12 RfDL1-12 DC pattern
LI I RI
1 2 2 1 2
0 1 0 1 1 0 1
LEn En REn 0
1 2 2 1 2 2 1 2 2 1 2
LB SB RB
0 0 1 0 1 1 0 1
(a) 1 2 2 1 2
RfDL3-1 RfDL3-12 RfDL3-12 RfDL3-12 RfDL1-12 pattern
(b) (c)
Figure 1. (a) Fifteen fields around/on a DLine that Double Cross and RfDL3-12 consider. (b) Sets of fields that
RfDL models consider, where the number assigned to each field indicates its dimension. (c) Iconic
representations of spatial arrangements modeled by Double Cross and RfDL3-12.
2. Conceptualization of Motions
A number of researchers in robotics have studied how people instruct mobile robots, in
pursuit of natural dialogue-based interactions. They have often sought a small number
of concepts that underlie the large diversity of expressions observed in their corpus
[6, 17, 26]. Recently, based on a series of empirical studies, several ontological
representations of natural space and spatial actions have been developed [17, 27]. The
45
intermediate use of such ontological representations allows us to avoid the mapping
from countless number of expressions to the domain model. Thus, in this work, we
adopt the set of motion concepts specified in one of the existing spatial ontologies,
called Generalized Upper Model 3.0 extended with space components (GUM) [17].
To conceptualize a route description that consists of a series of statements about
successive actions to be taken, GUM provides a concept called Generalized Route.
Generalized Route may contain representations of directional motions (e.g., go toward
the campus), path representations (e.g., pass the post office on the left, go along the
tramway), representations of goal-driven motions (e.g., go to the red building), and so
forth. Table 1 summarizes the GUM’s specifications relevant to motions. The
representations of directional motions are covered by General Directional
Destination/Source, the path representations are covered by Path Representing External
Indication/Placement, and the representations of goal-driven motions are covered by
Containment Destination. Note that the motion concepts in Table 1 do not strictly
follow the original notations in GUM, but are reorganized by the authors such that the
motion-relevant aspect of each concept is emphasized.
The concepts in Table 1 belong to two more generic concepts in GUM; one is
Relative Spatial Modality, which denotes the position of a remote landmark (e.g., pass
the park on the right), and another is Functional Spatial Modality, which specifies the
interaction between a route segment and a landmark (e.g., go into the park). In the
former concept, the landmark’s direction as seen from the route segment becomes
critical information for characterizing the motion. For such characterization, we can use
the concepts for specifying the landmark’s directions, such as Cardinal Directional and
Projective Relations (including Vertical Projection and Horizontal Projection). Since we
are considering planar movement, Horizontal Projection can be particularly used
together with General Directional Destination (e.g., go until the post office comes to the
right) and Path Representing External Indication (e.g., pass the park on the right).
Table 1. GUM’s specifications relevant to motions.
Applicability to Land-
GUM Specification Characterizing Factors Examples marks Modeled by
Points Regions
General Directional directional relation to a landmark go toward the bus stop
Destination √ √
on the end-point side approach the park
General Directional directional relation to a landmark go away from the bus
Source √ √
on the start-point side stop
Path Representing an approach to a landmark at a pass the bus stop
External Indication
√ √
midway point go by the park
Path Representing constant distance to a landmark
External Placement
go along the park √
during the movement
Containment the end-point located in the go to the bus stop
Destination √ √
landmark go into the park
the start-point located in the leave the bus stop
Containment Source √ √
landmark go out of the park
Path Representing the route segment located go via the bus stop
Internal Indication √ √
(partially) in the landmark go across the park
the route segment located
Parthood walk in the park √
completely in the landmark
46
3. Motion Concepts Referring to Point-Like Landmarks
This and the next sections explore the association between motion concepts in GUM
and motion patterns modeled by Double Cross and RfDL3-12. We start from the simple
scenario where the landmark is represented by a point. Suppose that the route segment
and the landmark are mapped to a DLine ab and a point p, respectively. Then, the
motion pattern is mapped to a DC pattern ab : p . It is assumed that the distance
between ab and p is small whenever a DC pattern holds between them.
If the route segment intersects with the point-like landmark (i.e., p ∈ ab ), a key
factor for characterizing the motion is the part of the route segment that intersects with
the landmark. In GUM, Containment Source (e.g., leave) refers to a motion pattern that
starts from a landmark, Containment Destination (e.g., go to) refers to a motion pattern
that ends at a landmark, and Path Representing Internal Indication (e.g., go via) refers
to a motion pattern that passes through a landmark. The spatial contexts of these three
motion concepts are mapped to DC patterns , , and , respectively.
If the route segment does not intersect with the point-like landmark (i.e., p ∉ ab ),
there are several strategies to characterize the motion patterns. For instance, we can
refer to the direction of the route segment’s end-point with respect to the landmark (e.g.,
go to the front of), even though DC patterns do not capture this information. Instead,
DC patterns may indicate whether the moving agent gets closer to or farther from the
landmark during the movement. For instance, General Directional Destination (e.g.,
approach), which refer to the motion patterns where the agent gets closer to the
landmark during the movement, corresponds to five DC patterns , , , , and .
Conversely, General Directional Source (e.g., go away from) corresponds to five DC
patterns , , , , and .
In natural dialogues, people may distinguish approaching motion patterns in more
detail, using such expressions as “go toward the bus stop” and “go until the bus stop
comes to the left”. We, therefore, introduce the following sub-concepts of General
Directional Destination:
• General Directional Destination Front, which refers to a motion pattern where
the front extension of the route segment penetrates the landmark (e.g., go
toward);
• General Directional Destination Left, which refers to a motion pattern where
the line that orthogonally passes through the route segment’s end-point
intersects with the landmark only on the left side of the route segment (e.g., go
until … comes to the left);
• General Directional Destination Right;
• General Directional Destination Left-Front, where the landmark is located
entirely or mostly at the left front of the route segment’s end-point (e.g.,
approach … on the left front); and
• General Directional Destination Right-Front.
The spatial context of these five sub-concepts are mapped to the DC patterns , , ,
, and , respectively. Precisely speaking, these five sub-concepts are the
combinations of General Directional Destination and Horizontal Projection. In a similar
way, five sub-concepts of General Directional Source are defined.
47
Another motion concept that DC patterns may capture is Path Representing
External Indication (e.g., go by). This concept refers to a motion pattern where the
moving agent approaches the landmark at a midway point on the route segment—in
other words, the agent gets closer to the landmark and then farther from it before
arriving at the end-point. Such motion patterns are mapped to two DC patterns and
. Naturally, two sub-concepts of Path Representing External Indication, namely Path
Representing External Indication Left and Path Representing External Indication Right
(e.g., go by … on the left/right), are distinguished based on which side of the route
segment the agent approaches the landmark.
In this way, General Directional Destination, General Directional Source, and Path
Representing External Indication, as well as their sub-concepts, are assigned
distinctively to the fifteen fields that Double Cross considers (Figure 2).
General Directional Destination Front
General Directional General Directional
Destination Left-Front Destination Right-Front
General Directional Destination
General Directional General Directional
Containment Destination Destination Left Destination Right
Path Representing External Indication Path Representing Path Representing
Path Representing Internal Indication External Indication Left External Indication Right
General Directional General Directional
Containment Source Source Left Source Right
General Directional Source General Directional General Directional
Source Left-Back Source Right-Back
General Directional Source Back
Figure 2. Motion concepts assigned to the fifteen fields that Double Cross considers.
4. Motion Concepts Referring to Region-Like Landmarks
Next, we consider the scenario where the landmark is represented by a simple region.
Suppose that the route segment and the landmark are mapped to a DLine ab and a
simple region R, respectively. Then, the motion pattern is mapped to an RfDL3-12 pattern
ab : R . It is assumed that the distance between ab and R is small whenever an RfDL3-12
pattern holds between them. We take a similar approach as before, but we have to care
about the difference between region-like landmarks and point-like landmarks. For
instance, let us consider General Directional Destination Front (e.g., go toward). When
the landmark is represented by a point, only one DC pattern is mapped to this
concept. On the other hand, when the landmark is represented by a region, multiple
RfDL3-12 patterns, such as , , and , are mapped to this concept, but is not
(because it cannot be an RfDL3-12 pattern). Like this example, each concept corresponds
to a set of RfDL3-12 patterns, which are determined by the specific conditions identified
in the following discussion.
4.1. Disjoint Patterns
We first focus on the motion patterns where the route segment does not intersect with
the region-like landmark (i.e., ab ∩ R = φ). Such disjoint motion patterns are mapped
to 127 of 1772 RfDL3-12 patterns. These patterns are associated with the same set of
motion concepts as the disjoint DLine-point patterns; that is, General Directional
48
Destination, General Directional Source, Path Representing External Indication, and
their sub-concepts.
General Directional Destination refers to a motion pattern where the moving agent
gets closer to the landmark (e.g., approach). This time, however, it is not always
possible to decide clearly whether a given motion pattern fits with this concept or not.
For instance, the motion pattern in Figure 3b probably fits with the concept of General
Directional Destination, but Figure 3c does not, although they are represented by the
same RfDL3-12 pattern , and obviously there are a variety of in-between patterns
whose characterization is difficult. On the other hand, we can clearly say that the
motion pattern in Figure 3a fits with General Directional Destination, because the
distance between the moving agent and every point in the region-like landmark
decreases monotonically during the movement. Also, it is clear that the motion patterns
in Figures 3d-e cannot fit with General Directional Destination, because the region-like
landmark has no point inside to which the distance from the moving agent decreases
monotonically during the movement. From this observation, we derived the following
two conditions:
• SCGDD (strong condition of General Directional Destination)—the motion
pattern is mapped to ab : R where the region R extends at least one field
among ab ’s SF, LF, RF, LEx, or REx, but no other field, and;
• WCGDD (weak condition of General Directional Destination)—the motion
pattern is mapped to ab : R where the region R extends over at least one field
among ab ’s SF, LF, RF, LEx, or REx, and neither En, I, nor En.
If a motion pattern satisfies the strong condition SCGDD, then this pattern always fits
with General Directional Destination (Figure 3a). On the other hand, if a motion pattern
does not satisfy the weak condition WCGDD, then this pattern does not fit with General
Directional Destination (Figure 3d-e). Note that if a motion pattern satisfies the strong
condition SCGDD, then this pattern also satisfies the weak condition WCGDD (and this is
why they are named strong and weak conditions). Note also that the weak condition
WCGDD includes the condition “R extends neither En, I, nor En”, which comes from this
section’s presumption ab ∩ R = φ.
If a motion pattern satisfies the weak condition WCGDD, but not the strong
condition SCGDD, then this motion pattern may or may not fit with General Directional
Destination (Figures 3b-c). In such a case, we need further criteria to judge whether (or
how much) the motion pattern fits with General Directional Destination; for instance,
the relative area of the landmark in which the distance between arbitrary point and the
moving agent decreases monotonically during the movement, or the relative length of
period during which the nearest distance between the moving agent and the region-like
landmark decreases can be used as the criteria of this evaluation.
(a) (b) (c) (d) (e)
Figure 3. (a-b) Motion patterns that fit with the concept of General Directional Destination and (c-e) those that
do not, together with the RfDL3-12 patterns that represent these motion patterns.
49
In a similar way, we developed the strong and weak conditions of the five sub-
concepts of General Directional Destination following their definitions in Section 3. For
instance, SCGDDF (strong condition of General Directional Destination Front) was
derived as the combination of SCGDD (strong condition of General Directional
Destination) and the additional condition of General Directional Destination Front—the
front extension of the route segment penetrates the landmark (Section 3). Similarly,
WCGDDF (weak condition of General Directional Destination Front) is derived as the
combination of WCGDD and the same additional condition of General Directional
Destination Front.
The developed conditions are summarized in Table 2. The conditions are
represented visually by icons with 3×5 cells. Just like the icons of RfDL3-12 patterns, the
icons’ fifteen cells correspond to the fifteen fields that RfDL3-12 considers, but at this
time they have three colors; black, gray, and white cells indicate the fields over which
the region must, may, and cannot extend. For instance, the condition icon indicates
that the region must extend over LF, SF, RF, may extend over LEx or REx, but cannot
extend over all other fields. This condition is satisfied by four RfDL3-12 patterns , ,
, and . As this example indicates, there are visual correspondence between each
condition icon and the icons of RfDL3-12 patterns that satisfy this condition.
Table 2. Strong and weak conditions of General Directional Destination and its sub-concepts, together with the
numbers of RfDL3-12 patterns that satisfy each condition without/with the region’s convexity assumption.
General Directional General Directional General Directional General Directional
Destination Destination Front Destination Left Destination Left-Front
at least
one
Strong
Condition
12, 11 4, 3 3, 3 4, 4
at least
one
Weak
Condition
102, 43 46, 9 31, 19 67, 21
The strong conditions in Table 2 look intuitive, as the icons visualize the images of
prototypical path-landmark arrangements that fit with each motion concept. On the
other hand, the weak conditions in Table 2 may not look straightforward. For instance,
RfDL3-12 patterns and satisfy the weak condition of General Directional
at least
on e
Destination (i.e., ), but the motion patterns in Figures 4a-b, which are ‘typical’
instances of and , do not fit nicely with General Directional Destination (i.e., it is
difficult to say that they are approaching patterns). On the other hand, the motion
patterns in Figures 4c-d, which also correspond to the same RfDL3-12 patterns and ,
probably fit nicely with General Directional Destination, because the moving agent gets
closer to the most/principal part of Thailand. Like this example, the weak condition of
each concept covers all RfDL3-12 patterns whose instantial motion patterns may fit with
each concept and, as a result, the condition may look not straightforward.
50
(a) (b) (c) (d)
Figure 4. Motion patterns that satisfy the weak condition of General Directional Destination, together with the
RfDL3-12 patterns that represent these motion patterns.
The second concept, General Directional Source, is the direct opposite of General
Directional Destination. Consequently, the sufficient and weak conditions for General
Directional Source and its five sub-concepts are derived from Table 2, simply by
flipping the icon vertically.
The third concept, Path Representing External Indication, refers to a motion pattern
where the moving agent approaches the landmark at a midway point of the route
segment (e.g., go by). If a motion pattern is mapped to an RfDL3-12 relation or ,
this pattern always fits with this concept, because the moving agent gets closer to every
point in the region-like landmark and then farther from it (Figures 5a-b). Conversely, if
a motion pattern is mapped to an RfDL3-12 pattern where the region extends over neither
LI nor RI, this pattern never fits with Path Representing External Indication (Figure 5e).
Otherwise, we need further criteria to judge whether or how much the motion pattern
fits with Path Representing External Indication (Figures 5c-d). Based on this
observation, the strong and weak conditions of Path Representing External Indication,
as well as those of its two sub-concepts, are developed (Table 3).
(a) (b) (c) (d) (e)
Figure 5. (a-c) Motion patterns that fit with the concept of Path Representing External Indication and (d-e)
those that do not, together with the RfDL3-12 patterns that represent these motion patterns.
Table 3. Strong conditions of Path Representing External Indication and its two sub-concepts, together with
the numbers of RfDL3-12 patterns that satisfy each condition without/with the region’s convexity assumption.
Path Representing Path Representing Path Representing
External Indication External Indication Left External Indication Right
Strong
Condition either
2, 2 1, 1 1, 1
Weak
Condition either
72, 42 36, 21 36, 21
51
Tables 2-3 show the numbers of RfDL3-12 patterns that satisfy each condition, as
well as the number of those patterns if the region is convex. Since many region-like
landmarks in the real world are represented by convex regions, such assumption is
often meaningful. We found that the number of RfDL3-12 patterns that satisfy each weak
condition is large. This stems from the fundamental ambiguity of region-like landmarks,
which may take countless shapes. However, if the region is convex, the number of
RfDL3-12 patterns that satisfy the weak condition of each concept drastically decreases
and becomes closer to the number of RfDL3-12 patterns that satisfy the strong condition.
This indicates that the knowledge of the landmark’s convexity is helpful to judge the
directional characteristics of motion patterns.
4.2. Non-Disjoint Patterns
Next, we focus on the motion patterns where the route segment intersects with the
region-like landmark (i.e., ab ∩ R ≠ φ), which are mapped to 1645 of 1772 RfDL3-12
patterns. A key factor for characterizing such motion patterns is topological
information; i.e., how the route segment intersects with the region. Thus, we consider
three topological categories, Cross, Within, and Touch, following OpenGIS’s
classification of topological line-region relation [28].
4.2.1. Cross
According to OpenGIS’s definition [28], “a line crosses a region” refers to a
configuration where the line’s interior intersects with both the interior and exterior of
the region. Motion patterns where the route segment crosses the region-like landmark
are associated with three concepts in GUM: Containment Destination, Containment
Source, and Path Representing Internal Indication (Figure 6). These three concepts
correspond to such expressions as “go into”, “go out of” and “go across”, respectively.
In addition, if the landmark’s spatial extent is not significant, these three concepts may
be associated with such expressions as “go to”, “leave” and “go via”, respectively.
(a1) (a2) (b1) (b2) (c1) (c2) (c3)
Figure 6. Motion patterns that fit with (a1-2) Containment Destination, (b1-2) Containment Source, and (c1-3)
Path Representing Internal Indication, together with the RfDL3-12 patterns that represent these motion patterns.
Table 4 shows the strong and weak conditions of Containment Destination,
Containment Source, and Path Representing Internal Indication. The strong condition of
Containment Destination requires the region’s convexity, because unless the region is
convex, RfDL3-12 patterns cannot guarantee that the DLine ends at the region’s interior
even if the region extends over Ex and all fields around it (compare Figure 6a1 with
Figure 8d2). For the same reason, the strong condition of Containment Destination
Source requires the region’s convexity. On the other hand, the strong condition of Path
52
Representing Internal Indication does not require the region’s convexity, because we
can guarantee that the DLine goes across the region when the region extends over LI, I,
and RI, but not all field around En and not all field around Ex (compare Figure 6c2 with
Figure 8b2).
4.2.2. Within
In [28], “a line is within a region” means that the line intersects with the region’s
interior, but not its exterior. In GUM, the concept of Parthood, which corresponds to
such expressions as “walk in the park”, refers to a motion pattern where the route
segment goes within a region-like landmark (Figures 7a-d). Even though GUM has no
refinement of Parthood, Figures 7a-d implies that we can topologically distinguish at
least four sub-concepts of Parthood, based on whether the route segment starts from
and ends at the landmark’s interior or boundary. The strong and weak conditions of
Parthood are shown in Table 4. The strong condition requires the region’s convexity,
because unless the region is convex, RfDL3-12 patterns cannot guarantee that the
DLine’s interior does not intersect with the region’s exterior, even if the region extends
over the DLine’s LI, I, RI, En, and Ex (compare Figure 7a with Figure 7e).
(a) (b) (c) (d) (e)
Figure 7. (a-d) Motion patterns that fit with the concept of Parthood and (e) the pattern that does not,
together with the RfDL3-12 patterns that represent these motion patterns.
Table 4. Strong and weak conditions of Containment Destination, Containment Source, Path Representing
Internal Indication, and Parthood, together with the numbers of RfDL3-12 patterns that satisfy each condition
without/with the region’s convexity assumption.
Containment Containment Path Representing
Parthood
Destination Source Internal Indication
not
all
Region’s Region’s Region’s
Strong &
convexity
&
con vexity
&
con vexity
not
Condition all
–, 5 –, 5 225, 25 –, 169
Weak
Condition
16, 5 16, 5 256, 25 256, 169
4.2.3. Touch
In [28], “a line touches with a region” means that the line intersects with the region’s
boundary, but not its interior. We found that the current version of GUM has no
specification that exactly refers to a motion pattern where the route segment touches
the region-like landmark. Thus, here we discuss the concept of Touch and its sub-
concepts apart from GUM. As shown in Figure 8, we can topologically distinguish three
sub-concepts of Touch—Touch at Entry, Touch at Interior, and Touch at Exit—which
refer to the motion patterns where the route segment touches the region-like landmark
only at its start point, interior, and end-point, respectively. The strong and weak
53
conditions of Touch and its three sub-concepts are shown in Table 5. Interestingly,
Touch at Entry has a strong condition only, because we can guarantee that the DLine
touches the region only at its start-point whenever the region extends over En, but
neither I nor Ex, and vice versa. Similarly, Touch at Exit has a strong condition only.
On the other hand, Touch at interior has both strong and weak conditions, because we
cannot guarantee that the DLine touches the region when the region extends over LI, I,
and RI, in addition to all fields around En or Ex (compare Figures 8b2 with Figure 6c3).
Similarly, Touch has both strong and weak conditions, since Touch is a superclass of
Touch at interior.
(a1) (a2) (b1) (b2) (c1) (c2) (d1) (d2)
Figure 8. Motion patterns that fit with the concept of Touch, as well as (a1-2) Touch at Entry, (b1-2) Touch at
Interior, and (c1-2) Touch at Exit, together with the RfDL3-12 patterns that represent these motion patterns.
Table 5. Strong and weak conditions of Touch and its sub-concepts, together with the numbers of RfDL3-12
patterns that satisfy each condition without/with the region’s convexity assumption.
Touch Touch
Touch Touch at Interior
at Entry at Exit
or or
Strong or
Condition either or
both
621, 250 115, 48 72, 18 115, 48
or or or or or or or
Same Same
Weak
as as
Condition either or not effective if the
both region is convex
above not effective if the above
region is convex
745, 250 103, 18
4.2.4. Comparison
In Sections 4.2.1-4.2.3, we observed that RfDL3-12 patterns capture a certain degree of
topological information, even though RfDL3-12’s frame of reference primarily highlights
directional distinctions. Interestingly, Tables 4-5 show that under the region’s
convexity assumption the number of RfDL3-12 patterns that satisfy the strong condition
of each concept is always same with the number of RfDL3-12 patterns that satisfy the
weak condition of the same concept. Consequently, when the landmark is represented
by a convex region, we can map a given motion pattern to topology-relevant motion
concepts without ambiguity. This indicates that the knowledge of the region’s
convexity is highly helpful to judge the topological characteristics of motion patterns,
in addition to the directional characteristics of motion patterns (Section 3).
54
5. Conclusions and Future Work
To model human concept of motions is an effective approach to enrich the
communication between people and computers/machines collaborating on spatio-
dynamic tasks. The previous analyses on human instructions to an intelligent semi-
autonomous wheelchairs [12] or mobile robots [16] observed many expressions that
refer to landmarks, specifying their direction or their intersection with the route. Thus,
based on Double Cross and its new counterpart for DLine-region arrangements, RfDL3-
12, this paper explored the modeling of a number of motion concepts that stand on a
mover-centric viewpoint. When the landmarks are represented by points, the motion
concepts were associated distinctively with the motion patterns modeled by Double
Cross. On the other hand, when the landmarks are represented by region, the
correspondence between the motion concepts and the motion patterns modeled by
RfDL3-12 had certain ambiguity, even though under the region’s convexity assumption
topology-related concepts were clearly associated with the motion patterns. In order to
decide the appropriate characterization of ambiguous motion patterns, we may need
further criteria other than RfDL3-12 patterns, which are left for future work. This paper
also demonstrated that the specification in GUM, as an upper model, is very useful to
capture a number of motion concepts in a generic and domain-independent way.
We are currently investigating to apply our findings to the interface of an
intelligent semi-autonomous wheelchair Rolland [29], such that elderly or impaired
people can intuitively control the wheelchair through natural dialogue. Even though
Double Cross and RfDL3-12 cover lots of motion concepts, we still need other spatial
models that feature different aspects of spatial contexts, in order to cover a wide variety
of concepts used in route instructions. For instance, to cover the concepts of goal-
oriented motions (e.g., go to the front of, go behind), we need a projection-based model
whose referent is a point (Section 1). To model the remaining motion concepts by
additional spatial models and to realize the comprehensive use of multiple spatial
models for the interpretation of behavioral descriptions is left for future work.
Acknowledgments
This work is supported by DFG (Deutsche Forschungsgemeinschaft) through the
Collaborative Research Center SFB/TR 8 Spatial Cognition – Subproject I3-SharC. We
would also like to thank Joana Hois and Robert Ross for fruitful discussions on the
conceptualization of motion expressions.
References
[1] Talmy, L.: How Language Structures Space. In: Pick, H., Acredolo, L. (eds.): Spatial Orientation:
Theory, Research, and Application. Plenum Press, New York, NY, USA (1983) 255-282
[2] Lindner, S.: What Goes up Doesn't Necessarily Come Down: The Ins and Outs of Opposites. In: 18th
Regional Meeting of Chicago Linguistics Society, pp. 305-323. University of Chicago Press. (1982)
[3] Langacker, R.: Foundations of Cognitive Grammar, vol. 1. Stanford University Press, Stanford, CA,
USA (1987)
[4] Langacker, R.: Grammer and Conceptualization. Mouton de Gruyter, Berlin, Germany / New York, NY,
USA (1999)
[5] Dewell, R.: Over Again: Image-Schemata Transformations in Semantic Analysis. Cognitive Linguistics
5, 351-381 (1994)
55
[6] Krüger, A., Maaß, W.: Towards a Computational Semantics of Path Relations. In: Workshop on
Language and space at the 14th National Conference on Artificial Intelligence (1997)
[7] Kray, C., Baus, J., Zimmer, H., Speiser, H., Krüger, A.: Two Path Prepositions: Along and Past. In:
Montello, D. (ed.): COSIT '01, Lecture Notes in Computer Science, vol. 2205, pp. 263-277. Springer
(2001)
[8] Richter, K.-F., Klippel, A.: Before and After: Prepositions in Spatially Constrained Systems. In:
Barkowsky, T., Knauff, M., Ligozat, G., Montello, D. (eds.): Spatial Cognition V, Lecture Notes in
Artificial Intelligence, vol. 4387, pp. 453-469. Springer (2007)
[9] Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Frank, A., Campari, I.,
Formentini, U. (eds.): International Conference GIS – From Space to Territory: Theories and Methods
of Spatio-Temporal Reasoning in Geographic Space, Lecture Notes in Computer Science, vol. 639, pp.
162-178. Springer (1992)
[10] Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning Using Orientation, Distance, and Path
Knowledge. Applied Intelligence 6, 49-58 (1996)
[11] Kurata, Y., Shi, H.: Interpreting Motion Expressions in Route Instructions Using Two Projection-Based
Spatial Models. To appear in KI-2008, Lecture Notes in Artificial Intelligence. Springer (2008)
[12] Shi, H., Bateman, J.: Developing Human-Robot Dialogue Management Formally. In: Symposium on
Dialogue Modelling and Generation (2005)
[13] Krieg-Brückner, B., Shi, H.: Orientation Calculi and Route Graphs: Towards Semantic Representations
for Route Descriptions. In: Raubal, M. (ed.): GIScience 2006, Lecture Notes in Computer Science, vol.
4197, pp. 234-250. Springer (2006)
[14] Werner, S., Krieg-Brückner, B., Herrmann, T.: Modelling Navigational Knowledge by Route Graphs.
In: Freksa, C., Brauer, W., Habel, C., Wender, K. (eds.): Spatial Cognition II, Lecture Notes in
Artificial Intelligence, vol. 1849, pp. 295-316. Springer (2000)
[15] Krieg-Brückner, B., Frese, U., Lüttich, K., Mandel, C., Mossakowski, T., Ross, R.: Specification of an
Ontology for Route Graphs. In: Freksa, C., Knauff, M., Krieg-Brückner, B., Nebel, B., Barkowsky, T.
(eds.): Spatial Cognition IV, Lecture Notes in Artificial Intelligence, vol. 3343, pp. 390-412. Springer
(2005)
[16] Bugmann, G., Klein, E., Lauria, S., Kyriacou, T.: Corpus-Based Robotics: A Route Instruction
Example. In: 8th Conference on Intelligent Autonomous Systems, pp. 96-103 (2004)
[17] Bateman, J., Hois, J., Ross, R., Farrar, S.: The Generalized Upper Model 3.0: Documentation.
Technical report, Collaborative Research Center for Spatial Cognition, University of Bremen, Bremen,
Germany (2006)
[18] Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a Directed Line
Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposium for Behavioral Monitoring
and Interpretation, pp. 62-76 (2007)
[19] Goyal, R., Egenhofer, M.: Consistent Queries over Cardinal Directions across Different Levels of
Detail. In: Tjoa, A.M., Wagner, R., Al-Zobaidie, A. (eds.): 11th International Workshop on Database
and Expert Systems Applications, pp. 876-880 (2000)
[20] Levinson, S.: Language and Space. Annual Review of Anthropology 25, 353-382 (1996)
[21] Frank, A.: Qualitative Spatial Reasoning: Cardinal Directions as an Example. International Journal of
Geographical Information Science 10, 262-290 (1996)
[22] Kurata, Y., Shi, H.: Projection-Based Models for Capturing Human Concepts of Motion. To appear in
Spatial Cognition '08 (2008)
[23] Gottfried, B.: Reasoning about Intervals in Two Dimensions. In: Thissenm, W., Pantic, M., Ludema, M.
(eds.): IEEE International Conference on Systems, Man and Cybernetics, pp. 5324-5332 (2004)
[24] Moratz, R., Nebel, B., Freksa, C.: Qualitative Spatial Reasoning about Relative Position: The Tradeoff
between Strong Formal Properties and Successful Reasoning about Route Graphs In: Freksa, C., Brauer,
W., Habel, C., Wender, K. (eds.): Spatial Cognition III, Lecture Notes in Artificial Intelligence, vol.
2685, pp. 385-400. Springer (2003)
[25] Schneider, M., Behr, T.: Topological Relationships between Complex Spatial Objects. ACM
Transactions on Database Systems 31, 39-81 (2006)
[26] Kray, C., Blocher, A.: Modeling the Basic Meanings of Path Relations. In: 16th International Joint
Conference on Artificial Intelligence, pp. 384-389. Morgan Kaufmann (1999)
[27] Grenon, P., Smith, B.: Towards Dynamic Spatial Ontology. Journal of Spatial Cognition and
Computation 4, 69-104 (2004)
[28] OpenGIS Consortium: OpenGIS Simple Features Specification for SQL (1998)
[29] Lankenau, A., Röfer, T.: The Role of Shared Control in Service Robots – the Bremen Autonomous
Wheelchair as an Example. . In: Röfer, T., Lankenau, A., Moraz, R. (eds.): Service Robotics –
Applications and Safety Issues in an Emerging Market, Workshop Notes, pp. 27-31 (2000)
56