A Size-Based Qualitative Approach to the Representation of Spatial Granularity

1 Introduction

Representation of local, granular spatial contexts is crucial for reducing complexity of reasoning in AI applications, such as mobile robots or spatial configuration systems. Via the notion of spatial context-awareness, this topic has gained importance also in other fields of research, such as research on improved human-computer-interfaces, ubiquitous computing, and location-based augmented reality [Chen and Kotz, 2000; Dey and Abowd, 2000; Kanter, 2003; Schilit et al., 1994].

A local spatial context is understood in this article as an area currently under consideration in a spatial reasoning process. The boundary between this area and the surrounding space together with the spatial granularity of the representation separates what is relevant at a given time from what is

∗This work was supported by Seondo project of MIC, Korea, by the UCN Project, the MIC 21st Century Frontier R&D Program in Korea, and by the BK 21 Project in 2006.

†Corresponding author irrelevant: to a mobile robot, e.g., near objects may be of immediate relevance, and information about what is near is often more certain, more reliable, and more detailed than about what is further away; for planning ahead, however, details about the immediate vicinity are secondary, and a less detailed representation of the wider surroundings is needed. As Hobbs [1985] pointed out, the ability to switch between representations of different granularity may be one of the fundamental characteristics of intelligence.

This article discusses a qualitative account of spatial granularity in which the notions of proximity and grain-size, which are formally both related to distance, are combined into a characterization of spatial granularity and local spatial context. In contrast to the geometric approach presented in [Schmidtke, 2003; 2005a], the concepts are axiomatically characterized in a way so as to be compatible with mereotopological axiomatic systems and reasoning mechanisms. The notion of grain-size is formalized using relations of comparison; quantitative, metric concepts are not necessary. The approach differs from other mereotopological approaches to spatial granularity, such as the stratified rough sets of [Bittner and Stell, 2003] or the granular partitions of [Bittner and Smith, 2003], as it focusses on the notions of grain-sizes and the limited extent of a spatial context as primary factors of spatial granularity. These notions can be used to organize the spatial locations of a domain into levels of granularity, without requiring partitioning of the domain.

Ways for applying our approach in the representation of spatial context for ubiquitous computing environments, and issues of vagueness and change of granularity have been discussed in [Schmidtke, 2005b; Schmidtke andWoo, 2006]. In this article, we give a model as a proof of soundness for a simplified axiomatic characterization, show its formal relation to other approaches on spatial granularity, and demonstrate its applicability for representing common sense concepts.

Starting from a mereotopological framework, the notion of spatial granularity is specified based upon special regions, called extended locations, which are characterized so as to serve as both grain-regions and context-regions (Sect. 2). An extended location can be a region, such as, e.g., a room in a building, that-on a coarse level of granularity-is conceived to be a point-like location, whose extension is irrelevant, or-on a finer level of granularity-the spatial extension of a context, which delimits what is relevant in the context.

The approach is thoroughly evaluated in Sect. 3 with respect to related works, soundness, and expressive power. An example for modeling of a domain in two scenarios is sketched. Applicability for common sense Knowledge Representation is demonstrated with formal specifications of otherwise difficult notions involving a concept of granularity-dependent relevance of extension, namely: point-like locations, as regions with an irrelevant extension, adjacency of locations as overlap in an area of irrelevant extension, and spatial indistinguishability of locations as sameness up to irrelevant parts.

2 Characterization of Spatial Granularity

In this section, the mereotopological framework for a qualitative, size-based axiomatization of spatial granularity is presented. After the rudimentary relations of connection and part are specified, extended locations can be characterized as linearly ordered by an ordering relation smaller (Sect. 2.1). This latter relation is the central tool for the formalization of size-based granularity in Sect. 2.2.

In contrast to the axiomatic characterization presented in [Schmidtke and Woo, 2006], we do not distinguish in this article between arbitrary regions and extended locations, i.e. regions which can be grains and context regions. This choice simplifies the discussion in Sect. 3, but would severely restrict the possibilities for representing the location of objects. As Sect. 3.3 illustrates, extended locations can justifiably be termed point-like locations. For an application in which both point-like, coarse locations, and detailed shape information about objects is to be represented, extended locations could be modeled in a sorted logic as a subtype of regions.

2.1 Extended Locations

A mereotopological basis was chosen for the characterization of extended locations. Extended locations fulfill basic requirements for regions [Casati and Varzi, 1999; Asher and Vieu, 1995; Randell et al., 1992]: connection C is a reflexive (A1) and symmetric relation (A2); the relation ⊑ (part of ) can be defined in terms of C (D1): x is part of y, iff every region that is connected to x is also connected to y. 1

It can be shown that ⊑ is a reflexive, antisymmetric relation. For a thorough treatment of mereotopological ontological questions, however, a more elaborate framework would be needed [Casati and Varzi, 1999; Asher and Vieu, 1995; Randell et al., 1992].

In contrast to general regions, extended locations have a unique size, i.e. can be ordered uniquely according to their size. More precisely, the notion of size, and thus size-based granularity, can be derived from a linear ordering ≤ (smaller or of equal size) on extended locations. The relation ≤ is a reflexive (A3), transitive (A4), and linear (A5) relation, and all parts of a location are smaller or of the same size as the location (A6).

1 In order to abbreviate formulae, the scope of quantifiers is to be read as maximal, i.e. until the end of a formula, or until the first unmatched closing bracket after a quantifier. Additionally, the following precedence is used: ¬, ∧, ∨,→,↔, def⇔.

The relation ≤ can be used to define an equivalence relation of congruence of size ≡ (same size) and an asymmetric subrelation < (smaller).

The equivalence classes with respect to ≡ correspond to the possible sizes in a domain. However, this notion of size does not necessarily correspond to a notion of distance supporting the axioms of a metric. Further restrictions would be necessary to ensure this. Stronger geometric characterizations of a region-based notion of size are given in [Dugat et al., 2002; Borgo et al., 1996], in which a relation similar to ≤ is the basis for characterizing spheres; a weak geometric characterization of region-based size for which the triangle inequality of a metric is not a consequence has been presented in [Schmidtke, 2003; 2005a]. An advantage of a less restrictive formalization is that it is gives more representational freedom for modelling a domain and choosing an appropriate granulation. The notion of size characterized with the relation ≤ does not need to correspond to a purely spatial notion of size as derived from, e.g., the Euclidean metric, but could, for instance, also include functional aspects: a small kink in the blade of a knife could thus be modeled as being more important than in its handle. 2 This notion of size and relevance is compatible with the above axiomatization, but would not be supported by the more restrictive geometric characterizations [Dugat et al., 2002; Schmidtke, 2003].

2.2 Grain Regions and Context Regions

Granularity, as characterized by [Hobbs, 1985] is a means to retrieve simplified, filtered representations of a domain from more complex, richer representations. Spatial and temporal granularity are closely related to the concept of grain-size in a local spatial or temporal context [Schmidtke, 2005b]. Parts of an object that are smaller than the grain-size can be disregarded as unimportant details; objects beyond the range of the area of the local context are not in the focus of current considerations; and objects which extend beyond this range likewise need not be represented as a whole, representing local parts would be sufficient for many purposes in this case. If objects beyond this range or objects smaller than the grain-size need to be accessed, a change of context has to be initiated: as we zoom out a larger area is covered, but small details are lost, zooming into a scene, smaller details are focussed, and objects further away become irrelevant. This photo metaphor of spatial granularity has been discussed by [Galton, 2000, §1.6]; the results of [Kosslyn, 1980] can be understood as supporting evidence for granularity phenomena in spatial imagery.

2 This example has been suggested to us by a reviewer.

The notion of an extended location being a grain location relative to a context location is axiomatically characterized using a relation |◁ , with x |◁ y denoting that x is a grain location of the context location y. Zooming out then is an operation of changing from a context location c1 to a larger location c2 containing c1, with the grains of c2 also being larger than the grains of c1. Axiom A7 formally characterizes this property: grains are ordered in the same way as their respective context locations and vice versa.

For a given domain, it might be useful to have atomic locations that do not have any parts and thus no grain locations either. We accordingly define as proper context locations those extended locations which have grain locations (D4); and demand that such locations are covered by grains without any gaps (A8): any location that is connected to a proper context location c is connected to some grain of c. It is worth noting that this axiom is the only ontological axiom in a narrow sense, as it actually guarantees existence of locations under certain conditions. The last axiom (A9) states that the grains of a context are proper parts of the context.

Since (A7) demands that grain locations are ordered with respect to ≤ in the same way as their respective context locations, we obtain from (A7) with c1 = c2 that all grains of a context location have equal extension (1). For g1 = g2 in (A7), it follows accordingly that all context locations of a grain have equal extension (2). The range of sizes corresponding to the sizes equal to or smaller than a given proper context location and equal to or larger than its grains thus can function as a level of spatial granularity in accordance with the axiomatization of levels of granularity given in [Schmidtke, 2005b]. In particular, it is possible to characterize a corresponding ordering on levels of spatial granularity with relations ≺ and ≈: c1 is of finer granularity than c2, iff there is a grain of c2 that is larger than c1 (D5); c1 is of compatible granularity with c2, iff c1 is not smaller than any grain of c2 and c2 is not smaller than any grain of c1 (D6).

It can be shown that, if restricted to the class of CL-locations (D4), ≺ is a semiorder with ≈ as a relation of indistinguishability. The proof follows along the lines of those given in

[Schmidtke, 2005b; Schmidtke and Woo, 2006]. Semiorders and non-transitive indistinguishability play an important role in the mathematical modeling of vagueness in perceptual classification [Suppes and Zinnes, 1963], e.g., of lengths or colors in psychophysical experiments [Palmer, 1999, p. 671]: if direct comparison is not possible, subjects may judge two lengths A and B to be the same, and the length B to be the same as C, without necessarily judging A and C to be the same lengths. A composition table for reasoning about semiorders has been given in [Schmidtke and Woo, 2006]. The mechanisms for managing contextual change of granularity as described in [Schmidtke, 2005b] for the case of temporal granularity can be applied accordingly.

3 Evaluation

In this section, the approach is evaluated with respect to related works, soundness, and expressive power. A formal comparison between the chosen size-based approach and the partitioning approach of [Bittner and Smith, 2003] is presented in Sect. 3.1. Soundness of the axiomatic characterization is proven with an example model of an office scenario (Sect. 3.2), which also serves to illustrate application of the concepts in standard scenarios in the fields of robotics and ubiquitous computing. The gained expressive power is illustrated in Sect. 3.3 with granularity-dependent specifications for otherwise difficult common sense notions involving the concept of irrelevant extension in a context.

3.1 Comparison to Partitioning Approaches to Granularity

The above axioms are neutral with respect to the question whether space is partitioned by the extended location regions. Axiom A8 demands that space is completely covered by extended locations on every given level of granularity, but allows for locations to overlap. AxiomA7 does not restrict this either. However, it may be desirable for some applications to impose stronger restrictions, in order to increase inferential power. A partitioning of context regions, i.e. that each context-region is completely partitioned by its grains, can be enforced with (P): a grain does not overlap another grain of the same context region.

This formalization only restricts grains of the same contextregion, but not, e.g., grains of different sizes, which are still allowed to also partially overlap. A stronger restriction is stated in the axiom MA4 in the theory of granular partitions [Bittner and Smith, 2003, p. 119]: "If two cells within a partition overlap, then one is a subcell of the other." This requirement can be formulated in the given theory by demanding that two locations can only overlap if one is contained in the other (C).

A consequence of (C) with (1) is that every context-region is partitioned by its grains (P). Actually, (C) is stronger than (P): (P) concerns only locations of the same size, whereas (C)

(b)

Figure 2: The simple layout of an office domain as an example of a model for the axiomatic system.

additionally demands that the locations of one size group into the locations of a larger size, i.e., that locations of different sizes are not permitted to overlap, as illustrated in Fig. 1b. This restriction is too strong for the intended modeling in Sect. 3.3. The more general approach suggested here allows for different partitions to be modeled as belonging to the same granularity if they agree with respect to ⊑ and <.

3.2 An Example Model

In order to show soundness of the characterization and as an example for illustration of the concepts to be defined in Sect. 3.3, a simple model for the axiomatic system is provided in terms of point sets in the coordinate space R2 : the space is given by the quadratic area A covering a simple layout of offices (Fig. 2); it is interpreted by the point set AI = [0, 1]2 . Connection C is interpreted by non-empty intersection, and ⊑, by the subset relation (⊆). The set LI interpreting the domain of extended locations consist of AI, the set of areas R = {HI , O1I , O2I , O3I , O4I , O5I , O6I } containing the point sets corresponding to the seven regions of the hallway H and of the rooms O1-O6 (including the walls separating them and any door spaces, see Sect. 3.3), and the set of circular discs (with respect to a presupposed distance function δ and a certain fixed maximal radius rmax, smaller than half the width of a room) around points lying in AI .

where D(P, r) is the disc of radius r ∈ R around the point P ∈ AI: 3 D(P, r) = {Q ∈ AI | δ(P,Q) ≤R r}. The relation ≤ is interpreted by the transitive closure of the relation

3 More precisely, D(P, r) is the intersection of AI with the disc around P .

≤∗ containing the relation ⊑ (interpreted by ⊆) as demanded by (A6), the elements of R as being of the same granularity according to above assumption, and the ordering on the discs in LI derived from the ordering ≤R on the radii of discs.

With ⊆ and ≤R being ordering relations that do not conflict with each other, (A3)-(A5) follow accordingly.

For the axioms in Sect. 2.2, an interpretation for |◁ is needed: the grains of A are the rooms and the hallway; the grains of a disc of radius r can be set to always have the size rc , for a certain fixed factor c > 1; 4 and the grains of rooms are discs of a certain fixed radius rg, with rmax < rg ≤ rmax.

c

Axiom A8 holds since R was defined so as to cover AI , and there is a disc D(P, r) for every size 0 < r ≤ rmax around every point of AI. All grains are subsets of their respective context regions and elements of LI , and no context is its own grain (A9). Axiom A7 can also be shown: the regions in R are contained in AI ; for every disc, there is a disc of the same size contained in a region of R since rmax was required to be smaller than half of the width of a room; and for the ordering on discs, we obtain that r1 < r2 , iff r1 < r2.

c c A similar structure, with a restricted minimum size for the discs, could be the result of representing a certain office environment for an application in robotics or ubiquitous computing. In a scenario of a service robot moving through an office environment, the level of granularity of the offices could be used, e.g., for possible addresses in commands to the robot, whereas the level of granularity corresponding to discs having the diameter of the robot can serve as the level of exact point-like locations of the robot. For planning local motion, e.g., a robot may employ numeric relative coordinates, whose accuracy varies with the speed of motion. Discs of larger sizes can be used to represent such vague coordinates. As errors add up, a computationally more expensive logic-based reasoning process for relocalization can be triggered. The formalism thus allows for reasoning about qualitative long range navigation as well as quantitative short range navigation in a unifying manner. A similar interpretation can be given for a ubiquitous computing scenario, as location sensing technologies differ with regard to accuracy and type of sensed location [Hightower and Borriello, 2001].

3.3 Definition of Granularity-Dependent Concepts

Granularity-dependent and context-dependent concepts such as spatial indistinguishability and adjacency of locations can be described with reference to an underlying partitioning of the plane. So it remains to show, how these notions can be expressed in the size-based approach and in which way the two approaches differ as regards expressiveness. The key concept to achieve this is the distinction between relevant and irrelevant locations contained in a context-region: a location x is a relevant sublocation of a context region xc if it is completely contained in the context-region and has at least grainsize (D7).

4 This simple characterization suffices for the purpose of constructing an example model and illustrating the concepts. For actual applications, however, limitations of accuracy have to be considered.

This notion can be used to distinguish between different types of overlap between two size-congruent locations: if two locations are distinguishable only by sublocations of irrelevant size, they can be called spatially indistinguishable ⊃ ⊂ (D8); two locations relevantly overlap ⊃⊂ (D9), iff they share a common relevant sublocation, but are not indistinguishable; and locations having only common sublocations of irrelevant extension are called granularly adjacent ⊃|⊂ (D10).

These relations can be used to model granularity-dependent adjacency and vague identity of locations as well as modes of movement of objects. In Fig. 3, the extended locations corresponding to offices are determined by the region an office occupies including the walls and any door spaces. If the parameter rg in the model is chosen so that the grains of the context regions of offices are larger than the width of the walls but smaller than the door spaces, e.g. as corresponding to the size of possible positions of a service robot, then we obtain that an office is classified

• as adjacent to the offices with which it shares a wall,
• as relevantly overlapping the hallway.

The example illustrates that space can be structured with the proposed characterization of granularity in a similar way as with a partitioning, but without imposing unnecessary restrictions, thus opening additional options for representation:

• To which office a certain wall belongs does not have to be decided. The walls can be modeled as boundaries with irrelevant extension.
• The relation of relevant overlap can be used to model accessibility, and to describe the viable paths.
• The discrete representation of space on the level of granularity of the offices can be combined with a dense or continuous conceptualization of space on finer levels.

The example also shows how a modeling using extended locations can offer benefits over a modeling based on points. For the possible positions of a robot moving through the domain, only the unoccupied locations of sufficient size are possible locations: the robot could be localized by a location of at least the size of its extent, a coarser location would be the room it is currently in. From the perspective of a perceiving mobile robot, its location on the finest level is determined only relative to a larger surrounding context region. Its absolute position in the domain can be inferred by combining this local relative position with knowledge about its position on a coarser granularity. Self-localization thus is meaningful only as localization relative to a larger context. 5

Given different levels of temporal granularity, the movement of a robot on a trajectory can be discretized into a sequence of extended locations 〈x1, x2, . . . , xn〉 representing the robot's position at different times:

• on a very fine level of temporal granularity, no relevant motion is perceivable: consecutive positions xi and xi+1 are indistinguishable: xi ⊃ ⊂ xi+1,
• on an intermediate level of temporal granularity, consecutive positions can additionally be adjacent or relevantly overlapping, depending on the velocity of the robot.
• for a coarse level of temporal granularity, consecutive positions have to be of a coarser spatial granularity, in order to be related.

The example of motion shows another advantage for the representation with extended locations over the representation by points. The different cases listed above cannot be distinguished in a point-based representation: two points on a trajectory can only be identical or disjoint. A region-based representation without granularity adds additional relations, such as overlap and external connection [Galton, 2000, §6.3]. Spatial granularity, as characterized here, encoding strata of basic sizes, adds further concepts of approximate location. The relation ⊃ ⊂, like ≈, is symmetric and reflexive, but transitive only if space is partitioned by the extended locations.

4 Outlook and Conclusions

In this article, an approach to spatial granularity was discussed in which granularity is represented as based on the sizes of certain regions, called extended locations. The mereotopological basis for the axiomatic characterization allows for combination and comparison with related approaches. The axiomatized theory could be shown to be a generalization of existing approaches to spatial granularity. The analysis in Sect. 3 illustrated that the proposed approach gives more representational freedom for structuring application spaces in comparison to approaches proposing a partitioning of the domain.

5 Closely related to this conclusion is the question whether the statement "I am now here" should be a tautology in a logic for spatial and temporal context, cf. [Forbes, 1989].

In order to derive reasoning mechanisms, such as composition tables for the relations described in Sect. 3.3, the characterization would have to be restricted with additional assumptions about the underlying space. However, the assumption that space is partitioned by the locations is a very restrictive one, as the relations of indistinguishability and adjacency would be collapsed to identity and sharing of portions of the boundary, respectively. The example model illustrated that a whole range of possible alternatively structured spaces can be characterized, including spaces partitioned in a less strict way. These alternative characterizations can be useful to avoid ad-hoc decisions, e.g., in modeling boundaries, as the example of the representation of the walls between offices showed. It is likely that this increased expressiveness comes at a price. Future work will accordingly include investigating questions of completeness and complexity.