Project Leader
Michael Zakharyaschev
www.dcs.bbk.ac.uk/~michael
Project staff
Roman Kontchakov
www.dcs.bbk.ac.uk/~roman
Other Project Partners
Manchester University
Universiteit Hasselt
Project Details
Funded by EPSRC
April 2007  March 2010
Keywords
Spatial reasoning, logic, Euclidean spaces, mereotopology, elementary geometry
Download
euclid (doc)
euclid (pdf)

Computational Logic of Euclidean Spaces
Spatial KR&R background
Much of the spatial information we encounter in everyday situations is qualitative, rather than quantitative, in character. Thus, for instance, we may know which of two objects is the closer without measuring their distances; we may perceive an object to be convex without being able to describe its precise shape; or we may identify two areas on a map as sharing a boundary without knowing the equation that describes it.
This observation has prompted the development, within Artificial Intelligence, of various formalisms for reasoning with qualitative spatial information. Although substantial progress has been made in analysing the mathematical foundations and computational characteristics of such formalisms, most of that progress has centred on systems for reasoning about highly abstract problems concerning (typically) arbitrary regions in very general classes of topological spaces.
But of course, the geometrical entities of interest for practical problems are not arbitrary subsets of general topological spaces, but rather mathematically very wellbehaved regions of 2 and 3dimensional Euclidean space. Moreover, the geometrical properties and relations these problems are concerned with are typically not merely topological, but rather affine or even metric in character. Together, these factors severely limit the practical usefulness of current qualitative spatial reasoning formalisms. Overcoming this limitation represents an exciting mathematical and computational challenge.
Project Aims
We propose to meet this challenge by drawing on developments in mathematical logic, geometrical topology, and algebraic geometry that the spatial reasoning literature in AI has so far failed fully to exploit.
Specifically, we are investigating the computational properties of spatial and spatiotemporal logics for reasoning about mathematically wellbehaved regions of 2 and 3dimensional Euclidean space. We are developing and implementing algorithms for reasoning with these logics. This investigation will illuminate the important relationships between hitherto separate research traditions, provide new techniques for addressing challenging problems in the mathematical geometry, and yield logics of direct relevance to practical spatial reasoning problems.
Publications
[1] M. Aiello, I. PrattHartmann and J. van Benthem, editors. Handbook of Spatial Logics. Springer, 2007. [2] B. Konev, R. Kontchakov, F. Wolter and M. Zakharyaschev. On dynamic topological and metric logics. Studia Logica, 84:129160, 2006. [3] F. Wolter and M. Zakharyaschev. A logic for metric and topology. Journal of Symbolic Logic, 70:795828, 2005.
