Computational Logic of Euclidean Spaces

Lead Research Organisation: University of Manchester
Department Name: Computer Science

Abstract

Much of the spatial information we encounter in everyday situations isqualitative, rather than quantitative, in character. Thus, forinstance, we may know which of two objects is the closer withoutmeasuring their distances; we may perceive an object to be convexwithout being able to describe its precise shape; or we may identifytwo areas on a map as sharing a boundary without knowing the equationthat describes it. This observation has prompted the development,within Artificial Intelligence, of various formalisms for reasoningwith qualitative spatial information.Although substantial progress has been made in analysing themathematical foundations and computational characteristics of suchformalisms, most of that progress has centred on systems for reasoningabout highly abstract problems concerning (typically) arbitraryregions in very general classes of topological spaces. But of course,the geometrical entities of interest for practical problems are notarbitrary subsets of general topological spaces, but rathermathematically very well-behaved regions of 2 and 3-dimensionalEuclidean space; moreover, the geometrical properties and relationsthese problems are concerned with are typically not merely topological, butrather affine or even metric in character. Together, these factorsseverly limit the practical usefulness of current qualitative spatialreasoning formalisms. Overcoming this limitation represents anexciting mathematical and computational challenge.We propose to meet this challenge by drawing on developments inmathematical logic, geometrical topology, and algebraic geometry thatthe spatial reasoning literature in AI has so far failed fully toexploit. Specifically, we shall investigate the computationalproperties of spatial and spatio-temporal logics for reasoning aboutmathematically well-behaved regions of 2- and 3-dimensional Euclideanspace. We shall develop and implement algorithms for reasoning with these logics. This investigation will illuminate the important relationships betweenhitherto separate research traditions, provide new techniques foraddressing challenging problems in the mathematical geometry, andyield logics of direct relevance to practical spatial reasoningproblems.

Publications

10 25 50

publication icon
Kontchakov R (2013) Topological Logics with Connectedness over Euclidean Spaces in ACM Transactions on Computational Logic

publication icon
Kontchakov R (2010) Spatial logics with connectedness predicates in Logical Methods in Computer Science

publication icon
Nenov Y (2010) Computer Science Logic

publication icon
Nenov Yavor Neychev (2011) Computability of Euclidean spatial logics

publication icon
Pratt-Hartmann I (2009) Data-complexity of the two-variable fragment with counting quantifiers in Information and Computation

 
Description This project investigated the computational properties of Qualitative Spatial Logics: formalisms for representing, in non-numerical terms, information about the relationships between regions in space. The basic problem is this: given a description of some putative spatial arrangement, determine whether that description is possible---i.e. spatially realizable. The computational complexity of answering this question depends on the representation language we employ, and on the model of space it is interpreted over. Our task in this project was to chart this dependency. The qualitative relations we focused on were the (mereo-) topological relations of inclusion, contact and connectedness, as well as the affine relation of convexity. Concerning topological representation languages, we made two major advances: the first was to identify the significance of logics with a primitive predicate expressing the property of connectedness (i.e. the property of consisting of a single piece). Previous work on topological logics had largely ignored this property (and were unable to express it), resulting in formalisms which had only limited ability to model real-life spatial arrangements. We established the computational effect of adding predicates expressing the property of connectedness (or related notions) to all the principal extant topological representation languages. The results we obtained illustrated a more complicated and subtle complexity-theoretic landscape than had been encountered in the case of logics without connectedness. The second major conceptual advance was to identify the sensitivity of spatial logics featuring the connectedness predicate (or its variants) to the precise choice of interpretation over low-dimensional Euclidean spaces. Previous work on topological logics had concentrated almost exclusively on interpretations over very general classes of topological spaces. For languages unable to express connectedness, such a general approach was justified, because these languages are generally too inexpressive for the underlying space to make any difference. For languages with a connectedness predicate, however, the effect of restricting interpretation to Euclidean spaces (of various dimensions) is, as we discovered, dramatic. We showed that even the least expressive of the languages we investigated was sensitive to whether certain physically implausible spatial entities (in the jargon: non-tame sets) were counted as spatial regions. The computational complexity of many of these logics (in the versions both with and without non-tame regions) was determined. Thus, by bringing into focus the interacting ideas of logics with connectedness and their interpretation over low-dimensional Euclidean spaces, we have made a significant impact on the research agenda in the area of Qualitative Spatial Logics. Concerning logics able to express the affine notion of convexity, we achieved several technical advances, published in a further two conference papers. In particular, an axiom system for first-order spatial logic with convexity interpreted over two-dimensional space was obtained, and the precise degrees of undecidability of such logics over low-dimensional Euclidean spaces was determined, yielding unexpected consequences for the expressive power of the formalism in question.

Two students at Manchester received the degree of PhD for work undertaken directly on this project.
Exploitation Route The work reported here has potential applications to robotics and geographic information systems (GIS).
Sectors Digital/Communication/Information Technologies (including Software)

URL http://www.dcs.bbk.ac.uk/~roman/CLES/
 
Description Our results show, in essence, that the problem of reasoning about qualitative spatial relationships involving regions of the plane (and indeed of higher-dimentional spaces) is of much higher complexity than originally supposed. This result is of relevance to AI and robotics, but there are no direct technological applications.
First Year Of Impact 2010
Impact Types Cultural