Qualitative Representation of Spatial Knowledge
| Type of publication: | Book |
| Citation: | hernandez_94_qualitative |
| Series: | Lecture Notes in Artificial Intelligence |
| Volume: | 804 |
| Year: | 1994 |
| Publisher: | Springer Verlag |
| Userfields: | content={1 Introduction 1.1 The relevance of spatial knowledge 1.2 The problem and why it should be solved 1.3 The kind of solution sought 1.4 Overview 2 Qualitativeness 2.1 Qualitative vs. quantitative knowledge 2.2 Properties of qualitative representations 2.3 Structured relational domains 3 A cognitive perspective on knowledge representation 3.1 Issues in knowledge representation 3.2 Knowledge representation model 3.3 Modalities of represenation 3.3.1 The declarative/procedural distinction 3.3.2 The propositional/analogical distinction 3.3.3 The qualitative/quantitative distinction 3.4 Summary 4 Qualitative represenation of positions in 2-D 4.1 2-D scenes 4.1.1 Characteristics 4.1.2 Relevant dimensions 4.2 Arrangement 4.3 Topological relations 4.3.1 Systematic derivation of topological relations 4.3.2 Properties of the derived set 4.3.3 Structure of the topological domain 4.4 Orienation 4.4.1 Systematic derivation of orientation relations 4.4.2 Structure of the orientation domain 4.4.3 Reference frames 4.4.4 Objects with extension 4.5 Examples 4.6 Summary 5 Reasoning with qualitative representation 5.1 Transforming between frames of reference 5.2 Composition of spatial relations 5.2.1 Composition of binary topological relations 5.2.2 Composition of orientation relations 5.2.3 Composition of topological/orientation pairs 5.2.4 Structure and table lookup 5.2.5 The effect of multiple constraints 5.3 Constraint reasoning 5.3.1 Constraint satisfaction problem 5.3.2 Consistency improvement 5.3.3 Heuristics 5.4 Exploiting the structure of space 5.4.1 Combined structure of topological and orientation relations 5.4.2 Abstract maps 5.4.3 Propagation heuristics 5.4.4 Constraint relaxation 5.4.5 Coarse reasoning and hierachical organization 5.5 Summary 6 Applications 6.1 Building cognitive maps 6.2 Visualization 7 Extensions of the basic model 7.1 3-D space 7.2 Size 7.3 Distance 7.4 Shape 8 Relevant related work 8.1 Other qualitative approaches to the representation of space 8.1.1 Interval algebras 8.1.2 Cartesian tuples of relations 8.1.3 Other relational approaches 8.2 Other approaches to the representation 8.2.1 Representation modalities 8.2.2 Cognitive maps and route finding 8.2.3 Linguistically motivated research 8.2.4 Relational algebras 9 Conclusion 9.1 Main contributions 9.2 Future research issues 9.3 Summary A Composition tables for various special cases}, date-added={2012-09-03 15:47:30 +0200}, date-modified={2012-09-03 15:47:30 +0200}, notes={Revised version of H.'s dissertation (1992).}, project={fremdliteratur}, registry={C7 U13}, state={read; not everything understood; contents, section 1.4, chapter 9 and bibliography copied; summarized}, summary={{1 Introduction 1.1 The relevance of spatial knowledge Four kinds of spaces are enlisted (Freksa / Habel 1990b): mathematical space, physical space, psychological space and metaphorical space. Also the concept of cognitive space is introduced. Examples of where spatial knowledge is required in AI are given. 1.2 The problem and why it should be solved Existing approaches are based on the following assumtions: the more details the better and numerical coordinate representation is the most appropriate. Drawbacks of quantitative approaches are: complexity, falsifying effects, partial and uncertain information, missing adequacy and transformational \"impedance\". These are explained shortly including examples. 1.3 The kind of solution sought Properties of the proposed model of representation are listed: cognitive adequacy: qualitativeness of spatial knowledge, its hierachical organization, reasoning at different granularity levels it uses relative representation based on locative (?) relations among objects and between objects and distinguished reference structures (landmarks, boundaries) other properties: under-determined; if information is coarse, the reasoning process is less involved; a scene is represented as a net of mutually constraining locative relations 2 Qualitativeness 2.1 Qualitative vs. quantitative knowledge This section defines quality and quantity. 2.2 Properties of qualitative representations Properties of qualitative representations are listed and explained shortly. Among others: under-determination, handling of vague knowledge using coarse granularity levels. 2.3 Structured relational domains The choice of a set of relations structures the domain according to the viewpoint used. Structural properties oh physical space have to be taken care of. 3 A cognitive perspective on knowledge representation 3.1 Issues in knowledge representation Some general issues on knowledge representation are presented. 3.2 Knowledge representation model This section presents the knowledge representation model as proposed by Palmer extended by the concept of the observer (the one that designs or uses the representation) whose role is made explicit. 3.3 Modalities of representation Here qualitative representation is embedded in the context of other modalities of representation. These are: the declarative / procedural distinction the propositional / analogical distinction (implicit vs. explicit, holistic vs. compositional, absolut vs. relative) the qualitative / quantitative distinction 4 Qualitative representation of positions in 2-D This chapter introduces a model for the qualitative representation of positions in 2-D space. 4.1 2-D scenes By projecting 3-D scenes on 2-D space \"uniqueness of positions\" is lost and we get a hierachical organization of space (still objects can overlap). Only convex objects without holes are considered. The size proportions of objects influence the type of positional relation that can hold between them. To determine relative positions three objects are needed: the primary object, the reference object and the point of view ( the primary object is located relativ to the reference object as seen from the point of view ). Two factors determine the relative poitions of objects: relative orientatios and extensions of objects. This yields two classes of spatial relations: topological relations ( orientation is ignored) and orientation relations (extension is ignored). 4.2 Arrangement This section deals with arrangement as the simplest form of qualitative positional information using Schlieder (1990a,b). 4.3 Topological relations Here the topological relations are derived systematically guaranteeing that they are complete and mutually exclusive (Egenhofer / Franzosa 1991). The relations are: disjoint (d), tangent (t), overlaps (o), contains-at-border (c@b), included-at-border (i@b), contains (c), included (i), equal (=) Properties: d, t}, o,={are symmetric; c@b, i@b and c, i are pairwise converses; = and c give information about relative size and shape the neighbouring strucure of topological relations is examined resulting in 3 alternatives. neighboring relations behave similarly (i.e. have similar compositions). groups of neighboring relations can be considered as a single \"coarse\" relation. hierachically organized levels of granularity are defined (contact, no contact..) 4.4 orientation the following sets of orientation relations (at various granularity levels) are derived: 1.for points: level 1: left1, right1, collinear1lr or back1, front1, collinear1fb (these are 2 complementary sets for level 1) level 2: both level 1 sets are merged together and in the case of possibility 2 rotated by 45 degree possibility 1: left-back2, left-front2, right-front2, right-back2 possibility 2: back2, left2, front2, right2 level 3: built in similar manner as at level 2 f3, fr3, b3, l3, r3, lb3, rb3, lf3, rf3 all sets are complete and mutually exclusive. (see retz-schmidt (1988) on the cognitive importance of axes.) some words on the relationship between arrangement and orientation follow. the structure of the orientation domain is examined: - uniform circular neighbouring structure on each level ( called ron - relative orientation node) - coarse relations are not just aggregations of fine distinctions common level used: 16 sectors which is fine enough to express any of the 3 levels considered (hˆgg / schwarzer 1991) some considerations concerning the reference frame follow: -i.e. the orientation that deterines the distinction in which the primary obj. is located relative to the reference obj. - three types: intrinsic, extrinsic, deictiv (all explained shortly) maintained knowledge about relative positions could be stated declaratively like this: prim. obj., [top., orient.], refr. object, refr. frame where refr. frame can be implicit or explicit implicit orientation is used as the canonical reference frame. 2.for objects with extension and shape: size and shape influence the orientations. the area in which a particular orientation is accepted as a valid description is called acceptance area. previous work on how to handle orientation of extended objects: evans (1968) and haar (1976): - relative orientation on the centroids, triangular areas with overlap - good approximation for objects with uniform size and shape or far away from each other - fails for objects of different size in \"close proximity\" (defined with respect to relative size and shape) peuquet / ci-xiay (1987): - modification of this model for \"close proximity\" by moving triangular area relative to the direction at issue kobler (1992): - deals with overlapping objects ( all drop the requirement of mutual exclusion of orientations ) the model proposed: - 1. case: far away : triangular model withour overlapping areas - 2. case: close proximity ( closer than three times the max. radius of refr. object (ad hoc value): variant of the modified triangular model withour overlapping acceptance areas ( heterogenous areas depending on the \"shape\" ) - 3. case: overlapping: kobler's scheme but geometric centroid used not the functional center point - in cases of ambiguity, recur either to a coarser orientaion or to orientation in the complementary set 4.5 examples nice example. 5 reasoning with qualitative representation 5.1 transforming between frames of reference this section deals with the following transformation between frames of reference: intrinsic --> implicit extrinsic --> implicit deictic --> implicit (all are explained shortly) by using analogical representations transformation can be achieved by \"rotating\" the labels. 5.2 composition of spatial relations the compositions of binary topological relations are derived from their definitions ( egenhofer 1991 ). using conceptual neighbourhood interesting regularities can be found: all resulting disjunctions of relations are connected (neighbours) the composition table is almost symmetric (except i and i@b heve to be substituted by c or c@b and vice versa) when the vertical order of i, i@b and c,c@b is flipped only 21 different relation sets occur. after two iterations a fixed point is reached with a closed set of 26 different sets of relations, all of them connected then the compositions of orientation relations are presented. the following regularities occur: a composition contains all orientations in between and including x and y on the shortest path of the ron (see 4.4) the composition is symmetric relations in the composition are always conceptual neighbours it is shown that the compositions of topological / orientation pairs contains fewer relations (is more constrained). 5.3 constraint reasoning first the constraint satisfaction problem (csp) is formally defined. then improved constraint satisfaction algorithms are discussed: 1.algorithms that modify the search space a) prior to the search (consistency improvement): constraint propagation is presented b) during the search (hybrid algorithms): look-ahead / look-back procedures, graph theoretical methods and dynamic programming techniques are mentioned 2.algorithms that use heuristics to guide the search 5.4 exploiting the structure of space this section shows how cs-algorithms can be improved by exploiting the structure of space. first the combined structure of topological and orientation relations (conceptual neighbourhood) is presented. abstract naps are introduced. they contain for each object in a scene a data structure with the same neighbourhood structure as the domain required for the task at hand. design decisions for the presented algorithms are: the structure of space should be taken advantage of only local consistency check should be done, insertation and path-finding \"on demand\" hierachical and functional decomposition of space should be used to propagation weighting of positional relations should be used to avoid \"information decay\". data structures and algorithms for inserting, deleting and path-finding are presented using a dependency network. a method for constraint relaxation (weakening of constraints to reach consistency) using the structure of the relational domain is discussed shortly. here other neighbouring relations are included in their\ disjunctive definitionsinstead of retracting them as a whole. 6 applications 6.1 building cognitive maps here approaches to the building of cognitive maps are discussed. in particular: hafner / kobler (1991), kobler (1991), hahn (1990), funt (1980) 6.2 visualization a process for the visualization of a given qualitative representation is introduced. steps: 1.prototypical room and objects 2.functional\ clustering 3.fix unambiguous positions 4.generate subspaces / assign objects 5.resolve local conflicts 6.actual rendering 7 extensions of the basic model 7.1 3-d space qualitative representation of 3d positional information is briefly discussed, among others refering to funt (1980) and schwarzer / hˆgg (1991). 7.2 size the size dependencies of topological relations are summarized. the following approaches to qualitative representation of size are reviewed: allen (1983), mukerjee / joe (1990), zimmermann (1991) and raiman (1986) 7.3 distance the section shortly discusses how distance can be represented in a qualitative way. 7.4 shape the following literature concerning qualitative models for shape is reviewed: binford (1971), pentland (1986), dickinson (1991), hˆgg (1993), schwarzer (1993) 8 relevant related work this chapter summarizes the literature closely related to hernandez' work. the most important ones are summarized shortly. these are: 8.1.1 interval algebras j. f. allen (1983): maintaining knowledge about temporal intervals c. freksa (1992): temporal reasoning based on semi-intervals 8.1.2 cartesian tuples of relations h.-w. guesgen (1989): spatial reasoning based on allen's temporal logic a. mukerjee / g. joe (1990): a qualitative model for space 8.1.3 other relational approaches j. freeman (1975): the modelling of spatial relations c. e. pfefferkorn (1975): a heuristic problem solving design system for equipment or furniture layouts m. di manzo / f. giunchiglia / e. pino (1985): space representation and object positioning in natural language driven image generation s. green (1987): spaces - a system for the representation of commonsense knowledge about space for design k. d. forbus / p. nielsen / b. faltings (1991): qualitative spatial reasoning: the clock project c. freksa (1991): qualitative spatial reasoning a. g. cohn / z. cui / d. a. randell (1992): logical and computational aspects of spatial reasoning a. u. frank (1992): qualitative spatial reasoning with cardinal directions c. freksa (1992): using orientation information for qualitative spatial reasoning c. freksa / k. zimmermann (1992): on the utilization of spatial structures for cognitively plausible and efficient reasoning t. fuhr / f. kummert / s. posch / g. sagerer (1992): an approach for qualitatively predicting relations from relations e. clementini / p. di felice / p. van oosterom (1993): a small set of formal topological relationships suitable for end-user interaction c. freksa / r.rˆhrig (1993): dimensions of qualitative spatial reasoning g. f. ligozat (1993): models for qualitative spatial reasoning l. vieu (1993): a logical framework for reasoning about space 8.2.1 representation modalities d. l. waltz / l. boggess (1979): visual analog representation for natural language understanding r. reiter / a. k. mackworth (1989): a logical framework for depiction and image interpretation b. chandrasekaran / n. h. narayanan (1990): towards a theory of commonsense visual reasoning 8.2.2 cognitive maps and route finding b. j. kuipers / t. levitt (1988): navigation and mapping in large-scale space d. v. mcdermott / e. davis (1984): planning routes through uncertain territory w. k. yeap (1988): towards a computational theory of cognitive maps 8.2.3 linguistically motivated research a. herskovits (1986): language and spatial cognition c. habel / s. pribbenow (1989): zum verstehen r‰umlicher ausdr¸cke des deutschen - transivit‰t r‰umlicher relationen 8.2.4 relational algebras r. g¸ting (1988): geo-relational algebra: a model and query language for geometric database systems r. laurini / f. milleret (1988): spatial data base queries: relational algebra versus computational geometry s.-k. chang / q.-y. shi / c.-w. yan (1987): iconic indexing by 2d-strings d. papadias / t. sellis (1992): spatial reasoning using symbolic arrays d. papadias / t. sellis (1993): the semantics of relations in 2d space using representative points (vs - very short, s - short, md - more detailed ) 9 conclusion 9.2 future research issues integration of metric knowledge, path knowledge, non-spatial knowledge, interpretation of relations and its relationship to linguistic concepts and perceptual representations and mental models are considered as future research issues. appendix a - composition tables for various special cases appendix a contains: composition table for binary topological relations (set representation) composition table for the closed set of binary topological relations composition tables for level 1-3 orientations for solids summary of shape description vocabulary}}, |
| Keywords: | |
| Authors | |
|
Attachments
|
|
|
Notes
|
|
|
|
|
|
Topics
|
|
|
|
|