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 well-behaved regions of 2 and 3-dimensional 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 spatio-temporal logics for reasoning about mathematically well-behaved regions of 2- and 3-dimensional 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. Pratt-Hartmann 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:129-160, 2006. [3] F. Wolter and M. Zakharyaschev. A logic for metric and topology. Journal of Symbolic Logic, 70:795-828, 2005.