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 [Dipole Calculus].

The conceptual neighborhood graph for the 14 basic relations by Schlieder

• Bibliography