Reasoning on the Patterns of Spatial Arrangements
between a Path and a Region-Like Landmark
Hui Shi, Yohei Kurata
SFB/TR 8 Spatial Cognition, Universität Bremen{shi, ykurata}@informatik.uni-bremen.deINTRODUCTION
RfDL (Region-in-the-frame-of-Directed-Line) is a series of spatial models

that distinguish the patterns of spatial arrangements between a path and aregion-like landmark at different levels of granuralities (Kurata and Shi2008). These models are useful for capturing path-centric concepts of motions, such as “go toward”, “pass … on the right”, and “go across”. Each
RfDL model adopts a specific frame of reference (Levinson 1996), which
partitions the space on/around the path into a set of fields. Each pattern of
path-landmark arrangements is defined as the set of fields over which thelandmark extends. Among the eight models proposed by Kurata and Shi(2008), the finest model RfDL3-12 corresponds to Double Cross (Freksa1992), since both models adopt the same ‡-shaped intrinsic frame thatcombines left-right, front-side-back, and entry-interior-exit distinctions(Fig. 1a). The aim of this work is to develop a foundation of spatial reasoning on the patterns of path-landmark arrangements modeled by RfDL3-12,
making use of the correspondence between RfDL3-12 and Double Cross.
The developed reasoning methods can be applied, for instance, to the mobile robots that interpret human route instructions. For visualization, pathlandmark arrangement patterns modeled by Double Cross and RfDL3-12,
called DC-patterns and RfDL3-12-patterns, are represented by icons, whose
black cells indicate the fields over which the landmark extends (Fig. 1b).
LF SF RFLEx Ex RExLIIRILEn En REn
LB SB RB(a)Fig. 1:(b)(a) The frame of reference adopted by Double Cross andRfDL3-12, and (b) icons of DC- and RfDL3-12-patterns.

INVERSION, HOMEING, AND SHORTCUTIn Double Cross, inversion (INV), homing (HM), and shortcut (SC) are theoperations that map a DC-pattern ab : c to ba : c , bc : a , and ac : b , respectively (Zimmermann and Freksa 1996). In a practical sense, if we know thedirection of a location c as seen from a path ab , INV ab : c gives c’s direc-()()

tion as seen from the reversed path ba , HM ab : c gives all possible direc-()

tions of the origin a as seen from bc , and SC ab : c gives all possible directions of b as seen from the shortcutting path ac (Fig. 2a). Thus, considering similar perspective changes (Figs. 2a-b), we defined the inversion,
homing, and shortcut of an RfDL3-12-pattern ab : R (R: a region) as(()())

INV ab : R = ba : R , HM ab : R = U x∈R bx : a , and SC ab : R = U x∈R ax : b .

cbcbaaInversioncbRRcbbaa

HomingShortcutbaInversion

Fig. 2:(Rxba(a) Double CrossRbxaa

HomingShortcut(b) RfDL3-12

Perspective changes in inversion, homing, and shortcut operations.

)

INV ab : R gives R’s direction as seen from the reversed path ba . It is easi-()ly derived by the icon’s half-turn (Fig. 3a). HM ab : R gives all possible
directions of the origin a as seen from a path bx where x is somewhere in R.

( )It is derived as the union of the results of DC-homing HM ab : x where()x ∈ R (Fig. 3b). Finally, SC ab : R gives all possible directions of b as seenfrom a shortcutting path from ax where x is somewhere in R. It is derived
similarly by union operation (Fig. 3c). Note the results of RfDL3-12-homing
and RfDL3-12-shortcut are a set of DC-patterns. Thus, RfDL3-12-homing andRfDL3-12-shortcut cannot be applied repeatedly to RfDL3-12-patterns, unlike
DC-homing and DC-shortcut that can be applied repeatedly to DC-patterns.
This limitation stems from the heterogeneity of RfDL3-12-patterns, which areestablished by two points and a region, instead of three points.

(a) inversion
Fig. 3:

ab : R1x∈R(b) homing

ab : R1

bx : aunion

DC shortcut

Udecompose

union

DC homingba : R1

decompose

half-turn

ab : R1

Ux∈Rax : b(c) shortcut

Derivation of inversion, homing, and shortcut of the RfDL3-12pattern ab : R in Fig. 2b. Icons with gray cells represent a set ofDC-patterns, each with only one black cell among the gray cells.

COMPOSITION
The composition of DC-patterns ab : c and bc : d , denoted as ab : c ; bc : d ,gives all possible patterns of ab : d (Freksa 1992). Similarly, we can consider the composition of a DC-pattern ab : c and an RfDL3-12-pattern bc : R ,denoted as ab : c ; bc : R , which gives all possible patterns of ab : R . For instance, if c is located at the right front of ab and R extends over the left
front to the right front of bc (Fig. 4), there are 15 possible patterns of
ab : R . Basically, this composition is derived as the union of the results of
the DC-composition ab : c ; bc : x , considering a point x that moves in R
(Fig. 4). From Freksa’s (1992) composition table, we can determine
ab : c ; bc : x when x is located at bc ’s left-front, straight-front, and rightfront, respectively. Each of the three results of ab : c ; bc : x specifies thefields where x can be located with respect to ab . Since R contains x, R extends over at least one of the fields that each of the three results specifies(Condition 1). In addition, R extends over no field other than the union of
the three results (Condition 2). Among all RfDL3-12-patterns, only 15cc

RbFig. 4:

ab : cbc : Rbc : x ( x ∈ R )

=;

=;

=

Condition 1

Condition 2a;

union

b

ab : c; bc : R
ab : c; bc : x

Derivation process of the composition ab : c; bc : R .

patterns satisfy these two conditions (Fig. 4). Thus, these 15 patterns are
the result of the composition ab : c ; bc : R .
We can also define another type of composition, which combines twoRfDL3-12-patterns—say, ab : R1 ; bx : R2 ( x ∈ R1 ) . This composition gives allpossible ab : R2 after a two-step movement from a via b to somewhere x inR1, during which ab : R1 and bx : R2 are observed. Similarly, this composition is derived as the union of the results of DC-composition ab : x ; bx : y ,considering two points x and y that move in R1 and R2, respectively.
CONCLUSIONS AND FUTURE WORK
RfDL models are useful for characterizing path-landmark arrangements in aqualitative way, because the spatial patterns of RfDL models highlight

where and how the landmark extends as seen from a moving agent. Indeed,
Kurata and Shi (2008) applied RfDL3-12 model to associating path-landmark
arrangements with a number of human concepts of motions. In this paper,
we developed a foundation of qualitative spatial reasoning on the pattern of
the RfDL3-12 model. Reasoning on the patterns of the other coarser RfDL
models is also possible by assuming all potentially corresponding RfDL3-12patterns and integrating the results of reasoning on these patterns. In ourcurrent work, we are developing a set-theoretic computational approach torealize the operations discussed in this paper.
REFERENCES
Freksa, C. (1992) Using Orientation Information for Qualitative Spatial
Reasoning. International Conference GIS. A. Frank, I. Campari, and U.
Formentini. Berlin, Springer. LNCS 639.
Kurata, Y. and H. Shi (2008) Interpreting Motion Expressions in Route Instructions Using Two Projection-Based Spatial Models. To appear in KI2008.
Levinson, S. (1996) "Language and Space." Annual Review of Anthropology 25: 353-382
Zimmermann, K. and C. Freksa (1996). "Qualitative Spatial Reasoning Using Orientation, Distance, and Path Knowledge." Applied Intelligence 6:49-58.