（计算机应用技术专业论文）基于区域延伸定性空间表示及推理的研究.pdf

江苏大学硕士学位论文 摘要 定性空间推理( q u a l i t a t i v es p a t i mr e a s o n i n g ) 是指利用空间理论和人工智能技术 对空间对象进行建模、描述和表示，并据此对空间对象间的空间关系进行定性分析 和处理的过程，是处理常识性空间知识的一种人工智能的方法。定性空间推理已成 为空间推理的主要研究领域之一，并广泛应用在空间数据查询、机器入寻航、空间 规划等方面。研究、分析、探讨定性空间的表示和定性空间推理方法，无论是对空 间推理自身的发展，还是对促进空间推理的应用都有着重要意义。 本文基于区域连接演算( r e g i o nc o n n e c t i o nc a l c u l u s ) 理论，结合形态学， 并考虑到人的认知过程，研究空白j 拓扑关系、方向关系、距离关系的集成表示的形 式化模型和推理方法。本论文的创新点如下： 1 、以区域作为空间原语，将区域连接演算( r c c ) 中的连接关系( c ) 和形态学 ( m o r p h o l o g y ) 中的全等关系( c g ) 作为原始空间关系，并在此基础上引入了区域度 量函数一一区域延伸，提出了以区域为度量单位的空间关系形式化的度量方法。 2 、在区域延伸演算的基础上，构建了一个统一的空间关系表示的形式化模型。 在这个模型中，对空间拓扑关系、方向关系、距离关系以及区域大小进行了描述。 3 、研究了基于区域延伸的空间关系表示模型的计算性质。在区域延伸这一度量 基础上，针对c l e m e n t i n i 的定性距离模型的缺陷，提出了一种在任意方向上距离运 算的方法。为区域之间方向关系与距离关系的集成推理提供一种新颖的方法。 4 、在约束处理规则( c h r s ) 和e c l i p s ep r o l o g 的基础上，实现了拓扑、方向和距 离关系推理。 在以上所述的创新工作的基础上，对研究的内容进行了模拟，通过对一个空间 规划问题实例的求解过程，证明上述基于区域延伸的定性空自j 关系表示模型以及基 于该模型的定性空间推理方法是正确可行的。 基于区域延伸的空间关系表示的形式化模型及其推理方法在空间导航和空间规 划等领域有着重要的应用。 关键词：定性空间关系表示，定性空间推理，r c c ，区域延伸 江苏大学硕士擘位论文 a b s t r a c t q u a l i t a t i v es p a t i a lr e a s o n i n gi s 强a r t i f i c i a li n t e l l i g e n c em e t h o dt od e a lw i t hg e n e r a l s p a t i a lk n o w l e d g e i tm e a n su s i n gs p a t i a lt h e o r ya n da r t i f i c i a li n t e l l i g e n c et om o d e l m g ， d e p i c ta n de x p r e s ss p a t i a lo b j e c t , a n dt h eq u a l i t a t i v ea n a l y z ea n dd i s p o s a lp r o c e s s i n go f r e l a t i o no ft h es p a t i a lo b j e c t sa c c o r d i n gt ot h e s e q u a l i t a t i v es p a t i a lr e a s o n i n gh a sb e e n a nm a i n l yr e s e a r c hf i e l do fs p a t i a lr e a s o n i n g , a n dw a sd i f f u s e l ya p p l i e di ns p a t i a ld a t a q u e r y , r o b o tn a v i g a t i o na n ds p a t i a lp r o g r a m m i n ge t c r e s e a r c h , a n a l y z ea n dd i s c u s s i o no n e x p r e s s i o na n dr e a s o n i n gm e t h o do f q u a l i t a t i v es p a t i a la r ev e r yi n f l u e n t i a ln om a t t e rt ot h e d e v e l o p m e n t o f i t s e l f o r t h e a p p l i c a t i o n o f s p a t i m r e a s o n i n g b a s e do nr c c t h e o r y , a n dc o m b i n ew i t l lm o r p h o l o g yw em a d ear e s e a r c ho nt h e f o r m a l i z i n gm o d e lo fs p a t i a lt o p o l o g yr e l a t i o n , d i r e c t i o nr e l a t i o na n dd i s t a n c er e l a t i o n s i n t e g r a t e de x p r e s s i o n , i na d d i t i o nc o n s i d e r i n gh o m i n i n ee o g n i z ep r o c e s s n l em a i n i n n o v a t i o nc a nb ec l a s s e da sf o u rp a r t s ： 1 t a k er e g i o n 鹊s p a t i a lf u n d a m e n t a ln o t i o n , t h ec o n n e c t i o nr e l a t i o n ( c ) o fr e g i o n c o n n e c t i o nc a l c u l o u s ( r c c ) a n dt h ec o n g r u e n tr e l a t i o n ( c g ) o fm o r p h o l o g ya so r i g i n a l s p a t i a ir e l a t i o n , a n db a s e do nt h ea b o v ei n t r o d u c ei n t or e g i o ne x t e n d ，t h em e a s u r ef u n c t i o n o fr e g i o n , w ep u tf o r w a r dam e a s u r em e t h o do ff o r m a l i z i n gt h es p a t i a lr e l a t i o nw h i c hu s e r e g i o na sm e a s u r eu n i o n , s e q u e n t i a l l yc r e a t e daf o r m a l i z i n gm o d e lb a s e do nr e g i o ne x t e n d u n i f o r me x p r e s s i o no f s p a t i a lr e l a t i o n 2 b a s e do nt h er e g i o ne x t e n da l g o r i t h m ，w eg e n e r a t eac o m m o nf o r m a l i z a t i o nm o d e l w h i c hp r e s e n t st h er e p r e s e n t a t i o n sa b o u ts p a t i a lt o p o l o g i c a lr e l a t i o n ，d i r e c t i o nr e l a t i o n , d i s t a n tr e l a t i o na n dt h es i z eo f t h er e g i o n 3 s m d i e do nt h ef o r m a l i z i n gm o d e l sc a l c u l a t ep r o p e r t yb a s e do nr e g i o ne x t e n d e x p r e s s i o no fs p a t i a lr e l a t i o n m a k ea ni m p r o v e m e n to nc l e m e n t i n i sq u a l i t a t i v ed i s t a n c e b a s e do nr e ：g i o ne x t e n dm e a s u r e m e n t ，t h e np u tf o r w a r dad i s t a n c eo p e r a t i o nm e t h o do n d i s c r e t i o n a ld i r e c t i o nw h i c ho v e r c a m ec l e m e n t i n i sq u a l i t a t i v ed i s t a n c em o d e l sl i m i t a t i o n t h u sp r o v i d ean o v e lm e t h o df o ri n t e g r a t i n gr e a s o n i n gd i r e c t i o nr e l a t i o nb c t w e e nr e g i o n s a n dd i s t a n c er e l a t i o n 4 b a s e do nc h r sa n de c l p s 。p r o l o g ，d i s c u s s e dt h er e a l i z a t i o no fp r o l o g ， t o p o l o g i c a l ，d i r e c t i o na n d d i s t a n c er e l a t i o nr e a s o n i n g b a s e do nt h ei n n o v a t i o np o i n t s ，s i m u l a t et h er e s e a r c hc o n t e n t ，a tl a s t , b yt h e r e s o l u t i o np r o c e s s i n go fas p a t i a lp r o g r a m m i n gc a s ei n d i c a t et h a tt h eq u a l i t a t i v es p a t i a l r e l a t i o ne x p r e s s i o nm o d e lb a s e do nr e g i o ne x t e n s i o ni sf e a s i b l ea n dt h eq u a l i t a t i v es p a t i a l r e a s o n i n gm e t h o db a s e do nt h em o d e li se f f e c t i v e i t 江苏大学硕士学位论文 t h es p a t i a lr e l a t i o ne x p r e s s i o n sf o r m a l i z i n gm o d e lb a s e do nr e g i o ne x t e n s i o na n di t s r e a s o n i n gm e t h o d sa g ev e r yi m p o r t a n ti ns p a t i a ln a v i g a t i o na n dp r o g r a m m i n ga n ds oo i l k e yw o r d s ：q u a l i t a t i v es p a t i a lr e l a t i o n sr e p r e s e n t a t i o n ，q u a l i t a t i v es p a t i a l r e a s o n i n g ，r c c ，r e g i o ne x t e n s i o n l i i 江苏大学硕士学住论文 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权江苏大学可以将本学位论文的全部内容或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口， 在年解密后适用本授权书。 本学位论文属于 不保密团。 学位论文作者签名：徽 2 0 0 7 年6 月1 3 日 指导刻磁氢匆啦 2 0 0 7 年6 月1 3 日 江苏大学硕士学位论文 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容以外，本论文不包含任何其他个人或 集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：弓友j 乏 日期：2 0 0 7 年6 月1 3 日 江苏大学硕士擘位论文 第一章绪论 本章对定性空间表示与推理的研究现状，本文的研究对象、目的以及研究的主 要内容进行介绍。 1 1 研究背景 空间推理( s p a t i a lr e a s o n i n g ，s r ) 是指利用空间理论和人工智能( a r t i f i c i a l i n t e l l i g e n c e ) 技术对空间对象进行建模、描述和表示，并据此对空间对象间的空间关 系进行定性或定量分析和处理的过程。目前，空间推理被广泛应用于地理信息系统、 机器人导航、高级视觉、自然语言理解、工程设计和物理位置的常识推理等方面， 并且正在不断向其他领域渗透，其内涵非常广泛。空间推理的研究在人工智能的研 究中占有很重要的地位，是人工智能领域的一个研究热点【。 定性空间推理所研究的是空间推理中关于定性的部分内容，它主要从空间对象 间关系的定性表示与推理的角度来研究空间推理问题。定性空间关系主要包括拓扑、 方向、距离等空间关系。拓扑关系是空间关系中最重要的基本关系，其模型可分为 区域拓扑【2 3 4 j 、点集拓扑两大类，它们都有比较完整的理论体系。方向关系描述了对 象之间的空间顺序关系，其主要描述方法有基于锥形【5 1 以及基于投影等。距离关系一 种范数，是空间对象间的某种度量关系，c l e m e n t i n i 等人【6 】将距离划分为不同层次( 如 近、中等、远等) ，给出了划分的原则，并且结合“基于圆锥”的方向模型与距离关 系，提出了位置演算方法。 研究、分析、探讨空间拓扑关系、距离关系以及方向关系的集成表示和在此基 础上的定性空间推理技术，无论是对于促进空间推理本身的发展，还是对空间推理 应用研究的开展都有着极为重要的意义。 1 2 国内外研究现状 1 2 1 定性空间表示的研究现状 空间关系一般包括度量关系、方位关系和拓扑关系等，空间拓扑关系是最基本 的最稳定的空间关系，方向关系是空间的一种顺序关系，而距离关系则是最常见的 度量关系。 目前，空间对象拓扑关系的研究主要集中在两个方面：( 1 ) 确定的区域间空间关 江苏大学硕士学位论文 系的研究，主要体现在g i s 和空间推理的相关研究中；( 2 ) 不确定区域的表示及其分 析方法的研究，主要体现在地理分析、图像理解和计算机视觉的相关研究当中。本 文只研究确定的区域间的空间关系。 一、对于确定性区域间拓扑关系模型，有基于区域的拓扑理论和经典的点集拓 扑理论两类方法，其中最有代表性的是r c c 模型和n - 交集模型。除了r c c 模型和 n 交集模型外，还有以下一些模型。 ( 1 ) c b m ( c a l c u l u s b a s e dm e t h o d ) r c c 及n - 交集模型研究的拓扑关系划分越来越精细，但作为人类的认知常识是 不能同时区分这么多关系的。文献川以人类认知为基础，给出了5 种基本拓扑关系 t o u c h , i n , c r o s s ，o v e r l a p ，d i s j o i n t ，称为c b m ( c a l c u l u s - b a s e dm e t h o d ) 。在此基础上， 通过添加线对象与区域对象的求边界函数，证明了c b m 与d e9 i m 具有相同的拓扑 关系分类能力。由此，将空间对象间拓扑关系的分类与人类认知习惯联系了起来。 ( 2 ) v o r o n o i 图模型 在研究空间点的邻近区域或影响区域时，使用了v o r o n o i 图。李成民等瞵】基于 v o r o n o i 图，提出并研究了面条模型中动态空间关系推断的四邻近数序模型，给出了 唯一、完备性推断规则。陈军等 9 1 基于v o r o n o i 图用交叉与交相结合的方法对9 i m 进 行改进，提出了基于v o r o n o i 图的9 交集模型( v o r o n o i b a s e d9 - i n t e r s e c t i o n ) 来摇述空 问拓扑关系和空间方位关系。 ( 3 ) 拓扑不变量方法 拓扑关系是拓扑变换下的不变量，因此从拓扑不变量的角度研究空间对象问的 拓扑关系是一种自然的选择。文献【0 1 在4 1 m 的基础上研究了空间对象相交的类型、 维数、序等不变量，给出了分类不变量的概念。利用不同的分类不变量可以刻画空 间拓扑关系更进一步的细节，给出拓扑关系更丰富的分类。 二、方向关系模型 方向是一个普通的空间概念，在日常生活中经常使用。人们通常将方向看做目标 之间的空间关系，从而建立方向关系的描述模型。方向关系是空间对象之间一类重 要的空间关系，它描述了空间对象之间的一种顺序关系，这种关系是存序的。耳前 许多学者对空间目标方向关系的表示和推理提出了一些有价值的理论和方法。 ( 1 ) 基于锥形的方向关系模型 1 9 7 6 年h a a r 提出了空间方位关系表示的锥形模型，它以参考对象的质心为原点， 用两条相互垂直的线将r 2 空间划分为四个无限的锥形区域，每个锥形的角平分线分 2 江苏大学硕士学位论文 别是东、南、西、北四个主方向。目标对象落在锥形区域的主方向就是目标对象相 对于参考对象的方位。 在基本的锥形模型基础上，p e u q u e t d 等通过引入参考对象的最小边界矩形 m b r ( m i n i m u mb o u n d a r yr e c t a n g l e ) 和朝向侧的概念，改进了锥形模型，使其能够判 断一些较为复杂对象间的方位关系；另一类改进是增加主方向的数目，使得锥形模 型能够判定更复杂的方位关系。锥形模型的优点是能够方便地调整主方向的数目。 ( 2 ) 基于投影的方向关系模型 将对象投影到坐标轴上并比较投影坐标值的大小来确定对象问的方位关系是一 种常用的方位关系模型，称为基本投影模型。选择不同的投影坐标轴将得到不同的 投影模型。图1 1 给出了三种投影模型，分别称为垂直投影模型、水平投影模型和垂 直一水平投影模型。其中0 为参考对象的投影位置，当目标对象的投影位置也为o 时， 两个对象间的方位关系称为同位( o ) 。 w # e 州 e 一 wtew s r r s 鲁直授髟摸蔓瘩平投影羲生垂l 瘩早爱簪援量 r e 图1 1 三种基本投影模型 基本投影模型能够较好地表示空间点对象间的方位关系。例如，任意两个点对 象a , b ，它们在垂直投影下y 坐标分别记为a y 、b y ，那么有： i n 当a ， b o 当a ，= b ( 3 ) “双十字”模型 1 9 9 2 年，f r e k s a 1 1 】在“基于投影”方法的基础上，通过引入“视点”，提出了“双 十字”模型( 图1 2 ) 。 该模型基于人类感知空间的方式，方向关系为“前”、“后”，“左”、“右”，“上”、 “下”等。在“双十字”模型中，除参考对象和目标对象外，还引人了视点对象， 因而这是一种相对方向关系的表示。首先，从视点对象到参考对象的直线将平面分 成三部分，然后垂直于该直线并分别经过视点和参考对象的两条直线再将平面细化， 划分成1 5 个部分，对应于1 5 个方向关系，其中有2 个点、7 条线、6 个区域( 图1 2 ) 。 江苏大学硕士学位论文 该模型用三元关系表示相对方向关系，在机器人导航中有着广泛应用。 l 21 2 4 1 0 68 l l 9 7 图1 2 “双十字”模型 ( 4 ) 井字空间模型 这种表示方法以参照对象为中心( 常采用空间对象的最小边界矩形m b r 表示空 间对象本身) ，将整个空间划分为正东( i 也) 、正南( r s ) 、正谣( r w ) 、正北( r n ) 、 西北( n w ) 、东北( n e ) 、东南( s e ) 、西南( s w ) 和中心区域( o ) 九个区域， 通过各个对象本身与九个区域之间交的结果来描述它们与参照对象之间的方向关 系。 当参考对象不是点对象时，以参考对象的最小边界矩形m b r 来近似表示它，并 作垂直一水平投影，得到井字空间投影模型( 简称井字空间模型) ，如图1 3 ，其中o 表示同位方位关系。特别地，可以认为垂直一水平投影模型是参考对象为点对象时 的井字空间模型。 井字空间投影模型将r 2 划分为9 个区域，每个区域的主方向依次规定为r n ，n e ， r e ，s e ，r s ，s w , r w , n w ，s a ，称为井字空间的强方位关系。然而，这9 个强方位与人 类认知中的方位关系有差异，如在人类对方位认知中还包括东、南、西、北等方位 关系。为此，扩展强方位关系获得如下的1 3 种方位关系：d 一 r n ，n e ，r e ，s e ，r s ，s w , r w , n w , s a ，n ，e ，s ，w 其中：n = ( n w 八r n ) v ( r n 八n e ) v ( n w 八r n 八n e ) e = ( n e 八r e ) v ( r e 八s e ) v ( n e 八r e 八s e ) s = ( s w 八r s ) v ( r s 八s e ) v ( s w 八r s 八s e l w r - 烈w r w ) v ( r w 八s w ) v ( n w a r w a s w ) 在这里，我们将方位关系看作了空间方位谓词( r d ) ，也就是说方向关系是一种 二元有序偶对： 。，、f 丁若空间对象x 与坨间有方向关系r 尺( x ，力2 1f 若空间对象x 与y 之间无方向关系r 4 江苏走学硕士学位论文 n w n e 。 e s v v s e s 图1 3 井字空同方向模型 如果对目标对象也做最小m b r 划分，那么就成为最小边界矩形模型( d l 卯) 。 ( 5 ) d r m 模型 g o y a l 等 1 2 , 1 3 魄出d r m 模型( d i r e c t i o nr e l a t i o nm a t r i x ) ，该模型也是以投影模型 为基础，按照参考对象的m b r 将空间分成9 个部分，用符号集 n ，s ，e ，w ，n e ，s e ， s w , n w 0 中的符号表示这9 个方向片在地理空间的方向，o 表示与参考对象的 m b r 相同的方向区域。目标对象用确定的多边形表示，即表示方向关系时考虑到目 标对象的形状对方向的影响。用一个3 x 3 矩阵表示目标对象相对于参考对象的方向， 矩阵中的每个元素表示目标对象与相应的方向区域取交集时的结果，即矩阵元素在 m ，m ) 中取值。方向关系矩阵模型能够区分2 1 8 种基本方向关系。 基于投影的方向关系矩阵模型是一种常用的方向关系模型，相关的研究成果有 p a p a d i a s 1 等提出的9 方位模型和1 6 9 方位模型。 ( 6 ) 曹菡等【1 4 1 对d r m 模型进行了扩展，提出了空间方位关系的多级分层描述。 将参照物体、目标物体区分为点、线和面等目标加以研究。以参照对象是点、线、 面等情况建立目标间方向关系描述的3 层模式结构，每层模式又分别建立了基本方 向关系描述、推理模型和方向关系描述、推理细化模型。文献f l5 】提出了基于v o r o n o i 图的空阳j 方向关系描述模型。 三、距离关系模型 距离关系是空间对象之间最基本的空间属性之一，距离模型中的距离不同于拓 扑与方向的一面在于距离是可以度量的，也就是说对象间的距离是一种范数，如欧 式几何中的距离关系需要满足三个条件：pg x ) = o ，po ( ，y ) = p ( y ：，p ，y p p ( y , z ) p z ) 。基于坐标的一般的n 维空间距离定义【1 6 1 ： p p ( x ，y ) = ( ix , 一只| ，) “9 。然而在现实环境下，人们对于距离概念的把握，并不依 江苏大学硕士学位论文 赖于数学上物体所具有的坐标。事实上，在一个定性环境中，我们没有办法建立定 量的距离概念。人们的空间距离概念依赖于许多文化和经验因素。例如说a 离b 近 就不仅是它们的绝对位置近，而且和确定参照系统中的其它物体的形状、大小和位 置都相关。 距离的表示分为绝对距离和相对距离，绝对距离关系直接表示两个空间对象之 间的距离，相对距离关系是通过与其它对象的比较，间接表示两个对象间的距离。 绝对距离可以是定性关系，也可以是定量关系，而相对距离一般是定性的。 距离关系是空间对象间的某种度量关系，c l e m e n t i n i 等人【6 】将距离划分为不同层 次( 如近、中等、远等) ，给出了划分的原则，并且结合“锥形”方向模型与距离关 系，提出了位置演算方法。 有时单纯的距离关系不足以用于推理，需要结合方向信息，方向与距离的结合 称为位置( p o s i t i o n a l ) 信息。1 9 9 3 年，z i m m e r m a n n 等人旧提出了一种根据两点间的连 线确定第3 点位置的方法，并用d e l t a 算子把定性方向和距离概念结合起来。1 9 9 7 年，c l e m e n t i n i 等人1 6 1 将“基于圆锥”方向模型 1 2 1 与绝对距离关系相结合，提出了位 置演算方法( 如图1 4 c a ) 所示) 。1 9 9 9 年，i s l i 等人提出了将相对距离关系分别与“投 影”方向模型( 如图1 4 ( b ) 所示) 和“双十字”方向模型相结合的方法。 w s e r il x 仅x 父女支 、 i k 菇k ：( x ： y a 摹于“锥形”模型与绝对距离的结合b 基于“投影”模型与相对距高结台 图1 4 距离与方向关系模型的结合 1 2 2 定性空间推理的研究现状 空间问题有着其固有的复杂性和不确定性，人们在分析空间问题时经常使用定 性方法描述地理空问。定性空间推理现己成为空间推理的重要研究领域【1 9 1 。 ( 1 ) 组合表推理 虽然关于定性空间推理的研究已有十几年，获得了一些推理方法，但是基于组 合表的推理仍是定性空日j 推理最常见的推理方法【2 0 】。组合表推理的简单性与有效性 6 江苏大学硕士学位论文 受到许多研究者的关注【2 1 讲1 。 ( 2 ) 逻辑演算 通过逻辑演算来进行推理是定性空间推理的另一种方法。r a n d e l l ，c u ia n dc o h n l 2 j 通过空间谓词c ( x ，y ) 定义空间逻辑系统，将空间对象间的拓扑关系表示为谓词公式， 利用一阶谓词逻辑建立了一阶逻辑范畴下空间拓扑关系推理技术。文献 2 s l 用命题逻 辑来表示空间对象间的拓扑关系，由此空间推理成为命题演算。文献 2 9 1 将模态逻辑 引入空闻拓扑关系的描述与推理中，进行7 一些尝试性研究。b e n n e t t l 3 0 1 发展了空间 逻辑的研究成果，给出了空间对象关系表示与推理的命题逻辑方法，b e n n e t t l 7 1 将模 态逻辑方法引入到空间对象关系表示与推理中。b e n n e t t 和c o h n 3 l l 研究了多维多模 态逻辑在定性时空推理中的应用。 ( 3 ) 拓扑关系推理的分层逼近法 石纯一，廖士中等1 3 2 1 将定性空间推理问题划分为易处理类与非易处理类，给出 了易处理类的分层逼近的推理方法。所谓易处理类就是能在在多项式时间内得到解 决的问题集合。由此，他们建立了空间区域对象间组合表的推导算法，推导出了空 间区域之自j 的拓扑关系组合表。进一步的工作是利用r c c 8 的概念邻域，设计了空 间拓扑关系约束满足问题的分层逼近法，实现了不同拓扑关系层次间的推理。 ( 4 ) 基于描述逻辑的空间推理 描述逻辑( d e s c r i p t i o nl o 画c ) 是为了表示概念和概念层次知识而设计的知识表 示语言，可以合并并且给出众所周知的基于框架( f r a m e s ) 、语义网络( s e m a n t i c n e t w o r k s ) 、面向对象的表示( o b j e c t - o d e n t e dr e p r e s e n t a t i o n s ) 、语义数据模型( s e m a n t i c d a t am o d e l s ) 的系统的逻辑基础。其基本构件是概念( c o n c e p t s ) 、任务( r o l e s ) 和个体 ( i n d i v i d u a l s ) 。概念描述个体集合的公共属性并且可以视为个体集合的一元谓词，任 务被解释为个体间的二元关系。描述逻辑的主要推理工作是包含和可满足性检验。 为了充分支持空间区域间定性关系的可判定推理和定量数据性质的可判定推 理，文献p 3 】定义了适用于由点、线、和区域共同组成的具体域d p ，给出了具体域可 满足性检验算法，奠定了适用于空间推理的d l s r ( d p ) 描述逻辑的基础，提出描述逻 辑d l s r ( d p ) ，并讨论了其语法、语义、约束和算法。 综上所述，定性空间推理更多的研究工作在集中在定性空间关系的某个方面， 对于空间关系的集成表示方面以及基于定性空间关系的集成表示基础上的推理的研 究相对较少。文献1 3 4 1 认为在时空推理研究领域中，单独的空间关系( 拓扑、方向) 研究 已经比较充分，提出了一些有价值的模型，但实际应用常常要求将多种空间信息结 7 江苏大学项士学位论文 合起来加以利用，这种结合就包括多种空间关系的结合。本文通过分析r c c 理论， 将形态学的全等关系引入到r c c 中，提出区域延伸演算，达到扩充r c c 以建立包 含拓扑关系、方向关系和距离关系的统一的形式化模型的目的。 1 3 本文的研究内容 本文研究的内容主要包括以下几部分： 一、r c c 模型的研究 二、以区域作为空问原语，将r c c 理论中的连接关系c 和形态学( m o r p h o l o g y ) 中的全等关系c g 作为原始空间关系，并在此基础上引入了区域度量函数一一区域延 伸，提出了以区域为度量单位的空间关系形式化的度量方法，进而构建了一个基于 区域延伸的空间关系表示的形式化模型。该模型能够以多种粒度表示拓扑、方向以 及距离等空闻关系。 三、研究了基于区域延伸空间关系表示模型的计算性质。在区域延伸这一度量 基础上，对c l e m e n t i n i 的定性距离模型进行了改进，提出了一种在任意方向上距离 运算的方法，从而克服了c l e m e n t i n i 的定性距离模型的缺陷。为区域自j 方向关系与 距离关系的集成推理提供了一种新颖的方法。 四、在约束处理舰t j ( c h r s ) 和e c l i p s ep r o l o g 的基础上，实现了拓扑、方向和 距离关系推理。 五、对研究的内容进行了模拟，通过对一个空间规划问题实例的求解过程，证 明上述基于区域延伸的定性空间关系表示模型以及基于该模型的定性推理方法是有 效的。 1 4 本文的内容安排 全文共分6 章，涉及定性空间拓扑关系、方向关系以及距离关系的表示、基于 区域延伸的空间关系表示模型以及建立在该模型基础上的定性空间关系推理方法， 给出了一个关于该模型的表示和推理的应用实例，并对结果进行了分析。 第l 章绪论，介绍了定性空间表示和推理的基本概念与研究内容，以及国内外 研究现状，并分析了现有研究中的一些不足，确定了本文的研究内容。 第2 章是关于r c c 模型的研究。通过研究，分析了r c c 推理的几种常用方法， 以及对r c c 进行扩展的途径，从而为基于区域延伸的空间关系表示打下逻辑基础。 第3 章在r c c 模型基础上，引入了区域延伸的这一区域的度量方法，构建了拓 扑关系、方向关系以及距离关系集成表示模型，扩展了r c c 模型对空问拓扑关系的 8 江苏大学硕士擘位论文 描述能力，并将其推广到方向和距离关系上。 第4 章在拓扑关系组合表、方向关系以及距离模型组合表的基础上，研究并扩 展了r c c - - 8 模型的组合表，给出了r c c - - 9 模型以及组合表，针对经典的距离模 型的缺点，提出了一种基于区域延伸的任意方向上的距离运算方法， 第5 章给出了应用空间关系集成表示模型进行空间关系推理的一个原型系统， 并据此给出了一个实例，并对运行结果进行了分析。 第6 章是总结全文所做的工作和创新之处，同时提出了一些需要进一步深入研 究的内容。 9 江苏大学硕士学位论文 第二章r c c 模型 定性空间推理的基础是定性空间表示。在定性的空间表示和推理模型中，影响 最大的就是区域连接演算( r c c ) 模型。 区域连接演算( r c c ) 是由r a n d e l l 等人为实现定性空间表示与推理而提出的一 阶理论。该理论是在c l a r k e l 3 5 3 q 的个体连接演算的基础上提出来的，它修正了在 c l a r k e 系统中存在的几个问题，形成了一套正式的空间的表示与推理的形式化系统。 这就促成了区域连接演算理论的产生与发展。 2 1 区域连接演算的提出 在r c c 理论中，重要的概念是区域与连接。r c c 理论中的空间本体是区域， 而不像在其他的空间表示与推理方法中那样，使用传统的点作为空间本体，区域是 这些点的集合。在r c c 理论中，对于区域的解释是任意维的，但是所有的区域都 必须是同维的而不能是混合维的，这样的区域被称为是正则的( r e g u l a r ) 。通常的， 般的区域解释是三维的。在r c c 理论中可以处理开区域或闭区域的问题。同时 也把区域看作是真正的空间可扩展的，因此就会出现了一个区域为空的可能性。除 了这些约束之外，在r c c 理论中允许各种各样的区域，尤其区域可以是多块的， 还可以是有内部有孔的、有管道的或者是断裂的，等等。 r c c 最初的系统是在文献0 7 1 中提出的，是从c l a r k e 的系统的基础上得到的。 然而文献【2 】对r c c 理论做了一定的修正，提出了一个修正的理论，该理论在一个重 要的方面与c l a r k e 的理论不同，并且有着更为广泛的应用。其中最重要的改变就是 对c ( x ，y ) 解释的改变：c l a r k e 的解释是两个区域x 和y 至少共享一点，然而在r c c 理论中新的解释是两个区域拓扑的封闭区域共享一点。 2 2r c g 公理系统 r c c 的基础语言仅仅包括一个原语c ( ) ( ，y ) ，读做“区域x 与区域y 相连”。 通过下面的两条公理来保证关系c 是自反的和对称的： v x c ( x ，x ) 】 v xv y 【c ( x ，”- - c ( y , x ) 】 利用c ( x ，y ) ，可以定义一系列的基础的二元关系见表2 1 。 在没有明确指出的情况下，函数和谓词的所有的参数都是定义的区域类，其中 1 0 江苏大学硕士学位论文 的关系p ，p p ，t p p 和n t p p 是非对称的同时支持逆关系。对于这些关系的逆关系 分别用p i ，p p i ，t p p i 和n t p p i 来表示。表2 1 中给出了这些关系的解释与定义。 表2 1r c c - - 8 中由连接关系定义的关系 关系解释关系的定义 d c ( x , ” x 与y 不相连 一c 伍y ) p ( ) 【y )x 是y 的一部分v z c ( z , x 卜心亿y ) 】 p 敢x y )x 是y 的真部分p ( 】，y ) a p ( y x ) e q ( x , y )x 与y 相等p ( ) ，y ) a x ) o ( ) y )x 与y 重叠3 z v ( z ，x ) p 亿y ) 】 d r ( ) 【，y )x 与y 相离_ 1 0 ( x ，y ) p o ( x , y )x 与y 郝分重叠o ( x ，y ) a - , p ( x , y ) a p ( y , x ) e c ( x , y )x 与y 外部相连c ( x ，y ) ，o ( ) 【，y ) t p p ( x , y )x 是y 的真部分且与y 相切p p ( 工，y ) 3 z e c ( z ，x ) ae c ( z ，y ) 】 n t p p ( k y )x 是y 的真部分且不与y 相切尸| p ( 工，y ) a - , 3 z e c ( z , x ) ae c ( z ，y ) 】 在这些定义的关系中，集合 d c ，e c ，p o ，e q ，t p p ，n t p p ，皿p i ，n t p p i ， 证明为是互不相交且是联合完备( j e p d ) 的，把这八个关系的集合称之为r c c 8 。 上面描述豹关系的完整的集合可以被嵌入到一个关系格中，就像在图2 1 中给出的 那样。符号t 被用来表示重言而符号上用来表示矛盾。这些关系的排列是通过一个包 含关系来完成的，由底向上是逐渐减弱的关系。例如，p p 蕴涵着t p p ，p p 蕴涵着t p p 或者是n t p p 。较低范围的边界上的最大的关系是互斥的。 例如关系t p p 和n t p p ，p 和d r 。这一个格对应着一条定理( 例如v x y 【p p ( x ，y ) 一 t p p ( x ，y ) v n t p p ( x ，y ) 】) 。 图2 1 由c 定义的关系的包含格在r c c 理论中同时需要一些布尔函数，这些布 尔函数的定义在下面给出： v x c ( x ，u ) 】 v x ，y , z c ( z , s u m ( x ，y ) ) i c ( z ，】【) v c ( z ，”】 v x ，y c c o m p l ( x ) ) i ，n 1 1 p p x ) 】a 0 c o m p l ( x ) ) m - - , p ( y , x ) 】 v x ，y , z c 亿p r o d ( x ，y ) ) v w p ( w , x ) a p ( w , y ) a c ( z ，w ) 1 】 v x ，y n u l l ( p r o d ( x ，y ) ) - = - d r ( x ，y ) 】 v x ，y , z c ( z ，d i i t ( x ，y ) ) - - 一c ( z ，p t o d ( x ，c o m p l ( y ) ) ) 】 由于空间区域可以由许多块不连接的部分组成。因此需要定义一个谓词用来判 断区域是否是单块的： 江苏大学硕士学位论文 c o n ( x ) - - - v y , z s u m ( y , z ) = x c z ) 】 图2 1 由连接c 关系定义的关系包含格 很明显，如果每一个区域都有一个不相切的真部分，那么在每一个模型中将有 无数多个区域。在空间表示的逻辑方法中，在处理描述空间位置类型的形式表达式 时，不直接表示这些位置的结构。虽然在r c c 理论中空间区域是无限可分的，但 这不意味着推理系统的执行需要无限多的数据结构，相反，根据一套高维的定性事 实来表示复杂的位置将是非常简洁的。 2 3r c c 关系的连续变化 到现在为止，我们对于空间区域的描述只是涉及了空间的静态属性而没有开发 一个演算来表达一个空间区域的结构是如何随时间而变化的。这样的动态推理，很 显然在很多的领域中是非常的重要的。在许多的领域中，都做出这样的一个假设： 变化是连续的。在定性空间推理中，连续性假设就是假定形状的改变和移动都是连 续的。图2 2 指出了r c c 8 中在考虑连续性时可能的状态转变。 例如，在一个从关系d c 向p o 的连续变化中，一定也包含e c ，这可以用概念 邻域图来表示。我们下一章所定义的区域延伸演算可以更容易表示这种区域之间拓 1 2 江苏大学硕士学位论文 扑关系变化的连续性。 图2 2r c c - 8 中拓扑关系的连续变化 2 4 使用