【作者】 富倩；

【导师】 欧阳继红；

【作者基本信息】 吉林大学 ， 计算机应用技术， 2010， 博士

【摘要】 关于人工智能的研究方法,时间与空间的表示及推理总是它最重要的组成部分之一。近年来,时空推理日趋成为活跃的研究方向,是人工智能、地理信息系统、机器人导航、图像理解、计算机视觉、时空数据库等领域的重要研究内容之一。在众多的空间关系中,对象间的拓扑关系是最基本的,空间拓扑关系模型的研究是空间推理中的热点问题,在定性空间推理中占有极其重要的地位。空间拓扑关系的建模方法主要包括基于逻辑和基于代数两大类,其代表工作分别是Randell等的RCC理论和Egenhofer的交集模型。目前,基于简单对象的空间拓扑关系研究已形成一套较为成熟、完善的理论体系。然而在现实世界中,空间对象不是简单的而是复杂的,传统空间关系模型已难以满足实际应用的需求,基于复杂对象的空间关系形式化模型的研究势必成为今后定性空间推理发展的一个重要趋势。在开发空间关系模型的形式化方法时,一个重要的问题是在表达能力和计算易处理性之间进行权衡。交集模型虽然计算复杂性较低,但其表达力相对有限;RCC形式化模型表达力虽较强,但其推理计算的难度很大。如何建立表达力较强且计算复杂性较低的形式化方法是空间关系建模的重要内容之一。形状是对象最重要的性质,也最难定性描述。传统的空间关系模型多将对象作为统一整体,不考虑其形状特征。随着复杂空间关系建模的发展,定性形状表示日益成为定性空间推理的一个重要方面。目前针对复杂对象的空间关系建模研究主要集中在拓扑和方位两方面,复杂空间对象性质的研究主要集中在形状表示方面。本文针对空间中一类特殊的复杂对象(即空间凹形区域),围绕其拓扑关系建模及形状关系表示展开了研究和讨论。分析、总结了当前定性空间推理中复杂对象拓扑关系模型和形状关系模型的相关研究工作。拓扑关系模型方面,为增强传统拓扑模型(以凸形区域为表示基元)的表达力和实用性,针对简单凹形区域(即只包含一个凹处的凹形区域),提出了基于点集理论的拓扑关系模型RCC62,以及基于模态逻辑的拓扑关系模型RCC62*.形状关系模型方面,以基于区域的形状表示为研究主线,为解决Cohn的定性形状表示方法中SameSide谓词存在的问题,给出一种改进的凹处同异侧关系判断方法。本文的主要贡献和研究结果如下:(1)复杂对象空间关系建模方法目前多数空间关系处理方法的研究,只是针对二维空间、简单对象、简单对象(间)单一种类空间关系进行的。但在现实世界中,空间不是二维平面的而是三维立体的,空间对象不是简单的而是复杂的,空间对象间关系不是单一的而是多种并存的,我们称之为复杂空间关系。现有复杂空间关系建模的研究主要包括复杂对象的空间关系建模、空间对象的定性形状表示,三维空间关系模型,多方面空间关系结合推理等。围绕拓扑关系和形状关系的相关研究工作,重点介绍了基于一阶逻辑的拓扑模型、基于模态逻辑的拓扑模型和基于代数方法的拓扑模型,以及定性形状关系模型。(2)简单凹形区域拓扑关系模型RCC62基于点集拓扑学,对二维空间中简单凹形区域的拓扑关系进行建模,展开了以下研究工作:扩展9-交集矩阵为16-交集矩阵;基于16-交集矩阵,对RCC23进行细化得到RCC62,给出RCC62的概念邻域图和最近拓扑关系图;建立了RCC62的推理系统,推导出RCC62的复合表。RCC62的表达力强于RCC23,对空间关系的刻画更细致、准确。(3)拓扑关系模型RCC62*的表示系统在RCC62模型的基础上,建立了基于模态逻辑的拓扑关系模型RCC62*的表示系统,具体工作如下:基于S4模态的内部算子以及凸壳算子,给出了16-交集矩阵的模态定义;基于扩展的零阶直觉演算,将RCC62的基本关系转化为由模型约束和蕴含约束构成的模态公式二元组,得到RCC62*的表示系统。RCC62*的表达力不低于RCC62,且其形式化程度要强于RCC62模型。(4)拓扑关系模型RCC62*的推理系统基于Gentzen的相继式演算推理方法,将拓扑关系的复合推导问题转化为与其对应的模态公式序列的有效性判断问题。分别研究了基于零阶经典演算和零阶直觉演算的RCC8复合关系推导。在此基础上,加入模态凸壳算子,使用凸壳算子的模态特征公式和Hudelmaier规则对模态公式序列的有效性进行判定,从而建立了RCC62*的推理系统。(5)空间凹形区域的定性形状表示形状是空间对象的重要特征。空间推理中主要使用定性方法描述对象的形状特征。以基于区域的形状表示法为主线,分析了Cohn提出的一种基于连接关系和凸壳概念的分层定性形状表示法;在此基础上,指出Cohn方法中存在的不足之处,并给出一种改进的凹处同异侧关系判断方法,其判断结果更加合理。综上所述,本文在空间推理方面的综述,为定性空间推理中复杂对象空间关系建模的进一步研究明确了方向。关于简单凹形区域间拓扑关系模型RCC62的研究,一定程度上完善了RCC23模型,增强了模型的表达力和实用性。结合RCC62模型和模态化的凸壳算子,给出了拓扑关系模型RCC62*的表示系统。基于Gentzen的相继式演算推理方法,建立了RCC62*的推理系统,一定程度上实现了表达力较强、形式化程度较好且计算复杂性较低的空间建模方法。关于定性形状表示方面的研究,弥补了以往空间关系建模中缺少对空间对象本身进行有效表示的不足。总之,本文的研究结果对复杂对象拓扑关系建模、空间对象的定性形状表示、基于模态逻辑的定性空间推理以及地理信息系统、空间数据库和空间查询等,具有一定的理论意义和应用价值。更多还原

【Abstract】 In all the research methods of Artificial Intelligence, the representation and reasoning of time and space is always one of the most important components. In recent years, spatio-temporal reasoning has become the hot researching directions, which makes it the one of the important researches in Geographic Information System, Robotics Navigation, Image Understanding, Computer Vision and Spatio-Temporal Database.Among the various spatial relations, the topological relation between spatial objects is the most basic one, which is one of the basic problems in the research of qualitative spatial reasoning. Therefore, research on the model of spatial topological relation became the hot issues in spatial reasoning, and has played a very important role in qualitative spatial reasoning. The methods for modeling spatial topological relation are classified into mainly two kinds, i.e. the logic-based ones and the algebra-based ones, in which the most typical models are Region Connection Calculus (RCC) and intersection model. So far, the research on spatial topological relations of simple objects are formed a mature and sophisticated theory system. However, the spatial objects are not simple but complicated in the real world. It is hard for the traditional topological models to satisfy the requirements of practical applications. Thus, it is necessary to set up the models which can describe the spatial topological relation of complicated objects, which would be one of the most important trends in the future development of spatial reasoning. The major problem in developing a useful formalism for reasoning about spatial information is the trade off between expressive power and computational tractability. Whilst Egenhofer’s representation does allow for certain inferences to be computed effectively, the scope of the theory is limited. On the other hand, although the formalism presented by Randell et al. is very expressive, since it is presented in 1st-order logic, reasoning in the calculus is extremely difficult. How to build a spatial model of topological relation which is both expressive and has a low computational tractability is one of the directions of our research work. Shape is one of the most important features of object, and is hard to describe in a qualitative way. The shape characteristic is not considered in the traditional spatial relation models which take the object as a whole. The qualitative shape representation has become an important aspect in the field of qualitative spatial reasoning as the rapid development of complex spatial relation modeling.Researches on spatial relation modeling of complex objects are currently focusing on topological relation models and directional relation models, and the work on property researching of complex spatial objects is mainly focusing on the representation of shape feature. This thesis focuses on the research problems of a special kind of complex objects in space, which is spatial concave region. The topological relation and qualitative shape representation of concave regions are surveyed and discussed. The existing models of topological relation and qualitative shape representation of complex objects are surveyed analyzed. With the topological aspects, in order to enhance the expressiveness and practicability of traditional models which take the convex region as representing elements, the algebraic method based RCC62 model which describes the topological relation between simple concave regions and the logical method based RCC62* model are proposed. With the shape aspect, focusing on the the region-based qualitative shape representation methods, an improved method for distinguishing the SameSide relation of two concavities in a concave region is proposed to resovle the problems existing in Cohn’s method for qualitative shape representation of concave regions.The major contributions and research results are as follows:(1) The survey of modeling methods on spatial relation of complex objects.Most of the existing methods in spatial relation modeling are limited for describing simple objects, the single spatial relation between simple objects in 2D space. However, the world we lived in is 3D space, the spatial object in it is also complex and there are more than one spatial relation exists in the real world, which we called complex spatial relation. The existing researches on complex spatial relation modeling mainly include the topological relation models of complex objects, the qualitative shape representation of spatial object, the 3D spatial relation models, and the reasoning of combined spatial relation. Focusing on the relative research work on topological relation and shape relation, the first-order based topological models, the modal logic based topological modesl, the algebraic based topological models and the qualitative shape representation models are surveyed and analyzed.(2) RCC62 model for representing and reasoning of simple concave regionsBased on the point set topology theory, the modeling for topological relation of simple concave regions is conducting which includes the following research work: based on 16-intersection matrix, the RCC23 are refined to RCC62. The Conceptual Neighborhood Graph and the Closest Topological Relation Graph of RCC62 are given; reasoning formalism for RCC62 is presented, from which the composition table of RCC62 can derived. There are 39 new relations in RCC62, which is more expressive than RCC23, in which the description for spatial relation is more accurate.(3) The representing system of topological relation model RCC62*On the basis of RCC62 model, the representing system of topological relation formal model is proposed in a modal way, which includes the following research work: based on the interior operator of S4 modal logic and Bennett’s modal explanation of convex hull operator, the modal definition of 16-intersection matrix is given; based on the extended intuitionistic 0-order calculus, the basic relations of RCC62 is transformed to a two-tuple structure which composed of both model constraint and entailment constraint, from which the representing system of RCC62* model is derived. The expressiveness of RCC62* is the same as RCC62, yet RCC62* has a more formal representation structure than RCC62.(4) The reasoning system of topological relation model RCC62*Several usual reasoning methods in modal logics are introduced, which include tabuleaux based, resolution based, translation based and sequent calculus based reasoning methods. Based on Gentzen’s sequent calculus reasoning method, the reasoning procedure of spatial relation is translated into the validity determination problem of the corresponding sequent of modal formula. The reasoning of spatial relations which are instances of the RCC8 relation set are analysed respectively in a 0-order classic calculus and a 0-order intuitionistic calculus. The modal convex-hull operator is then introduced and the validity testing for certain sequent of modal formula is implemented based on the modal schema of convex-hull operator and Hudelmaier’s proof rules. The reasoning system of RCC62 is then established in a modal way.(5) The qualitative shape representation of spatial concave regionsShape characteristic is one of the important features of a spatial object. The qualitative representation method is adopted for characterizing the shape features of objects in spatial reasoning. Among the region-based methods for qualitative shape representation, Cohn’s hierarchical method base on connection and convex hull is analyzed; in order to solve the problems existing in Cohn’s SameSide predicate, an improved method of qualitative shape representation for SameSide distionction of concavities is presented. The results derived using our improved method is more reasonable.The survey of research contributions in spatial reasoning, direct the further research on spatial relation models of complex object in qualitative spatial reasoning. The research work on topological relations modeling between simple concave regions, have a refinement of the RCC23 model, thus both the expressiveness and practicality of the original model are inhanced. Combined with RCC62 model and Bennett’s modal explanation of convex hull operator, the representing system of topological relation model RCC62* is proposed. The reasoning system of RCC62* is also established based on Gentzen’s sequent calculus reasoning method. The research work on modeling spatial topological relation in a modal way has the advantage of both expressive and of lower computational complexity. Research on qualitative shape representation makes up the deficiency of lacking effective description of the spatial object itself.In a word, the study results of this thesis are of both theoretical and practical benefit to further researches on modeling topological spatial relation of complex objects, qualitative shape representation of spatial object, modal logic based qualitative spatial reasoning, Geographic Information System and Spatial Database.更多还原