Interpreting Motion Expressions in Route Instructions
Using Two Projection-Based Spatial Models
Yohei Kurata and Hui Shi
SFB/TR 8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany{ykurata, shi}@informatik.uni-bremen.de

Abstract. This paper explores the applicability of two formal models of spatial
relations, Double Cross and RfDL3-12, to interpret some typical expressions thatpeople use for describing a route. The relations in these two models allow thequalitative representation of the location and spatial extent of a landmark as
seen from a route segment. We explore the correspondence between therelations in these two models and the motion expressions that refer to a pointlike and a region-like landmark, respectively, which consist of the same set of
direction-related expressions and specific sets of topology-related expressions.
Through this exploration, we identify intrinsic ambiguities in the directionrelated motion expressions that refer to a region-like landmark. Finally, we
propose the generalization of our approach by using a spatial ontology, which
potentially enables the mobile robots to interpret a large variety of expressions
in human route instructions.

1

Introduction

A dialogue-based interface is a promising technology for the robots that work
together with ordinary people. Especially, the mobile robots that navigate in humanliving spaces, such as the intelligent semi-autonomous wheelchair Rolland [1], shouldbe equipped with an ability to communicate verbally with human users about theirnavigation plans. Formal models of qualitative spatial relations between a directedline segment (DLine) and another geometric object are helpful for developing such atechnology [2], because those relations capture the prominent characteristics of routelandmark arrangements based on how people conceptualize the spatial context, andthe existing studies report that many expressions in human route descriptions concern
the actions associated with landmarks [3, 4]. Thus, this paper explores two formal
models of such DLine-object relations, Double Cross [5, 6] and RfDL3-12 [7], tointerpret some typical expressions that people use for describing motions in a flat
human-scale space. DLine-point relations in Double Cross (in short, DC relations)allow us to represent the location of a point-like landmark as seen from a routesegment. Similarly, DLine-region relations in RfDL3-12 (in short, RfDL3-12 relations)allow the representation of both the location and spatial extent of a region-likelandmark as seen from a route segment. The presence of motion expressions that
presume the landmark’s spatial extent observed in [8-9], such as “go into …” and “goto the end of …”, motivated us to study RfDL3-12 relations in addition to DC relations.
This paper focuses on the motion expressions that concern the relation between alandmark and an entire route segment. Meanwhile, we do not discuss theinterpretation of goal-oriented motion expressions, such as “go to the left of …”,
which concern the spatial relations between a landmark and a potential goal. Suchlandmark-location relations are used not only for describing motions, but also fordescribing static scenes and, accordingly, they are already well studied (e.g., [12]).
The reminder of this paper is structured as follows: Section 2 reviews Double
Cross and RfDL3-12. Section 3 identifies the correspondence between DC relations andmotion expressions. Then, Section 4 explores the correspondence between RfDL3-12
relations and motion expressions, finding some issues in such associations. Finally,
Section 5 concludes with a short discussion about the generalization of our approach.

2

Double Cross and RfDL3-12

When an agent moves straightly in a space guided by a landmark, its movement
pattern is represented by the spatial arrangement between a directed line segment(DLine) and another geometric object. The DLine represents the route segment on
which the agent proceeds, while another object corresponds to the landmark. The
landmark is represented by a point if its spatial extent is not significant; otherwise, thelandmark is represented as a region (or possibly a line if its width is not significant).
Double Cross is a model of spatial relations between three points [5], which arealso viewed as the relations between a straight DLine and a point [6]. Double Cross
projects a ‡-shaped intrinsic frame of spatial reference [11] onto the space, by which
twelve fields around the DLine and three fields on the DLine are defined (Fig. 1a). In
this paper, these 15 fields are called LF (left front), SF (straight front), RF (rightfront), LEx (left at exit), Ex (exit), REx (right at exit), LI (left of interior), I (interior),
RI (right of interior), LEn (left at entry), En (entry), REn (right at entry), LB (leftback), SB (straight back), and RB (right back). Based on which field contains thepoint, Double Cross distinguishes 15 DLine-point relations.
RfDL (Region-in-the-frame-of-Directed-Line) is a series of projection-basedmodels of spatial relations between a straight DLine and a simple region. Based on
the use or non-use of left-right, front-side-back, and entry-interior-exterior
distinctions with respect to the DLine, 23 = 8 types of DLine-centric intrinsic frames
are introduced. The spatial relation in each model is defined as the set of fields overwhich the region extends. The finest model, called RfDL3-12, distinguishes 1772
DLine-region relations [7] based on the ‡-shaped frame that distinguishes 15 fields(Fig. 1a). These 15 fields are the same with those of Double Cross and, therefore,
RfDL3-12 has a strong correspondence with Double Cross.
Both DC relations and RfDL3-12 relations are represented by icons (Fig. 1b). The
icons have 3×5 blocks, which geometrically correspond to the 15 fields that eachmodel considers. The icon of a DC relation has one marked block, which indicates thefield that contains the point. The icon of an RfDL3-12 relation has one or more marked
block, which indicates the set of fields over which the region extends. Accordingly, inboth models, relations are distinguished visually by the icons’ marking patterns.

LF SF RF
LEx Ex REx
LI

I

RI

LEn En REn
LB SB RB(a)(b)

Fig. 1. (a) Fifteen fields that Double Cross and RfDL3-12 consider. (b) Examples of a DC
relation and an RfDL3-12 relation represented by icons.

3

DC Relations and Motion Expressions

This section explores the correspondence between DC relations and some motion
expressions that refer to a point-like landmark (e.g., a bus stop). Suppose that theroute segment and the landmark are mapped to a DLine ab and a point p,
respectively. Then, the movement pattern is mapped to a DC relation ab : p . We
assume that the distance between ab and p is small enough for people to recognize p
as a landmark along ab whenever a DC relation holds between them.
“Approach” is a motion expression that refers to a movement during which the
distance between the moving agent and the landmark decreases, but does not become
zero. Thus, this expression corresponds to five DC relations where p is located at
ab ’s SF, LF, RF, LEx, or REx. “Approach” is further distinguished into five subexpressions: “go toward”, “go until … comes to the left”, “go until … comes to theright”, “approach … on the left front”, and “approach … on the right front”. These
five expressions are mapped uniquely to the five DC relations where p is located at
ab ’s SF, LEx, REx, LF, and RF, respectively.
The motion expression opposite to “approach” is “go away from”. This expression
corresponds to five DC relations where p is located at ab ’s SB, LB, RB, LEn, or REn.
Similarly, “go away from” can be distinguished into five sub-expressions, “go straightaway from”, “go away from … on the left back”, “go away from … on the rightback”, “go away from … on the left”, “go away from … on the right”, which aremapped uniquely to the five DC relations where p is located at ab ’s SB, LB, RB, LEn,and REn, respectively.
“Pass by” is a motion expression that refers to the movement where the landmark
is located ahead at the beginning and later comes behind the moving agent. Thus, thisexpression corresponds to two DC relations where p is located at ab ’s LI or RI.
Naturally, “pass by” is distinguished into “pass by … on the left” and “pass by … on
the right” depending on whether p is located at ab ’s LI or RI.
In this way, three expressions, “approach”, “go away from”, and “pass by”, andtheir twelve sub-expressions are assigned distinctively to the twelve fields around ab(Fig. 2). All of these expressions presume the state where the point-like landmark is
located around the route segment. If the landmark is located on the segment’ start-point, interior, and end-point (i.e., if the movement is characterized by the DC
relations where p is located at ab ’s En, I, and Ex), then “depart from”, “pass”, and“arrive at” are the typical expressions that fit with the movement pattern,
respectively. These three expressions concern the topological characteristics of theroute-landmark arrangement (i.e., how the route intersects with the landmark).
Go toward …

Approach …

Pass by …

Arrive at …

Pass …

Approach… on the left front

Approach … on the right front

Go until … comes to the left

Go until … comes to the right

Pass by … on the left
Go away from … on the left

Going awayfrom ….

Depart from …

Going away from … on the left backPass by … on the right
Go away from … on the right
Go away from … on the right back
Go straight away from …

Fig. 2. Motion expressions assigned distinctively to the fields on/around a route segment.

4

RfDL3-12 Relations and Motion Expressions

Next, we consider the situation where the landmark is represented by a region.
Suppose that the route and the landmark are mapped to a DLine ab and a region R,
respectively. Then, the movement pattern is mapped to an RfDL3-12 relation ab : R .
For the situation where the landmark is located around the route segment, we canconsider the same set of motion expressions as before (i.e., “approach”, “go awayfrom”, “pass by”, and their sub-expressions). This time, however, the correspondence
between these expressions and spatial relations is not clearly determined. For
instance, let us think about “approach”. It is certain that “approach” fits with the
movement pattern where the distance between the moving agent and every point on
the landmark monotonically decreases (Fig. 3a). Moreover, it is clear that “approach”
cannot fit with the movement pattern where the landmark has no point inside to which
the distance from the moving agent decreases monotonically during the movement(Fig. 3f). Thus, we consider the following two conditions of “approach”:• strong condition: the movement pattern is mapped to ab : R where R extends atleast one field among ab ’s SF, LF, RF, LEx, or REx, but no other field, and;• weak condition: the movement pattern is mapped to ab : R where R extends over at
least one field among ab ’s SF, LF, RF, LEx, or REx, and neither En, I, nor En.
If a movement pattern satisfies the strong condition (e.g., Fig. 3a), this pattern always
fits with the expression of “approach”. On the other hand, if a movement pattern does
not satisfy the weak condition (e.g., Fig. 3f), this pattern never fits with thisexpression. Note the movement patterns in Figs. 3b-e satisfy the weak condition, but
not the strong condition. The movement patterns in Figs. 3b and 3d may well be
described as “approach”, but those in Figs. 3c and 3e probably not. This indicates thepresence of borderline cases between Figs. 3b-c and between Figs. 3d-e, even though
the movement patterns of each pair belong to the same RfDL3-12 relation, respectively.

(a)

(b)

(c)

(d)

(e)

(f)

Fig. 3. Example of movement patterns that satisfy (a) both the strong and weak conditions of“approach”, (b-e) the weak condition only, and (f) neither.

In order to evaluate how well “approach” fits with the movement pattern when it
satisfies only the weak condition (e.g., Figs. 3b-e), we need further criteria; forinstance, the relative length of period during which the nearest distance between themoving agent and the landmark decreases (compare Fig. 3b-c). In addition, thecomparison of Fig. 3d-e indicates that it is better to consider a minimum threshold of
the speed that the nearest distance decreases. The degree of fitness is then evaluatedby the membership function of a fuzzy concept “approach” in Eqn. 1, where a and b
are the location vector of the route segment’s start-point a and end-points b, x is thelocation vector of the moving agent,− Δ distance ( x , R )Δxis the relative speed that the nearest

distance decreases, and α is its threshold (α >0).

μ approach =⎞⎛1lim ⎜ ∑Δx ⎟⎟− Δ distance ( x , R )>αb − a Δx →0⎜⎝ x∈[a ,b ] ∧
Δx
⎠

(1)

As we considered in the previous section, “approach” is further distinguished into
five sub-expressions. Their definitions, however, become slightly different when thelandmark is represented by a region:• “go toward …” refers to the movement where the landmark stretches across thefront extension of the route segment (Fig. 3a);• “go until … comes to the left/right” refers to the movement where the landmark
appears the straight left/right of the moving agent when it comes to or near theend-point of the route segment (Fig. 3b); and• “approach … on the left/right front” refers to the movement where the landmark
mostly extends over the left/right front of the moving agent when it arrives at theend-point of the route segment (Fig. 3b).
Table 1 summarizes the strong and weak conditions of “approach” and its subexpressions using icons. These ‘condition icons’ follow the structure of the icons of
RfDL3-12 relations, where the icon’s 15 blocks geometrically correspond to the 15
fields that RfDL3-12 considers. Black, gray, and white blocks indicate the fields overwhich the region R must, may, and cannot extend, respectively. In addition to these
conditions, it is possible to define membership functions that quantify how well each
sub-expression fits with a given movement pattern, as we have defined such afunction for “approach” (Eqn. 1). This is, however, beyond the scope of this paper.
“Go away from” is the motion expression that is opposite to “approach”.
Consequently, the strong and weak conditions of this expression, as well as those of
its sub-expressions, are derived from Table 1 simply by flipping the icons vertically.

Table 1. Conditions of the motion expression “approach” and its sub-expressions imposed on
RfDL3-12 relations, together with the number of relations that satisfy the conditions.
Approach …

Go toward …

Go until … comesto the left

Approach …
on the left front

4

3

4

46

7

67

at least
one

StrongCondition
12
at leastone

Weak
Condition

102

The motion expression “pass by” that refers to a region-like landmark is essentiallythe same as “pass by” that refers to a point-like landmark. The condition of “pass by”(i.e., the landmark is located ahead at the beginning and later comes behind themoving agent) is satisfied if the R is entirely contained in ab ’s LI or RI, but not both.
Table 2 shows the conditions of “pass by” and its two sub-expressions. As this tableindicates, whether these expressions fit with a given movement pattern or not can be
determined only from the RfDL3-12 relation that characterize this movement pattern.
Table 2. Conditions of the motion expression “pass by” and its sub-expressions imposed on
RfDL3-12 relations, together with the number of relations that satisfy these conditions.
Pass by …

Pass by … on the left

Pass by … on the right1

1

either2

Next, we consider the situation where the landmark is located over the routesegment. Such situations are covered by 1645 of the 1772 RfDL3-12 relations. Some ofthese relations correspond to a unique motion expression. For instance, the RfDL3-12
relations in Figs. 4a-b correspond to the expressions “go across …” and “pass theedge of …”, respectively. Meanwhile, the RfDL3-12 relation in Fig. 4c corresponds totwo different expressions: “go into …” and “go to the edge of … and keep going”.
Like this example, the use of RfDL3-12 relations for characterizing a movement pattern
may leave certain ambiguity, because if a certain part of a DLine intersects with aregion, the RfDL3-12 relation tells the presence of this intersection, but does not
specify whether this DLine’s part intersects with the region’s interior or boundary.
Alternatively, the model of topological DLine-region relations [2] serves as a niceframework for handling the motion expressions that refer to a region-like landmark
located over a route segment, because for such a landmark people pay primalattention to whether the moving agent starts from, passes through, or ends at thelandmark’s inside, edge, or outside, which are the topological characteristics of routelandmark arrangements. Indeed, topological DLine-region relations capture suchmotion expressions as “go into”, “go out of”, “go across”, “go within”, “leave theedge of”, “arrive at the edge of”, “pass the edge of”, and so forth [2]. This, however,does not necessarily mean that RfDL3-12 relations are useless for capturing such
topology-related motion expressions. Actually, it is confirmed in [7] that:• 76.2% of RfDL3-12 relations are mapped to a unique topological relation; and• 100% of RfDL3-12 relations are mapped to a unique topological relation when thelandmark is represented by a convex region (e.g., rectangles, circles).
Thus, many RfDL3-12 relations can be associated with topology-related motion
expressions by way of topological DLine-region relations without ambiguity,especially in the indoor environments where many landmarks (e.g., tables, sofas,
beds, and closets) are represented by convex regions.

(a)

(b)

(c)

Fig. 4. Examples of RfDL3-12 relations that capture topological characteristics of movement
patterns (a-b) without and (c) with ambiguity.

5

Conclusions and Future Work

Formal treatment of human route descriptions is essential for developing intelligent
dialogue-based interface of the mobile robots that navigate in human living spaces.
This paper demonstrated that DC relations and RfDL3-12 relations, which allow thequalitative representation of landmarks’ location and spatial extent as seen from aroute segment, are useful for capturing some typical motion expressions in humanroute descriptions. We observed that the same set of motion expressions that concern
the landmark’s direction is applicable to both situations where the landmarks are
represented by points or regions, although some expressions may have intrinsic
ambiguities for the latter situation. For such ambiguous expressions, it is possible toevaluate how well each expression fits with the movement pattern as a membershipvalue of a fuzzy concept. We also examined different sets of motion expressions thatconcern the topological characteristics of route-landmark arrangements.
The existing analyses of human route descriptions (e.g., [3, 9]) show the presenceof several motion expressions that neither Double Cross nor RfDL3-12 may cover, suchas “go to the left of …” and “go behind …” These goal-oriented motion expressions
presume landmark-centric frames of spatial reference, whereas both Double Cross and
RfDL3-12 consider path-centric frames. This indicates the necessity of additional
spatial models for capturing more wide range of expressions in human routedescriptions (e.g., [12]).
This paper examined some concrete motion expressions in English. This approach
looks straightforward, but lacks generality. Alternatively, we are currently
investigating the correspondence between DC/RfDL3-12 relations and generalized
concepts of motions in an upper-level spatial ontology, called the Generalized Upper

Model [10]. For instance, the expressions “go across …”, “pass through …”, and“gehen über …” correspond to the same concept in this ontology, called PathRepresenting-Internal, if their slight nuance is neglected. If the set of RfDL3-12
relations that corresponds to this ontological concept is clarified beforehand, mobile
robots can determine the possible movement patterns that satisfy the user’s such
request as “go across the parking lot”, “pass through the car park”, and “gehen Sieüber den Parkplatz”. This approach will definitely expand the applicability of ouranalysis in this paper as a foundation of dialogue-based interface of mobile robots.
Acknowledgments
This work is supported by DFG (Deutsche Forschungsgemeinschaft) through the
Collaborative Research Center SFB/TR 8 Spatial Cognition – Subproject I3-SharC.

References
1. 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)
2. Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a
Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposiumfor Behavioral Monitoring and Interpretation, pp. 62-76 (2007)
3. Denis, M.: The Description of Routes: A Cognitive Approach to the Production of Spatial
Discourse. Current Psychology of Cognition 16, 409-458 (1997)
4. May, A., Ross, T., Bayer, S., Tarkiainen, M.: Pedestrian Navigation Aids: Information
Requirements and Design Implications. Personal and Ubiquitous Computing 7, 331-338(2003)
5. 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, LNCS, vol.
639, pp. 162-178. Springer (1992)
6. Zimmermann, K., Freksa, C.: Qualitative Spatial Reasoning Using Orientation, Distance,
and Path Knowledge. Applied Intelligence 6, 49-58 (1996)
7. Kurata, Y., Shi, H.: RfDL: Models for Capturing Directional and Topological
Characteristics of Path-Landmark Arrangements. (submitted)
8. Bugmann, G., Klein, E., Lauria, S., Kyriacou, T.: Corpus-Based Robotics: A RouteInstruction Example. In: 8th Conference on Intelligent Autonomous Systems, pp. 96-103(2004)
9. Shi, H., Tenbrink, T.: Telling Rolland Where to Go: HRI Dialogues on Route Navigation.
In: Coventry, K. and Tenbrink, T. and Bateman, J. (eds.): Spatial Language and Dialogue,
Oxford University Press (to appear)
10.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)
11.Levinson, S.: Language and Space. Annual Review of Anthropology 25, 353-382 (1996)
12.Mukerjee, A., Gupta, K., Nautiyal, K., Singh, M., Mishra, N.: Conceputual Description ofVisual Scenes from Linguistic Models. Image and Vision Computing 18, 173-187 (2000)