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

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

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

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

装配几何可行性判别的符号OBDD技术研究

采用了有序二叉决策图(OBDD)描述装配几何可行性,给出了装配操作及其几何可行性的符号表示,设计了装配操作几何可行性的符号OBDD判别算法,给出了装配几何可行性的研究实例,开发了装配的原型系统以支持装配规划,原型系统运行结果表明符号OBDD技术用于装配几何可行性判别的有效性。     

基于深度强化学习的双向装配序列规划

为了解决复杂装配模型的序列规划问题,并使算法对任意初始状态具有较高的适应性,本文提出了一种包含正向装配以及逆向拆解的一体化双向装配序列规划方法BASPW–DQN.针对复杂装配模型,首先进行了一体化装配序列规划的问题描述与形式化表示;在此基础上,引入了课程学习及迁移学习方法,对包含前向装配和逆向错误零件拆卸两部分过程的双...     

基于几何推理的装配序列自动规划研究

文章以问题规约的求解策略,以分解法规划产生的装配序列,提出与或图表达装配体拆卸序列解空间。通过求解拆卸序列与或图的解空间得到装配体的拆卸序列,将拆卸序列反向得到装配序列。为降低装配体拓扑联接图的复杂度,对作业组件做出识别。另外提出了判断零件拆卸性的三个条件,大部分零件无需进行干涉检验,而白逻辑推理即可判断是否满足拆卸条件,避免了多次试凑,具有更高的求解效率,可更广泛地用于装配序列求解。     

基于语义的虚拟装配仿真模型研究及应用

针对虚拟装配中装配模型的信息完备性与虚拟仿真系统的交互效率之间的矛盾,提出一种轻量化的基于树-图分离结构的虚拟装配模型,该模型包括装配树模型和语义关系图模型。装配树模型以二叉树的形式表达虚拟产品的层次结构以及零部件间的装配顺序,语义关系图以二分图的形式表达零件之间的装配关系。将该模型应用于水轮机组虚拟装配仿真系统中,不仅满足了虚拟仿真过程对装配模型信息表达的要求,而且减少了系统存储负担,提高了交互效率。     

用户关注度相关的装配模型动态可视化

为了方便地展示复杂模型各零件之间的三维结构,并清楚地揭示出它们之间的层次装配约束关系,提出一个面向用户交互的装配模型浏览系统.通过构造层次有向拆卸图来保存各零件的拆卸顺序,并采用递归法创建其干涉矩阵和拆卸有向图;装配约束图中的各顶点均用相应零件的图像来表示,以便于用户直观地选择所关注零件.由于采用了focus+context的方式来生成装配约束图,用户所关注零件的局部邻域被自动调整到视图的中心,并且放大显示.另外还提出了一种基于用户关注度的零件颜色自动选取算法,通过鲜明的颜色对比进一步突出用户所关注的装配关系.实验结果证明,该系统有效地提高了用户交互以及装配效率.     

基于几何推理的装配序列自动规划研究

以问题规约的求解策略和分解法规划产生的装配序列,提出与或图表达装配体拆卸序列解空间,通过求解拆卸序列与或图的解空间,得到装配体的拆卸序列;将拆卸序列反向得到装配序列,为降低装配体拓扑联接图的复杂度,以作业组件做出识别,文中提出判断零件可拆卸性的三个条件,使大部分零件无需进行干涉检验,而由逻辑推理即可判断是否满足拆卸条件,避免了多次试凑,有更高求解效率,可更广泛地用于装配序列求解上。     

基于图论和蚁群算法的虚拟装配序列规划研究

为了解决复杂装配体装配序列生成与优化问题,首先建立装配体的有向关联图,生成对应的关联矩阵.在运用蚁群算法求解满足最小装配代价的装配序列解的过程中,通过改进信息素更新策略,更新局部和全局信息素,指导蚁群快速寻找全局最优解;同时引入信息素挥发系数自适应调节机制,避免了求解过程陷入局部最优.最后通过实例验证了算法的有效性.     

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

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

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.     

The symbolic OBDD scheme for generating mechanical assembly sequences

Assembly sequence planning is one of typical combinatorial optimization problems, where the size of parts involved is a significant and often prohibitive difficulty. The compact storage and efficient evaluation of 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, assembly knowledge models of liaison graph and translation function are formulated by OBDDs, and OBDD-based representation of assembly sequences is proposed. A novel OBDD-based procedure was presented to generate all geometrically feasible assembly sequences from the OBDDs of liaison graph and translation relation. This procedure can be used conveniently on the computer and all the feasible sequences can be derived. The great advantage of OBDD-based scheme is that the storage space of OBDD-based representation of feasible assembly sequences does not increase with the part count of assembly dramatically so quickly as that of AND/OR graph does. We developed the prototype tool for generating assembly sequence using Visual C++ and CUDD package, and undertake some experimental tests. It was shown that the OBDD scheme generated feasible assembly sequences correctly and completely.     

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

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

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

与或图搜索是人工智能领域一项一定范围内通用的问题求解技术。基于传统数据结构的与或图表示技术极大地限制了与或图搜索算法可求解问题的规模。本文在Mahanti等提出的含圈与或图理论框架基础上,给出了基于OBDD的含圈与或图符号表示方法,并提出了一种求解含圈与或图最小代价解图的符号搜索算法。实验结果表明：该算法在处理大规模含圈与或图时具有明显优势。     

Lower bounds on the OBDD size of two fundamental functions' graphs

Ordered Binary Decision Diagrams (OBDDs) are a data structure for Boolean functions which supports many useful operations. Among others it finds applications in CAD, model checking, and symbolic graph algorithms. Nevertheless, many simple functions are known to have exponential OBDD size with respect to their number of variables. In order to investigate the limits of symbolic graph algorithms which work on OBDD-represented graph instances, it is useful to have simply-structured graphs whose OBDD representation has exponential size. Therefore, we consider two fundamental functions with exponential lower bounds on their OBDD size and transfer these results to their corresponding graphs. Concretely, we consider the Indirect Storage Access function and the Hidden Weighted Bit function.     

利用OBDD编码的快速二值图算法(英文)

对利用有序二元判定图 OBDD 编码二值图像进行了研究,该方法可以节约大量的空间,并在此基础上,提出了各种二值图的算法,包括解码和集合运算(并、交、差、对称差、包含和互补)。实验结果表明这种基于OBDD 编码的方法比现有的二值图编码方法效率更高。     

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

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

Design of a real-time AND/OR assembly scheduler on an optimization neural network

The problem of finding an AND/OR precedence-constraint assembly schedule using optimization neural computation is presented. The precedence relationships of assembly operation result from the geometric constraints of subtasks. Because of the existence of geometric constraints among assembly subtasks, the assembly operation involves AND/OR precedence relationships; that is, the order of assembly crucially determines whether the desired task can be achieved. A feasible assembly schedule is a schedule that satisfies these AND/OR precedence constraints.It has been shown that all the feasible assembly schedules can be generated by transforming geometric constraints of subtasks to the pattern-matching operation. Using the question-answer pattern and pattern-matching operation, the assembly scheduling problem can be transformed into an AND/OR precedence-constrained traveling salesman problem (TSP). Two precedence-constrained TSPs, cost-constrained TSP (CCTSP) and state-constrained TSP (SCTSP), are discussed. The CCTSP artificially sets the cost of the prohibited moves to a very large value which ensures that the constraints are satisfied, while the SCTSP restricts the movement of next assembly subtasks. The advantage of the SCTSP over CCTSP in the generation of the assembly schedule will be illustrated.A novel method proposed here is to obtain the best AND/OR precedence-constraint assembly schedule using neural network computation. The geometric constraints of an assembled object are transformed into the elements of the connection matrix which specifies the connection strength among neurons. A modified Hopfield network is used to tackle the AND/OR precedence-constraints assembly scheduling problem. Multirobot assembly sequences generation is also discussed. The designed algorithm can accommodate various constraints and applications. Detailed algorithms, examples and experiments are presented.     

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

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