基于仿真和知识的广义动态约束网络技术

针对并行协同设计中的参数不确定性,将普通的约束网络扩展为广义动态约束网络,以对设计中的不确定性信息进行管理.建立了包含领域级约束和知识级约束的广义动态约束网络模型;提出了基于仿真分析和自适应响应面法的领域级约束建模的有效方法,并提出模糊-粗糙集算法,对仿真结果进行数据挖掘,实现了知识级约束获取;基于模板技术给出了广义动态约束网络中各种约束的统一表示方法;构造了有效的约束冲突求解策略和一致性求解算法,求出一致性设计区间.最后通过设计实例验证了文中方法的有效性.     

数值与符号的耦合约束求解模型

采用约束关系依赖图(CRDG)表达耦合约束之间的依赖关系,从而建立数值与符号耦合约束模型.提出耦合约束的求解算法:对CRDG进行最小独立子图分解,对存在耦合约束的子图用"孪生变量法"进行一阶解耦,对没有耦合约束的子图用传统方法进行独立求解,求解之后再对孪生变量进行等效性验算.该耦合约束模型及其求解算法拓展了传统约束理论,实现了教学求解和推理求解有机地结合.     

挖掘机协同设计中知识冲突管理系统的设计与实现

为解决复杂机械产品协同设计中的知识冲突问题,研究了产品设计时约束网络的建立方法和约束的分层管理,并采用区间传播算法求解约束满足问题,解决了协同设计中基于约束的冲突检测和冲突归档问题。在理论研究的基础上,开发了一种基于J2EE平台Struts+IBatis轻量级框架的协同设计中知识冲突管理系统,在一定程度上解决了协同设计中的知识冲突问题,并以挖掘机产品设计选择轴承为实例验证了知识冲突管理系统的正确性和可行性。     

分布式冲突检测系统的研究与实现

提出一种支持并行设计的分布式冲突检测方法,设计并开发分布式冲突检测系统。该系统以约束网络的一致性区间求解算法为核心,通过计算约束网络中各设计参数的可行域区间,可以有效地检测产品设计过程中的冲突。软件系统采用B/S结构,以支持地理分布的协同设计团队的设计工作,并以铁路列车某型转向架工程设计为例验证了该方法的有效性。     

自由特征模型约束求解研究*

在对自由特征模型参数化基础上,提出一种约束求解的新方法。该方法对自由特征形体定义点进行参数化,建立几何约束图,将约束问题分解为三角形约束和四面体约束两大类,分别进行求解,定义手向性规则,利用该规则将子问题组合为全局解。在自主开发的HUST-CAIDS（哈尔滨理工大学计算机辅助工业设计系统）中实现了本算法,并得到满足设计者需求的模型。     

密集标志点集的拓扑保持变换方法*

在对自由特征模型参数化基础上,提出一种约束求解的新方法。该方法对自由特征形体定义点进行参数化,建立几何约束图,将约束问题分解为三角形约束和四面体约束两大类,分别进行求解,定义手向性规则,利用该规则将子问题组合为全局解。在自主开发的HUST-CAIDS（哈尔滨理工大学计算机辅助工业设计系统）中实现了本算法,并得到满足设计者需求的模型。     

求解加热炉调度的改进修复式约束满足算法

针对钢铁生产中加热炉调度问题,考虑炉容受限的情况,以最小化板坯的Makespan和最小化总在炉加工时间为目标建立问题的多目标优化模型,将其归结为多旅行商问题。针对问题的NP-难特性,提出一种改进的修复式约束满足算法求解。松弛炉容约束得到初始调度,在检测冲突变量并构造冲突板坯的可替换加热炉集合的基础上,以开工时间偏移最小规则为冲突板坯重新指派加热炉,得到可行的调度方案。数据实验验证了模型和算法的可行性和有效性。     

卫星任务调度统一化建模与多策略协同求解方法

针对卫星任务调度“一星一系统”、测运控分离的现状,以卫星执行任务产生的星上独立事件和星地协同事件作为调度对象,以事件可执行时机作为调度资源,建立卫星任务调度统一化约束满足模型,将传统运控任务调度与测控任务调度纳入统一的建模方法.为保障模型的通用性和适应性,设计包含构造启发式、智能优化和针对性算法改进的多策略协同求解方法,搭建卫星任务调度算法与调度模型松耦合、模块化的系统架构.实验测试表明,所提出方法能够弥补传统模型在敏捷遥感卫星任务调度和高轨卫星测控调度场景下的局限性,在Benchmark问题和实际应用场景中均表现出良好的适用性和优化效果.     

带容量约束配送中心选址的改进粒子群算法

在Median-based模型的基础上,建立了带容量约束的配送中心选址模型,并给出求解算法。为避免算法早熟,提出一种异质多群体粒子群算法,将种群划分为主群和若干异质拓扑结构子群,平衡算法的开发与探索能力。设计了二进制与浮点数混合并行编码,将改进算法用于求解带容量约束的配送中心选址模型。仿真实验结果表明,此改进算法提高了最优解的求解精度与收敛速度。     

有限资源约束的产品开发多项目协同排程

针对有供应商参与的大批量制造企业产品协同开发特点,分析了多项目协同计划编制与设计资源在不同需求、不同时段、有无冲突等状态下的匹配情况,建立了多项目协同计划编制与资源颗粒约束匹配模型和实现算法,针对常见的计划与资源颗粒匹配时的无前置计划、有前置计划、计划与资源冲突等三种情况,提出了一种基于有限设计资源约束的新产品开发多项目协同计划编制方法,并用一实例对所建模型和计划编制方法进行了验证,证明提出的方法是可行的。     

基于动态约束网络的约束优化分解

约束网络通过对较大规模的任务和问题的分解，传递了并行工程产品开发过程中的各多功能小组之间必然存在的相互制约、相互依赖的关系。在任务和问题简单分解的过程中，由于所得到的子问题之间通常是不能完全独立的，因而只能在有限程度上降低难度、简化问题。在分析了约束求解的研究现状和不足的基础上，提出了一种基于动态约束的约束优化分解方法，使得各个子任务、子问题间的关系得到进一步的分解，从而在满足原要求的基础上，得到优化的结果。     

时间约束工作流的可调度性分析

提出一种时间约束工作流的可调度性分析方法。针对时间约束Petri网（Timing Constraint Petri Nets,TCPN）为普通Petri网无法建模多参与资源的不足,给出了扩展的时间约束Petri网（w-TCPN）的定义;结合w-TCPN的拓扑结构,从模型和实例两个层次,给出了w-TCPN变迁可调度的判定定理;提出了时间约束的调整策略。w-TCPN的研究使得时间约束工作流的建模和可调度性分析更加合理。     

The CCUBE Constraint Object-Oriented Database System

Constraints provide a flexible and uniform way to represent diverse data capturing spatio-temporal behavior, complex modeling requirements, partial and incomplete information etc, and have been used in a wide variety of application domains. Constraint databases have recently emerged to deeply integrate data captured by constraints in databases. This paper reports on the development of the first constraint object-oriented database system, CCUBE, and describes its specification, design and implementation. The CCUBE system is designed to be used for the implementation and optimization of high-level constraint object-oriented query languages as well as for directly building software systems requiring extensible use of constraint database features. The CCUBE data manipulation language, Constraint Comprehension Calculus, is an integration of a constraint calculus for extensible constraint domains within monoid comprehensions, which serve as an optimization-level language for object-oriented queries. The data model for the constraint calculus is based on constraint spatio-temporal (CST) objects that may hold spatial, temporal or constraint data, conceptually represented by constraints. New CST objects are constructed, manipulated and queried by means of the constraint calculus. The model for the monoid comprehensions, in turn, is based on the notion of monoids, which is a generalization of collection and aggregation types. The focal point of our work is achieving the right balance between the expressiveness, complexity and representation usefulness, without which the practical use of the system would not be possible. To that end, CCUBE constraint calculus guarantees polynomial time data complexity, and, furthermore, is tightly integrated with the monoid comprehensions to allow deeply interleaved global optimization.     

相接行凸约束网络的快速识别算法

约束网络为计算机科学中的许多问题提供了一种有效的表示方法.一般而言,约束满足问题是NP完全的.然而,许多实际问题通常对约束的结构或形式施加了特殊的限制,从而能够高效地加以解决.迄今,为了识别易处理约束类,人们对特殊的约束或约束网络方面进行了许多研究.相接行凸(connected row-convex,简称CRC)约束网络是Deville等人提出的一类易处理问题.为了给该类问题寻求有效的快速识别算法,在CRC约束网络相关工作基础上,提出了CRC约束矩阵的标准型.在分析CRC约束矩阵的标准型性质的基础上,利用行凸(row-convex,简称RC)约束网络的判定,结合PQ树(由P节点和Q节点构成的树)的性质和矩阵的索引表示法,给出了CRC约束网络的快速识别算法.该算法的时间复杂度为O(n³d²),其中,n为约束网络涉及的变量数,d为各变量的定义域中最大定义域的大小.该时间复杂度达到该类问题的最佳时间复杂度,从而为实际的CRC约束满足问题的求解提供了可行的方法.     

Constraint Databases: Promising Technology or Just Intellectual Exercise?

This paper describes the state of Constraint Databases (CDBs), a young discipline at the intersection of Database Management, Constraint Programming, Computational Geometry and Operations Research. As in Constraint Logic Programming, constraints in CDBs are a first class data type, and can play many modeling roles including spatial and temporal behavior, complex design requirements, and partial and incomplete information, for which existing databases have proven inadequate. We motivate the importance of CDBs, outline the work in the area that has been done, the current trends, and future directions and challenges. We briefly discuss (1) constraint modeling, canonical forms and algebras, (2) data models and query languages, (3) indexing and approximation-based filtering, (4) constraint algebra algorithms and global optimization, and (5) systems and case studies. We argue that CDBs are a promising technology that will impact many important application realms, and furthermore have the potential to be integrated into future database systems, and operations research and constraint programming tools.     

Reasoning with Numeric and Symbolic Time Information

Representing and reasoning about time is fundamental in many applications of Artificial Intelligence as well as of other disciplines in computer science, such as scheduling, planning, computational linguistics, database design and molecular biology. The development of a domain-independent temporal reasoning system is then practically important. An important issue when designing such systems is the efficient handling of qualitative and metric time information. We have developed a temporal model, TemPro, based on the Allen interval algebra, to express and manage such information in terms of qualitative and quantitative temporal constraints. TemPro translates an application involving temporal information into a Constraint Satisfaction Problem (CSP). Constraint satisfaction techniques are then used to manage the different time information by solving the CSP. In order for the system to deal with real time applications or those applications where it is impossible or impractical to solve these problems completely, we have studied different methods capable of trading search time for solution quality when solving the temporal CSP. These methods are exact and approximation algorithms based respectively on constraint satisfaction techniques and local search. Experimental tests were performed on randomly generated temporal constraint problems as well as on scheduling problems in order to compare and evaluate the performance of the different methods we propose. The results demonstrate the efficiency of the MCRW approximation method to deal with under constrained and middle constrained problems while Tabu Search and SDRW are the methods of choice for over constrained problems.     

Solution Techniques for Constraint Satisfaction Problems: Foundations

The Constraint Satisfaction Problem (CSP) is ubiquitous in artificialintelligence. It has a wide applicability, ranging from machine visionand temporal reasoning to planning and logic programming. This paperattempts a systematic and coherent review of the foundations ofthe techniques for constraint satisfaction. It discusses in detail thefundamental principles and approaches. This includes an initialdefinition of the constraint satisfaction problem, a graphical meansof problem representation, conventional tree search solutiontechniques, and pre-processing algorithms which are designed to makesubsequent tree search significantly easier.     

LEARNING TO SUPPORT CONSTRAINT PROGRAMMERS

This paper describes the Adaptive Constraint Engine (ACE), an ambitious ongoing research project to support constraint programmers, both human and machine. The program begins with substantial knowledge about constraint satisfaction. The program harnesses a cognitively-oriented architecture (FORR) to manage search heuristics and to learn new ones. ACE can transfer what it learns on simple problems to solve more difficult ones, and can readily export its knowledge to ordinary constraint solvers. It currently serves both as a learner and as a test bed for the constraint community.     

基于约束的协同设计冲突检测模型

针对协同设计冲突无法准确全面检测的问题,提出了一种基于约束的冲突检测模型。在分析了协同设计中约束分层和约束满足问题的基础上,该检测模型将约束划分为已知约束关系集合和未知约束关系集合两部分,分别对其进行冲突检测。采用区间传播算法验证已知约束关系集合;提出用免疫算法优化反向传播(BP)神经网络来模拟未知约束关系集合进行冲突检测,并与遗传算法优化BP神经网络进行对比,收敛速度提高了62.96%,证明了算法具有较快的收敛速度和较强的全局收敛能力。为实现计算机支持的冲突检测,研究了基于可扩展标记语言(XML)文档的约束关系集合表达方法,设计了基于约束满足的冲突检测系统的架构体系,并以C#和Matlab为平台开发了行星齿轮箱协同设计冲突检测系统。最后,通过实例验证了冲突检测模型的可行性和有效性。     

Constraint-Based Design of Embedded Intelligent Systems

Substantial progress has been achieved using the standard Constraint Satisfaction Problem framework. However, there is a major unsolved challenge confronting the constraint research community: the constraint-based design of embedded intelligent systems. This requires a new online model of constraint satisfaction and new computational tools for specifying, modeling, verifying and implementing constraint-based, hybrid, intelligent systems, such as robots. The Constraint Net model of Zhang and Mackworth allows the design of hybrid intelligent systems as situated robots: modeling the robot and the environment symmetrically as dynamic systems. If the robot's perceptual and control systems are designed as constraint-satisfying devices then the total robotic system, consisting of the robot symmetrically coupled to the environment, can be proven correct. Some theoretical and practical advances based on this model are described, including experiments with the constraint-based design of robot soccer players.