Computational Logic of Euclidean Spaces

我们在日常生活中遇到的许多空间信息都是定性的，而不是定量的。因此，例如，我们可以知道两个物体中哪一个更近，而不需要测量它们的距离;我们可以认为一个物体是凸的，而不需要描述它的精确形状;或者我们可以在地图上识别出两个共享边界的区域，而不知道描述它的方程。这一观察促进了人工智能的发展，定性空间信息推理的各种形式主义，虽然在分析这些形式主义的数学基础和计算特性方面取得了实质性的进展，大部分的进展集中在系统的reasoningabout高度抽象的问题有关（通常）arbitraryregions在非常一般的类拓扑空间。当然，实际问题中感兴趣的几何实体是一般拓扑空间的非严格子集，但在数学上却是2维和3维欧几里得空间中表现良好的区域;此外，这些问题所涉及的几何性质和关系通常不仅是拓扑的，而且是仿射的，甚至是度量的。总之，这些因素严重限制了目前的定性spatialreasoning形式主义的实用性。克服这一限制是一个令人兴奋的数学和计算的挑战。我们建议通过利用数理逻辑、几何拓扑和代数几何的发展来迎接这一挑战，而人工智能中的空间推理文献迄今未能充分利用这些发展。具体来说，我们将研究空间和时空逻辑的计算特性，用于推理2维和3维欧几里得空间的数学上表现良好的区域。我们将开发和实现用这些逻辑进行推理的算法。这项研究将阐明迄今为止独立的研究传统之间的重要关系，提供新的技术来解决数学几何中的挑战性问题，并产生与实际空间推理问题直接相关的逻辑。

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.