An Algebraic Approach to Granularity in Qualitative Time and Space Representation

1 . Introduction

"Imagine, you are biking in a flat countryside. At some distance ahead of you there is something still. You are just able to say (a) that a truck (T) is aside a house (H), it seems that they meet. When you come closer to them (b) you are able to distinguish a bumper (B) between them, and even closer (c), you can perceive the space between the bumper and the house."

This little story shows the description of the same reality perceived at several resolution levels: this is called granularity. Granularity would not be a problem if different individuals, institutions, etc . would use the same granularity. This is not the case and, moreover, these individuals communicate data expressed under different granularities. There could be a problem if, for instance, someone at position (a), asked "how would you call that which is between H and T?" because at that granularity, the description of the scene would assume that there is nothing between H and T. The study of granular knowledge representation thus tries to express how the same phenomenon can, in some sense, be consistently expressed in different manners under different granularities. This is achieved through operators which, for a situation expressed under a particular granularity, can predict how it is perceivable under another granularity.

Granularity can be applied to the fusion of knowledge provided by sources of different resolution (for instance, agents - human or computers - communicating about the same situation) and to the structuring of reasoning by drawing inference at the right level of resolution (in the example of figure 1, the granularity (a) is informative enough for deciding that the truck driving wheel is on the left of the house- from the standpoint of the observer).

On one hand, in [Hobbs 1985], granularity is expressed in an abstract way (i.e. not connected to time) between two, more or less detailed, logical theories. On the other hand, the physical time-space and its representation have been well­ studied because many applications require them. A very popular way to deal with time [Allen 1983] and space [Egenhofer& 1992; Randell& 1992] is the representation of relationships between areas of these spaces. [Montanari& 1992; Ciapessoni& 1993] introduced operators for quantitative time granularity which share a common ground with those of [Euzenat 1993].

The paper first recalls some basics about time representation (§2). This section can be skipped by those who already know the subject. Then, the usual interpretations of time and granularity in this context are introduced. Afterwards, required properties for granularity change operators in the classical time algebra are presented (§3). This part is very important since, once accepted, the remainder is directly deduced. The only set of operators (for instant and interval algebra) satisfying the required properties are thus deduced in §4. The extension of granularity operators towards space representation is then briefly discussed (§5).

The proofs of all the propositions, but the "only" part of the first one, can be found in [Euzenat 1994].

2 . Background

Classical notions about temporal algebras, neighborhood structures and instant-interval conversions are presented here.

2.1. Temporal algebra

There has been considerable work carried out on qualitative time representation. Here are reminded several notions about the algebra of topological and vectorial relationships holding between time entities.

An instant is a durationless temporal entity (also called time point by analogy with a point on a line). It can be numerically represented by a date. Qualitatively representing these instants requires identifying them and putting them in relation. There are three possible mutually exclusive relationships between instants. They are called «before» ( <), «after»(>) and «simultaneously»(=). The set{<,=,>} is called A3.

It is sometimes possible to deduce the relationship between two instants x and z, even if it has not been provided, by propagating the otherwise known relationships. For instance, if x is simultaneous ( { =}) to y which is anterior ( { <}) to z, then x is anterior to z; this is called composition of temporal relations. The composition operator X3 is represented by a composition table (table 2) which indeed indicates that =X3< gives { <}.

A (continuous) period is a temporal entity with duration. It can be thought of as a segment on a straight line. A numerical representation of a period is an interval: a couple of bounds (beginning instant, ending instant) or a beginning instant and a duration. Intervals can be manipulated through a set of 13 mutually exclusive temporal relationships between two intervals (see table 3); this set is called A13.

The composition operator x 13 is represented by a composition table [Allen 1983], similar to the table 2, which allows to deduce, from a set of intervals and constraints between these intervals, the possible relations between any two of these intervals.

2.2. Extensions of notations

Let r be either A13 or A3, v be the logical disjunction and x be the composition operator on r, the following notations are used (in a general manner, <2r ~X> is an algebra of binary relationships). The lack of knowledge concerning the actual position of some temporal entity x with regard to the temporal entity y is expressed by a sub-set p of r which is interpreted as the disjunction of the relations in p:

Thus, x{b m}y signifies that the temporal entity x is anterior to or meets the temporal entity y. The following conventions are used below:

• When a result is valid for both algebras, no distinction is made between the temporal entities concerned. The base sets (A13, A3, and maybe others), as well as the composition x and reciprocity -1 operators are not distinguished;
• The letter p represents a sub-set of the corresponding base set of relations {p~r); the letter «r» represents a relationship.
• p-1 represents the set of relations reciprocal of those contained in p: { r-1; rep}.
• p 1 xp2 represents the distribution of x on v:

2.3. Neighborhood structure

Two qualitative relations between two entities are called conceptual neighbors if they can be transformed into one another through continuous deformation of the entities [Freksa 1992a]. A conceptual neighborhood is a set of relations whose elements constitute a connected sub-graph of the neighborhood graph.

DEFINITION (conceptual neighborhood): A conceptual neighbor relationship is a binary relation N { on a set r of relations such that N{ (q ,r2) iff the continuous transformation of an entity 01 in relationship q with another entity 02 can put them in relation r2 without transition through another relation.

The graph of figure 2a represents the graph of conceptual neighborhood N: between instants (the only continuous deformation is translation). The graph of Figure 2b represents the conceptual neighborhood N1~ for the deformation corresponding to the move of an extremity of an interval (more generally, the deformation corresponds to moving a limit). Throughout the paper, the only considered transformation A is the continuous move of a limit (called A-neighborhood in [Freksa 1992a]). The influence of this choice is acknowledged when it matters.

2.4. Conversion from interval to instant formalisms

Relationships between intervals can be expressed in function of the relationships between their bounding instants (see table 4): any relationship between x=<x- x+> and y=<y­ y+> is expressed by a quadruple (q , r2, r3, r4) of relationships between the extremities defined as so:

considering that x-<x+ and y·<y+, each possible relationship between the bounding instants are expressible with such a quadruple (see table 4). The symbol =>is used such that =>x is the expression of an interval as a couple of extremities and => r a relationship between intervals expressed as a quadruple. => is extended towards sets of relations such that =>p is a set of quadruples. Thus:

Since any formula representing relationship between four instants x-, x+, y- and y+ satisfying the properties of intervals (x-<x+ and y <y+) can be expressed under that form, the inverse operation ¢::: is defined. It converts such an expression between bounding instants of two intervals into a set of relations expressing the disjunction of relations holding between the intervals. Of course, both operators ( ¢::: and =>) are inverse.

3 . Requirements for granularity change operators

Operators for transforming the representation of a temporal situation from one granularity to another can be defined so that the resulting representation is compatible with what can be observed under that granularity. The requirements for building such operators are considered here. The first section concerns what happens to classical models of time and to temporal entities when they are seen through granularity. The second one provides a set of properties that any system of granularity conversion operators should enjoy. These properties are expressed in a sufficiently abstract way for being meaningful for instants and periods, time and space.

3.1. Granularity change operators

Time is usually represented under a particular granularity. Thus, the time representation system presented so far is an adequate representation for time under any granularity (as far as only qualitative properties are considered). For instance, the three situations of figure 1 can be expressed in the same formalism with objects and qualitative relations between them. Provided that only the positions of the objects along the horizontal line are considered, the three elements (T, B and H) are related to each other in the way of figure 1c by T { m} B (the truck meets its bumper) and B { b} H (the bumper is before the house).

The relationship between two representations of the same reality under two different granularities has to be explicited. As a matter of fact, the situations of figure 1 cannot be merged into one consistent situation: figures 1b and c together are inconsistent since, in (b), B{m}H and, in (c), B{b}H which, when put together, gives B{}H. First, the reasons for these problems are examined before providing a set of properties that granularity change operators must satisfy.

Time is usually interpreted as a straight line, instants as points and intervals as segments. Under a numerical light, granularity can be defined as scaling plus filtering what is relevant and what is not (a discretization). However, granularity is a special filter since, as the name indicates, it filters on size. For the time concern, the granularity of a system can be defined as the duration of the smallest relevant event (relevance being defined independently beforehand). But what happens to non relevant events? There are two solutions:

• they can vanish;
• they can remain with size 0, i.e. as instants.

In both cases, these solutions share additional consequences (for symbolic representations): if, under a coarse granularity, one observes that some event is connected to another this can be wrong under a finer granularity since a non relevant laps of time could be relevant here. In another way, when communicating the same observation, it must be cared that the short laps of time may be non relevant (and thus that the relationship between the event can be disconnected). This is what happened for the relationship between B and H, which is { b}, in Figure 1 c, and becomes { m}, in 1 b.

In order to account for this situation, which appears to be regular, a downward (resp. upward) operator is needed which, from a relationship observed under some particular granularity, is able to provide a set of relationships at a finer (resp. coarser) granularity which represents what can be perceived under that last granularity. The purpose here, is not to design granularity conversion operators which can make events vanish or turn into instants (see [Euzenat 1993]) but rather operators which can account for the possibility of having, under a finer granularity, new space between two entities, and, vice-versa, that a space can become non relevant under a coarser granularity. These operators are called upward and downward granularity conversion operators and noted by the infix g jg' and g' .!g operators (where g and g' are granularities such that g is finer- more precise - than g', i.e. that the size of relevant events is smallest in g than in g'). The following g~g· operator will be used for any of them when the property holds for both (then there is no constraint upon g and g'). So, unless stated otherwise, each formula below is universaly quantified on the gs, and constrains g~g' (resp. g~g') whenever g jg' (resp. g' .!g) is used. As usual, the notation g~g· introduced for the conversion of a single relationship is extended towards sets:

3.2. Properties for granularity change operators

Anyone can think about a particular set of such operators by imagining the effects of coarseness. But here are provided a set of properties which should be satisfied by any system of granularity conversion operators. In fact, the set of properties is very small. Next section shows that they are sufficient for restricting the number of operators to only one (plus the expected operators corresponding to identity and conversion to everything).

Self-conservation

Self-conservation states that whatever be the conversion, a relationship must belong to its own conversion. It is quite a sensible and minimal property: the knowledge about the relationship can be less precise but it must have a chance to be correct.

Neighborhood compatibility

A property considered formerly is the order preservation property [Hobbs 1985] which states (a part of this):

However, this property has the shortcoming of being vectorial rather than purely topological. Its topological generalization, is reciprocal avoidance:

Reciprocal avoidance, is over-generalized and causes problems with auto-reciprocal relationships (i.e. such that r=r-1). The neighborhood compatibility, while not expressed in [Euzenat 1993] has been taken into account informally: it constrains the conversion of a relation to form a conceptual neighborhood (and hence the conversion of a conceptual neighborhood to form a conceptual neighborhood).

This property has already been reported by Christian Freksa [1992a] who considers that a set of relationships must be a conceptual neighborhood for pretending being a coarse representation of the actual relationship. (2) is weaker than the two former proposals because it does not forbid the opposite to be part of the conversion, but, in such a case, it constrains whatever be in between the opposite to be in the conversion too. Neighborhood compatibility seems to be the right property, partly because, instead of the former ones, it does not forbid a very coarse grain under which any relationship is converted in the whole set of relations. It also seems natural because granularity can hardly be imagined as discontinuous (at least in continuous spaces).

Conversion-reciprocity distributivity

An obvious property for conversion is symmetry. It is clear that the relationships between two temporal occurrences are symmetric and thus granularity conversion must respect this.

Inverse compatibility

Inverse compatibility states that the conversion operators are consistent with each other, i.e. that, if the relationship between two occurrences can be seen as another relationship under some granularity, then the inverse operation from the latter to the former can be achieved through the inverse operator.

For instance, if someone in situation (b) of figure 1 is able to imagine that, under a finer granularity (say situation c), there is some space between the bumper and the house, then (s)he must be whiling to accept that if (s)he were in situation (c), (s)he could imagine that there is no space between them under a coarser granularity (as in situation b).

Cumulated transitivity

A property which is usually considered first is the full transitivity:

This property is too strong; it would for instance imply that:

Of course, it cannot be achieved because this would mean that there is no loss of information through granularity change: this is obviously false. If it were true anyway, there would be no need for granularity operators: everything would be the same under each granularity. The cumulated transitivity can be expected:

However, in a purely qualitative calculus, the amounts of granularity (g) are not relevant and this property becomes a property of idempotency of operators:

At first sight, it could be clever to have non idempotent operators which are less and less precise with granularity change. However, if this applies very well to quantitative data, it does not apply for qualitative: the qualitative conversion applies equally for a large granularity conversion and for a small one which is ten times less. If there were no idem potency, converting a relationship directly would give a different result than doing it through ten successive conversions.

Representation independence

Representation independence states that the conversion must not be dependent upon the representation of the temporal entity (as an interval or as a set of bounding instants). Again, this property must be required:

Note that since <= requires that the relationship between bounding instants allows the result to be an interval, there could be some restrictions on the results (however, these restrictions correspond exactly to the vanishing of an interval that which is out of scope here).

4 . The granular system for time relations

Once these six properties have been defined, one can start generating candidate upward and downward conversion operators. However, the requirements are so precise that they leave no place for choice. It is shown below, by starting with the instant algebra, that there is only one possible couple of operators. Afterwards, this easily transfers to interval algebra.

4.1. Conversion operators for the instant algebra

The 64(=23.23) a priori possible operators for converting < and = can be easily reduced to six: the constraint (1) restricts the conversion of< to be { <}, { <=}, { <>} or { <=>} and that of { =} to be in { =}, { <=}, { =>} or { <=>}. The constraint (2) suppresses the possibility for < to become { <>}. The constraint (3) has been used in a peculiar but correct way for eliminating the { <=} (resp. { =>}) solutions for =. As a matter of fact, this would cause the conversion of =-1 to be { =>} (resp. { <=} ), but =-1 is = and thus its conversion should be that of=.

There are still six possible conversion operators left (ld, a, ~. y, o and Nl). Since the above table does not consider whether the operators are for downward or upward conversion, this leaves, a priori, 36 upward-downward couples. But the use of property (4) - the putative operators must be compatible with their inverse operator (and vice-versa)- reduces them to 5: ld-Id, a-~. y-y, o-o andNI-NI.

The solution Id-Id cannot be considered as granularity since it does not provide any change in the representation. The solution NI-NI is such that it is useless. The o-o pair has the major flaw of not being idempotent (i.e. o-&o): as a matter of fact, the composition of o with itself is NI, this is not a good qualitative granularity converter (this violates property 5). There are two candidates left: the y-y has no general flaw, it seems just odd to have an auto-inverse operator (i .e. which is its own inverse) since upward and downward conversion are perceived as asymmetric; it could be a candidate for upward conversion (it preserves the equality of equals and weakens the assertions of difference) but it does not fit intuition as a downward conversion operator (for the same reasons) . Moreover, y does not respect vectorial properties such as order-preservation (y is just ~ plus the non distinction between < and > ). Thus the a-~ pair is chosen as downward/upward operators. The main argument in favor of a-~ is that they fit intuition very well. For instance, if the example of figure 1 is modeled through bounding instants (x- for the beginning and x+ for the end) of intervals T+, s-, s+ and H-, it is represented in (c) by T+=B- (the truck ends where the bumper begins), B-<B+ (the begining of the bumper is before its end), B+<H- (the end of the bumper is before the begining of the house) in (b) by s+=w (the bumper ends where the house begins) and in (a) by s-=s+ (the bumper does not exist anymore). This is possible by converting with the couple a-~ which allows to convert B+<H- into s+=H- (= E ~<)and s-=s+ into B-<B+ ( < E a=), but not with the use of y as a downward operator. Thus the following result is established:

PROPOSITION: The table 6 defines the only possible non auto-inverse upward/downward operators for A3.

Table 6. Upward and downward granularity conversions between instants .

The operators of table 6 also satisfy the properties of granularity operators.

PROPOSITION: The upward/downward operators for A3 of table 6 satisfy the properties (1) through (5).

4.2. Conversion operators for the interval algebra

By constraint (6) the only possible operators for A13 are now given. They enjoy the same properties as the operators for A3.

PROPOSITION: The upward/downward operators for A13 of table 7 are the only one to satisfy the property (6) with regard to the operators of A3 of table 6.

PROPOSITION: The upward/downward operators for A13 of table 7 satisfy the properties (1) through (5).

The reader is invited to check on the example of figure 1, that what has been said about instant operators is still valid. The upward operator does not satisfy the condition (2) forBneighborhood (violated by d, sand f) and C-neighborhood (o, s and f). This result holds since the corresponding neighborhoods are not based upon independent limit translations while this independence has been used for translating the results from A3 to A13.

6. Extension to spatial relations

Qualitative time representation has inspired several extensions towards qualitative spatial representation [Hernandez 1994] . However, there is no universally acknowledged representation. In [Euzenat 1994], two of them, which can be considered as the simplest (those of [Giisgen 1989] and [Egenhofer& 1992; Randell& 1992]), have been provided with granularity operators by applying transformations to the temporal operators.

These two schemes are either too rigid or too loose. The ideal solution would be to treat independently concepts such as containment (topology) or orientation (vectorial spaces). There are various ways to deal with orientation: global reference frame [Giisgen 1989], global sectorial reference frame [Hernandez 1994] and local (to each object) sectorial reference frame [Freksa 1992b]. Granularity has been introduced in the former while the two latter introduce a new problem: the expression of orientation is also subject to granularity. However, the formal treatment presented above does only consider the structure subject to granularity. Such a structure <r,-l,x,N> is made of:

• a set of relations r;
• a converse operator (r is closed by -1 );
• a composition operation x;
• a neighborhood relation N.

It seems that such a structure can be given to orientation representation as introduced in [Freksa 1992b; Hernandez 1994]. The existence and unicity of granularity operators, seem intuitively correct, but remain to be proved.

7 . Related works

Jerry Hobbs introduced the concept of granularity from the non distinguishability of particular terms with regard to a given set of predicates (these terms can be substituted in the range of any of the predicates without changing their validity). Here, the granularity has been given a priori, in the structure of time and the scaling notion, while Hobbs defines a granularity with regard to relevant predicates. To our knowledge there is no other proposal for integrating granularity into qualitative time representation.

There has been tremendous work on granularity in metric spaces. One of the more elaborate model is that of [Montanari& 1992; Ciapessoni& 1993]. It proposes a quantitative temporal granularity based on a hierarchy of granularities strictly constrained (to be convertible, divisible, etc.) which offers upward and downward conversion operators for instants and intervals (instead of their relationships). [Euzenat 1993] offers a more general (i.e. less constrained) framework for quantitative relationships and thus achieves weaker properties. Hence, the properties obtained here for qualitative representation are compatible with the quantitative representation of [Montanari& 1992; Ciapessoni& 1993].

8. Conclusion

In order to understand the relationships between several granularities, a set of requirements have been established for conversion operators. The only possible operators filling these requirements have been defined. Moreover other properties of the operators have been established (preservation of the relationship between points and interval) and other operators for other kind of spaces can be derived for the actual operators for time. These operators can be used for combining information coming from different sources and overcoming their contradictory appearance. [Euzenat 1993] provides more results about the relationship between granularity and inference which can be used for implementing reasoning algorithms.

Acknowledgements

Many thanks to Hany Tolba who carefully commented a longer version of this paper.