结合方向关系和拓扑关系的约束满足推理

结合定性空间推理中的区域连接演算（RCC）和基于区域的主方向关系模型,应用拓扑和方向关系上的复合表,将方向关系和拓扑关系的推理看作约束满足问题（CSP）,给出了结合RCC8和主方向关系的约束满足问题推理算法,该算法可结合拓扑关系和方向关系进行推理。     

RCC5与主方位关系结合的定性空间推理

解决实际问题需要将多方面空间信息结合进行推理,仅考虑单方面空间信息是不够的.多方面空间信息结合推理已成为定性空间推理的一个研究热点.现有拓扑与方位结合推理工作主要集中在与基于最小外包矩形或单片方位模型的结合.方位信息描述是近似的,不适于精确推理;因此分别采用主方位模型和RCC5描述方位、拓扑信息.根据定义给出基本RCC5和主方位关系间的相互依赖及异质复合表;讨论了其上约束满足问题,得到一个路径相容算法,并分析了推理复性问题.     

基于粒度层次的方位关系推理

方位关系推理是空间推理的一个重要方面。本文主要研究的是方位关系推理的问题之一——基于层次的方位关系表示与推理。文中首先从区域间的覆盖关系出发,提出了基于空间粒度的层次划分方法;然后,从“点对象”和“矩形对象”两个方面研究了基于粒度层次的方位关系表示与推理方法,并给出了相应的推理算法。文中的推理实例验证了粒度划分与推理方法的可行性。     

结合拓扑和方位的定性空间推理方法*

空间区域的拓扑关系和方位关系是空间推理的重要研究内容,以往的工作集中在单一的空间方面, 这不能满足实际应用领域的需要.基于主方位模型给出了主方位关系的形式化定义,考虑到拓扑与方位间的相互依赖关系,提出了结合拓扑和方位的定性表示与推理算法,能够处理多方面空间信息,在空间数据库和机器人导航等领域具有实际应用价值.     

基于MBR的拓扑、方位、尺寸结合的定性空间推理

解决实际问题需将多方面空间关系结合进行推理,多方面空间关系结合推理已成为定性空间推理的研究热点;已有工作主要集中在两方面空间关系结合,缺少两方面以上空间关系结合工作.为解决上述问题,通过最小外包矩形近似表示区域对象,利用其在坐标轴上投影间的关系表示相应空间关系;提出扩展矩形关系模型,实现拓扑、方位和尺寸关系的统一表示和推理;给出RCC8、主方位及尺寸关系转换成扩展矩形关系的转换算法;讨论其上关系取反和复合,指出其复合是基于相容性而非存在性;证明(强预)凸扩展矩形关系约束网是可处理的.     

基于结合空间拓扑和方向关系信息的空间推理

结合了定性空间推理中著名的区域连接演算（region connection calculus,RCC）和基于区域的方向关系演算（cardinal direction calculus,CDC）,并且给出两个演算在两个方向上的交互表,即RCC8-To-CDC和CDC-To-RCC8．给出了结合RCC8和CDC知识的约束满足问题的路径一致算法（path consistency algorithm）（该算法是对Allen著名的路径一致算法的修改）,并且采用两个队列实现了该算法,采用这种结构可以实现并行计算．在该算法中,基于以上两个交互表的交互操作被嵌入到算法里面来保证整个约束满足问题的一致性．算法的计算复杂性证明是多项式的,     

基于标识变化的时空推理

空间变化是空间信息处理中的热点问题,标识变化是空间变化的关键问题之一.但是现有工作侧重表达,知识推理能力较弱.为此,研究了基于标识变化的时空推理问题.给出了基于多段图和集合论的标识变化形式化语义,在此基础上定义了二元关系模型.针对基本关系约束满足问题,提出了构造性求解算法,并证明了代数封闭算法可解;针对全关系约束满足问题,提出了一致场景算法.理论分析和实验应用均表明该方法能有效解决信息不完整、不准确情况下的标识变化表示与推理问题,对此类问题其它同类模型尚不能很好解决.     

混合维拓扑和尺寸关系的定性空间推理

定性空间推理(QSR)研究空间关系,多数工作集中在单维空间关系,但在地理信息系统(GIS)中多维对象很常见.混合维对象空间关系是指点、线和区域3类对象出现在同一场景的情况,该类问题对定性空间推理研究有着重要的理论意义和应用价值.但这方面的研究工作还比较少.在已有的混合维区域连接演算的基础上进行完善,提出了MRCC5混合维拓扑模型,并研究了其上约束满足推理问题的复杂度.对定性尺寸关系进行了混合维扩展.给出了MDS模型,进而研究了其推理问题.在以上工作基础上.提出了RCCA和MDS的结合模型,给出并分析了结合模型的推理算法.将定性空间推理相关研究推广到混合维领域,深入研究了混合维拓扑关系推理,提出了混合维尺寸以及混合维拓扑尺寸结合模型.     

面向语义Web语义表示的模糊描述逻辑

分析了语义Web语义表示理论的研究现状及存在的问题,提出了一种新的面向语义Web语义表示的模糊描述逻辑FSHOIQ(fuzzy SHOIQ).给出了FSHOIQ的语法和语义,提出了FSHOIQ的模糊Tableaux的概念,给出了一种基于模糊Tableaux的FSHOIQ的ABox约束下的可满足性推理算法,证明了可满足性推理算法的正确性.提出了FSHOIQ的TBox扩展和去除方法,并证明了FSHOIQ的TBox约束下的包含推理问题可以转化为ABox约束下的可满足性推理问题.FSHOIQ为语义Web表示和推理模糊知识提供了理论基础.     

三维几何约束求解的自由度归约算法

三维几何约束求解在装配设计、几何造型和动力学分析等领域有着广泛的应用．在分析基本几何元素间的约束关系对刚体自由度状态影响的基础上,提出刚体自由度的归约算法,以求得满足约束后刚体的自由度状态空间;以刚体自由度状态空间分析为基础,实现对合理约束的推理求解和约束一致性维护,该算法解决了三维几何约束求解中自由度计算问题,同时避免了一些推理求解算法中出现的“组合爆炸”问题．     

集成多方面信息的定性空间推理及应用

以往的定性空间或时空推理工作多数面向单一时空方面,这不符合实际应用需要.提出了集成拓扑、尺寸和时间3方面信息的定性表示和推理技术,并应用到时空GIS中.给出了面向GIS的拓扑、尺寸和时间的表示方法,并研究了它们之间的依赖性.提出了集成这3方面信息的约束满足问题求解算法TriRSAT.在时空GIS中,把定性时空表示用于约束关系库,把TriRSAT算法用于时空数据一致性检查和时空查询.应用结果显示,该理论和方法能有效地集成处理多方面时空信息,在时空数据库、机器人导航等领域有着广泛的应用前景.     

A condensed semantics for qualitative spatial reasoning about oriented straight line segments

More than 15 years ago, a set of qualitative spatial relations between oriented straight line segments (dipoles) was suggested by Schlieder. However, it turned out to be difficult to establish a sound constraint calculus based on these relations. In this paper, we present the results of a new investigation into dipole constraint calculi which uses algebraic methods to derive sound results on the composition of relations of dipole calculi. This new method, which we call condensed semantics, is based on an abstract symbolic model of a specific fragment of our domain. It is based on the fact that qualitative dipole relations are invariant under orientation preserving affine transformations.The dipole calculi allow for a straightforward representation of prototypical reasoning tasks for spatial agents. As an example, we show how to generate survey knowledge from local observations in a street network. The example illustrates the fast constraint-based reasoning capabilities of dipole calculi. We integrate our results into two reasoning tools which are publicly available.     

DOMAIN-INDEPENDENT TEMPORAL REASONING WITH RECURRING EVENTS

Numerous examples of temporal reasoning involve a process of abstraction from the number of times an event is to occur or the number of times events stand in a temporal relation. For example, scheduling a recurring event such as one's office hours may consider things like the relative temporal ordering of the office hours and a number of other events in a given work day. The number of times office hours will actually be held may be unknown, even irrelevant, at the time of scheduling them. The objective of this article is to formulate a domain-independent framework for reasoning about recurring events and their relations. To achieve this end, we propose an ontology of recurrence based on the model-theoretic structure underlying collective predication using plural noun phrases. We offer a calculus of binary temporal relations for temporal collections based on a well-defined transformation of interval temporal relations into recurrence relations. Finally, we describe a reasoning framework based on manipulating knowledge stored in temporal relation networks, which is in turn a specialization of the CSP (constraint satisfaction problem) framework. The reasoner manipulates recurrence relations in the network to determine the network's consistency or to generate scenarios.     

A Comparison between SAT and CSP Techniques

The aim of this paper is to establish a connection between the propositional logic and the constraint based reasoning frameworks. This work is based on a translation of the satisfiability problem (SAT) into the binary constraint-satisfaction problem (CSP). The structure of the SAT problem and its associated CSP are then exploited together for characterizing tractable SAT problems, increasing the effectiveness of the classical reduction rules: unit clause and monotone literal rules, and expressing the arc and path consistency concepts with logical inference rules. This study leads to compare the behaviors of the DP and MAC procedures for solving respectively a SAT instance and its binary CSP expression.     

基于缓冲区的扩展拓扑关系模型及应用

定性空间推理在人工智能等领域有着广阔的应用前景,但目前单方面空间关系研究较多,多方面结合研究较少,这与实际应用需求不符.由于各类空间关系具有独立性,需要找到适当的理论将它们融合,目前对于拓扑、距离结合模型的研究还不够充分.针对缺乏基本关系可处理且易于在GIS系统中实现的模型等情况,提出了一种扩展拓扑关系模型BERCC.BERCC源于RCC理论,其主要思想是通过考虑缓存区之间的拓扑关系来提高模型表达能力,同时能表达一定程度的距离信息.推导了BERCC的弱复合表,证明了BERCC基本关系是可处理的,给出了一个包括全集关系和基本关系的可处理子集,在此基础上实现了约束满足推理算法.最后,基于该理论和方法实现了一个实验系统,进一步验证了模型及算法的正确性和实用性.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

Solution Techniques for Constraint Satisfaction Problems: Foundations

The Constraint Satisfaction Problem (CSP) is ubiquitous in artificialintelligence. It has a wide applicability, ranging from machine visionand temporal reasoning to planning and logic programming. This paperattempts a systematic and coherent review of the foundations ofthe techniques for constraint satisfaction. It discusses in detail thefundamental principles and approaches. This includes an initialdefinition of the constraint satisfaction problem, a graphical meansof problem representation, conventional tree search solutiontechniques, and pre-processing algorithms which are designed to makesubsequent tree search significantly easier.     

通用几何约束系统统一建模研究

在几何约束和几何实体的基本约束和欧拉参数表达的基础上,研究了通用几何约束系统的统一建模问题。通过对三维几何实体姿态约束和位置约束解耦性的分析,抽象出球实体、盒体和球盒体三种基本几何实体表达空间几何实体,并以基本约束的组合表达几何约束,形成几何约束模型特有的层次结构;并以有向图管理几何约束系统,可以清晰地反映姿态约束和位置约束的解耦性,实现约束系统的细粒度分解,得到规模更小的求解序列,实现高效求解。方法实现于原型系统WhutVAS中。