R3-[Q-Shape] - Research: Qualitative Spatial Reasoning
Neighborhood Based Reasoning
Neighborhood-based reasoning describes whether two spatial configurations of objects can be transformed into each other by small changes [Fre91]. Originally conceptual neighborhood has been defined on temporal events only (Two relations between pairs of events are conceptual neighbors if they can be directly transformed into one another by continuous deformation (e.g. shortening or lengthening) of the events [Fre91].), but the concept can be adapted to spatial entities as well. The conceptual neighborhood of a qualitative spatial relation which holds for a spatial arrangement is the set of relations into which a relation can be changed with minimal transformations, e.g. by continuous deformation. Such a transformation can be a movement of one object of the configuration in a short period of time. On the discrete level of concepts, neighborhood corresponds to continuity on the geometric or physical level of description: continuous processes map onto identical or neighboring classes of descriptions [Fre04]. Spatial neighborhoods are very natural perceptual and cognitive entities and other neighborhood structures can be derived from spatial neighborhoods, e.g. temporal neighborhoods. The term continuous in the presence of transformation or deformation needs a grounding in spatial change over time. From our point of view the continuous transformation is the continuous motion of a robot .
This can be described by the function , where is a set of times and is a set of possible positions of .
Now assuming and being topological spaces, the motion of is continuous, if the the function is continuous [Gal00b]. Detailed work on different aspects of continuity were investigated in [BG04,Dav01,Gal97,Gal00a,HC01,Mul98]. Based on different definitions of continuity different neighborhood graphs may arouse. This is also true for different robot kinematics, e.g. comparing differential drive robots versus omnidirectional drive robots.
A movement of an agent can then be modeled qualitatively as a sequence of neighboring spatial relations which hold for adjacent time intervals. Using this qualitative representation of trajectories neighborhood-based spatial reasoning can be used as a simple, abstract model of robot navigation and exploration. Neighborhoods can be formed recursively and represented by hierarchical tree or lattice structures.
Schlieder [Sch95] mapped orientation onto ordering. He defined the orientation on triangles and for every set with more than three points recursively for every triangle. He extracted 14 basic relations to reason about ordering of line segments(16 potential triangle configurations, but two configurations are geometrically impossible). The conceptual neighborhood graph is shown in the figure below. The labels are defined on the Dipole Calculus Page.
Bibliography
[BG04]: Brandon Bennett and Antony P. Galton. A unifying semantics for time and events. Artificial Intelligence, 153(1-2):13-48, March 2004.
[Dav01]: E. Davis. Continuous shape transformation and metrics of shape. In Fundamenta Informaticae, volume 46, pages 31-54. May 2001.
[Fre91]: Christian Freksa. Conceptual neighborhood and its role in temporal and spatial reasoning. In Madan G. Singh and Luise Travé-Massuyès, editors, Proceedings of the IMACS Workshop on Decision Support Systems and Qualitative Reasoning, pages 181 - 187, North-Holland, Amsterdam, 1991. Elsevier.
[Fre04] Christian Freksa. Spatial Cognition - An AI Perspective. In Proceedings of 16th European Conference on AI (ECAI 2004), 2004.
[Gal97]: Anthony Galton. Space, time, and movement. In Oliviero Stock, editor, Spatial and Temporal Reasoning, pages 321-352. Kluwer Academic Publishers, Dordrecht, 1997.
[Gal00a]: Antony Galton. Qualitative Spatial Change. Oxford University Press, 2000.
[Gal00b]: A.P. Galton. Continuous motion in discrete space. In A.G. Cohn, F. Giunchiglia, and B. Selman, editors, Proc. 7th Internat. Conf. on Principles of Knowledge Representation and Reasoning (KR2000), pages 26-37. Morgan Kaufmann, San Francisco, CA, 2000.
[HC01]: Shyamanta M. Harzarika and Anthony G. Cohn. Qualitative spatio-temporal continuity. Lecture Notes in Computer Science, 2205:92-107, 2001.
[Mul98]: Philippe Muller. A qualitative theory of motion based on spatio-temporal primitives. In Anthony G. Cohn, Lenhart Schubert, and Stuart C. Shapiro, editors, KR'98: Principles of Knowledge Representation and Reasoning, pages 131-141. Morgan Kaufmann, San Francisco, California, 1998.
[Sch95]: C. Schlieder. Reasoning about ordering. In A. U. Frank and W. Kuhn, editors, Spatial Information Theory - A Theoretical Basis for GIS (COSIT'95), pages 341-349. Springer, Berlin, Heidelberg, 1995.