Representation and Processing of Spatial Expressions

Patrick Olivier, Klaus-Peter Gapp

• Publisher: Psychology Press
• Year: 1998
• eBook ISBN: 9781135690281
• Edition: 1
• Topic: Psychology
• Subtopic: Cognitive Psychology & Cognition
• Index: Psychology

Coping with spatial expressions in a plausible manner is a crucial problem in a number of research fields, specifically cognitive science, artificial intelligence, psychology, and linguistics. This volume contains a set of theoretical analyses as well as accounts of applications which deal with the problems of representing and processing spatial expressions. These include dialogue understanding using mental images; interfaces to CAD and multi-media systems, such as natural language querying of photographic databases; speech-driven design and assembly; machine translation systems; spatial queries for Geographic Information Systems; and systems which generate spatial descriptions on the basis of maps, cognitive maps, or other spatial representations, such as intelligent vehicle navigation systems. Though there have been many different approaches to the representation and processing of spatial expressions, most existing computational characterizations have so far been restricted to particularly narrow problem domains, usually specific spatial contexts determined by overall system goals. To date, artificial intelligence research in this field has rarely taken advantage of language and spatial cognition studies carried out by the cognitive science community. One of the fundamental aims of this book is to bring together research from both disciplines in the belief that artificial intelligence has much to gain from an appreciation of cognitive theories.

1
Neat Versus Scruffy: A Review of Computational Models for Spatial Expressions

Amitabha Mukerjee
Indian Institute of Technology Kanpur

This chapter reviews the computational modalities for representing spatial expressions. The focus is on computational or synthetic models, as opposed to cognitive or linguistic aspects. A number of formalisms based on qualitative paradigms such as topology seek to discretize space into regions based on alignment or tangency. This approach may be termed as “neat.” Yet a large class of spatial expressions (e.g., “near,” “move away from”) do not involve alignments, and even some that do (e.g., “in front of”) have gradations. These gradations in a continuum are clearly less “neat”; we may view these as “scruffy”; there appears to be a growing trend toward the scruffy in recent times. The distinctions between the different models reviewed are demonstrated using the canonical example of “the chair in front of the desk.”

1. INTRODUCTION

The philosopher Wittgenstein, when young (Tractatus, 1921), claimed to have provided a “final solution” to the problem of logic and language, based on a set of primitives that describe the boundaries of what can be expressed. In essence, this approach claims that thought is grounded on a set of distinct symbols, a “neat” discretization. In later years (Philosophical Investigations, 1953) he himself rejected this view, insisting that language can properly be considered only with respect to its use in specific behavioral contexts (“scruff”). Nuallain and Smith (1995) compared this famous transformation from neat to scruff to the change of paradigm within the AI (artificial intelligence) community from a primitive-based model of semantics to a more context sensitive one. The contradiction between the neat and the scruffy holds probably over the entire domain of artificial intelligence, and certainly to the topic of this survey—the computational modeling of spatial expressions.

Representing space has a rich history in the physical sciences, where many representations were developed for encoding orientations, points, vectors, rigid body motions, and so forth. These representations are, as a class, continuous and serve to locate objects in a quantitative framework—for example, in a multidimensional space of coordinates. Any assignment of values to the coordinates results in a unique and precise location for the entity.

Spatial expressions, on the other hand, operate on a loose partitioning of the domain, a discretization into regions such as “in front/back” or “near/far,” where the location, and even the partitioning itself, is specified with a large degree of ambiguity. The task of finding suitable representations for this less precise description has turned out to be considerably more difficult than was initially realized. The emphasis has been on creating discretizations that matched the linguistic partitions. Unfortunately, each discretization that was created, for example, the many versions of the “ON” primitive in the blocks world, attempted to enforce the loose partitioning of a spatial expression onto the straitjacket of strict, numerical distinctions. Representations proliferated, more or less on an ad hoc basis. With the emergence of qualitative reasoning, the partitioning was done more systematically, mapping the complete set of distinctions deriving from a given set of landmarks, and treating all zones between the landmarks as indistinguishable.

1.1. The Evolution of the “Neat”

Very early AI created discretizations on an ad hoc basis, for example, by defining cells that were sensitive to the choice of origin and frame size. Discretizations mapped the continuous world into a set of discrete symbols, and the partitions were defined by the programmer based on pragmatic considerations of what appeared to suit the theory, as opposed to any systematic basis; such models may be called gerrymandered discretizations and remind one of the classification of the heavens in the work of Ptolemy, say. An example of this is the proliferation of interpretations that ON(A, B) had in the early Blocks World models (see Fig. 1.1).

More systematic discretizations were achieved by defining the complete set of partitioning based on landmarks. For example, in one-dimensional space Allen (1983) used a set of two landmarks (endpoints) in the

FIG. 1.1. Where does ON(A, B) end? This was a popular predicate in early AI and had many interpretations, depending on the flexibility of the programming. Some versions rejected overshoot (c) and most did not admit rotation (d). Partitionings were chosen to be convenient to the programmer—a gerrymandering approach common to the early stages of all sciences, forced by the belief that “neat” partitions are the basis for all meaning.

reference object (RO); the two endpoints of the located object (LO) were described completely in terms of these as a set of 13 possible orderings or arrangements (see Fig. 1.10, discussed in more detail later). Such thinking extends to spatial situations with a one-dimensional envisionment, as in the road scene of Fig. 1.2. Similarly, in higher dimensions, all possible visibility orderings based on a set of points can be modeled as an arrangement of visible points—this results in a partitioning of the plane into a set of qualitative zones: lines (two or more points aligned on same line), points (two or more lines intersecting), and regions (no two points aligned) (Kuipers, 1977; Schlieder, 1994). For example, in the four-landmark case (Fig. 1.2b), there are 23 lines, 7 points, and 18 regions based on visibility orderings on the landmarks ABCD. The partitioning in these models was based on the alignment between some fundamental entities,

FIG. 1.2. Alignment-based discretizations, (a) Position: “The post office is past the Safeway store” as a linear interval model, (b) Orientation: A set of points partitions the domain into regions based on visibility arrangements. Multipoint alignments result in lower dimensional entities like lines and points.

such as two points in the interval model, or two orientations in the visibility-ordering model.

Qualitative reasoning models that create discretizations based on alignment now have a varied set of representational structures, many of them involving considerations of topology, focusing on connectivity rather than position (Cohn, Randell, Cui, & Bennett, 1993; Egenhofer & Franzosa, 1991). Expressions involving tangency, or transition from contact to no-contact situations, can be expressed in terms of such predicates. Other models define local frames on the objects based on intrinsic, extrinsic, or deictic (or other) considerations, which can be used to combine position and orientation (Forbus, Nielsen, & Faltings, 1991; Hernández, 1994; Mukerjee & Joe, 1990).

Within the class of alignment-based models, the systematic treatment of all possible relations resulted in much better handling of spatial expressions, especially in the zones near contact. For example, the ON relation in the orthogonal blocks world can be handled elegantly by considering a multidimensional projection model, instead of subjectively chosen predicates like “not-touches.”

To simplify things tremendously, qualitative models may be thought of as multidimensional orderings of point-sets; these are in general very expressive in the region near contact or alignment—here slight changes in spatial position or orientation result in changes of order, and generate topologically relevant information. However, qualitative models are not very meaningful for noncontact or nonalignment positions, such as in the spatial prepositions like “near” or “between” or in expressions such as “moved farther away from” or “veer sharply to the left.” These relations involve no changes in the alignments or orderings of the objects, and are changes of measure rather than of quality; consequently they cannot be modeled with purely qualitative formalisms. Experience reveals that many projective spatial prepositions such as “in front of” also have a gradation; for example, in Fig. 1.3, the chair A is more “in front of” the desk than the chair E, say. In a discretized model for the desk, as in the proj...

Table of contents

• Contents
• Preface
• 1 Neat Versus Scruffy: A Review of Computational Models for Spatial Expressions
• 2 On Seeing Spatial Expressions
• 3 Time-Dependent Generation of Minimal Sets of Spatial Descriptions
• 4 A Computational Model for the Interpretation of Static Locative Expressions
• 5 Generating Dynamic Scene Descriptions
• 6 A Three-Dimensional Spatial Model for the Interpretation of Image Data
• 7 Shapes From Natural Language in VerbalImage
• 8 Lexical Allocation in Interlingua-Based Machine Translation of Spatial Expressions
• 9 Schematization
• 10 Toward the Simulation of Spatial Mental Images Using the Voronoï Model
• 11 Generating “Mental Maps” From Route Descriptions
• 12 Integration of Visuospatial and Linguistic Information: Language Comprehension in Real Time and Real Space
• 13 Human Spatial Concepts Reflect Regularities of the Physical World and Human Body
• 14 How Addressees Affect Spatial Perspective Choice in Dialogue
• 15 Spatial Prepositions, Functional Relations, and Lexical Specification
• 16 The Representation of Space and Spatial Language: Challenges for Cognitive Science
• Author Index
• Subject Index
• Contributors