Research Paper Review
CompSci 765 S2 C Advanced Artificial Intelligence 2005
 
Qualitative Spatial Reasoning
Christian Freska
Institut fur Informatik
Technische Universitat Munchen
Germany
Reviewer
Mukul Pahwa mpah004@ec.auckland.ac.nz
 
Reference
Christian Freska, "Qualitative Spatial Reasoning", Cognitive and Linguistic Aspects of Geographic Space, 361-372, 1991.
 
Keywords
Space, Spatial Inference Engine, Abstraction, Qualitative Knowledge, Quantitative Knowledge, Aquarium Metaphor
 
Related Papers

Allen, J., Maintaining knowledge about temporal intervals. CACM 26, 11, 832-843. Block, N., ed., 1981. Imagery. MIT Press. Cambridge, Massachusetts, 1983.

Freksa, C., Communication about visual patterns by means of fuzzy characterizations. XXIInd Intern. Congress of Psychology, Leipzig, 1980.

Freksa, C., Temporal reasoning based on semi-intervals. ICSI TR-90-016, International Computer Science Institute, Berkeley, 1990.

Guesgen, H. W., Spatial reasoning based on AllenÕs temporal logic. ICSI TR-89-049, International Computer Science Institute, Berkeley, 1989.

Hernandez, D., Relative representation of spatial knowledge: the 2-D case. To appear in: D.M. Mark & A.U. Frank (eds.) Cognitive and Linguistic Aspects of Geographic Space. Kluwer, Dordrecht, 1990.

Lakoff, G., Women, fire, and dangerous things: what categories reveal about the mind. University of Chicago Press, Chicago, 1987.

Lakoff, G. & Johnson, M., Metaphors we live by. University of Chicago Press, Chicago, 1980.

Reiter, R., Mackworth, A., A logical framework for depiction and image interpretation. Artificial Intelligence 41, 125-155, 1989.
 
Summary
Physical Space

Physical space is defined to be the domain in which all physical events take place, and as a reference domain for the interpretation of non-spatial concepts.The author points out how space is perceived multi modally (visually, tactily, acoustically, by smell and temperature sensations), and has modifiable dimensions (move objects by physical force or move ourselves). Since its perception by humans is so rich, it serves as a suitable medium for conveying knowledge of abstract and non-spatial concepts. In order to use our extensive knowledge of space to map abstract concepts to this concrete domain and back, the author explains the design of a spatial inference engine.
Spatial Inference Engine

A spatial inference engine is part of a specialized representation system that is capable of making analogies to space for transformations of non-spatial concepts. Freska points out that space has some universal properties and constraints and these should be modeled explicitly into such a system. Examples such as how a drawing paper uses analogies to the properties of space in Constructive geometry, and how Cartography exploits spatial properties of maps as an analogy to those of the real world, explain the author’s stand. Properties such as the following must be built into the system:

Uniqueness constraints:
Each object exists exactly once;
Each location coincides with at most one object

Topology:
Movement in space is possible only between neighboring locations (this property should hold on any level of representation).

Conceptual Structures:
Properties related to the neighborhood of spatial relations. For example, a spatial relation 'A is to the left of B' and 'A touches B on the left' are spatial conceptual neighbors since there is a direct transition from on relation to the other when the spatial arrangement is modified.

Abstraction:
It is not always possible to solve problems in the real world since high costs or a lot of effort might be needed (weight, size etc.). In such situations, the system must be able to abstract from extra, unnecessary information during transformations. Abstraction, it is stated, ‘liberates representations from insignificant details and focuses on the significant distinctions’. The author suggests that once a problem is abstract enough, we should formalize its knowledge using a formal language such as predicate logic.
 
However, there are properties of real space that must be abstracted from and some that must be maintained (such as the constraints). In other words, we would like to represent only that knowledge that is needed to solve a problem. Since we cannot measure the amount of knowledge we might need beforehand, we cannot be too restrictive. As an example on the kind and range of knowledge needed, Freska illustrates the differences in precise maps and way finding. The former uses quantitative knowledge for absolute locations, and the latter uses qualitative knowledge for distinguishing quantities. The properties that we want to maintain are the universal constraints of space that have been discussed before.
The author argues that qualitative knowledge is closer to the way human beings interact and therefore, such a system must be capable of handling it. Qualitative knowledge is shown to have top-down granularity as compared to a bottom-up approach of quantitative knowledge. Qualitative knowledge and representation allows much more freedom by not requiring the use of distinct units and numbers (larger, smaller, and equal). The author contrasts qualitative representations with quantitative representations. With an example such as size:

Quantitative Representation
Granularity of unit regulates distinguishable classes
Need to know beforehand the sizes to distinguish

Qualitative Representation
Smaller, larger, equal
No pre defined sizes
Depending on need, coarser or finer descriptions are compared
 
The use of qualitative knowledge is explained very well using the Aquarium metaphor where two observers, without using any co-ordinates or numbers can convey to each other the fish they are talking about. James Allen’s temporal approach is briefly explained during the end of this paper. The author explains how these relations can be transformed into space, in the same context as the aquarium. The author points out the increase in the thirteen relations when applied to space, is directly proportional to the dimensions. This paper concludes with a mention of the application areas for qualitative spatial reasoning such as in Geographic Information Systems, Electric Circuits and Navigation.
 
Evaluation
I think this paper is very well written and structured. The author explained his ideas with adequate examples that ensure clear understanding. In the introduction, space and its properties are explained. It is made clear why it is an important medium for conveying knowledge about spatial or non-spatial concepts. The main concept in the paper, a spatial inference engine is then explained with its designs, constraints, and examples. Issues that may affect the inference engine are talked about under abstraction. The author then points out what knowledge we should and shouldn’t abstract from. A contrast between qualitative and quantitative knowledge and representation explains why such a system must be able to support qualitative knowledge. This is further explained using the aquarium metaphor. Spatial properties in one and higher dimensions are discussed briefly, in the same context as the aquarium metaphor. And the author concludes with mentioning the fields where this system is and can be applicable.
I must mention however author went a bit overboard with explanations in certain sections which I think resulted in a repetition. Like when discussing abstraction and qualitative knowledge, the same ideas are mentioned a few times.