Spatial Relations for Positioning Objects in a Cabinet

Abstract

This paper proposes a set of qualitative spatial relations designed for supporting human-machine communication about objects' locations in 'planar' storage. Based on Allen's interval relations and RCC-5 relations, our relations are derived by combining directional and mereo-topological relations between the projections of objects onto the 2D background. We identify 29 realizable relations, which are then mapped to positioning expressions in English.

Keywords

• spatial communication
• relative locations
• mereo-topological relations
• directional relations
• RCC-5
• Allen's interval relations

Introduction

When people describe the location of an object, they often use the relative position of the object with respect to other objects which can be identified more easily. In order that people can communicate with smart environment via natural dialogue, computers should be able to understand and generate such positioning expressions. To process such positioning expressions, we may apply existing models of cardinal directional relations (e.g., [ 1, 2 ]) or those of mereo-topological relations (e.g., [ 3, 4 ]). However, existing direction models distinguish too large number of relations—for instance, Papadias and Sellis [ 1 ], Cicerone and Felice [ 5 ], and Kurata and Shi [ 6 ] distinguish 169, 218, and 222 relations, respectively. In addition, we have to care the application of mereo-topological relations, because partonomy actually does not hold between physical objects. This paper, therefore, proposes a task-oriented set of qualitative spatial relations designed for supporting human-machine communication about object locations in a cabinet, based on the model of cardinal directional relations in [ 1 ] and that of mereo-topological relations in [ 3 ] (Section 2). Here a cabinet refers to any ‘planar’ storage in which we can neglect the front-back arrangement of two different objects. Moreover, objects are limited to physical objects in the real world (i.e., 3D single-component spatial objects without cuts or spikes, which never intersect with each other). The resulting relations, called cabinet relations, are smoothly mapped to natural language expressions for positioning objects (Section 3).

Formalization of Cabinet Relations Allen [ 7 ] distinguished 13 relations between two intervals. Considering projections of 2D objects onto x- and y-axes and the interval relations between these projections on each axis, Guesgen [ 8 ] distinguished 1313 relations between two 2D objects. His theory, called Rectangular Algebra (RA), is used typically for capturing north-southeast-west relationships, but here we use it for capturing above-below-left-right relationships in a cabinet, setting x-, y-, and z-axes parallel to the cabinet’s width, height, and depth axes and considering the projections of 3D objects onto the xyplane. Moreover, we summarize the 13 interval relations into 6 relations (Fig. 1b), such that (i) each relation captures how the main bodies of two intervals overlap and (ii) converse of each relation is uniquely determined. The original 1313 relations and the new 66 relations are called RA relations and simplified RA relations, respectively. For instance, the arrangement of two objects in Fig. 1a is represented by a RA relation (meets, starts) or by a simplified RA relation (proceeds, within).

RCC-5 relations [ 3 ] consist of five mereo-topological relations, namely DR (discrete), PO (partial overlap), PP (proper part), PPI (proper part inverse), and EQ (equal). In our cabinet scenario, we consider the projection of each object onto xyplane, whose inner spaces (i.e., empty spaces enclosed by the projection), if they exist, are filled. Then, considering RCC-5 relations between the space-filled projections, we distinguish three spatial relations between the original objects, namely separate, enclosed, and encloses (Fig. 1c). These three relations capture whether one object is enclosed by another object as seen from the front of the cabinet, thereby called enclosure relations. Note that the projections never take PO and EQ relations, since in our scenario two objects never overlap nor have a front-back arrangement.

A cabinet relation between two objects is defined as a pair of their enclosure relation and simplified RA relation. For instance, the cabinet relation in Fig. 1a is represented as [separate, (proceeds, within)]. Since we have 3 enclosure relations and 66 simplified RA relations, there are 366 = 108 pairs of relations. However, only 29 pairs (Fig. 2) are realizable in the real world because (i) when the enclosure relation is enclosed, the simplified RA relation must be (within, within) (note that (within, equal), (equal, within), and (equal, equal) are impossible because two objects never overlap nor have a front-back arrangement), (ii) similarly, when the enclosure relation is encloses, the simplified RA relation must be must be (includes, includes), and (iii) when the enclosure relation is separate, the simplified RA relation can be any but neither (within, includes), (within, equal), (includes, within), (includes, equal), (equal, within), (equal, includes), (equal, equal), (equal, overlap), nor (overlap, equal), since these relations presume the overlap of two objects. 3

Mapping from Cabinet Relations to Positioning Expressions When people explain the location of an object, they often rely on topological relations between the object and other related object (especially if they intersect) or directional relations between them (especially if they are located separately). Thus, the cabinet y [enclosed, (within, within)]

(a) [separate, (succeeds, within)]

(k) [separate, (includes, includes)] (u) (a) [encloses, (includes, includes)]

(b) [separate, (succeeds, includes)]

(l) [separate, (includes, overlap)] (v)

x (Figs. 2e-h) 2w, and 2y) relations, which capture both topological and directional characteristics of objects’ arrangements, have certain correspondences to positioning expressions. Indeed, we can map the cabinet relations to the following English expressions:  [enclosed, (within, within)]

A is in B (Fig. 2a)  [encloses, (includes, includes)]

A contains B (Fig. 2b)

 [separate, (proceeds, proceeds)] 

A is at the lower left of B (Fig. 2c)

 [separate, (proceeds, within/includes/equal/overlap)]  A is at the left of B  [separate, (within/includes/equal/overlap, proceeds)]  A is below B (Figs. 2o, 2s,  [separate, (within, within)] 

A is surrounded by B (Fig. 2q)

 [separate, (includes, includes)] 

A surrounds B (Fig. 2u)

Among 29 cabinet relations, 24 relations are assigned each to a certain expression. Other 5 relations (Figs. 2r, 2v, 2-2) refer to rather complicated arrangements and are difficult to characterize with simple expressions.

Allen’s Interval Relations before meets metBy after starts during finishes finishedBy contains startedBy equal overlaps overlappedBy (b)

Simplified Interval Relations proceeds succeeds within includes equal overlap

RCC-5 Relations

Enclosure

Relations DR PO PP PPI EQ (c) separate

 enclosed encloses 

In actual dialogues, people use lots of expressions for describing locations. For generality, we can consider an intermediate use of ontologies. For instance, we can assign [separate, (proceeds, within)] to an ontological concept, which is then mapped to such expressions as “at the left of” in English and “-no hidari-ni” in Japanese. As a similar work, Shi and Kurata [ 9 ] mapped path-landmark relations to ontological concepts in GUM [10]. Such generalization in our model is left for future work. 4

Conclusions and Future Work

This paper introduced a set of qualitative spatial relations designed for the positioning of physical objects in a cabinet. These cabinet relations will work powerfully for supporting human-machine communication in smart environments. At this moment, the mapping between the cabinet relations and language expressions is empirical and thus, we need certain justification of this mapping in future work. We may also need certain fine-tuning of the model, considering the use of additional information such as adjacency/distance between two objects. Lastly, another issue in our future agenda is to implement the proposed idea and test its applicability in practical systems.

References

1. Papadias , D. , Sellis , T. : Spatial Reasoning Using Symbolic Arrays . In: Frank, A. , Campari , I. , Formentini , U . (eds.): International Conference GIS ( 1992 )

2. 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 )

3. Randell , D. , Cui , Z. , Cohn , A. : A Spatial Logic Based on Regions and Connection . In: Nebel, B. , Rich , C. , Swarout , W. (eds.): Knowledge Representation and Reasoning , pp. 165 - 176 . Morgan Kaufmann, San Francisco, CA, USA ( 1992 )

4. Egenhofer , M. , Herring , J.: Categorizing Binary Topological Relationships between Regions, Lines and Points in Geographic Databases . In: Egenhofer, M. , Herring , J. , Smith , T. , Park , K. (eds.): Ncgia Technical Reports 91-7 . NCGIA, Santa Barbara , CA, USA ( 1991 )

5. Cicerone , S. , Felice , P. : Cardinal Directions between Spatial Objects: The PairwiseConsistency Problem . Information Science 164 , 165 - 188 ( 2004 )

6. Kurata , Y. , Shi , H. : Toward Heterogeneous Cardinal Direction Calculus: . In: Mertsching, B. , Hund , M. , Aziz , M. (eds.): KI 2009, Lecture Notes in Computer Science , vol. 5803 , pp. 452 - 459 . Springer, Berlin/Heidelberg ( 2009 )

7. Allen , J.: Maintaining Knowledge About Temporal Intervals . Communications of the ACM 26 , 832 - 843 ( 1983 )

8. Guesgen , H.: Spatial Reasoning Based on Allen's Temporal Logic . Technical report , International Computer Science Institute ( 1989 )

9. Shi , H. , Kurata , Y. : Modeling Ontological Concepts of Motions with Two Projection-Based Spatial Models . In: Gottfried, B. , Aghajan , H. (eds.): Behavioral Monitoring and Interpretation , CEUR Workshop Proceedings , vol. 396 , pp. 42 - 56 . CEUR-WS.org ( 2008 ) 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 )