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.