Computational Logic of Euclidean Spaces

我们在日常生活中遇到的许多空间信息都是定性的，而不是定量的。因此，例如，我们可以知道两个物体中哪一个更近，而不需要测量它们的距离；我们可能认为一个物体是凸形的，而不能描述它的精确形状；或者我们可能识别地图上的两个区域共享一个边界，而不知道描述它的方程。这一观察结果促进了人工智能内部各种用定性空间信息进行推理的形式主义的发展。尽管在分析这种形式主义的数学基础和计算特征方面取得了实质性进展，但大多数进展集中在对非常一般的拓扑空间类中涉及(通常)任意区域的高度抽象问题的推理系统上。当然，对实际问题感兴趣的几何实体是一般拓扑空间的公证子集，而不是2维和3维欧氏空间的数学上非常好的区域；此外，这些问题所涉及的几何性质和关系通常不仅是拓扑的，而且是仿射的，甚至是度量的。综合起来，这些因素严重限制了当前定性空间推理形式主义的实际有效性。克服这一限制代表着一个令人兴奋的数学和计算挑战。我们建议通过利用数理逻辑、几何拓扑和代数几何的发展来应对这一挑战，而人工智能中的空间推理文献迄今未能完全利用这些发展。具体地说，我们将研究空间和时空逻辑的计算性质，用于推理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.