基于符号零压缩二叉决策图的装配可行性判定方法

为了扩大装配序列规划的求解规模并提高求解效率,提升装配自动化水平,给出了装配体联接矩阵和干涉矩阵的零压缩二叉决策图描述,建立了基于符号零压缩二叉决策图的装配操作可行性判定方法。基于该方法,可以高效地求解出一个装配体的可行装配操作。结合实例验证了基于符号零压缩二叉决策图的装配体模型和可行装配操作判定方法的正确性和可行性。     

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

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

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

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

二叉决策图在逻辑综合中的应用

二叉决策图(BDDs)是布尔函数的一个表示方法,最近它被广泛应用于逻辑综合、布尔电路的模拟和测试等领域.在这些应用中,有些基本问题需要解决,其中包括电路图到决策图的转换.本文提出一个转换的方法.文中分两步叙述,首先是对无扇出电路的转换,然后是对有扇出电路的转换,最后把两者结合为一个通用算法.     

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

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

基于符号零压缩二叉决策图的组合测试用例生成方法

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2～4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。     

基于图的子装配识别与装配序列规划

本文基于图建立了装配模型,并提出了一种基于配合关联图的子装配识别和装配序列 规划方法．直接从配合关联图出发识别出围绕箱体、轴和螺纹联接等典型零件所形成的子装 配;对配合关联图进行了简化,完成了基于配合关联图的装配序列规划．     

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

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

基于二叉决策图的网络可达性计算

针对现有攻击图生成方法中普遍通过网络扫描获得网络可达性信息存在信息不完整、耗时长、产生网络干扰等不足,提出一种基于二叉决策图的网络可达性计算方法。该方法利用二叉决策图建模防火墙规则,通过高效的集合运算计算网络可达性。真实环境检测和模拟实验均表明该方法具有精确、耗时短、无网络干扰等优点,适用于大规模网络可达性的计算,推动了攻击图在大规模网络中的应用。     

二叉决策图在逻辑综合中的应用

二叉决策图（BDDs）是布尔函数的一个表示方法，最近它被广泛于逻辑综合、布尔电路的模拟和测试等领域。在这些应用中，有些基本问题需要解决，其中包括电路图到决策图的转换。本文提出一个转换的方法。文中分两步叙述，首先是对无扇出电路的转换，然后是对有扇出电路的转换，最后把两者结合为一个通用算法。     

Symbolic OBDD representations for mechanical assembly sequences

Assembly sequence planning is one typical combinatorial optimization problem, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of all the feasible assembly sequences is one crucial concern. Ordered binary decision diagram (OBDD) is a canonical form to represent and manipulate the Boolean functions efficiently, and appears to give improved results for large-scale combinatorial optimization problems. In this paper, subassemblies, assembly states and assembly tasks are represented as Boolean characteristic functions, and the symbolic OBDD representation of assembly sequences is proposed. In this framework, the procedures to transform directed graph and AND/OR graph into OBDDs are presented. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of all the feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of both directed graph and AND/OR graph do. We undertake many experimental tests using Visual C++ and CUDD package. It was shown that the OBDD scheme represented all the feasible assembly sequences correctly and completely, and outperforms either directed graph or AND/OR graph in storage efficiency.     

基于图论和启发式搜索的装配序列规划算法

将装配序列规划中成熟的割集法和人工智能中启发式搜索方法相结合，提出一个高效的装配序列生成算法。此算法在启发函数的指导下，直接产生所需的最佳装配规划，避免了单独采用割集法产生装配AND／OR图而导致的组合爆炸的问题。同时省去了在选择装配规划时，对整个装配AND／OR图进行再次搜索。此算法与其它算法相比具有效率高、智能性强的特点。最后给出了一个实例。     

基于符号EVBDD的安全多方计算

决策函数的有效表示是安全多方计算研究中的热点问题。符号描述技术是表示决策函数的一种新方法。针对基于代数决策图(ADD)的决策函数表示中出现的叶子节点规模膨胀以及导致协议面临的状态空间爆炸问题,引入边值二叉决策图(EVBDD)技术,给出了一种基于EVBDD的决策函数表示方法。该方法首先利用EVBDD结构,将决策函数描述为EVBDD的符号化形式,避免了传统ADD表示中出现的叶子节点规模膨胀现象。然后通过添加虚节点,解决了计算路径上出现的隐私泄露问题。在此基础上,提出了EVBDD的加解密算法,并设计了一种新的基于EVBDD的安全两方计算协议。最后,对协议的正确性、安全性和效率进行了分析。结果表明,与基于代数决策图的解决方案相比,新协议在效率上有明显的提高。     

基于规则和爆炸图的装配序列规划

提出局部爆炸图的概念,运用几何干涉规则生成各直角坐标方向的局部爆炸图;在确立各方向的合并顺序后,用合并规则生成各零件的合并约束前元集;并据此进行局部爆炸图合并求解装配序列,实现了规则推理和几何推理算法的紧密结合,有效地避免了装配序列组合爆炸,降低了装配规划的计算复杂度,保证规划所得装配序列的可行性和实用性．     

装配序列规划研究综述

装配序列规划是机器人智能装配中的一项重要研究课题，也是ＣＡＤ／ＣＡＭ以及ＣＩＭＳ研究的一个重要组成部分，涉及计算机，人工智能，自动化，机器人和机械工程等领域，本文对机械装配序列规划研究的历史和技术现状进行了综述。     

Petri网的符号ZBDD可达树分析技术

Petri网是一种适合于并发系统建模、分析和控制的图形工具.可达树是Petri网分析的典型技术之一,它通过标识向量集合表征系统的状态空间,组合复杂性严重制约了该分析技术可处理系统问题的规模.零压缩决策图(Zero-Suppressed Binary Decision Diagrams,ZBDD)是一种新型的数据结构,是表示和处理稀疏向量集合的一种有效技术.文章基于Petri网町达标识向量的稀疏特征,给出了Petri网分析的符号ZBDD技术,该技术通过对标识向量(状态)的布尔向量表示、可达标识向最(状态)的符号ZBDD生成,实现Petri网可达状态空间的高效符号操作和紧凑符号表示.实验表明,基于ZBDD的符号可达性分析算法能够有效处理较大规模Petri网问题.     

二叉判定图最优化算法研究综述

对近年来二叉判定图(BDD)最优化算法的成果和发展趋势进行了综述和讨论，重点介绍精确排序算法和动态启发式排序算法．给出了BDD优化算法的改进建议：用不完全枚举法的优势和随机过程动态规划策略改进BDD优化算法．     

Language-Emptiness Checking of Alternating Tree Automata Using Symbolic Reachability Analysis

Alternating tree automata and AND/OR graphs provide elegant formalisms that enable branching- time logics to be verified in linear time. The seminal work of Kupferman et al. [Orna Kupferman, Moshe Y. Vardi, and Pierre Wolper. An automata-theoretic approach to branching-time model checking. J. ACM, 47(2):312–360, 2000] showed that 1) branching-time model checking is reducible to the language non-emptiness checking of the product of two alternating automata representing the model and property under verification, and 2) the non-emptiness problem can be solved by performing a search on an AND/OR graph representing this product. Their algorithm, however, can only be implemented in an explicit-state model checker because it needs stacks to detect accept and reject runs. In this paper, we propose a BDD-based approach to check the language non-emptiness of the product automaton. We use a technique called “state recording” from Schuppan and Biere [Viktor Schuppan and Armin Biere. Efficient reduction of finite state model checking to reachability analysis. Int. Journal on Software Tools for Technology Transfer (STTT), 5(2–3):185–204, 2004] to emulate the stack mechanism from explicit-state model checking. This technique allows us to transform the product automaton into a well-defined AND/OR graph. We develop a BDD-based reachability algorithm to efficiently determine whether a solution graph for the AND/OR graph exists and thereby solve the model-checking problem. While “state recording” increases the size of the state space, the advantage of our approach lies in the memory saving BDDs can offer and the potential it opens up for optimisation of the reachability analysis. We remark that this technique always detects the shortest counter-example.     

二元决策图和故障树相融合的无线传感器网络可靠性分析

为了提高无线传感器分析网络可靠性,提出一种基于二元决策图和故障树相融合的无线传感器网络可靠分析方法;首先根据无线传感器网络拓扑结构建立了故障树模型,然后将无线传感器网络故障树转化为二元决策图结构,最后采用仿真实验分析了不同节点冗余度、不同跳数条件下无线传感器网络的可靠性;仿真结果表明,文章方法的分析结果可以帮助无线传感器网络性能的优化,可以提高无线传感器网络的可靠性.