【作者】 王芳；

【导师】 刘大有；

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

【摘要】 本文围绕方向关系推理以及多种空间关系结合推理展开一系列的研究工作，研究内容包括以下几个方面：1.从定性空间信息的表示和推理两个方面阐述了定性空间推理的研究现状及热点问题。重点介绍了基于区域的定性空间推理模型，包括区域连接演算、区间代数、矩形代数以及主方向演算。2.研究了空间主方向关系的逆关系推理。给出了推理矩形主方向关系及一般主方向关系的逆关系的算法，证明它们是正确完备的，并给出了主方向演算中全部218个基本关系的逆关系表。3.给出一种新的主方向关系复合推理算法，证明该算法是正确完备的，并指出对算法做两处改动就可以使之用于REG*区域集合上的主方向关系推理。4.给出主方向演算的一个新的易处理子集——饱和凸矩形主方向关系集合。证明出其上的相容性问题可以利用路径相容算法在多项式时间内得到判定，并证明出该子集是主方向演算的一个子代数。5.研究了RCC-8关系、矩形主方向关系以及定性尺寸关系三者结合的定性空间推理。提出一种面向三种关系结合的相容性判定算法——TRIPATH-CONSISTENCY，证明出该算法的时间复杂性为O(n3)，空间复杂性为O(n2)。进一步证明出当限定所考虑的区域集合为矩形区域，所输入的关系集合为基本RCC-8关系集合、基本矩形主方向关系集合以及定性尺寸关系集合时，算法TRIPATH-CONSISTENCY对于判定结合后的约束网络的相容性是充分的。更多还原

【Abstract】 Space is a fundamental part of our life. Our whole existence is embedded in space.Perceiving space, representing space, reasoning about space, and communicating about spaceare the major abilities and requirements of any intelligent system. Therefore, it is an importanttask of Artificial Intelligence research to provide methods for handling spatial information.There are mainly two different approaches for representing spatial knowledge, thequantitative approach and the qualitative approach. The quantitative is the classical approachwhich depends on numerical values. However, when describing a spatial configuration orwhen reasoning about such a configuration, often it is not possible or desirable to obtainprecise quantitative data. In these cases, quantitative approach doesn’t work, and qualitativeapproach may be used. Qualitative reasoning is an approach for dealing with commonsensespatial knowledge without using numerical computation.Qualitative spatial representation and reasoning (QSR) has become an important subfieldof Artificial Intelligence. QSR has gained increasing popularity in recent years withapplications in spatial information systems, navigation, natural language understanding,spatial databases, spatial data mining, computer vision, CAD/CAM and so on. However, thereare still several problems in existing researches in QSR and need to take some further anddeep investigations.In this paper, we do some researches on reasoning about cardinal direction relations andabout combining different spatial relations. We start with an overview of qualitative spatialrepresentation and reasoning, and especially focus on those models based on regions,including Region Connection Calculus (RCC), Interval Algebra (IA), Rectangle Algebra (RA)as well as Cardinal Direction Calculus (CDC). Then, we carry out and complete the following research contents:1. The inverse and composition operations are used as mechanisms for inferring new spatialrelations from existing ones. Such mechanisms are typically an essential part of theoryresearch and practical application, e.g. consistency checking, preprocessing spatial queries,identifying tractable subclass of a set of relations, and so on. Inverse and composition arealso an essential part of Relation Algebra, so their formal study is a prerequisite to anyalgebraic approach to spatial reasoning. In this thesis, we investigate the two problems ofthe CDC which is a cardinal direction relation model proposed by Goyal and Egenhoferfor extended objects.（1） Research on computing the inverse of cardinal direction relations (CRs). We firstdevelopment an algorithm for computing the inverse of rectangle-CRs, which is a setof a special type of CRs defined in CDC, by exploiting the evident connectionbetween basic rectangle-CRs and interval relations. Then, we consider progressivelythe general cardinal direction relations in CDC, the inverse of which is computed byreducing to the computation of the inverse of rectangle-CRs. Analyzing in theoryand the final results both demonstrate that our algorithms are correct and complete.（2） Research on composing cardinal direction relations (CRs). We first propose a novelmethod for computing the composition of cardinal direction relations over connectedregions. We demonstrate our algorithms are correct and complete. Then, ouralgorithm is adapted to compute the composition of cardinal direction relationsbetween possibly disconnected regions.2. Research on tractable subclass. We present a new tractable subclass of CDC: the set ofsaturated-convex rectangle cardinal direction relations which we redefined and contain400relations. We also prove that the path-consistency method is sufficient for decidingconsistency in the new subclass.3. Research on combining different spatial relations. We addressed the problem of combiningthree types of spatial relations, namely topology relations, expressed as RCC-8contraints,qualitative size relations(QS), and direction relations, expressed as rectangle-CRscontraints. We present a cubic time path-consistency algorithm, namedTRIPATH-CONSISTENCY, for processing a set of constraints that combine RCC-8, QSand rectangle-CRs. We show that when only basic RCC-8relations, basic rectangle-CRs,and any QS relations are used, the algorithm TRIPATH-CONSISTENCY is correct and complete for deciding the consistency of the combined sets of constraints.更多还原