Spatial Reasoning with Applications to Mobile Robotics

Qualitative Reasoning aims at studying concepts and calculi on them that arise often at early stages of problem analysis when one is refraining from qualitative or metric details, cf., [14]; as such it has close relations to the design, cf., [10] as well as planning stages, cf., [29] of the model synthesis process. Classical formal approaches to spatial reasoning, i.e., to representing spatial entities (points, surfaces, solids) and their features (dimensionality, shape, connectedness degree) rely on Geometry or Topology, i.e., on formal theories whose models are spaces (universes) constructed as sets of points; contrary to this approach, qualitative reasoning about space often exploits pieces of space (regions, boundaries, walls, membranes) and argues in terms of relations abstracted from a common-sense perception (like connected, discrete from, adjacent, intersecting). In this approach, points appear as ideal objects (e.g., ultrafilters of regions/solids [78]). Qualitative Spatial Reasoning has a wide variety of applications, among them, to mention only a few, representation of knowledge, cognitive maps and navigation tasks in robotics (e.g. [39], [40], [41], [1], [3], [21], [37], [26]), Geographical Information Systems and spatial databases including Naive Geography (e.g., [24], [25], [33], [22]), high-level Computer Vision (e.g. [84]), studies in semantics of orientational lexemes and in semantics of movement (e.g. [6], [5]). Spatial Reasoning establishes a link between Computer Science and Cognitive Sciences (e.g. [27]) and it has close and deep relationships with philosophical and logical theories of space and time (e.g., [65], [8], [2]). A more complete perspective on Spatial Reasoning and its variety of themes and techniques may be acquired by visiting one of the following sites: [75], [83], [56]. Any formal approach to Spatial Reasoning requires Ontology, cf., [32], [70], [11]. In this Chapter we adopt as formal Ontology the ontological theory of Lesniewski (cf. [49], [50], [69], [47], [36], [18]). This theory is briefly introduced in Section 2. For expressing relations among entities, mathematics proposes two basic languages: the language of set theory, based on the opposition element—set, where distributive classes of entities are considered as sets consisting of (discrete) atomic entities, and languages of mereology, for discussing entities continuous in their nature, based on the opposition partwhole. Due to this, Spatial Reasoning relies to great extent on mereological theories of part, cf., [4], [5], [6], [12], [15], [30], [31], [28], [71], [72], [55].