装配序列生成的有序二叉决策图技术研究

为提高装配序列规划求解效率,在图论割集法的基础上,引入有序二叉决策图描述装配关联图、装配操作、装配几何可行性和装配稳定性。利用装配优先约束关系,简化装配关联图,设计了基于符号有序二叉决策图技术的装配序列生成算法,分析了该算法的时间复杂度。在每一次割集分解之后,检验子装配体的几何可行性和稳定性,实现装配序列生成过程中状态空间的隐式表示和搜索。研究实例验证了基于符号有序二叉决策图技术的装配序列生成算法的可行性和有效性。

基于符号有序二叉决策图的装配序列生成技术

为提高装配序列规划求解效率和自动化水平,给出了装配体联结图模型、干涉向量和接触向量模型的有序二叉决策图描述,建立了基于符号有序二叉决策图模型及操作的可行装配序列生成技术。结合实例验证了基于有序二叉决策图的装配体模型和可行装配序列生成技术的正确性和可行性。

基于有序二叉决策图的装配序列符号表示方法

通过建立装配状态的二进制编码和装配操作的布尔特征函数,给出了装配序列描述的有序二叉决策图(OBDD)方法;建立了从装配序列的与或图模型到OBDD模型的转换规则;并对装配序列表示的与或图模型和OB-DD模型进行了存储效率比较.实验结果表明:OBDD方法具有较好的存储性能,可以改善复杂装配体的装配序列表示的存储效率,适合于复杂装配体的可行装配序列的描述.

一类新型抽象数据类型:有序二叉决策图

有序二叉决策图OBDD(Ordered Binary Decision Diagram)是布尔函数的一种规范表达形式、一种的新的数据结构。基于OBDD能够完成布尔函数的有效表述和操作运算,可以看作为一类新的抽象数据类型。OBDD在VLSI逻辑综合和验证的成功应用结果引起了学术界和工业应用界的极大关注。迄今为止,OBDD技术及其工业应用已有了长足的发展、产生了不少的研究结果。本文对OBDD相关技术问题、OBDD扩展形式、OBDD应用等方面的研究现状进行了综述和讨论。

基于有序二叉决策图的路径规划可行性研究

对全局环境未知且存在障碍物情况下的移动机器人路径规划问题进行了研究。借助有序二叉决策图的原理,首次采用有序二叉决策图数据结构来表示机器人工作空间中的信息环境模型,并对它们进行了二进制编码,建立一个有效紧凑的OBDD环境模型。利用该OBDD模型能自动规划了免碰撞路径,获取一条从起始状态(包括位置及姿态)到达目标状态的安全、高效的无碰路径。实验仿真结果表明,所提出的方法是正确和有效的。

有序二叉决策图在防火墙规则库设计中的应用

在防火墙规则库的设计中利用有序二叉决策图(ordered binary decision diagram,OBDD)来表示防火墙的访问控制规则集,改变了传统的顺序存储规则的规则库设计方法,以增加预处理时间为代价,有效地提高了规则的匹配速度,从而提高了防火墙的性能及其安全性.

产生式知识的有序二叉决策图表示及其推理

为了更完整地表示产生式规则构成的知识库及更有效地进行知识推理,给出了基于有序二叉决策图OBDD(Ordered Bi-nary Decision Diagram)的产生式知识表示模型。在此基础上实现了基于OBDD的知识推理规则及相关算法,并结合实例对OBDD模型及其推理规则的可行性进行了分析。

基于有序二叉决策图的粗糙集属性约简的符号方法

针对现有属性约简算法主要基于代数表示和信息表示的方法,基于改变属性约简问题的知识表示方法,提出区分矩阵的有序二叉决策图(OBDD)的表示方法。给出了属性约简的区分矩阵模型到OBDD模型的转换方法,得到了信息系统的区分矩阵的OBDD模型,并对区分矩阵表示和OBDD模型的存储空间进行了实验对比。结果表明,OBDD模型具有较好的存储性能,可降低对象数量和属性个数较多的信息系统的属性约简问题的空间复杂度。

基于二叉决策图的状态组合爆炸问题并行求解方法

布尔函数的可满足性和等价性等问题的NP完备性所导致的状态组合爆炸问题严重地限制了大规模、甚至工业小规模问题的解决。然而在实际问题的处理中,对布尔函数采取恰当的描述并建立相应描述下的操作算法,可以有效地减缓甚至避免问题处理过程中的状态组合复杂性。而本文就是利用了OBDD来建立布尔函数模型并求解实际问题,结果在效率上较传统方法有很大提升。

考虑安全性需求的航空电子网络可靠性模型

航空电子网络的可靠性水平表征其对航电任务完成能力的支撑程度,基于单一连通性考虑的网络可靠性模型仅涵盖了网络的结构信息,无法有效评价网络对不同安全关键任务的支撑能力,影响对网络安全性的真实评价。提出了一种综合考虑任务安全关键属性和网络结构属性的航电网络可靠性分析模型。基于安全关键度邻接矩阵,采用边扩张分解创建网络的有序二叉决策图,实现对网络可靠性的评价。通过分析实际航空电子全双工交换式以太网(avionics full-duplex switched ethernet,AFDX)交换机网络,在加入4个等级的任务安全约束(safety constraint of task,SCT)后,可有效剔除高风险路径,任务在网络中可传输的链路安全关键度累积平均分别降低1.19%、9.47%、29.18%和58.14%。

二值图像序列的符号OBDD表征模型的研究

利用有序二叉决策图OBDD对二值图像序列数据进行建模,根据图像序列的帧间相关性,图像序列的OBDD共享了大量结点,节省一定的存储空间,为图像序列的有关处理提供了一个新的数据表示方法。

基于OBDD的灰度图像无损压缩算法

提出一种基于有序决策二叉图(OBDD)的灰度图像无损压缩算法,该算法将灰度图像划分成独立的位平面,利用二值图像的开关性,用OBDD模型来表征位平面,然后对OBDD进行有效的编码,最后用算术编码压缩进一步减少冗余。实验结果表明,本算法的压缩比优于WinZIP。

基于OBDD的含圈与或图搜索算法研究

在含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明,该算法在处理大规模含圈与或图时具有明显优势。

提高产品装配联接图分解效率的算法研究

割集生成算法和子图过滤算法是基于割集的装配序列规划的基础,本文通过分析不同基本割集组合之间的关系,设计了更合理的割集生成算法,同时还引进了有序二叉决策图OBDD表示子图集合,设计了更高效的算法以过滤已分解的子图,从而提高了装配联接图的分解效率.

基于OBDD的有向图的存储与操作研究

本文讨论了一种基于OBDD的有向图的存储结构,给出了基于OBDD的有向图的操作方法及搜索算法。实验结果表明,该存储结构与传统的邻接表的存储结构相比,在处理大规模的有向图时,具有较高的存储效率。

基于符号OBDD的子图同构约束求解算法

针对求解子图同构问题计算复杂性较高的问题,提出了一种基于符号OBDD的子图同构约束求解算法(OBDD-SI)。该算法对子图同构进行CSP建模,采用OBDD对该模型进行隐式表示和刻画。结合OBDD符号操作技术和回溯算法进行求解,执行弧一致性技术对不满足约束的值进行过滤,从而得到子图同构的所有解。实验结果表明,本算法具有良好的求解性能。

约束满足问题求解的符号OBDD桶消元算法

桶消元算法是求解约束满足问题的一种典型推理方法。针对桶消元算法面临的状态空间爆炸问题,将有序二叉决策图(OBDD)技术与该算法结合起来,给出了约束满足问题的一种求解算法。通过对约束满足问题中变量和域值的编码,将CSP问题转化为命题可满足性问题,给出了约束满足问题的OBDD表示方法;基于桶消元的算法思想,在约束满足问题的OBDD表示的基础上,利用OBDD的"与"操作和"量化"操作等,避免了传统算法中状态的显式枚举,隐式地实现了对CSP的求解。对大量随机生成的测试用例进行了实验分析,结果表明提出的符号算法明显优于桶消元法和符号直接求解法。

装配序列规划问题的CSP模型及其符号OBDD求解技术

完全、正确的可行装配序列的表示和生成是装配序列评价、优化和选择的前提,为此建立了单调非线性装配意义下的可行装配序列规划问题的约束满足问题(CSP)模型,并给出了基于有序二叉决策图(OBDD)的符号求解算法.首先以装配联接图和移动向量函数为装配体模型,给出了装配联接图模型的共享二叉决策图(SBDD)表示、移动向量函数的OBDD表示,以及装配序列规划问题的CSP描述;然后将生成所有可行装配序列的问题转化为对CSP求解所有可能解的问题,利用回溯算法对CSP问题进行符号OBDD求解,得到了满足几何可行性约束的所有可行装配序列.最后通过装配体实验验证了基于CSP模型和OBDD推理的装配序列生成技术的正确性和可行性.

柔性制造系统中生产调度问题求解的一种符号算法

讨论了基于有序二叉决策图的有界Petri网符号分析,给出了其中镜像计算的一种新算法,进而建立了柔性制造系统生产调度问题的符号有序二叉决策图求解算法。该算法在求解过程中通过对状态空间及其搜索过程中相关数据的有序二叉决策图表示,避免了状态和搜索的显示枚举,实现了隐式高效操作,进而改善了算法的计算性能。仿真实验表明了算法的有效性。

基于OBDD的拆卸几何可行性判别方法研究

在基于割集的拆卸序列生成算法中,对拆卸操作的几何可行性进行判别是频繁的操作。引进有序二叉决策图OBDD合理表示拆卸约束,设计了基于OBDD的几何可行性判别算法,比较了基于OBDD的判别算法与基于移动函数的判别算法的时间复杂度,结果表明基于OBDD的几何可行性判别算法比基于移动函数的判别算法具有更高的判别效率。