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.
People |
ORCID iD |
Michael Zakharyaschev (Principal Investigator) |
Publications
Kontchakov R
(2014)
Spatial reasoning with RCC 8 and connectedness constraints in Euclidean spaces
in Artificial Intelligence
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 |