相容关系及其应用

该文从相容关系的概念及冲突关系的形式描述入手,研究了冲突关系与相容的的数学原理,构造了集合的划分算法,并运用划分算法设计程序解决了补考安排问题。     

有限集上相容关系的完全覆盖的基数估计与求解程序设计

该文对有限集上相容关系以及对应完全覆盖的基数进行了分析估计,得到了相应的几个估计公式,并对相容关系所对应的完全覆盖及其所含元素个数的求解设计了相应的程序。     

一种基于相容关系的聚类算法*

聚类分析是数据挖掘中一个重要研究内容。传统的聚类算法可划分为硬聚类和模糊聚类两大类,提出一种基于对象集上的相容关系的聚类算法,该算法通过极大相容簇来对数据对象集进行分类,使得同一对象可以属于不同的簇,而每个簇又有自己独有的成员对象,从而得到既不同于硬聚类也不同于模糊聚类的聚类效果。实验进一步表明了该算法的聚类的合理性。     

基于相容关系的粗糙集理论的推广

文章给出了一种基于相容关系的推广的粗糙集模型。当传递性不能满足时,等价关系弱化为相容关系,用相容核代替等价类来构造上、下近似算子,从而给出一种推广的粗糙集模型。较之于以R(x)代替等价类所得到粗糙集模型,该文所得到的上、下近似算子分别是闭包算子和内部算子,而且对未知知识的(近似)刻画更为精确。     

相容关系下的覆盖粗糙集

为了更有效地覆盖粗糙集理论应用到数据挖掘领域,所以对相容关系下的覆盖粗糙集进行了一系列的探究。首先介绍了基于相容关系的覆盖的定义以及基于相容关系的覆盖的特例--最大相容类的集合生成的覆盖的一些性质;其次对相容关系下由所有最大相容类的集合生成的覆盖中的可约元进行了讨论,并对这个条件下覆盖是否为单一的覆盖进行了探讨;接着借助于最小描述提出了k-最简覆盖这个概念,并对其做了简单的探究;最后探究了一些评价相容关系下的覆盖粗糙集的数值标准,并且分析了绝对覆盖率和相对覆盖率相等的情况。     

相容关系下的分割知识约简算法的研究

粗糙集理论是一个能有效地删除冗余特征的工具。由于实际应用的数据往往是连续的,并且结构复杂、特征多,现有的粗糙集知识约简方法对真实复杂的数据计算效率较低。为此,首先将相容关系应用于粗糙集的知识约简,再将复杂的信息表纵向分割成简单的缩减表和小规模信息表,然后把缩减表和小规模信息表连接起来进行知识约简。实例表明,提出的方法能够有效提高粗糙集对复杂数据的计算效率。     

一种微指令格式的设计方法及其应用

一条微指令中含有多个要并行执行的微命令，但一个微机系统的所有微命令中的某些微命令根本不可能同时存在于同一微指令中。本文根据这五约束条件，设计出一种将相斥性的微命令放在微指令中的相同段，而相容性微命令放在不同段，从而既保证微命令并笔执行，又保证点的位数最少的微指令字的形成方法。     

几类相容粗糙集模型的研究

在经典粗糙集模型中,上、下近似满足很多好的数学性质,其中包括对偶性。在一般粗糙集模型中,这些性质中的某一些不再被满足。Yao给出了在一般粗糙集模型中定义上、下近似的新思路,即首先利用对象的邻域定义下近似（上近似）,然后再将上近似（下近似）定义为该下近似（上近似）的对偶。为保留经典粗糙集模型中一些好的数学性质,根据Yao的方法,在相容粗糙集模型中利用最大相容类对偶地定义了两类新的上、下近似概念,并讨论了它们的性质。对比发现,这两类新的上、下近似保留了大部分初始相容粗糙集模型中上、下近似所满足的性质,且有新的性质成立。     

基于相容矩阵的改进属性约简算法

原属性约简算法在计算相容关系时,存在大量重复计算,从而导致时间复杂度为O(|C|3|U|2)。针对该问题,基于不完备决策表,提出时间复杂度为O(|U|2)的高效相容矩阵计算算法,在此基础上,设计改进的基于相容矩阵的属性约简算法。通过实例证明,当空间复杂度相同时,改进算法的时间复杂度从原有O(|C|3|U|2)降为O(|C|2|U|2)。     

概率最大受限路径相容算法

研究了可用于求解约束满足问题的最大受限路径相容算法(maxRPC).maxRPC算法执行过程中有大量无效的寻找路径相容证明(PC-witness)的操作,有效地识别和避免这些无效的寻找PC-witness的操作,可以提高maxRPC算法的求解效率.首先,提出了在一条约束上任意两个相容的值在任意路径上存在PC-witness的概率;然后,基于这一概率提出了一种概率最大受限路径相容算法(PmaxRPC),并将新算法成功应用于求解约束满足问题的回溯搜索.实验结果显示:PmaxRPC可以避免一部分无效的寻找PC-witness的操作,在求解约束满足问题时,PmaxRPC效率高于maxRPC.在某些测试用例上,PmaxRPC比maxRPC和最流行的弧相容算法效率更高.     

虚拟现实中手与虚拟物体碰撞检测的一种算法

在虚拟现实技术中，人与虚拟空间物体的碰撞检测是非常重要的研究课题之一。由于空间物体结构的复杂性和碰撞响应的多样性，故找出一种通用检测算法是极为困难的。该文针对飞机机舱内的可操纵物体：开关，按钮，油门杆，停车杆等，实现了一种实时精确的碰撞检测算法。     

一个计算凸多面体间碰撞点的快速算法

计算两个物体之间的碰撞点是碰撞响应的基础,也是一项系统开销很大的任务.因此,研究碰撞点快速求解算法对碰撞响应的实时性具有重要意义.该文提出了一个算法,当在虚拟环境中检测到碰撞时,应用此算法可以在碰撞响应之前快速计算出两个物体之间的准确碰撞时间,并能计算出此时两个物体之间的碰撞点.     

对简化轮数的SNAKE(2)算法的碰撞攻击

为了研究简化轮数的SNAKE(2)算法抵抗碰撞攻击的能力,根据算法的一个等价结构,给出了SNAKE(2)算法的一个6轮区分器。通过在此区分器前后加适当的轮数,对7/8/9轮的SNAKE(2)算法实施了攻击。其攻击的数据复杂度依次为O(2⁶)、O(26.52)、O(2¹⁵),时间复杂度依次为O(29.05)、O(218.32)、O(226.42),攻击结果优于对SNAKE(2)算法的Square攻击。     

一种基于正关系的多Agent协调算法

多Agent之间的协调(coordination)与协作(cooperation)已经成为多Agent系统(multiagent system,MAS)中的一个关键问题。这是因为MAS的主要研究目标之一就是使得多Agent的信念、意图、期望、行为达到协调甚至协作。在开放、动态的MAS环境下,具有不同目标的多个Agent必须对其资源的使用以及目标的实现进行协调[1,4]。例如,在出现资源冲突时,若没有很好的协调机制,就有可能出现死锁。而在另一种情况下,当单个Agent无法独立完成目标,需要其它Agent帮助时,则需要协作。本文提出了一种基于正关系的多Agent协调机制和协调算法。在该算法中,通过使用这种协调机制,Agent能委托或接受交互中的子计划,从而形成系统负载均衡和有效降低系统运行开销。     

实时碰撞检测算法的探讨与研究

本文对碰撞检测算法的分类进行了阐述,并比较了按层次包围盒法分类的包围盒AABB、包围球、方向包围盒OBB、固定方向凸包的包围盒FDH、时空包围盒检测算法（STBB）的构造难度高低,存储量大小和相交测试复杂度高低等方面。同时,也对空间分割法下的各类算法进行了分析。最后介绍了两种新趋势下的混合碰撞检测法进行了归纳研究,并总结了算法的优劣和新的方向。     

不规则图形排样系统中靠接算法比较研究

对不规则图形排样过程中的判交和碰靠过程进行了分析和比较,重点讨论了基于位图的判交和碰靠技术。实验表明：该方法计算量较小,从而较大幅度提高了不规则图形的排样速度。     

一种软构件依赖关系的拓扑布局算法

本文提出了一种圆环型的有向图拓扑布局算法,能够清晰地展示软构件之间的相互依赖关系,有助于设计人员更好地理解和分析多构件系统中构件间依赖关系的整体态势,进而优化系统结构,提高系统性能,实现高效的软构件组装。     

自治水下机器人避碰算法及其仿真研究

为了提高水下机器人(AUV)在复杂海洋环境下的自适应性,文章对传统的避碰方法进行了改进.对AUV的禁入区和潜在碰撞区进行了安全性分析.建立了前视声纳模型以及三维水下规划空间模型.提出了基于强化学习、BP神经网络及人工势场相结合的避碰算法.在AUV与环境的试错交互中,借助于来自成功和失败经验的奖励和惩罚值,不断改进水下机器人的自治能力.设计了AUV深度行为模糊协调器, 对潜深行为和距底高度行为进行协调融合.开发了AUV运动规划与仿真的半实物软件系统,仿真试验证明了算法的合理性与可行性.研究对于提高AUV的自主性和安全性具有重要的应用价值.     

基于Sphere和OBB混合的碰撞检测算法

层次包围盒是碰撞检测中常用的方法。实现了一种混合使用Sphere和OBB两种包围盒的碰撞检测算法,这种算法在包围盒树的上层使用Sphere,下层使用OBB,吸取了Sphere构造简单,相交测试简单以及OBB紧密性好的优点,可以快速排除没有发生碰撞的对象,在对象发生旋转之后仅需要对下层OBB部分进行相应旋转。通过灵活选择不同层次的数量,可以适用于不同的虚拟场景。通过模拟两辆汽车碰撞的实验,证明了算法在检测速度上优于仅适用OBB的RAPID算法。     

Collision Detection Algorithm to Distinguish Between Intended Contact and Unexpected Collision

Industrial and service robots often physically interact with humans, and thus, human safety during these interactions becomes significantly important. Several solutions have been proposed to guarantee human safety, and one of the most practical, efficient solutions is the collision detection using generalized momentum and joint torque sensors. This method allows a robot to detect a collision and react to it as soon as possible to minimize the impact. However, the conventional collision detection methods cannot distinguish between intended contacts and unexpected collisions, and thus they cannot be used during certain tasks such as teaching and playback or force control. In this paper, we propose a novel collision detection algorithm which can distinguish intended contacts and unexpected collisions. In most cases, the external force during a collision shows a noticeably faster rate of change than that during an intended contact, and using this difference, the proposed observer can distinguish one from the other. Several experiments were conducted to show that the proposed algorithm can effectively distinguish intended contacts and unexpected collisions.