Spatial Relations for Positioning Objects in a Cabinet

Universität
BremenTOKYO METROPOLITAN UNIVERSITY

Yohei Kurata

Hui ShiTokyo Metropolitan Universityykurata@tmu.ac.jp

Universität Bremen
shi@informatik.uni-bremen.deResearch Goal

Possible Relations and Expressions

To propose a set of qualitative spatial relations
designed for supporting man-machine communication
about object locations in a cabinet ‘Planar’ storage where we canEven though we can consider 3×6×6 = 108 cabinet relations,only 29 relations are possible in the real world:

ignore the front-back arrangement of two different objects

For example:[separate, (proceeds, proceeds)]

Textbooks are located at the top shelf[separate, (proceeds, equal)] [separate, (proceeds, includes)]at the left of[separate, (proceeds, succeeds)][separate, (overlap, succeeds)] [separate, (within, succeeds)][separate, (equal, succeeds)] [separate, (includes, succeeds)][separate, (succeeds, succeeds)][separate, (succeeds, overlap)] [separate, (succeeds, within)][separate, (succeeds, equal)] [separate, (succeeds, includes)]at the upper left of

A bottle is at the right of a box

An umbrella is on a box[separate, (proceeds, overlap)] [separate, (proceeds, within)]at the lower left ofabove

A model ship is in a bottle

A box is below a pack of files

at the upper right ofIn smart home environment, machines have to communicate
such ‘positioning expressions’ with ordinary people.
But why do we consider a new set of relations, instead of using a
existing sets of topological relations and directional relations?
Reason 1

Reason 2

Existing direction models distinguishhuge number of relations:• Papadias & Sellis [1]  69 relations• Cicerone & Felice [2]  218 relations• Kurata & Shi [3] 222 relations

Topological relations [4-5] are based onpartonomy and connectivity, but partonomy
does not hold between physical objects• Porland is in Oregon (partnomy)• An model ship in a bottle (not partonomy)[separate, (succeeds, proceeds)]

at the lower right of[enclosed, (within, within)]inat the right of[separate, (overlap, proceeds)] [separate, (within, proceeds)][separate, (equal, proceeds)] [separate, (includes, proceeds)]

below[encloses, (includes, includes)][separate, (within, within)]contains[separate, (includes, includes)]surrounded bysurrounds[separate, (overlap, within)][separate, (overlap, includes)][separate, (within, overlap)][separate, (includes, overlap)][separate, (overlap, overlap)]

——

—

—

—

Our Model

As shown above, most of the 29 cabinet relations can be mapped tosimple positioning expressions in English.

First, we consider the cross-section of objects.

For generality, we can consider an intermediate use of ontologicalconcepts:
e.g.,[[separate,t (proceeds,(d within)]ithi )]To capture topological characteristics, we consider enclosure
relations, which correspond toRCC-5 relations [5].

To capture directional characteristics, we consider simplified
version of Allen’s interval relations[6] on x- and y-axes.
yat the left of (English)
in the left side of (English)-no hidari-ni ((Japanese)p)

LEFT-OFconceptp…

Reasoning on Cabinet Relations
Converse of a cabinet relation can be derived by combining the converse of eachelement.

ye.g., r(A, B) = [separate, (proceeds, within)]  r(B, A) = [separate, (succeeds, includes)]x

separate

encloses

RCC-5
Relations

Enclosure
RelationsDRseparate


POPP

PPI

EQ

x

(within, succeeds)(within, within)

Allen’s
Interval
Relations

Simplified
Interval
Relations

before
meets
metBy
after

proceeds

startsduringfinishes
enclosed

encloses

succeeds

Similarly,Similarly compositions of two cabinet relations can be derived by combining thecomposition of each element pair.
e.g., r(A, B) = [separate, (proceeds, within)]r(B, C) = [encloses, (includes, includes)]  r(A,C) = [separate, (proceeds, *)]Composition table of the enclosure relations
separate

separate

enclosed

encloses*

separate,enclosed

separate

enclosed

separate

enclosed*

encloses

separate,encloses

enclosed,encloses

encloses

withinfinishedBy
contains
startedBy

includes

equal

equal

overlaps
overlappedBy

overlap

Composition table of the simplified interval relations
proceeds
succeeds

proceeds

succeeds

withinincludes

equal

proceeds*

proceeds,within,overlaps

proceeds

proceeds

succeeds

proceeds,
succeeds,
within,overlaps

proceeds,
succeeds

proceeds,
succeeds*

overlaps
proceeds,
within,overlaps
proceeds,
succeeds,
within,overlaps
proceeds,
succeeds,
within,overlaps

withinproceeds

proceeds,
succeeds

within*withinincludesproceeds,
within,includes,overlaps

proceeds,
succeeds,
within,includes,overlaps

equal,
within,includes,overlaps

within,includeswithin,includeswithin,includes,overlaps

equal

proceeds

proceeds,
succeeds

withinwithin,includes

equal

overlaps

overlaps

proceeds,within,includes,
overlaps

proceeds,succeeds,within,includes,
overlaps

within,overlaps

proceeds,succeeds,within,includes,overlaps

overlaps*Future Work

Finally, we combine the enclosure relation and the pair of interval relations.

• To find justification for the proposed mapping between cabinet relations andpositioning expressions• To
T implement
i lt theth above
b
idea
idand
d testt t its
it applicability
li bilit in
i a smartt homehenvironment
References[1] Papadias, D., Sellis, T.: Spatial Reasoning Using Symbolic Arrays. In: International Conference GIS (1992)[separate, (within, succeeds)][encloses, (within, within)][2] Cicerone, S., Felice, P.: Cardinal Directions between Spatial Objects: The Pairwise-Consistency Problem. Information Science 164, 165-188 (2004)[3] Kurata, Y., Shi, H.: Toward Heterogeneous Cardinal Direction Calculus: . In: KI 2009, LNCS 5803, pp. 452-459. (2009)[4] Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships between Regions, Lines and Points in Geographic Databases. In: NCGIA
Technical Reports 91-7 (1991)

These relations are called cabinet relations.

[5] Randell, D., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection. In: Knowledge Representation and Reasoning, 165-176(1992)[6] Allen, J.: Maintaining Knowledge About Temporal Intervals. Communications of the ACM 26, 832-843 (1983)