空间推理的初步认识 地图学与地理信息系统 王润科

本次讨论从分为以下四个方面 1 .空间推理的定义。 2. 空间推理的研究机构。 3. 空间推理的研究进展。 4. 我的认识。

究竟什么是空间推理？空间推理具有哪些性质或属性？空间推理的主要研究方向和研究热点有哪些？对这些“领域问题”的正确回答和解释是我们进一步开展学习工作的基础。

空间推理的定义 空间推理是指利用空间理论和人工智能AI (artificial intelligence) 技术对空间对象进行建模、描述和表示,并据此对空间对象间的空间关系进行定性或定量分析和处理的过程。目前, 空间推理被广泛应用于地理信息系统、机器人导航、高级视觉、自然语言理解、工程设计和物理位置的常识推理等方面, 并且正在不断向其他领域渗透, 其内涵非常广泛。空间推理的研究在人工智能中占有很重要的地位, 是人工智能领域的一个研究热点。

首先, 如果利用空间理论对物理对象进行推理，那么任何实际物理对象的空间延伸必定类似于空间区域,而不会类似于点之类的更低维的对象； 在空间推理过程中, 我们必须确定什么样的空间对象是我们可以接受的(即特定空间的本体论)。 本体论的第1个问题是, 什么是空间对象的基元？在数学空间理论中, 点(或点和线)被视为空间对象的基元, 诸如区域之类的扩展空间对象可以被视为点的集合。而在空间推理领域中, 则倾向于将空间区域视为空间对象的基元. 其理由是: 首先, 如果利用空间理论对物理对象进行推理，那么任何实际物理对象的空间延伸必定类似于空间区域,而不会类似于点之类的更低维的对象； 其次, 大多数自然语言提及的“点”也不是精确的点; 第3，如果需要, 研究者可以利用空间区域来定义点。但是, 当我们对一个三维物理对象进行抽象时, 有时需要把一个三维物理对象视为二维甚至一维对象。

本体论的第2个问题是，什么是嵌入空间的本质 本体论的第2个问题是，什么是嵌入空间的本质? 按照惯例, 研究者可以将嵌入空间的本质视为 。 但研究者也可以把嵌入空间想像为离散或有限的, 这样可能对我们的实际应用更有帮助。 本体论的最后一个问题是, 如何为多维空间建模? 一个方法是分别考虑每一维, 每个区域分别向每一个维上作投影,然后在每一维上进行推理。 此方法的不足是两个实际上不重叠的个体, 它们的投影却可能重叠在一起。

空间推理具有以下11项关键属性, 其中,至少前7 项是基本空间推理所必具备的, 其余的为可选项。 (1) 空间推理是以空间和存在于空间中的空间对象为研究对象。我们不能脱离空间和存在于空间中的空间对象来研究空间推理。 (2) 在空间推理过程中运用人工智能技术和方法。 (3) 空间推理处理的是一个或几个推理的问题。 (4) 空间推理是基于空间和存在于空间中的空间对象已经被 建模的前提下。 我们不能在没有模型的情况下讨论空间推理。 (5) 空间推理必须能够给出关于空间和存在于空间中的空间对象的定性或定量的推理结果。 (6) 空间推理必须能够描述空间行为。

(7) 当空间推理模型把问题分解为几个组成部分时, 必须能够描述这些组成部分的相互作用。 (8) 在空间推理过程中, 可能用到空间谓词, 空间中确定的点使某些空间谓词为真, 而使另一些空间谓词为假。 (9) 空间推理应该能够处理带有模糊性和不确定性的空间信息。 (10) 空间推理中应该能够添加和处理时间因素, 即成为时空推理。 (11) 空间推理应该具有空间自然语言理解能力。

2.空间推理的主要研究机构 1.美国国家地理空间数据交换所NGDC (National Geospatial Data Clearinghouse) 所属的USGS (U. S. Geological Survey) 站点是美国国家空间数据基础设施NSDI (National Spatial Data Infrastructure) 的重要组成部分。这个交换所提供了一个来自于U SGS 的查找地理空间信息或空间参考数据的途径, 这些数据是以元数据的形式存在的。这个站点是由USGS 和美国联邦地理数据委员会(FGDC——Federal Geographic Data Committee) 共同维护的。 USGS 根据数据内容可以分为生物学资源信息、地理信息、国家地图绘制信息和水资源信息这4个分布的数据集合。

2.美国国家地理信息和分析中心NCGIA (National Center for Geographic Information and Analysis) 是一个独立的研究联盟，致力于包括GIS 在内的地理信息科学和相关技术的基础研究，成立于1988 年. 这个联盟的3个协会是加利福尼亚大学、布法罗大学和缅因州大学，主要由国家自然科学基金会NSF (National Science Foundation) 资助, 现在, 这个联盟每年得到大约500 万美元的资助.今天,NCGIA 已经成为一个国际的基础研究焦点，它的3个站点吸引了来自世界各地的短期和长期访问者，它的教育节目也满足了不同层次的学生的需要。NCGIA 的研究课题主要包括：空间数据的精度和不确定性、认知的模型和表示等。http//www.ncgia.ucsb.edu

3.欧洲定性空间推理网SPACENET 是一个由多所大学联合的空间推理的网络, 分布在欧洲的有12 个SPACENET 站点, 是由欧盟资助的。由英国利兹大学计算机研究学院主任Anthony Cohn 教授领导, 致力于空间表示和自动推理(尤其是定性空间推理) 以及拓扑和形式化的空间模型。 Cohn, Randell 和Cui 等人曾提出了著名的区域连接演算(RCC) 算法。

匹兹堡大学的空间信息研究组, 是一个致力于空间信息的理解和应用的研究机构。它们的研究主要涉及GIS、超文本导航和科学可视化的特征、空间推理的形式方法和人们对空间认识经验的研究。 慕尼黑大学空间推理研究组, 主要研究方向是定性空间推理. 包括空间位置知识的表示、空间信息传播约束、定性空间推理和神经网络模型的综合。 瑞士洛桑的A I 实验室EPFL , 主要研究方向包括自然语言的语义和逻辑分析、时空推理、语言和感知之间的关系。

3. 空间推理的研究进展 3.1对空间推理的许多研究方向进行分类、归纳和整理之后得到的主要研究方向是： (1) 空间数据库的精度。 (2) 空间关系语言。 (3) 空间推理与地理信息系统。 (4) 空间决策支持系统。 (5) 空间数据的不确定性处理。 (6) 形式化的绘图知识。 (7) 时空推理。

(8) 定性空间推理。 (9) 空间推理的用户界面。 (10) 基于实例(CA SE-BASED) 的空间推理. (11) 空间推理的认知问题。 (12) 空间推理与机器人视觉。 (13) 常识推理。 (14) 区域连接演算RCC-8。

3.2空间推理的研究热点 大量的空间推理文献、近年来召开的国际空间推理学术会议以及Internet 网的空间推理站点都表明, 时空推理STSR (spatio-temporal spatial reasoning)、定性空间推理QSR (qualitative spatial reasoning) 和地理信息系统是空间推理的研究热点。

下面我主要谈谈时空推理和定性空间推理

时空推理 当今世界是在漫长的历史长河中，历经沧桑演变进化而来的。世界中的任何事物和现象都遵循着诞生、生长，直至消失或死亡的自然规律。同样，现代文明和科技的进步无不是人类历史的经验积累和结晶。人类在认识和解释当今世界事物和现象时,不但渴望甚至必须了解它们的过去,而且希望预测未知的将来,以便在必要的时候采取一定措施,使人类社会朝着美好的方向发展。在这绵延不断的历史轨迹中，无不打上了时间的烙印，因此,探索适宜的工具和方法,沿着时间脉络研究和推理客观世界内在机制和时空发展规律,就显得十分重要。

总的来说，影响空间推理结果的因素包括空间因素和时间因素。所谓时空推理是指在空间推理过程中添加时间因素。地表、地下和大气等空间对象的状态不仅受到空间因素的影响, 同时, 从一个漫长的时间过程来看，也必将受到时间因素的影响。可以说, 时空推理是更为一般的空间推理, 或者可以说空间推理是时空推理的一个特例。目前, 时空推理方面的研究还处于起步阶段。下面, 我简单地介绍一些权威学者对时空推理的认识和他们提出的时空推理模型。

1. Richard A. Block 在他的论文“Psychological Time and the Processing of Spatial Information”中指出：“与其说空间为时间提供了一个框架，不如说时间感知为空间感知提供了一个框架”。“位置和持续时间之间、个人经验和常识之间以及期望和回顾之间存在重要的区别”。他提出了上下文时间模型， 并且把它扩展到空间， 模型着眼于哪些变量对持续时间和其他种类的时间体验之间及行为和判断之间的相互作用有影响，这些变量包括实验者的特征、时间周期、时间周期上的活动和时间行为。

2. A. G. Cohn, Z. Cui, D. A. Randell 在他们的论文“Exploiting Temporal Continuity in Qualitative Spatial Calculus”中提出了一个空间知识推理的逻辑框架, 目的是为人工智能系统的表示和推理提供一个形式上的时间和空间的公理理论。 他们的形式方法可以用于时间或空间区域, 并且提供了一套基本关系和推理机。 特别是他们定义了基本关系的合成表, 可以用于检验时空约束, 甚至用于检验区域特征的时空演变。

3. 在论文“Temporal Dynamics and Geographic Information System s”中, Stephen Stead 认为, 现实世界是沿着一条根据数值的时间范围划分的有唯一顺序的时间路线运转。 他借鉴考古应用中的为时间建模的方法, 提出了标准切割时间技术方法, 存储风景快照作为解释背景。 Stead 把已知数据元素表示在四维空间(x , y , z 和t) 中, 这样一来, 就可以为现实世界的过程建模了。2000 年6 月在新奥尔良召开的IEA/A IE22000 研讨会和在德克萨斯召开的AAA I22000 研讨会以及2000年8 月在柏林召开的ECA I22000 等空间推理研讨会, 都是以时空推理为主题的。

定性空间推理 当描述一个空间配置或对这样的配置进行推理的时候, 要获得精确、定量的数据通常是不可能的或不必要的。在这种情况下, 可能要用到关于空间配置的定性推理。 定性空间表示包括许多不同的方面，我们不仅要判定什么样的空间实体是我们可以接受的，同时还要考虑描述这些空间实体之间关系的不同方法。例如, 我们可以仅考虑它们的拓扑结构、大小、形状, 或它们之间的距离。 当然, 这些概念之间并不是完全独立的。

Clarke 用C (x , y ) 表示两个区域x和y 是相互连接的, 所谓连接是指两个由点集构成的区域共享一点 Clarke 用C (x , y ) 表示两个区域x和y 是相互连接的, 所谓连接是指两个由点集构成的区域共享一点. 在区域连接演算RCC-8 系统中, 这种解释被稍加改动为: 共享一点的区域的闭包, 改动后的解释有助于区分区域、区域的闭包和区域的内部. RCC-8 是用于定性空间表示和推理的拓扑结构方法, 定性空间表示和推理中的空间区域是一个非空的拓扑空间子集. 在RCC-8 演算中, 使用8个穷举并且不相交的关系来描述两个空间区域之间的拓扑关系。

另一个拓扑关系表示和推理的方法是“n-交集”表示, 在这种表示方法中, 每一个区域都与3个点的集合联系在一起, 这3个点的集合分别是区域的内部、区域的边界和区域的补。两区域间的关系可以通过用一个被称为9-交集的3×3 的矩阵来刻画, 矩阵的每个元素表示来自每个区域的相应集合的交集是否为空。实际上, 利用一个更为简单的2×2 的4-交集矩阵就可以充分地描述RCC-8 关系。可是, 3×3 的矩阵允许表示更多的考虑到区域和嵌入空间之间关系的集合。

3.3目前的空间推理的研究 近几年, 由于认识到空间知识本质上是定性的, 定性空间推理(qualitative spatial reasoning) 研究成为空间推理研究的主流, 发展出公理化、代数、几何约束满足和基于模型的推理等方法。 下面就主要讨论目前国内的专家学者对空间推理研究。

3.3.1空间推理研究的方法学 廖士中, 王建民, 王海山提出了提出了空间推理一个新的一般框架和研究方法学。 概述了空间推理研究的内容、关键问题和基本方法, 从基本原则、形式框架、研究步骤、表示体系和推理框架等五个方面提出了空间推理研究的方法学, 结合实际研究案例阐述了该方法的合理性与有效性。最后指出了空间推理研究的进一步工作和方向。

1.空间推理研究方法学应以计算有效性和认知合理性为原则, 来评价空间推理的建模方法、表示形式和推理算法。——基本原则 2. 空间推理的形式框架为约束满足问(CSP)。 约束满足问题包含一组变量和一组变量间的约束, 目标是找到所有变量一个或多个赋值, 使得所有约束得到满足。——形式框架 3则空间推理的研究步骤如下。 步骤1. 界定易处理问题类。 步骤2. 基于概念邻域结构建立空间知识表示的层次体系。步骤3. 应用约束满足方法在层次体系中推导结论

4　表示体系 知识表示是概括智能行为的模型, 是人工智能研究中的基本问题之一。 找出被表示世界领域中的结构, 并构造各种保持结构的表示形式, 是各种表示方法的本质。表示有定量表示和定性表示、拟真表示和替代表示。 5 推理框架

(2)定性空间推理的分层递阶框架 分层递阶框架 定性空间推理的分层递阶框架包括空间知识的定性表示、定性建模以及定性推理的基本形式和基本原则。下面首先阐述定性空间推理一般框架的基本原则,然后分别论述空间知识定性表示和定性推理的一般形式和方法。 　 基本原则——分层递阶框架以计算有效性和认知合理性为原则, 来评价定性空间推理的建模方法、表示形式和推理算法。

定性表示是相对于定量表示而言的. 一般地, 定性表示仅表示独特的和主要的特征, 而定量表示以预定的单位表示所有的细节 定性表示是相对于定量表示而言的. 一般地, 定性表示仅表示独特的和主要的特征, 而定量表示以预定的单位表示所有的细节. 在建模方面, 定性表示独立于固定的粒度, 而定量表示以固定的粒度描述事物. 定性表示的性质可总结如下: (1) 适用于识别任务, 而不是重构任务. 定性表示针对给定的问题仅做必需的区分, 而不是以固定的粒度描述所有可能的状态. (2) 常基于比较, 反映量级的相对组织, 而不是绝对信息. (3) 是欠确定的. 定性表示可嵌入特定的上下文或一组对象中, 而不需要包含许多具体信息. (4) 可处理不明确的知识. 定性表示可根据问题的已知条件选择一个合适的粒度、抽象层次来表 示问题. (5) 独立于固定的粒度. (6) 增量性. 尽管单个定性关系的区分能力很弱, 但若干关系的交集可得到任意精细的区分.

下面给出一个定性空间推理分层递阶框架的一般推理方法,并进一步说明其中各步骤的实施方法。 步骤1. 界定易处理问题类。 步骤2. 基于概念邻域结构建立空间知识表示的层次体系。 步骤3. 应用约束满足方法在层次体系中推导。 结论。

则上述实现步骤3 的算法可描述如下： 算法1. RH , 定性空间推理分层递阶层框架定性推理的一般算法. 输入: H , 其中包含各个层次的推理规则，， 输出: 关于CL 的解及选定的层次level. 过程: 　步骤1. level←L ; 　 步骤2. 若level 层为“T”则返回“无解”; 若level 层为“⊥”则返回“平凡解”. 　 步骤3. 若level 层未标记, 则应用 对 进行约束传播, 否则返回“当前表示无法给出解”.

步骤4. 若约束传播的结果是不相容的, 则标记level 层, 　 level←level-1, 　 ←abstraction ( ) , 　转步骤2; 否则, 若约束传播的结果是平凡解, 则 　 标记level 层, 　 level←level+1, 　 ←specification ( ) , 　 转步骤2. 　步骤5. 返回相容解。

分析： 算法RH 中引用了两个子过程abstraction 和specification。这两个过程找出当前概念或关系在上一层(abstraction ) 和下一层(specification) 的概念或关系的闭包, 具有线性时间复杂性。显然算法RH 也是易处理的。

(3)基于规则知识的空间推理研究 空间推理表现为演绎、表达变换、条件推理三种基本形式。作者（沙宗尧 、边馥苓、陈江平、江聪世 ）认为,空间推理有深层的推理,也有浅层的推理,浅层次的空间推理不需要预先知道的领域或认知知识的支持,所以一般不涉及领域知识的表示与利用问题,而深层次的推理结合了人工智能技术,涉及到空间知识的获取、表达与利用,或称为基于规则知识的空间推理。

基于规则知识的空间推理过程即是在空间知识库、模型库、数据库的支持下感知空间数据库中的隐含信息,或在空间知识库、模型库、数据库的支持下能动于空间数据库并制造出满足特定要求的结果,该结果一般也以空间图形的形式表示。空间推理过程反映的是人类认识空间环境并改造空间环境的能动力。基于规则知识的空间推理过程由问题识别、模型调用、知识调用与控制、结果输出四个子过程组成。

1) 问题识别子过程是系统与系统使用者间的交互,需要解决的问题是自然语言的理解。这里仅提供在系统可以识别的情况下进行空间推理并获取结果的过程。 2) 模型调用子过程是系统识别出具体的任务后自动调用一个或若干个处理模型,通过查找模型库中的元信息,可以对系统的模型进行定位并执行。由于模型在模型库中具有惟一标号,因此可以方便地找到解决推理任务的模型。

3) 知识调用与控制子过程是由模型触发的,其过程是根据模型要求的规则知识因子或内容知识因子从知识库中调用知识,如果该知识为规则控制知识,则可能会触发下一级模型的调用,触发从空间数据库中提取地物类型、空间拓扑信息、空间位置等,为空间推理提供预备知识。 4) 结果输出子过程是循环步骤2) 、3) 的执行结果,最终得到目标数据的推理结果,给出满足所提问题条件的图形输出或文字结论。

以上过程中,如何定位到各推理步骤所需要的相关知识及如何利用这些知识是问题的关键。规则知识以产生式方式出现,具有“if ⋯then ⋯”的格式,因而易于进行推理控制。而面向对象的空间知识表示中,以知识类的形式出现,由于知识类具有一定的层次结构,并且通过面向对象的封装、继承和消息机制实现知识类的联系与信息交换,因此可以方便地获取推理结果。

除此之外，对空间推理还有很对的观点，比如陈军提出给予Voronoi图的9-交模型的空间推理，王生生等讨论了A SRA 的公理和基本性质, 研究了A SRA 和RCC5 关系映射中存在的不确定性; 把A SRA 应用于GIS, 提出了基于A SRA 的空间关系判定算法A SRA- RCC等。

4. 我的认识 从上面的专家学者在空间推理方面过的研究可以看出：目前，空间推理广泛的应用在地理信息系统中，而在地理信息系统中，对空间推理中的热点之一——定性空间推理是当前空间关系理论研究的一个难点，理论上还没有突破性的进展。

谢谢大家！