（计算机应用技术专业论文）距离与方向关系的定性推理研究.pdf

重庆大学硕士学位论文中文摘要 摘要 定性空间推理( q u a l i t a t i v es p a t i a lr e 鹳伽【i i l g ) 研究的是人类对几何空间中空间 对象及其关系定性认知常识的表示与处理，它是定性推理和空间推理相结合的产 物。它的主要研究内容包括：视觉对象的识别、认知图和路径规划、人类比喻的 模拟和定性物理的可视化。 方向关系和距离关系的表示是空间关系理论的重要组成部分，也是空间数据 库设计的重要基础，将二者结合起来研究将有助于设计有效的空间查询和有效的 数据处理方式。提高推理的有效性和准确性。这对于提高我国各行业( 特别是城 市规划、建设、管理、与服务) 的数字化水平，促进地理信息系统的发展，都有 着极为重要的学术和实用意义。 论文的主要内容及研究成果有以下几方面： 首先，介绍了定性空间推理和空间关系的基本概念、研究方法、研究内容， 研究现状等情况。 其次，介绍了距离与方向关系相结合的表示模型：锥形与距离划分模型，定 性三角模型。通过一个具体实侈比较了这两种方法。 第三，着重研究了定性三角推理方法。合理地划分了定性角度值和定性距离 值，研究了定往加法，提出了定性减法，并给出了相应的推理模式和规则组合表。 分析了推理过程中路线选择方法，得出了相关结论。给出已知量规模的估算公式。 最后，本论文在上述研究工作的基础上，开发出原型系统，实现了定性三角 推理等功能，验证了该方法的有效性与可行性。 本文对定性空间推理中的距离关系与方向关系的表示和推理作了深入的研 究，丰富和扩展了定性空间表示与推理的理论。通过对定性三角推理方法的研究， 增强了该方法的分析处理能力，拓宽了适用范围，提高了有效 生和可行性。 关键词；定性空间推理，距离关系，方向关系，定性三角推理 重庆大学硕士学位论文 英文摘要 a b s t r a c t q u a l i t a t i v es p a t i mr e a s o n i n ga n a l y z e sa n dp r o c e s s e st h eh u m a nc o g n i t i o no f g e o m e t r i cs p a t i a l o d m n l o nk n o w l e d g e , i ti sg e n e r a t e db yc o m b i n i n gq u a l i t a t i v e r e a s o n i n ga n ds p a t i a lr e a s o n i n g i ti n c l u d e sf i e l d ss u c ha sr e c o g n i t i o no fo p t i co b j e c t s ， r o u t e sp r o g r a m m i n g , m a pc o g n i t i o n , s i m u l a t i o no f h u m a np a r a b l ea n ds oo n r e s e a r c ho fd i r e c t i o n a lr e l a t i o na n dd i s t a n c er e l a t i o ni sa ni m p o r t a n tp a r to ft h e t h e o r ya b o u ts p a t i a lr e l a t i o n , a n di ti sa l s ot h ei m p o r t a n tb a s eo f d e s i g ns p a t i a ld a t a b a s e i n t e g r a t et h e s et w of a c t o r sw i l ld om u c hg o o d t od e s i g ns p a t i a lq u e r ya n dd a t ap r o c e s s i ti sg r e a t l ys i g n i f i c a t i v eb o t hi ns c h o l a r s h i pa n dp r a c t i c a l i t yt od i g i t a l i z ec i t yp l a n n i n g , c o n s t r u c t i o n , m a n a g e m e n ta n ds e r v i c e s ，a n dt oa c c e l e r a t et h ed e v e l o p m e n to f g i s t h em a i nc o n t e n t sa n dp r o d u c t i o n so f t h i sd i s s e r t a t i o na r ea sf o l l o w s ： f i r s t l y , t h i st h e s i si n t r o d u c e dt h ec o n c e p t s ，m e t h o d s ，c o n t e n t sa n dr e c e n ts t u d yo f q u a l i t a t i v es p a t i a lr e a s o n i n ga n ds p a t i a lr e l a t i o n s e c o n d l y , t h i st h e s i si n t r o d u c e dt h ed e n o t a t i v em o d e lw h i c hi n t e g r a t e st w of a c t o r s ： d i s t a n c ea n dd i r e c t i o n t h e r ea r et w oi m p o r t a n tm o d e l s ，o n ei sb a s e do ne x t e r n a l r e f e r e n c ef r a m e , w h i c hd i v i d e sd i r e c t i o ni n t oc o n e sa n dd i s t a n c ei n t os e g m e n t s ，t h e o t h e ri st h eq u a l i t a t i v et r i g o n o m e t r y t h e n , t h e s et w om e t h o d sa r ec o m p a r e da n d a n a l y z e db yu s i n gt h e mt or e s o l v et h es a m ep r o b l e m t h i r d l y , t h i st h e s i sf o c u s e so nq u a l i t a t i v et r i g o n o m e t r yr e a s o n i n g a b o v ea l l ，t h e q u a l i t a t i v ev a l u e so fa n g l ea n dd i s t a n c ea r ed e f i n e dr e a s o n a b l y t h e nq u a l i t a t i v ea d d i s s t u d i e d , q u a l i t a t i v es u b t r a c ti sp r e s e n t e d ，a n dt h er u l e so fr e a s o n i n ga r eg i v e nt o o f u r t h e r m o r e ，8 0 m eu s e f u lc o n c l u s i o n sa r ed r a w nb ya n a l y z i n gh o wt os e l e c tr e a s o n i n g r o u t e s a r e rt h a t ，af o r m u l ai sg i v e nf o re s t i m a t i n gh o wm a n yc o n d i t i o n sa tl e a s tw e m u s tk n o wb e f o r eq u a l i t a t i v er e a s o n i n g f i n a l l y , b a s e do nt h er e s e a r c hw o r ka b o v e , w ed e v e l o p e dap r o t o t y p es y s t e m ， w h i c hr e a l i z e dt h em o d u l e ss u c ha sq u a l i t a t i v et r i g o n o m e t r yr e a s o n i n g , a n dv a l i d a t e t h ev a l i d i t ya n df e a s i b i l i t yo f t h i sm e t h o d t h er e s e a r c h e si nt h i sp a p e re n r i c ha n de x p a n dt h et h e o r i e sf o rr e p r e s e n t a t i o na n d r e a s o n i n go fq u a l i t a t i v ed i r e c t i o n r e l a t i o na n dd i s t a n c er e l a t i o n t h e s er e s e a r c h e s p r o v i d et h ep r o c e e d i n gc a p a b i l i t y , v a l i d i t ya n df e a s i b i l i t yo fq u a l i t a t i v et r i g o n o m e t r y , i i 重庆大学硕士学位论文 英文摘要 a n dt h er a n g eo f u s i n gt h i sm e t h o da r ee x p a n d e dt o o k e y w o r d s ：q u a l i t a t i v es p a t i a lr e a s o n i n g , d i s t a n c er e l a t i o n s ，d i r e c t i o n a lr e l a t i o n s ， q u a l i t a t i v et r i g o n o m e t r yr e a s o n i n g i h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重废盔堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：豫t 卜音幻签字日期：弘d 年妨；。日 学位论文版权使用授权书 本学位论文作者完全了解重庞盍堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重麽太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( j l 巧。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：彳年小彩 导师签名： 签字日期：2 。叼年厂月；o 日 签字日期： 研虿 2 品净s 其夸b 重庆大学硕士学位论文 1 绪论 1 绪论 1 1 研究背景及现状 1 1 1 定性空间推理 定性空间推理是定性推理和空间推理的一个重要组成部分，与二者既有区别 又有联系，是二者相结合的产物。 定性推理( q r ，q u a l i t a t i v er e a s o n i n g ) 是对物理系统的行为、特征的描述、 预测、诊断和解释，它涉及具体系统的领域知识。它是通过对( 物理) 系统的结 构、行为、功能以及它们之间的关系和因果性迸行研究，以探索人类常识( 定性) 推理机制为目的，从而有效地完成各项求解任务的一种跨领域的推理方法体裂”。 人工智能中的定性推理理论源于对物理现象的研究，早期的工作常常是在特 定的论域中，比如针对动力学问题、流体力学问题和热流等问题进行讨论。1 9 7 7 年，r c i t e r 发表了第一篇定性推理方面的论文。1 9 8 4 年，( a r t i f i c i a li n t e l l i g e n c e ) 杂志出版了定性推理专辑，刊载了d ek l c e r 、f o r b u s 和k u i p e r s 等人关于定性推理 的奠基性文章，标志着定性推理开始走向成熟。1 9 9 1 年，( a r t i f i c i a li n t e l l i g e n c e ) 杂志出版了定性推理专辑( - - ) ，标志着定性推理又进入了一个重要阶段。 空间推理( s p a t i a lr e a s o n i n g ) 是指利用空间理论和人工智能a l ( a r t i f i c i a l i n t e l l i g e n c e ) 技术对空间对象进行建模、描述和表示，并据此对空间对象间的空间 关系进行定性或定量分析和处理的过程【2 】。空间推理的研究起源于2 0 世纪7 0 年代 初，最初是以量空间为研究对象，2 0 世纪8 0 年代，由于计算机图形学、计算机视 觉、图像处理、机器人学、计算复杂性、空间数据库、自然语言处理和专家系统 等领域都需要研究空间知识的表示和处理，因而形成了空间推理这新的专门的 研究领域【3 1 。多维的并且不能通过单一的纯量充分表示的空问，只是在近年成为了 知识表示中的一个重要研究领域。由于空间推理的研究对象的转变，极大地扩展 了空间推理的应用领域，使空间推理的理论和应用研究近年来有了长足的进展。 在国外，近年来成立了许多专门从事空间推理方面研究的协会和联盟，如 n c c l a ( n a t i o n a lc e n t e rf o rg e o g r a p h i ca n da n a l y s i s ) 、u s g s ( u s g e o l o 舀c a ls u r v e y ) 、 欧洲定性空间推理网s p a c e n e t 以及匹兹堡大学的空间信息课题组和慕尼黑大学 空间推理课题组等等。国际知名期刊a r t i f i c i a li n t e l l i g e n c e 近年来发表了许多篇空 间推理方面的文章，而且呈逐年增长的趋势，这可以从这本期刊近年来的总目录 中看出。大量的空间推理文献、近年来召开的国际空间推理学术会议以及i n t e m e t 网的空间推理站点都表明，时空推理s t s r ( s p a t i o t e m p o r a ls p a t i a lr e a s o n i n g ) 、定 性空间推理q s r ( q u a l i t a f i v es p a t i a lr e a s o n i n g ) 等是当前空间推理的研究热点。 重庆大学硕士学位论文1 绪论 目前，空间推理被广泛应用于地理信息系统、机器人导航、高级视觉、自然 语言理解、工程设计和物理位置的常识推理等方面，并且正在不断向其他领域渗 透，其内涵非常广泛。空间推理的研究在人工智能中占有很重要的地位，是人工 智能领域的一个研究热点【4 】。地理信息系统是空间推理应用得最为广泛的领域之 一，也是空间推理的研究热点之一。 随着研究的深入，近几年人们逐渐认识到，空间推理本质上是定性的，空间 推理的关键是形状的定性表示，所以研究空间推理的重点就是研究定性空间推理。 本论文强调定性空间推理是空间推理的重要组成部分。实际上，定性空间推理也 是定性推理的一个重要组成部分【5 1 。 定性空间推理( q s r ，q u a l i t a t i v es p a t i a lr e a s o n i n g ) 是对定性空间关系的表示、 分析与处理，它研究的是人类对几何空间中空间对象及其定性关系认知常识的表 示与处理过程f 6 l 。也就是说，定性空间推理是从几何、使用和功能三个方面研究空 间知识的表示和处理，它的主要研究内容包括：视觉对象的识别、认知图和路径规 划、人类比喻的模拟和定性物理的可视化。近几年，由于认识到空间知识本质上 是定性的，定性空间推理( q m l i t a t i v es p a t i a lr e a s o n i n g ) 研究已成为空间推理研究的主 流，发展出公理化、代数、几何约束满足、基于模型的推理及组合表等方法。 目前，将a l l e n 的时态逻辑与r a n d a l l 的空间逻辑结合起来，形成了空间、时 间、连续运动的表达逻辑【7 】，另外从定性空间推理派生出来的空阃规划理论，可用 于为一组几何对象寻找满足组约束的分布设计，有关方法主要用于设计自动化、 定性建模等领域。在这一领域己取得了一些较实际的成果，如约束满足问题( c s p ) 求解理论，而实际上很多定性空间规划都是个几何约束满足问题叼。 1 1 2 空间关系 空间关系是指地理实体之间存在一些具有空间特性的关系【s 1 。在g i s 中，空间 关系是空间查询与分析的基础，它包括拓扑关系、方向关系、度量关系。其中拓 扑关系是指在拓扑交换( 旋转、平移、缩放等) 下保持不变的空间关系，即拓扑 不变量，如对象之间的相离和相交关系；方向关系描述了对象在空间中的某种排 序，如前后、东西等等；度量关系是用某种度量空间中的度量来描述的对象之间 的关系，如对象之间的距离。 空间关系表示的基本任务是以数学或逻辑的方法区分不同的空间关系，给出 形式化表示。其意义在于澄清不同用户关于空间关系的语义，为构造空间查询语 言和空间分析提供形式化工具 9 1 。要准确有效地描述空间目标的位置，这三方面的 关系缺一不可。由于空间问题固有的复杂性和不确定性，空间关系的表示和推理 普遍采用定性的方法【lo 】。 作为空间关系的重要组成部分，空间方向关系( s p a t i a ld i r e c t i o nr e l a t i o n s h i p ) 2 重庆大学硕士学位论文1 绪论 的表示和分析不仅能够弥补现有地理信息系统数据库的空间特征存储、提取、查 询、更新等操作的不足，而且有利于加强现有地理信息系统对空问分析及辅助决 策的能力。目前，关于方向关系的推理模型包括以下几种：p r e q u e t t j 提出了一种 基于锥形模式的任意多边形方向关系判定算法；f r a n k t l 2 】贝提出了一种基于投影模 式的方向关系推理模型；s h a s h is h e k h a r 1 3 】等利用面向对象的方法建立了一个基于 矢量概念的方向推理模型；g e r a n df l i g o z a t _ 【14 】则建立了一个定性三角模型的方向 推理模式。但上述所有方向关系推理模型都是探索性的，它们只在特定类型空间 目标的方向关系推理中得到实际应用，其中的一个主要原因是目标的形状与几何 关系迥异。此外，空间方向关系究竟是一种定性空间关系还是定量空间关系，其 描述的精度以多少为合适学术界历来存在争议。澄清这一问题有助于在对空间方 向关系进行研究时确定空间方向关系数据库的建立、查询和推理方法，为空间分 析的可靠性提供理论依据。对于空间方向关系定性的一面，到目前为止学术界的 观点基本趋于肯定，因为运用空间方向关系进行定性推理是人们每天生活的最基 本思维活动，大部分的专家也直接把方向关系作为定性关系对待，如h e m a n d e z 、 c o h n 、f r e e m a n 、h a a r 、o l i v i e r & g a p p 、h o n g 、s h a r m a 等。e g e n h o f e r & g o l l e d g e 、 g o y a l 等认为空间方向关系也属于定量关系，o o y a l 以两点方向角精确计算为例进 行了论证。陈军和赵仁亮认为空间方向关系是一种具有顺序的定性关系，定性关 系与定量关系之间并不是绝对的，而是可以互相转换的。 另一方面，由于对象间空间关系的描述形式各不相同，对象间的空间关系是 极为复杂多样的，所以拓扑空间关系成为空间关系研究的重点和难点。一般说来， 对象间的空间关系与对象的维数、形态、大小及其所在空间的维数有关，各类拓 扑空间关系也存在着一定的联系。目前，拓扑空间关系的描述已有三种基本的方 法【l5 】：基于点集拓扑的四元组、九元组和维扩展法【1 6 1 。这些方法已能够较好地描 述两个空间对象的交集不为空的拓扑关系。但是还不能比较好地描述两个空间对 象的交集为空的拓扑关系。多种拓扑关系描述方法在这3 种基本描述方法的基础 上发展起来，例如文献【1 5 】对文献 1 7 】作者提出的拓扑空间关系描述方法作了适当 的改进，提出了基于v o r o n o i 图的维扩展描述法，文献1 8 ，1 9 1 将c l e m e n t i n i e t a l 所定义的维数扩展法加以扩充，提出了形式化地描述三维空间对象之间拓扑空间 关系的方法，并在此基础上，定义了三维拓扑空间关系的最小集。 由于方向关系和拓扑关系在空间关系中的重要地位以及它们在空间推理中所 起到的重要作用，关于这两方面的研究历来受到众多学者的关注，出现了大量的 文献资料，也取得了不错的成果。在以前的研究工作中，空间知识的定性表示多 局限于拓扑关系【批2 1 强2 3 2 4 1 和方向关系【2 i2 6 孔蕊2 9 1 这两方面，国内外在这方面的 研究比较成熟，提出了很多有效的推理模型和方法。传统上，拓扑关系的定性和 重庆大学硕士学位论文 l 绪论 形式化描述方法主要采用基于点集拓扑学的“n 一交集”模型( 例如4 元交、9 元交) 和基于区域连接的r c c 方法 9 1 。方向关系的定性表示主要有锥形法和投影法【8 1 。 近年来，用定性方法描述和表示空间知识越来越被广泛使用。随着定性空间 推理应用的发展，人们逐渐认识到距离关系在空间推理当中的重要作用，在考虑 空间问题的时候加入距离的因素能提高定性描述的准确性和推理结果的有效性。 拓扑关系与方向关系相结合来描述物体的位置信息，这种方式主要用于小范围区 间的情况，例如一个房间中的物体。在涉及大范围区间( 例如地理空间) 的情况 下，如果只有拓扑关系和方向关系显然是不够的，因此在描述物体的空间位置和 进行物体之间的空间信息的推理时，距离关系就显得犹为重要。距离与方向相结 合的定性空间推理研究也随之发展起来。 国外对距离的研究大约开始于上世纪9 0 年代，最初大量的相关工作都集中于 “尺度”的定性表示。f r a n k 在1 9 9 2 年明确地提出了在地理空间中距离( 远、近) 和基本方向( 东、南、西、北) 的定性推理方法，这是基于转化和合成这两个操 作的代数方法而建立的，并得到了一些初步的近似结果【2 5 】。德国的d a n i e l h e m a n d e z 和意大利的e l i s e oc l e m e n t i n i 、p a o l i n od if e l i c e 等人进一步提出了优于 f r a n k 的距离模型，在他们的模型中距离区间的划分更随意，一般遵循单调性 ( m o n o t o n i c i t y ) 、范围约束( r a n g er e s t r i c t i o n ) 、量级顺序( o r d e r so f m a g n i t u d e ) 这三 个规则 2 h ，使得推理的情况更具有普遍性，也拓宽了距离定性推理的适用范围。 随后，距离关系与方向关系相结合的研究逐渐发展起来，成为空间推理的新趋势。 目前，方向和距离相结合的表示与推理模型主要有两种。第一种是文献 2 1 】中所提 到的锥形与距离划分相结合的模型【2 l 捌，该模型是基于外部参考框架而建立，对 方向和距离的区分直观明了，能够初步确定两向量合成时距离的上下界。第二种 是本文要着重研究的定性三角模型3 1 l ，该模型基于直接参考框架建立，对距离和 角度进行定性划分，并推出组合表，当己知三角形的两相邻边及其夹角时就可以 根据组合表推出其余两个角和另外一边的取值范围。该方法的优点是推理简单， 思路明确，但在使用时必须建立物体间的参考框架且推理结果依赖组合表。l a t e c k i 和r o h r i g 在1 9 9 3 年提出了种在认知地图中推理定性角度关系的方法【3 2 】。他们的 研究主要是关于当已知三角形中角的方向( 顺时针、逆时针) 和角的定性划分( 锐 角、钝角) 时，三角形的定性描述。但这种方法在两个角合成时不定能得到唯 一确定结果。随后，j i m i n gl i u 在此基础上进一步扩展了以前的空间定性度量公式 和定性三角规则，细化了对距离和方向定性划分，给出了规则组合表【3 2 1 。这种方 法在定性划分不足够细的情况下会使推理结果不精确。本论文在该方法上进行了 改进，提高结果的准确性，并重新给出了推理组合表。 相对来说，国内关于方向和距离相结合的定性表示与推理的文献比较少，但 4 重庆大学硕士学位论文 1 绪论 近几年来对这方面的研究也越来越重视，使得这一课题成为新的研究热点。 1 2 研究的目的与意义 近年来，空间推理的理论发展非常迅速，国内外的各种研究团体、科研单位 都对它引起了高度的重视。随着空间推理研究的深入，定性空间推理的研究成为 空间推理研究的主流。同时，定性空间推理的研究领域也从人工智能拓展到更宽 广的领域，地理信息系统成为空间推理最成熟也最广泛的应用领域，定性空间推 理的发展也促进了g i s 的发展。定性空间推理的研究方法主要应用在空间关系的 描述和分析上，因此，研究、分析、探讨空问方向关系和定性空间推理，以及它 们的结合有着重要的学术和应用意义。 空间推理是推理的一种类型，其主要特征表现为推理所依赖的信息涉及空间 数据。空间推理可广泛运用于许多领域，如机器人路径规划、自动车辆控制、空 间货流管理、建筑布局、印刷电路板、g i s 等等【2 l 。这一课题的发展与成熟会在众 多应用领域产生积极影响。 近几年来随着研究的深入，人们逐渐认识到空间知识本质上是定性的，所以 空间推理的重点就是研究定性空间推理。在很多情况下，空间关系的定性描述比 定量描述包含更多的信息量。一般来说在现实生活中，人们主要靠认知和经验获 得空间位置信息，而获得和处理精确的、定量的数据又相当困难，所以对空间关 系进行描述与推理的时候采用定性方式会使得到的结论更具有说服力、更易于理 解、判断和使用。认识空间关系的本质与判定机理，寻找空间关系形式化描述、 表达和操作的方法与途径，便是空间关系理论研究的目的所在。方向关系和距离 关系的表示是空间关系理论的重要组成部分，也是空间数据库设计的重要基础，将 二者结合起来研究将有助于设计有效的空问查询和有效的数据处理方式并提高推 理的有效性和准确性。 本论文的目的，就是希望在对定性空间推理进行全面、系统研究的基础上， 利用距离关系与方向关系相结合的方式，探讨统一的形式化表示与推理模型以及 推理方法，并据此开发相应的功能模块。研究、分析距离与方向关系的定性推理 技术，对于提高我国各行业( 特别是城市规划、建设、管理、与服务) 的数字化 水平，促进地理信息系统的发展，都有着极为重要的学术和实用意义。 1 3 研究的内容 本文研究的内容主要包括以下几部分： 距离关系与方向关系表示方法的研究 重庆大学硕士学位论文 1 绪论 锥形与距离划分相结合的模型 定性三角推理模型 这两种方法的比较和分析 基于距离的推理的研究 距离划分的方式 定性距离值的定义方式 关于距离的定性推理方法 距离与方向两者的关系及结合的研究 定性加、减运算 针对具体实例进行推理 将推理模型应用于实际 定性三角推理原型系统开发 论文的结构和内容大致如下： 绪论：介绍本文的研究背景、研究的目的与意义以及研究的内容 定性空间推理与空间关系的表示 夺关于定性空间推理的研究 夺关于符合人类认知常识的表示模型的研究 夺各向异性的距离表示模型的研究 基于距离与方向关系的推理 夺锥形与距离划分相结合的模型的表示与推理方法 夺关于定性三角推理方法的研究 两种方法的比较与分析 知识库的设计 夺 知识库的基本概念 知识库的基本结构和内容 夺已知量规模分析 原型系统开发与实现：使用d e l p h i 开发一个原型系统验证论文中方向与距 离关系和空间推理的若干问题。 总结：对论文中提到的距离关系和方向关系的定性推理做一个总结，对存 在的问题做一个分析，以及下一步研究的方向和工作。 6 重庆大学硕士学位论文 2 定性空间推理与空间关系 2 定性空间推理与空间关系的表示 2 1 定性空间推理 当描述一个空间配置或对这样的配置进行推理的时候，要获得精确、定量的 数据通常是不可能或不必要的。在这样的情况下，可能要用到关于空间配置的定 性推理【3 3 】。下面，我们首先介绍定性推理与空间推理的基本概念，然后再分析定 性空间推理与它们之间的区别与联系。 2 1 1 定性推理 定性推理的出现有以下5 个主要的原因网： 1 ) 现实世界的常识推理 常识的使用与表示一直是人工智能中未解决的难题。常识的特点是可以利用， 但不定可以解释，而且不精确、不完备，但在很多情况下却极为有效。常识大 致可分为两类： 定性知识。这类知识有明确的结构，但不必精确描述各个环节的精确值，而 只能或只需陈述其变化趋势。也就是说，不使用数量来描述系统所表现的行为。 基于经验的知识。这类知识大多不能清楚地陈述出它的结构，但却是人类思 维活动中最有效的知识。 刻画定性知识是促成定性推理研究的最主要因素之一。人们在日常生活中可 以轻而易举地完成常识推理。比如向空中抛一个小球，可以预n d , 球首先继续向 上运动，而速率逐渐减小至零，其后以逐渐增大的速率向下运动直至撞到地面。 当然，也可以建立数学方程求解小球的运动轨迹来得出同样的结论，然而人们在 进行常识推理时既不需要数学知识也无须知道精确的物理定律，这就促使定性推 理去研究这种常识推理的知识类型以及人们是如何运用它的。 2 ) 特定领域的定性推理 人们不仅进行定性常识推理，在特定知识领域也常常进行定性推理。在复杂 的情况下这往往很有好处。有时只有关于行为的定性知识，而关于变量及其关系 的精确信息都不可能获得，在这种情况下就需要做出定性分析与预测。比如旅游 人数增加，可以预测风景名胜区的空气污染程度就会增大。这时，很难确切地知 道两者数量之间的数学关系。另外，在有些情况下( 比如只需要定性行为描述) ， 详细精确的定量信息也是不必要的。 3 ) 从第一原则出发的基于模型的推理 专家系统成功的一个主要因素在于大量地运用启发式知识，这种依赖于领域 的浅层知识能够非常有效地缩小搜索空间，但在超越它们狭窄的问题领域之后， 7 重庆大学硕士学位论文 2 定性空间推理与空间关系 即使是面对非常简单的问题也束手无策。另外在进行不同人物之间的知识转换时， 即使是同一形式的知识也会产生不同的理解。造成这种现象的主要原因在于目前 的专家系统缺乏领域的基础知识，这就引发了从第一原贝i j ( f i r s tp r i n c i p l e s ) 出发建构 系统的思想。所谓第一原则指的是使用深层( 基础) 知识而不是浅层( 启发式) 知识来建模和推理。如何表示和使用这种深层知识也是定性推理研究的一个重要 的课题。 4 ) 动态特性与时态推理 许多情况下需要了解系统的动态特性以及场景随时间变化的情况，而目前的 专家系统大多只能进行静态分析推理，缺乏时间的良好表示以及时态推理机制。 数字仿真虽然能对随时间变化的行为进行推理，但需要大量繁琐的数字计算。定 性推理研究的目的，就是要弄清楚如何进行定性行为时态推理以及如何有效地表 示相应的知识以利于问题求解。 5 ) 因果推理 因果推理是人类推理的种主要形式。因果性在人类认识世界的过程中占有 举足轻重的地位，a 引起b ”这种形式在日常生活中司空见惯。因果推理不仅需要 对系统的行为作出定性分析预测，而且要能够给出系统行为的因果解释。因而， 因果推理也成了促成定性推理研究的主要因素之一。 定性系统的构成 定性系统对实际物理系统的描述由三部分构成：结构描述、行为描述和功能 描述。 结构描述是用定性的形式表示实际物理系统的结构，并体现实际物理系统的 物理量及其相互作用关系。结构是确定定性推理模型的关键，研究者们往往根据 描述对象的不同采用不同的结构模型。 行为是实际物理系统的定性状态及其变化过程。行为描述是用定性的形式表 示实际物理系统中的物理量及其相互作用构成的网络的整体行为( a g g r e g a t e b e h a v i o r ) 。不同的结构描述模型将导致完全不同的行为描述。 功能描述是用定性的形式表示实际物理系统的行为表现与使用者目标的一致 性，这往往是针对人造系统而言的。功能描述是较行为描述更高层次的描述，它 是对实际物理系统行为表现的一种理解。 定性系统首先建立实际物理系统的结构描述，在此基础上通过定性预测得到 实际物理系统的行为描述，这个过程就是从结构描述到行为描述的转换过程，最 后通过分析系统的整体行为表现，得到实际物理系统的功能描述。 定性推理的基本要素 定性推理的基本要素包括：量空间、本体基元、建模原则、因果性等。 重庆大学硕士学位论文 2 定性空间推理与空间关系 1 ) 量空间 从定性推理研究的论域出发，可以区分两类不同的定性推理：一类论域中的变 量是连续变化的，另一类论域中的变量是离散变化的。比如，诊断和验证讨论的 都是数字化问题，属于离散型的定性推理研究，而其它大部分工作都属于第一类 研究范畴。对于第一类定性推理研究，必须把连续的论域定性量化为一个离散的 符号集，使得选择在同一个开域内的值表现出定性一致的行为性质，而边界值则 反映出发生重要转化的位置。沿用h a y e s 在n a i v ep h y s i c sm a n i f e s t o ) 一文中的 习惯，一个连续空间的离散化表示称为量空间( q u a n t i t ys p a c e ) 。最简单的量空间是 s = + ，0 ， ，分别表示正数、零和负数。关于量空间的选择、抽取和转换已有大量 研究工作。 2 ) 本体基元 定性推理模型必须有效地表示结构知识和行为知识。结构描述是以本体基元 ( o n t o l o g i c a lp r i m i t i v e s ) 为基础的。基元是实际物理系统结构中具有独立功能的最小 单元f l 】，不同基元的选择确定不同的结构描述，不同的结构描述确定不同的定性模 型。本体基元的选择一般应满足两个条件：一是表示有意义常识的最小单元；二 是能够描述所有的物理过程。例如，r c c 理论中，基元选择了区域( r e g i o n ) 。 3 ) 建模原则 从实际物理系统建立定性模型必须遵循以下3 个原则： 曲可合成性( c o m p o s i t i o n a l i t y ) 要求系统的行为描述必须从系统的结构中得出。在建立物理系统的结构描述 时，通常把它分解为子部件( c o m p o n e n t ) ，然后建立每个部件的结构描述及部件之 间相互作用的描述，这样，系统结构就由部件、部件行为和部件间的联系组成。 每个部件都表现出一定的行为，部件行为之间存在相互作用，实际物理系统的整 体行为能通过一定的方法从部件行为及它们之间的相互作用推导出来。 b ) 局部传播性( l o c a l i t y ) 在定性物理系统中，两个位置之问是否存在局部性是由它们之间是否存在直接 的物理连接来定义的。定性推理要求“影响( e f f e c t ) ”只能通过特殊的物理连接局部 传播，也就是部件的行为和状态变化只与直接相邻或直接相关的部件有关。对这 种局部传播规则的解释即是所谓的因果性( c a u s a l i t y ) 。 c ) 功能性( f u n c t i o n a l i t y ) 定性推理设计出来的系统必须具备一定的功能，它反映了系统行为与人类目标 之间的关系。功能是不同于行为的更高层次，由系统的部件功能构成系统的整体 功能，对系统功能的推理有利于对系统行为的理解以及系统设计中的优化。 定性方法与定量方法的区别 9 重庆大学硕士学位论文2 定性空间推理与空间关系 定性方法和定量方法虽然在本质上有所不同，但都是对实际物理系统的结构和 行为进行描述与分析。传统的定量方法能给出实际物理系统的精确描述，但不具 备推理能力；定性方法具备推理能力，能表达实际物理系统中的因果关系，能在 较高层次上给出系统的宏观描述，但在要求精确描述物理量时则显得无能为力， 它是以放弃对物理量描述的精确性为代价换取了对实际物理系统的推理能力。这 两种方法在一定程度上具有互相补充的性质。 2 1 2 空间推理 空间推理的属性 空间推理具有以下1 1 项关键属性【3 5 1 ，其中，至少前7 项是基本空间推理所必 须具备的，其余的为可选项。 1 1 空间推理是以空间和存在于空间中的空间对象为研究对象。不能脱离空间和 存在于空间中的空间对象来研究空间推理。 2 ) 在空间推理过程中运用了人工智能技术和方法。 3 ) 空间推理处理的是一个或几个推理的问题。 4 ) 空间推理是基于空间和存在于空间中的空间对象已经被建模的前提下。不能 在没有模型的情况下讨论空间推理。 5 1 空间推理必须能够给出关于空间和存在于空间中的空间对象的定性或定量 的推理结果。 6 1 空间推理必须能够描述空间行为。 7 ) 当空间推理模型把问题分解为几个组成部分时，必须能够描述这些组成部分 的相互作用。 8 ) 在空间推理过程中，可能用到空间谓词，空间中确定的点使某些空间谓词为 真，而使另一些空间谓词为假。 9 】空间推理应该能够处理带有模糊性和不确定性的空间信息。 1 0 ) 空间推理中应该能够添加和处理时间因素，即成为时空推理。 1 1 ) 空间推理应该具有空间自然语言理解能力。 空间推理的基本内容 通过总结和分析，我们得出空间推理的主要内容可以归纳成以下几个方面： 1 ) 空间数据库的精度 2 ) 空间关系语言 3 ) 空间推理与地理信息系统 4 ) 空间决策支持系统 5 ) 空间数据的不确定性处理 6 ) 形式化的绘图知识 i o 重庆大学硕士学位论文2 定性空间推理与空间关系 7 ) 时空推理 8 ) 定性空间推理 9 ) 空间推理的用户界面 l o ) 基于实例( c a s e - b a s e d ) 的空间推理 1 1 ) 空间推理的认知问题 1 2 ) 空间推理与机器人视觉 1 3 ) 常识推理 1 4 ) 区域连接演算r c c 8 空间推理的方法学 空间推理从几何、使用和功能三个方面研究空间知识的表示和处理，主要研 究的内容包括：空间推理与机器人视觉、形式化的绘图知识、空间关系语言、定 性空间推理等等。近几年，由于认识到空间知识本质上是定性的，定性空间推理 ( q u a l i t a t i v es p a t i a lr e a s o m g ) 研究成为空间推理研究的主流，发展出公理化、代数、 几何约束满足和基于模型的推理等方法【3 6 1 。 公理化方法以逻辑学或部分学( m e r e o l o g y ) 为基础，选择组基本的关系和谓 词，建立一类空间概念和关系的公理和推理规则，以此表示并处理空间知识。 代数方法把空间关系作为项来处理。在构造出基本空间关系的原子复合表后， 既可以利用约束满足算法通过实现关系集的复合运算完成推理，也可以建立全部 关系集复合运算的完全复合表，通过查表实现推理。 几何约束满足方法充分表示并利用几何领域的约束，通过约束满足方法实现 空间知识的表示和推理。 基于模型的方法首先建立空间知识的一种模型，如位形空间、符号投影串等， 然后把空间推理问题归约为经典的定性推理问题。 这些方法是空间推理的基本方法【靳l ，也是空间推理一般框架和方法学的基础。 在此基础上，人们提出了各种各样的空间推理一般框架和方法学，如f o r b u s 在不 足猜想的基础上提出空间推理的m d p v 框架，r o h r i g 提出了空间推理的序理论， h e m a n d e z 提出了许多建设性的构想，廖士中、石纯一等提出了分层逼近方法， k u i p e r s 在空间知识t o u r 模型的基础上进一步提出了s s h 模型。这些一般框架 和研究方法促进了空间推理的发展，开辟了空间推理研究的新局面。 上述这些概念的关系如图所示： 重庆大学硕士学位论文 2 定性空间推理与空间关系 审瓣箍理一般氍鬃翻商泼学 静缮遥避蓐 m d p v 蜒禁序残逾 辘 彳卜确 窀麓雅理的壤奉方穗 惩秘鳓寐满 萋霪缀繁的 凳璎纯痊滤 代数方法 避蠢缓 图2 1 空间推理的基本方法、一般框架和方法学及两者的关系 f i 9 2 ，1b a s i c m e t h o d s g e n e r a l t i a m e w o r k m e t h o d o l o g yo f s p a t i a lr e a s o n i n ga n d t h e i r r e l a t i o n s 2 1 3 定性空间推理与定性推理、空间推理之间的关系 定性空间推理( q s r ，q u a l i t a t i v es p a t i a lr e a s o n i n g ) 主要是对几何形状或者运动 性质进行