Information about Using Orientation Information for Qualitative Spatial Reasoning

A presentation of Freksa's 1992 paper on qualitative spatial reasoning with cardinal directions.

Outline • Introduction • Motivation • Previous approaches • Argument for qualitative orientation • Directional orientation in 2D • Augmenting qualitative relations • Conceptual neighborhood theory • Using the orientation-based framework • Applications • Further work 2

Introduction An approach to represent spatial knowledge using qualitative, neighborhood-oriented spatial information. 3

Motivation: Why qualitative? Quantitative knowledge obtained by measuring: 4

Motivation: Why qualitative? Quantitative knowledge obtained by measuring: “thirteen centimeters” 5

Motivation: Why qualitative? Quantitative knowledge obtained by measuring: “thirteen centimeters” • Requires mapping between object domain and scale domain • Mapping can produce distortions 6

Motivation: Why qualitative? Qualitative knowledge obtained by comparison rather than measuring: 7

Motivation: Why qualitative? Qualitative knowledge obtained by comparison rather than measuring: “longer” 8

Motivation: Why qualitative? Qualitative knowledge obtained by comparison rather than measuring: “longer” • Direct evaluation entirely within object domain • Focuses knowledge processing on information relevant to decision making 9

Motivation: Why spatial? • Spatial reasoning is essential to numerous actions and decisions • Arguably, physical space is more fundamental than logical reason: – Spatial reasoning more “primitive” in nature – Logic as an abstraction of spatial reasoning 10

Previous approaches to qualitative spatial reasoning Cartesian framework Güsgen, 1989 11

Previous approaches to qualitative spatial reasoning Cartesian framework Güsgen, 1989 String representations Chang & Jungert, 1986 12

Previous approaches to qualitative spatial reasoning Cartesian framework Güsgen, 1989 String representations Chang & Jungert, 1986 Object-boundary and interior intersections Egenhofer & Franzosa, 1991 13

Previous approaches to qualitative spatial reasoning Cartesian framework Güsgen, 1989 String representations Chang & Jungert, 1986 Object-boundary and interior intersections Egenhofer & Franzosa, 1991 Cardinal direction grids Frank, 1991 14

Why qualitative orientation? Availability of spatial information: • Qualitative orientation is available through pure perception • Other representations, such as Cartesian coordinates or cardinal orientation, refer to extra-perceptual information 15

Directional orientation in 2D Directional orientation a 1D feature determined by an oriented line Oriented line speciﬁed by an ordered set of two points A B orientation ab 16

Directional orientation in 2D Directional orientation a 1D feature determined by an oriented line Oriented line speciﬁed by an ordered set of two points A B orientation ba 17

Directional orientation in 2D Relative Orientation speciﬁed by two oriented lines Orientation of line bc relative to line ab 18

Properties of qualitative orientation wrt. location b and orientation ab 19

Properties of qualitative orientation wrt. location b and orientation ab 20

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd wrt. location b and orientation ab 21

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd wrt. location b and orientation ab 22

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd wrt. location b and orientation ab 23

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd wrt. location b and orientation ab 24

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic wrt. location b and orientation ab 25

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic opposite ∞ left yields right wrt. location b and orientation ab 26

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic opposite ∞ left yields right wrt. location b and orientation ab 27

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic opposite ∞ left yields right opposite ∞ opposite ∞ left yields left wrt. location b and orientation ab 28

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic opposite ∞ left yields right opposite ∞ opposite ∞ left yields left opposite ∞ opposite ∞ opposite ∞ wrt. location b and orientation ab left yields right 29

Properties of qualitative orientation Same transitive if ab=bc and bc=cd then ab=cd Opposite periodic opposite ∞ left yields right opposite ∞ opposite ∞ left yields left opposite ∞ opposite ∞ opposite ∞ wrt. location b and orientation ab left yields right Orientation is a circular dimension 30

Augmenting qualitative relations Front-back segmentation • cognitively meaningful to people and animals • most objects have this implicit dichotomy 8 disjoint orientation relations 0 straight-front straight-back 4 1 right-front 5 left-back 2 right-neutral 6 left-neutral 3 right- back 7 left-front 31

Orientation-based qualitative location + = front-back dichotomy wrt. front-back dichotomy wrt. ab in b ba in a 32

Orientation-based qualitative location c + = front-back dichotomy wrt. front-back dichotomy wrt. ab in b ba in a 33

Conceptual neighborhood Conceptual neighbor a relation that represents a direct transition in the object domain from the initial relation • Based on studies of temporal cognition • Cognitive & computational advantages 34

Conceptual neighborhood • Conceptual neighbor a relation that represents a direct transition in the object domain from the initial relation 35

Conceptual neighborhood • Conceptual neighbor a relation that represents a direct transition in the object domain from the initial relation 36

Conceptual neighborhood • Conceptual neighbor a relation that represents a direct transition in the object domain from the initial relation Conceptual neighbors: i and 6 i and 7 i and 0 6 and 7 7 and 0 37

Conceptual neighborhood • Conceptual neighbor a relation that represents a direct transition in the object domain from the initial relation Conceptual neighbors: i and 6 i and 7 i and 0 6 and 7 7 and 0 Not conceptual neighbors: Require intermediate relations 6 and 0 38

Conceptual neigborhood in represented domain 39

Conceptual neigborhood in represented domain 40

Conceptual neigborhood in represented domain • 15 qualitative relations • 105 (unordered) pairs • 30 conceptual neighbors 41

Conceptual neigborhood in represented domain Utility • Reﬂects represented world • Reasoning strategies entirely within the represented domain • Assist domain visualization • Computationally restrict problem space to feasible operations 42

Orientation-based qualitative distance • Finer spatial resolution conveys distance • Does not increase orientation precision 43

Represented entities Most approaches • spatially extended objects • convex or rectangular shapes Points as basic entities, fundamental approach • Properties & relations hold for entire spatial domain • Shapes can be described as points with various levels of abstraction and precision; ﬂexible 0D point city on wide area map 1D extension length of a road 2D projection area of a lake 3D constellation shape or group of objects 44

Qualitative spatial reasoning Using the orientation-based framework for inferences • Describe one spatial vector with relation to another • Infer unknown vector relations based on known relations 45

Qualitative spatial reasoning Using the orientation-based framework for inferences Given • relation of vector bc to vector ab • relation of vector cd to vector bc Infer location of d to vector ab 46

Qualitative spatial reasoning Using the orientation-based framework for inferences • Consider front-back dichotomies for known vectors 47

Qualitative spatial reasoning Using the orientation-based framework for inferences • Consider front-back dichotomies for known vectors • c right-front (1) ab 48

Qualitative spatial reasoning Using the orientation-based framework for inferences • Consider front-back dichotomies for known vectors • c right-front (1) ab • d right-back (3) cb 49

Qualitative spatial reasoning Using the orientation-based framework for inferences • Consider front-back dichotomies for known vectors • c right-front (1) ab • d right-back (3) cb Wrt. to original vector ab, vector bd is either right-front (1), front (0), or left front (2) 50

Composition table • Organize qualitative orientation-based inferences • Neighboring rows and columns show conceptual neighbors 51

Composition table • Initial conditions 52

Composition table • Possible locations of c 53

Composition table • Possible locations of d 54

Composition table • Orientation-less c=d d=b 55

Composition table 56

Composition table 57

Composition table 25% of all cases hold uncertainty • neighboring possibilities increase orientation angle up to 180˚ • degree of uncertainty is precisely known 58

Composition table r orientation of c wrt. ab s the orientation of d wrt. bc t orientation of d wrt. ab 59

4 Composition table 3 5 2 6 1 0 7 r orientation of c wrt. ab s the orientation of d wrt. bc t orientation of d wrt. ab 7 0 1 6 2 5 3 4 60

4 Composition table 3 5 2 6 1 0 7 r orientation of c wrt. ab s s the orientation of d wrt. bc 3 t orientation of d wrt. ab 7 0 1 6 2 r 1 5 3 4 61

Composition table r orientation of c wrt. ab s s the orientation of d wrt. bc 3 t orientation wrt. ab r and s are odd: t r t ={(r+s-1)…(r+s+1)} mod 8 1 7,0,1 t ={(1+ 3 -1)…(1+ 3+ 1)} mod 8 t = {3 … 5} mod 8 62

Fine grain composition table • Higher resolution • 2 front-back dichotomies • Produced by producing sub-rows and sub-columns from previous table 63

Applications • Determine an unknown location in space based on own location and known location • Wayﬁnding & route descriptions 64

Referencing work 257 citations in Google Scholar A few examples: – Computational methods for representing geographical concepts (Egenhofer, Glasgow, et al) – Schematic maps for robot navigation (Freksa, et al) – Pictorial language for retrieval of spatial relations from image databases (Papadias, et al) 65

Questions? 66

Freksa: Using Orientation Information for Qualitative Spatial Reasoning 2 The obvious question was raised whether the approach originally developed for the

Read more

Dan Tappan, Knowledge-based spatial reasoning for scene generation from text descriptions, Proceedings of the 23rd national conference on Artificial ...

Read more

Abstract. A new approach to representing qualitative spatial knowledge and to spatial reasoning is presented. This approach is motivated by cognitive ...

Read more

Qualitative Spatial Reasoning Using Orientation, ... “Qualitative spatial reasoning ... “Using orientation information for qualitative ...

Read more

Using Orientation Information for Qualitative Spatial Reasoning on ResearchGate, the professional network for scientists.

Read more

Spatial reasoning can ... Inferring new knowledge from this qualitative spatial information is ... the orientation of objects is obtained by using ...

Read more

Qualitative Spatial Reasoning ... even when a precise quantitative information is not available [2]. ... A qualitative spatial relative orientation

Read more

Spatial Reasoning and Applications Table ... information for qualitative spatial reasoning. ... Using orientation information for qualitative ...

Read more

... followed by understanding orientation ... that combine spatial and temporal information. ... Qualitative Spatial Reasoning using ...

Read more

## Add a comment