http://www.jimdavies.org/summaries/

@InProceedings{FreksaZimmermann1993, author = {Christian Freksa and Kai Zimmermann}, title = {On the Utilization of Spatial Structures for Cognitively Plausible and Efficient Reasoning}, pages = {61-66}, booktitle = {Proceedings of the Workshop on Spatial and Temporal Reasoning, 13th International Joint Conference on Artificial Intelligence}, address = {Chamberg, France}, year = {1993}, }

The paper (which also appeared in the Proceedings of the IEEE Intern. Conf. Systems Man and Cybernetics 1992, pp. 261-266, IEEE. Chicago.) is available as a PDF at http://www.cosy.informatik.uni-bremen.de/staff/freksa/publications/IEEE-SMC92h.pdf (as of 2006-02-08).

The paper also relies on another authored by Freksa, Using orientation information for qualitative spatial reasoning (herein noted as Freksa, 1992b), which is also available as a PDF: http://www.cosy.informatik.uni-bremen.de/staff/freksa/publications/UsOrInformation92.pdf (as of 2006-02-08).

- Spatial reasoning
- Orientation in space

The authors claim that human "knowledge about physical space differs from all other knowledge in a very significant way" (for example, we use many spatial metaphors in language when problem solving) and that "'dealing with space' should be viewed as cognitively more fundamental than abstract reasoning." Their aim is to create a "'spatial inference engine' which deals with [space] in a way more similar to biological systems;" using "imprecise, partial, and subjective" perceptions.

The authors introduce an *orientation grid* arranged around
a single vector from two arbitrary points in space. Other points in
space are defined in relation to this vector: either left, right, or
straight on it; in front, in back, or neutral to the vector. The
authors break this down into a 5 by 3 grid. For example, given vector
from point `a` to point `b`, `v` would be
far front-straight, `w` would be front-left, `x`
neutral-right, `y` straight-back, and `z` far
back-right (see table
below).

Left | Straight | Right | |

Front | v |
||

w |
|||

b |
|||

Neutral | x |
||

a |
|||

y |
|||

Back | z |

The idea of frontness implied in this model is defended by the authors, who claim "we conceptualize people, animals, robots, houses, etc. as having 'an intrinsic front side.'" They continue to describe what they see as the short comings of other models of orientation (Randell, 1991; Güsen, 1989; Schlieder, 1990; Hernández, 1992), pressing for perception-based qualitative reasoning which deals with incomplete knowledge. This model does this, as well as circumventing the problem of dealing with the shapes of surrounding objects. They also note that this model describes objects with respect to movement between two positions, not other objects.

**Inversion** (INV) of
the vector `ab` (to vector `ba`) is a simple
operation. Front becomes back, left becomes right, etc. Results of
this operation are always precise. The authors note that many previous
models do not deal with inversion as neatly (Schatz, 1990; Frank,
1991).

**Homing** (HM) is the
answer to "where is the start point `a` if I continue my way
by walking from `b` to [arbitrary point] `c`?" That
is, where is `a` in relation to the vector `bc`?
(see example below).

/ c . . .b / / a

The results of the homing operation are less precise than they are
in an inversion. The change from `a` to `b` then
back to `b` "with a few steps in between" relies on a null
reference vector, `bb`, which results in an blind block of
orientation front-straight. The authors say that this holds with the
behaviour of conceptually neighbouring relations (Freksa,
1992a,b).

**Shortcut** (SC) is the
deduction of `b` with relation to `ac`. This allows
the model to find the relative position of objects that are not along
a determined path, or just to find a shortcut to `c` (see example below). This operation is similar
to homing, except that its resultant blind block is back-straight.

\ c . . .b \ \ a

These three operations can be combined algebraically, but the combination is only associative, not commutative (e.g. INV × SC = HM, but SC × INV = SCI). The authors note that this associativity allows for the application of a general or parallel constraint propagation algorithm in which the order of combination is irrelevant.

**Composition** allows the system to deduce unknown
points from relations between known ones. For example, knowing
`c` in terms of `ab` and `d` in terms of
`bc` allows the system to find `d` in terms of
`ab` (see example
below). (The authors refer to another paper, Freksa 1992b, for a full explanation of
composition.)

/ c / . |/ . b . . d | | a

Stating that landmarks play an important role in human path finding, the authors present a simple environment in which their model of orientation is able to algebraically deduce relations between points in space. Here follows their description of this environment (see example below):

Walk down the road (

ab). You will see a church (c) in front of you on the left. Before you reach the church turn down the path that leads forward to the right (bd)… Where is the church [with relation to you]?

| / | d c | / |/ b | | a

Given `c` in terms of `ab` and `d` in
terms of `ab`, the model (running under a constraint
propagation mechanism "which would correspond to an unoriented forward
chaining task") mistakenly says that `c` is anywhere to its
front-, neutral-, or back-left; neutral- or back-straight; or even
neutral- or back-right. The answer should be anywhere to the
left. "The more appropriate results," write the authors, "may be
obtained if we do not ask for the direct composition that leads to
`c`:`bd`, but if we ask for the composition that
gives us the inverted relation `c`:`db` instead."
This does indeed give the more appropriate result: `c` is
either front-, neutral-, or back-left.

The authors ask whether this system of inference is complete. "Up to now we have only proven that we can deduce a relation between an arbitrary point [with respect to] to any line."

They say that the complexity of the inferences under this model are
of the order O(`k`³), where `k` is the number
of points. They also speculate of cases that may be of only polynomial
order ("only conceptually neighbouring relations without
'holes'?").

Lastly, the authors ask whether there is a preferred way of carrying out the computation under this model. "[T]he result of a deduction depends on the way the result is derived and which relations are used," as seen in the church example. The authors claim to be investigating whether there are preferred ways of making inferences.

- I found the diagrams in the paper helpful and recommend giving them a look
- Keep in mind that I wrote this summary as an undergraduate

Back to the Cognitive Science Summaries homepage

Cognitive Science Summaries Webmaster: JimDavies (jim@jimdavies.org) Last modified: Thu Apr 15 11:07:19 EDT 1999