三维装配几何约束组合的分类求解策略

针对两个刚体之间的三维几何约束求解问题,依据几何约束的参数结构 分析了角度约束和距离约束的解耦性,给出了角度约束和距离约束可解耦求解的条件;然后 对两个刚体之间的几何约束进行组合分析,总结出约束度不小于2 的几何约束构成的组合只 有几十种,且均可采用几何推理方法进行求解;最后阐述了附加方向约束、冗余约束和矛盾 约束对数值求解的不利影响,提出了三维几何约束组合的分类求解策略,并用实例验证了该 求解策略的有效性。     

二维几何约束求解器

开发了一个二维几何约束求解器.该求解器是新一代智能CAD系统的核心,它采用了基于图和规则的几何推理方法,高效、稳定、实用.论文提出了几何约束模型及其约束图表示,深入介绍了基于点刚体归约的几何推理算法,描述了求解器的体系结构.     

三维装配几何约束问题求解研究

讨论了普遍情况下三维几何约束求解的问题.首先,对基本几何元素求解问题进行了研究,在此基础上对两装配体进行装配的几何约束问题进行了研究,提出对三维几何约束复杂耦合问题进行求解的方法,该研究拓展了三维几何约束求解器的通用性.     

基于有向图的二维约束求解算法研究

针对过约束、几何完全定义状态判定和约束求解效率等问题,提出了基于约束图,利用自由度理论和约束冲突机制,通过反向约束方向平衡约束,进而通过排序进行约束求解的算法。算法采用约束图记录约束和几何的关系;通过约束平衡的方法进行过约束和几何完全定义的判定;采用排序求解方法,将庞大计算问题转化为一组相对简单的计算问题。算法已得到初步应用,对过约束和几何完全定义状态的判定有明显的效果,而且提高了约束求解效率。     

基于自由度分析的耦合几何约束求解

针对目前的CAD软件不能求解复杂耦合几何约束的问题,提出一种基于自由度分析的耦合几何约束求解方法.通过添加部分约束,将这些约束的值作为迭代变量,再对复杂约束耦合问题进行约束聚合;将没有被用到的约束作为迭代的目标函数进行计算,大大减少了传统方法中解决复杂约束耦合问题所需要的变量数,提高了计算过程的稳定性.在最坏情况下,对不同数量的聚合体构成的复杂约束耦合模式所需要添加的变量数进行了讨论,从原理上成功地解决了复杂耦合几何约束问题.该方法可以用复杂聚合模式作为几何设计的基本元素,较好地解决了二维几何约束求解问题.     

三维装配几何约束闭环系统的递归分解方法

由于现有几何约束分解方法无法分解三维装配几何约束闭环系统,故常采用数值迭代方法对其进行求解,但存在效率低、稳定性差等问题.为此,通过分析几何约束闭环图的拓扑结构和串联运动链的结构约束,提出基于串联运动链结构约束等价替换的三维几何约束闭环系统的递归分解方法.该方法通过不断地引入几何约束组合等价替换串联运动链的结构约束,从几何约束闭环系统中分离出可独立求解的子系统,实现几何约束闭环系统的递归分解.该方法可将此前许多必须整体迭代求解的三维几何约束闭环系统分解为一系列可解析求解的2个刚体之间的几何约束系统,明显提高了约束求解的效率和稳定性.最后用实例验证了方法的正确性和有效性.     

通用几何约束系统统一建模研究

在几何约束和几何实体的基本约束和欧拉参数表达的基础上,研究了通用几何约束系统的统一建模问题。通过对三维几何实体姿态约束和位置约束解耦性的分析,抽象出球实体、盒体和球盒体三种基本几何实体表达空间几何实体,并以基本约束的组合表达几何约束,形成几何约束模型特有的层次结构;并以有向图管理几何约束系统,可以清晰地反映姿态约束和位置约束的解耦性,实现约束系统的细粒度分解,得到规模更小的求解序列,实现高效求解。方法实现于原型系统WhutVAS中。     

一种利用有向图优化约束求解的方法

为克服约束求解的效率问题及可靠性问题，本文提出了一种基于图结构的约束求解方法，它利用图瓣形式来表示几何元素之间的约束关系，使得几何元素的求解从整体下降 至局部，将一个方程组的求解问题论为几个小方程组的求解，大大降低了计算复杂度，进而提高了求解的可靠性。     

面向欠约束几何系统的一种同伦求解方法

针对几何约束系统的数值求解过程中，经常发生的数值不稳定性问题，构造了一种面向欠约束系统的同伦方法，并将其与现有的求解与分解方法有机地结合起来，提出了一种牛顿－同伦混合方法，在牛顿迭代失败的位置自动调用欠约束同伦法，既提高了几何约束求解器的效率，同时又保证了求解的效率。     

二维几何约束多解问题的研究

对采用自由度分析方法求解几何约束问题进行了研究.对几何约束问题的图用自由度分析的方法进行分解可以使约束系统得到充分分解,并可以对高耦合的几何约束问题进行分离.通过转换把几何元素的求解问题,转换为点的定位问题,从而使几何约束的多解问题得到简化,几何约束的多解问题被归结为初始设计图形中点和直线间的相对关系.对未知半径和圆心的圆的求解问题进行了讨论,提供了几种比较通用的算法,可以简化程序的设计.     

h-graphs: A new representation for tree decompositions of graphs

In geometric constraint solving, 2D well constrained geometric problems can be abstracted as Laman graphs. If the graph is tree decomposable, the constraint-based geometric problem can be solved by a Decomposition–Recombination planner based solver. In general decomposition and recombination steps can be completed only when steps on which they are dependent have already been completed. This fact naturally defines a hierarchy in the decomposition–recombination steps that traditional tree decomposition representations do not capture explicitly.In this work we introduce h-graphs, a new representation for decompositions of tree decomposable Laman graphs, which captures dependence relations between different tree decomposition steps. We show how h-graphs help in efficiently computing parameter ranges for which solution instances to well constrained, tree decomposable geometric constraint problems with one degree of freedom can actually be constructed.     

Minimal Model Semantics for Sorted Constraint Representation

Sorted constraint representation is a very useful representation in AI which combines class hierarchies and constraint networks.For such sorted constraint representation,a problem is how to generalize the idea of default inheritance to constraint network,where the attributes in a class or between different classes interact with each other via the network.To give a formal account for the defeasible reasoning in such representation,a general sorted constraint logic is proposed,and a minimal-model semantics for the logic is presented.     

Geometric constraints within feature hierarchies

We study the problem of enabling general 2D and 3D variational constraint representation to be used in conjunction with a feature hierarchy representation, where some of the features may use procedural or other non-constraint based representations. We trace the challenge to a requirement on constraint decomposition algorithms or decomposition-recombination (DR) planners used by most variational constraint solvers, formalize the feature hierarchy incorporation problem for DR-planners, clarify its relationship to other problems, and provide an efficient algorithmic solution. The new algorithms have been implemented in the general, 2D and 3D opensource geometric constraint solver FRONTIER developed at the University of Florida.     

基于图结构描述的几何约束模型的研究与建立

本文提出了一种基于图结构描述的二维图形几何约束模型的建立及存储方法。该方法利用图论的概念和原理,提出用无向图的结构描述一个几何约束系统,用约束图表示图形的约束信息,规则图则用来表达几何推理的过程,同时利用面向对象的技术建立一种扩展的图的领接表的数据结构来存储约束模型。这种方法对约束的分类及表达清晰、直观,能够处理各种约束信息,效率及可靠性较高。     

基于时间Petri网的综合航电系统时序验证分析

综合航电系统是一种对可靠性、实时性要求非常高的嵌入式应用系统。为了解决针对复杂应用场景下综合航电系统的处理时间和工作时序预估较困难、且计算自动化程度不高等测试验证问题,提出了一种基于时间约束Petri网的综合航电系统时序验证和分析方法。给出了时间约束Petri网的形式化定义,分析了综合航电系统工作流程中各节点的时间属性,通过引入时序约束路径的概念,并提出了时序推理算法。通过在仿真算例中进行计算并对比实际运行数据,结果表明该方法在针对综合航电系统运行时序的验证分析方面具有有效性。     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

Visual analogy: Viewing analogical retrieval and mapping as constraint satisfaction problems

The core issue of analogical reasoning is the transfer of relational knowledge from a source case to a target problem. Visual analogical reasoning pertains to problems containing only visual knowledge. Holyoak and Thagard proposed that the retrieval and mapping tasks of analogy in general can be productively viewed as constraint satisfaction problems, and provided connectionist implementations of their proposal. In this paper, we reexamine the retrieval and mapping tasks of analogy in the context of diagrammatic cases, representing the spatial structure of source and target diagrams as semantic networks in which the nodes represent spatial elements and the links represent spatial relations. We use a method of constraint satisfaction with backtracking for the retrieval and mapping tasks, with subgraph isomorphism over a particular domain language as the similarity measure. Results in the domain of 2D line drawings suggest that at least for this domain the above method is quite promising.     

几何约束有向图的规划分解研究

在基于有向图表达的几何约束系统中,几何约束的匹配方向、分布状态以及有向图中强连通分量的规模直接影响到整个约束系统的求解;如何对几何约束系统进行合理规划,得到正确有效的求解序列,是目前约束分解研究的重要内容。该文提出了一个规划分解算法,它针对欠约束几何系统的特点,能够优化约束的初始匹配方向,对于约束匹配过程中生成的强连通子图,通过调整约束匹配方向,自适应地改善约束分布,从而减小强连通子图的规模,以求得到几何约束系统正确而高效的求解序列。同时,基于规划分解算法,完成了约束的奇异性分析,提供了面向分解的奇异性分析算法。