Computational Logic of Euclidean Spaces

Lead Research Organisation: Birkbeck, University of London
Department Name: Computer Science and Information Systems

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
Sheremet M (2010) A modal logic framework for reasoning about comparative distances and topology in Annals of Pure and Applied Logic

publication icon
Trybus A (2016) Rational Region-Based Affine Logic of the Real Plane in ACM Transactions on Computational Logic

 
Description We developed spatial knowledge representation formalisms that include the connectedness predicates. We also thoroughly investigated the computational complexity of reasoning with these formalisms.
Exploitation Route It would be interesting to implement spatial reasoning with connectedness over the Euclidean plane.
Sectors Digital/Communication/Information Technologies (including Software)

 
Description University of Hasselt 
Organisation University of Hasselt
Country Belgium 
Sector Academic/University 
Start Year 2007