基于Voronoi图的定性路径

定性路径是定性空间推理的一个基本概念。给出了一个基于Voronoi图的定性路径表示与推理方法。该方法应用Voronoi图的邻近关系来表示定性位置和定性路径,即用运动点所在Voronoi区域的邻域来表示定性位置,用运动点所经过的定性位置序列来表示定性路径。设计并实现了一个定性路径推理算法,基于初始Voronoi图及不同时刻所有Voronoi区域的边数来动态更新Voronoi图邻近关系,可识别出运动点并找出定性路径。实验结果表明,该方法是可行的。     

一种动态定性空间关系自动规划方法

为解决定性空间关系的规划问题,在概念邻域图的基础上提出描述动作与定性空间关系交互的邻域划分图.基于邻域划分图,提出了定性空间关系自动规划的形式化表示和推理算法,证明了算法的可靠性,并举例说明了新方法的应用.该方法在处理单方面空间关系规划中具有用通用性,在机器人导航方面具有潜在的应用前景.     

一种用于常识空间信息处理的定性空间关系模型

在空间信息处理中,一些常识空间信息通常结合多方面空间关系,而且这些空间关系是动态变化的.为了有效地表示这些复杂的空间关系,并对其进行推理,提出了一种结合拓扑、方向和大小关系的空间信息处理模型TDSC (topology-direction-size calculus),并基于TDSC模型提出了处理动态空间关系变化的表示推理框架.首先,利用同对象多属性的方法建立了融合大小、拓扑和方向关系的完备至斥基本关系表示;然后提出了复合表生成算法和推理算法,使得原有模型的表示和推理结果可以直接在新模型中使用.同时提出处理动态空间关系的邻域划分图,给出了邻域划分图的自动生成算法,以及TDSC模型的邻域划分图.最后给出基于TDSC模型邻域划分图的表示和推理框架,并结合实例说明框架的正确性和有效性.     

一个结合多方面定性空间信息的新方法

定性空间推理是人工智能领域中非常重要的研究内容.空间信息包含拓扑关系、大小关系、形状、距离等很多方面.以往多侧重于单一方面的研究,如何将孤立的各方面信息进行统一表示和推理是当前定性空间推理中的一个重要问题.提出利用结合操作来融合不同空间信息表示的新方法.利用结合操作,可以由原先完备互斥关系集合得到新关系,同时利用原有的复合表自动生成新关系的粗复合表.基于结合操作,给出2个理论模型:结合拓扑关系与大小关系模型、结合拓扑关系与远近关系模型.并提出了邻域划分图的概念,说明了邻域划分图与概念邻域图的关系.利用邻域划分图回答了Galton提出的问题:为什么LOS(视觉光线演算)的概念邻域图不同于标准的空间或时间关系的概念邻域图,这些关系的复合表中关系总是来自于概念邻域图.     

基于动作的动态空间推理

动态空间关系的表示和推理一直以来都是定性空间推理中的研究重点。通过用矩形关系来表示空间原语实体为区域的定性空间关系,对Bhatt定义的动态空间系统进行细化和扩展,定义空间实体的8个移动动作,并给出拥有多个空间实体的空间场景下区间关系在不同动作作用下的状态转移图和状态转移表,指出状态转移图和概念邻域图的区别。用一个元组对空间场景进行形式化表示,定义动态空间系统中的一个基本任务,即历史场景在空间实体动作作用下推出新空间场景,给出这个任务的解决方法,指出方法的局限和不足,同时给出一个应用场景。     

一种分层递阶的定性拓扑推理方法

文章针对现有的定性表示方法和拓扑推理算法存在的问题,提出了一种新的方法.首先,提出了基于概念邻域结构的定性表示方法.然后,给出了不同粒度层次上拓扑关系复合表的计算方法.最后,设计得出分层递阶的拓扑推理算法.文章给出的方法具有较高的认知合理性,所提出的推理算法可根据问题来选择合适的表示和推理层次,在已有推理算法给不出解的情况下,可以给出问题的合理解,对一般定性推理研究有参考价值.     

基于区域延伸的定性空间表示

在区域连接演算(region connection calculus,RCC)理论基础上给出了区域延伸的形式定义.通过区域延伸,定义了关联空间的概念,进而提出了空间表示的一个模型,在这个模型中给出了空间中物体的空间拓扑关系、距离关系、方向关系以及位置等信息的定性表示.智能体对空间关系的确定是通过区域延伸实现的,模型为智能体在约束空间环境中的行动推理提供了一个新的表示方法.     

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

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

传感环境下基于局部Voronoi图的启发式反监控路径发现算法

针对移动对象通过传感区域时的安全问题,提出了一种基于局部Voronoi图(VT)的启发式反监控路径发现算法.首先,给出了一种基于局部Voronoi图的路径暴露风险近似估算模型.在该模型中,移动目标可依据当前探测到的传感器节点位置信息动态生成局部Voronoi图,并可依据定义的暴露风险计算公式近似估算出局部Voronoi图中各条边所对应路径的暴露风险.然后,在此基础上设计并实现了一种启发式的反监控路径发现算法.在该算法中,移动目标可首先基于局部Voronoi图确定自己的下一跳位置点候选集,然后再基于定义的启发式代价函数从候选集中选择一个风险代价最小的位置点作为其下一跳目标位置点.最后,沿着局部Voronoi图中对应的最小暴露风险路径移动到该目标位置点.理论分析和实验结果表明,所提算法具有良好的反监控性能,针对部署有n个传感器节点的区域,能够使得移动对象在不超过O(n log n)的时间内快速找到一条具有较低暴露风险的路径来穿越整个传感区域.     

基于方向关系组合运算表的定性推理

方向关系的定性推理是GIS中的一个重要的理论问题。本文介绍基于井字空间的方向关系定性表示。着重讨论基于方向关系组合运算表的定性推理，最后给出一个基于方向关系组合运算表的定性推理算法。     

用Voronoi多边形扩展的空间数据模型

Voronoi图是一种基本几何结构 ,也是解决相关几何问题的有效的工具 .为了有效地解决 GIS中的空间目标间关系的动态构建、显示等问题 ,首先重点探讨了用 Voronoi图扩展的空间数据模型 ,然后主要从空间数据建模语义的角度出发 ,在研究 GIS面向对象的空间数据模型的基础上 ,提出了用 Voronoi多边形来部分地代替面向对象的数据模型间的关系定义 ,并给出了一个基于 Voronoi多边形的面向对象数据模型的框架 .该模型由于利用了Voronoi图具有的能良好地表示空间目标邻近关系的特性 ,并且由于通过空间目标的位置 ,能动态地获取和显示空间目标间的邻接关系 ,因而可以有效地弥补目前拓扑数据模型中 ,计算更新复杂及不能表示空间上邻近 ,而几何上不相接目标间的空间关系和栅格数据模型中不能有效地表达目标间拓扑关系的不足的问题 ,实践证明 ,这是一种较为理想的表示复杂空间关系的数据模型 .     

基于属性Petri网的属性粒推理研究

不确定性知识处理是人工智能研究中经常遇到的问题,基于定性映射的属性Petri网模型在动态表示认知思维中不确定性知识与逻辑推理方面具有优势。在属性拓扑空间中,给出了属性粒的基本定义和基本推理,在属性Petri网中对不确定性知识进行表达,并基于属性Petri网给出归结推理的基本形式和基本算法。结果显示,这种方法可以使定性映射和Petri网更易于动态和显式地表达认知不确定性知识,可为进一步研究Petri网在认知模型中的作用提供参考。     

基于定性约束的故障诊断设计

在B. J. Kuipers的QSIM算法基础上,提出了比较约束概念用于消减推理空间。给出了各定性约束的传递规则,用于对系统的推理仿真。以系统故障的观测结果为初始状态,依据约束流的传播,诊断变量异变的位置和原因,并把诊断结果进行正向推理,消除部分冗余。在压缩制冷系统实例中,根据制冷系统的定性微分方程建立约束关系。针对制冷效果不佳的症状,仿真诊断出故障源为系统中有空气或氟利昂充液量过大的故障,与实际系统相一致。     

基于空间球理论的定性空间表示

主要研究了三维空间中空间对象的关系表示,介绍了利用部分学理论和形态学理论定义空间球的方法.根据Bran-don Bennettd的RBG理论,定义了空间球的形态关系及判断方法,提出了空间球全等的公理系统,给出了利用空间球模型定性表示方向关系和距离关系的方法.智能体对空间关系的确定是通过空间球实现的,该模型为智能体在约束空间环境中的行动推理提供了一个新的表示方法.     

多种空间关系和时间结合的定性时空推理

空间实体之间存在多种时空关系,主要包含拓扑、方向、距离、尺寸和时间等.以往的研究工作主要集中于3种以下时空关系结合的表示和推理,而3种以上结合的研究很少.但多种时空关系之间是相互统一和相互约束的,所以,将它们全部综合起来研究是时空推理研究发展的必然趋势,也是实际应用的迫切需要.提出了采用矩形关系统一表示多种空间关系,以矩形关系变化次数表示时间的时空统一表示模型,并在此基础上,利用概念邻域图推导空间关系变化和时间变化.据此,结合矩形关系网络和路径一致性算法,提出了检验上述统一模型网络一致性的算法,并分析了算法复杂度.该研究成果提高了空间关系分析方法的准确性,减小了时间信息的冗余,对地理信息系统中空间实体间的空间关系以及时间变化的分析和查询等有一定的理论意义与应用价值.     

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

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

基于定性互信息的定性概率网歧义性约简

针对符号传播算法在符号相反的两条平行路径上进行推理时常常产生歧义性,提出一种基于定性互信息的歧义性约简方法。首先,给出定性互信息的严格定义。然后,提出基于定性互信息影响强度的定性概率网,进一步区分影响强度,并证明具有强度的定性影响的对称性、传递性和复合性。最后在Antibiotics数据集上,通过与已有方法推理结果的对比实验,验证该歧义性约简方法的正确性和高效性。理论分析和实验结果表明,基于定性互信息的定性概率网既保留定性推理的简明性,又能够有效约简定性推理的歧义性。     

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

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

拓扑关系的闭球模型及复合表的推导

Egenhofer和Franzosa提出的拓扑关系的4-交集模型是定性空间推理中常用的模型，但基于4-交集模型难以推导出拓扑关系的完备集、概念邻域和复合表．本文以拓扑学为基础，提出了（n，n）完备集的概念，建立了拓扑关系的闭球模型．基于闭球模型可以直接推导出拓扑关系的（n，n）完备集和概念邻域以及复合表．结果表明，对定性空间推理来说，闭球模型比4-交集模型更简单有效．     

多边形中的点可见性快速算法

针对点的可见性计算这一计算几何中的基础问题,提出一种支持任意查询点的可见多边形快速计算的基于多边形Voronoi图的点可见性算法.以与Voronoi骨架路径对应的Voronoi通道概念,以及相应的局部最短路径概念为基础,按照深度优先策略对Voronoi图进行遍历,在计算Voronoi骨架路径的同时计算局部最短路径,并基于局部最短路径计算所遍历的多边形边的可见部分.该算法可以处理“带洞”多边形,而且只对多边形进行局部访问;对于“带洞”多边形,由于该算法的数据结构比较简单、剖分空间合理且易于实现,因此仅需O(n)空间和O(nlgn)预处理时间.最后给出了在三维室内虚拟场景设计与漫游系统中的应用实例,结果表明文中算法是实际可行,且运行时间与点的可见多边形的边数和多边形的边数均呈线性关系.