@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).
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.