Modeling the Basic Meanings of Path Relations

1 Introduction

Space plays a central role in human cognition, and has therefore been a research focus in different disciplines like (computational) linguistics [Lakoff, 1987], cognitive sci­ ences [Kosslyn, 1994], psychology [Landau and Jackend­ off, 1993], and artificial intelligence [MaaB et al., 1993]. Sophisticated conceptual [Egenhofer, 1991] and compu­ tational models [Gapp, 1994] have been developed that made it possible to compute the appropriateness of spa­ tial relations in specific situations, thereby providing a better understanding of what is meant by certain spatial expressions. These results paved the way for intelligent systems that are able to analyze and generate natural language descriptions of space [Wahlster et al., 1998].

Within the field of spatial relations, so-called topo­ logical (e .g. near or at) and projective relations (like

Anselm Blocher

Collaborative Research Center 378 University of Saarbrucken Postfach 151150 66041 Saarbrucken Germany anselm@cs.uni-sb.de

right-of or above) have been most thoroughly exam­ ined. Both groups are point-to-point relations as they establish a spatial relation between two objects of arbi­ trary shape. (Between is an exception from this rule as it requires at least three objects to be computed correctly[Habel, 1989].) .

A different kind of spatial relations are the so-called path relations (e.g. along, around, or past). Much less attention has been payed to their conceptualization [Kruger and MaaB, 1997] and computation than in the case of point-to-point relations. This may be due to the greater complexity: the problem of computing the most appropriate path relation can only be solved if there is a path which consists at least of a simple line with a starting point and an ending point . As we will show in section 5, topological, projective, and path relations share nevertheless several (geometric) concepts.

In section 2, we present the basic ideas and concepts we will use throughout the paper. Based on an analysis of the linguistic side of the problem (section 3), we pro­ pose a semantic model which is described in section 4. In the following section, we turn to the geometric side, and establish a basic framework for geometric path re­ lations . These two sides are integrated to form a con­ sistent model which then is applied to various examples (section 6). Finally, we summarize our findings and give an outlook on future directions.

2 Key Concepts and Related Work

Following [Herskovits, 1986] we distinguish between the basic meaning of a spatial relation and its instantiation in a concrete situation: An object to be localized (LO) is set in relation to a reference object (RO) . Further­ more, a frame of reference has to be established in order to distinguish different spatial relations. Determining the origin and the orientation of the reference frame de­ pends on a multitude of factors such as the point of view of the observer/ addressee, or the intrinsic orientation of the RO [MaaB, 1993]. The computation of topological and projective relations relies on a frame of reference. It is used to extract the two essential parameters that are needed to evaluate the applicability of point-to-point re­ lations: the distance of the 10 from the RO (topological relations), and the angle disparity from a prototypical direction (projective relations).

[Gapp, 1997] proposed a model for spatial relations that is based on a three level referential semantics. On the lowest level, only purely visual information is avail­ able. This information is abstracted on the semantic level to a geometrical representation which the referen­ tial semantic itself relies on. Idealized meanings of spa­ tial relations are compared to the actual situation taking into account contextual factors that are modeled on the conceptual layer. A degree of applicability (DA) is com­ puted that rates how well a relation corresponds to the prototypical meaning, on a scale from 'zero' (not applica­ ble) to 'one' (fully applicable). For a detailed description of the factors and algorithms used to determine the DA of point-to-point relations, refer to [Gapp, 1997].

Path relations differ from their topogical and projec­ tive counterparts in two ways. On one side, the 10 is expected to be path-like: either its shape has to be path­ like, or it can be abstracted to a path-like shape. In some cases, this also holds for the RO. (In the computation of the applicability of point-to-point relations, the shape of the 10 is of lesser importance.) On the other side, the computation of path relations cannot be reduced to a simple two point problem. Figure 1 illustrates this fact: Trajectory (a) is certainly a better match for are­ lation along1 (describing a path that follows the form of the RO) than is trajectory (b). But there is no single point on either trajectory that can be used to determine the applicability of this relation. (While one may argue about the meaning of "along", along1 might actually capture a meaning facet.-)

3 Analysis of German Path Prepositions

From a computational perspective, one of the main prob­ lems in understanding natural language is its inher­ ent ambiguity. This is also true for path prepositions: The German path preposition 1 "zu" (roughly "to", "to­ wards"), for example , is used to describe trajectories that lead towards the reference object. The description "der Weg zu dem Park" ("the way to the park") can mean different things. It is not obvious where the trajectory starts, nor where it ends: Does it end outside the park, just at the border, or inside? The verbaliza­ tion process is affected by ambiguity, too: To describe a path that starts within the park and leads outside of it , one could, for example, use "a us" ( approx. "out of") or "von" ( approx. "from").

1 We use the term '(path) preposition' although, from a strictly linguistic perspective, not all of them are prepositions per se.

Table 1lists some of the most commonly used German path prepositions. We tried to express the basic mean­ ings of the main uses in natural language and- at a finer level of detail - in a more formal syntax. It should be stated that the table does not contain a complete de­ scription of all possible meanings of path prepositions but only meaning facets. The formal syntax is based on a subset of Egenhofer's semantics for topological re­ lations [Egenhofer, 1991] . "I" stands for containment of the 10 within the RO (inside), "M" for contact of the boundaries of 10 and RO (meet) , and "D" for the disjointness of them (disjoint) . So, a formula like

is to be read as

"The corresponding relation describes a path that starts either within the border, or on the border, or outside of the RO. On its way, the contact relation becomes true at least once, and it ends outside of the RO."

We use bold style for the main usage, plain style for possible uses, and italics for unlikely (but still possible) uses of a relation. An asterix (*) above the arrow indi­ cates that no special relation has to be fulfilled during transition. Although the table was created with Ger­ man prepositions in mind, preliminary research on the corresponding English prepositions indicates that a ba­ sic set of concepts exists across different languages. Ex­ ploratory studies in French and Japanese support this hypothesis, and justify the search for a language inde­ pendent conceptual model.

4 Basic Semantic Concepts

A first look at the meaning column in Tab. 1 reveals that the majority of the prepositions describes an approach towards an object. Only a few words are available to ex­ press an increase of distance (e.g. "von", "a us") . (This is not surprising since one usually follows a path with the target in mind.) Furthermore, there is a concept of angular movement (such as in "urn" and "entlang") . So, the two essential parameters (distance and angle) needed for the evaluation of point-to-point relations play an im­ portant role in the conceptualization of path relations, too.

A second observation is that the meaning component of some path prepositions (e.g. "in") contains a simple point-to-point relation. This relation is applied to either one of the endpoints of the trajectory (in the case of "in": to the ending point) , or to the entire trajectory (e.g. "past") . If we take out that element, we are left with a simple path relation that is only related to the path but not to a single point.

Based on these observations, we can establish a se­ mantics for path relations which relies on simple path relations. We propose the following five simple path re­ lations as building blocks for more complex ones. They can be combined with each other, and/or with point-to­ point relations to form higher order path relations .

• decrease-distance: the ending point of the trajec­ tory is closer to the RO than the starting point .
• increase-distance: the starting point of the tra­ jectory is closer to the RO than the ending point .
• maintain-distance: the distance of every point on the trajectory from the RO is the same.
• change-angle: the starting and the ending point form an angle with the RO.
• maintain-angle: the starting and the ending point show no angular disparity in relation to the RO.

Since the direction of the angular disparity cannot be expressed easily using path prepositions (at least as far as German, French, and English are concerned), it makes sense to have just one relation expressing undi­ rected change. This is not true in the case of distance, where we consequently differentiate approach and an in­ crease of distance.

5 Geometric path relations

As far as the geometric side of the computation of path relations is concerned, we first want to define clearly the object to be accomplished:

Given an 10 in path-like shape (or abstraction) represented by a trajectory, find the path rela­ tion which describes best the relation of the 10 to an arbitrary reference object (and compute a corresponding degree of applicability).

A trajectory is defined by n points (pt ... p; ... pN)· The endpoints Pt and PN denoting beginning and end of the trajectory are defined either by an explicit direction or by the order of the computational analysis itself. This description of the trajectory is provided by the conceptual layer mentioned in section 2. Its construction (e.g. by choosing a specific idealization or by indicating the starting point) is beyond the scope of this paper.

We rely on the following assumptions:

1. The LO is represented as a trajectory. This corresponds to the fact that a path preposition can hardly be applied to an object which is not path-like shaped at all (e.g. "the ball along the wall").
2. We want to describe the trajectory as a whole. Though it might be preferable to subdi­ vide the trajectory into parts (which analyzed one by one could possibly be associated more evidently with several path relations), the entire trajectory has to be analyzed in order to detect possible sub­ divisions. Therefore, it is appropriate to generate first an overall description using a single relation .

1. We want to describe the course of a trajec­ tory. In this case, point-to-point relations are not sufficient and path relations are needed.
2. We want to extend the computational model of static relations to path relations. Accord­ ingly, the DAs have to be comparable. This will be ensured by using the same essential parameters -distance and angle -, identically calculated frame of reference, reference points (the nearest points be­ tween LO and RO), and intermediate results of the computation of point-to-point relations.
3. We focus on path relations that correspond to path prepositions. As the geometric model is linked to linguistic concepts via the reference se­ mantics, path prepositions have to be kept in mind while exploring geometric path relations.

5.1 Two-point-trajectories

The most basic trajectory consists of exactly two dis­ tinct points and is called two-point-trajectory. On one hand, more complex trajectories - n-point-trajectories - can easily be constructed by concatenating n-1 two­ point-trajectories. On the other, even the most com­ plex trajectory can be split into a unique series of two­ point-trajectories. This implies that the first step to analyze path relations is to study the relations between two-point-trajectories and the reference object.

Any trajectory can be localized exactly using the con­ cepts of distance and angle. This corresponds to assump­ tion four and to the observations made in section 4. In order to describe the course of a two-point-trajectory as a whole (see asumption three) using distance and angle, the changes of these essential parameters between p1 and p2 have to be analyzed: Distance and/ or angle can ei­ ther be increased, maintained or decreased as depicted in Fig. 2a. This distinction - similar to the one made in the previous section - enables us to define basic path relations (see Tab. 2; cw: clockwise, ccw: counter-cw) .

Figure 2b shows that we can even sort trajectories according to the degree of being an optimal representant of a path relation: tjl is closer to the ideal meaning of approach than is tj2. Furthermore, we can compare different relations: The quality of the relation depart represented by tj3 lies in between the qualities of tjl and tj2 . To describe the differences between tj4 to tj6 other factors than course, e.g. the distance to the RO, have to be taken into account. Nevertheless, these trajectories are all optimal representants of the relation approach since we assumed that path relations depend on their course only. Consequently, the degree of applicability can be expressed as the difference in the distances (fl. d) of p1 and P2 with respect to the RO, divided by the length of the trajectory. As the computation of each of these distances corresponds to the one used for point-to­ point relations, the result ing DAs are comparable. Table 3 illustrates the computation of the DAs for the basic path relations defined above.

5.2 N-point-trajectories

Actually, in most cases trajectories representing abstrac­ tions of real world objects consist of more than two points. In order to extend the use of basic path relations to n-point-trajectories it suffices to build the weighted average over all parts of the trajectory.

However, as shown in Fig. 2c, there are differences in the course of n-point-trajectories we are still not able to describe using the basic path relations defined above: A distinction of the curvature of n-point-trajectories has to be made. Three types can be distinguished:

• tjP first approaches the RO and then departs: this curvature corresponds to the path relation past.
• tjT first departs from the RO and then approaches it again: this curvature corresponds to trip. 2
• tjF keeps the distance over the whole course, no curvature exists: this equals follow.

There are two possible ways to cope with curvatures: either by finding a suitable segmentation (which con­ tradicts assumption two), or by analyzing the essential parameter distance more thoroughly. A curvature can only exist if a trajectory has at least three points: In this case, the difference of t:.dRo (P2, p!) and t:.dRo (p3, p2) is either positive (trip) or negative (past). The degree of the curvature is measured as follows:

A n-point-trajectory's curvature can easily be ex­ pressed by the weighted curvatures of the inner points.

6 Results

Table 4 integrates the semantic aspects of German path prepositions developed in section 3 and path relations constructed according to section 5. They may be com­ bined with each other, or with point-to-point relations. (Path relations refer to the entire trajectory while point­ to-point relations refer to the trajectory point(s) men­ tioned explicitely in brackets.)

However, there is no 1: 1-correspondence between a given preposition and a specific realization. Since a sin­ gle preposition can be used to describe different situ­ ations, and a single situation can be described using different prepositions, there is a n:m-relation between language and geometry. To overcome the vagueness of language, contextual factors can be taken into account. Additionally, vagueness (precision) can be modeled ex­ plicitly as proposed in [Kray, 1998].

2 There seems to be no corresponding path preposition nei­ ther in German nor in English.

Table 5 shows exemplary results for the trajectories in Fig. 1 and 3. As expected, the DAs for 1(a) and 1(b) are significantly different. The examples in Fig. 3 also yield reasonable results.

7 Conclusion

The connection between visual and verbal space is an im­ portant issue in the development of natural language sys­ tems that are concerned with spatial information. In this paper, we presented an analysis of German path prepo­ sitions, and used the results to deduce a basic semantics for path relations. Extending the model for spatial re­ lations, we showed how those findings can be integrated with geometric path relations.

Currently, our results are being integrated in a lo­ calization agent [Wahlster et al., 1998] and in a mobile tourist [Deep Map, 1999] guide. In addition, their poten­ tial for anytime behavior (interruptability with increas­ ing quality over time) [Dean and Boddy, 1988] is being investigated. In the future, we plan to develop segmenta­ tion algorithms that are based on the methods proposed in this paper. A subdivision of a complex trajectory may improve the quality of path descriptions due to the finer granularity. Furthermore, we intend to evaluate the meaning facets of path prepositions empirically.

Acknowledgments: The research presented in this paper was funded by the Collaborative Research Center 378 at the University of Saarbrucken, the German Re­ search Center for Artificial Intelligence GmbH (DFKI), and the European Media Laboratory GmbH (EML) at Heidelberg, Germany.