A Rigorous Global Filtering Algorithm for Quadratic Constraints*

This article introduces a new filtering algorithm for handling systems of quadratic equations and inequations. Such constraints are widely used to model distance relations in numerous application areas ranging from robotics to chemistry. Classical filtering algorithms are based upon local consistencies and thus, are often unable to achieve a significant pruning of the domains of the variables occurring in quadratic constraint systems. The drawback of these approaches comes from the fact that the constraints are handled independently. We introduce here a global filtering algorithm that works on a tight linear relaxation of the quadratic constraints. The Simplex algorithm is then used to narrow the domains. Since most implementations of the Simplex work with floating point numbers and thus, are unsafe, we provide a procedure to generate safe linearizations. We also exploit a procedure provided by Neumaier and Shcherbina to get a safe objective value when calling the Simplex algorithm. With these two procedures, we prevent the Simplex algorithm from removing any solution while filtering linear constraint systems. Experimental results on classical benchmarks show that this new algorithm yields a much more effective pruning of the domains than local consistency filtering algorithms.*This article is an extended version of [23].     

带有多个可转化约束的频繁项集挖掘算法

1.引言频繁项集的挖掘是数据挖掘课题中的一个很重要的方面,然而频繁项集的挖掘过程通常会产生数目庞大的频繁项集,并且其中的绝大多数并不是客户所期望得到的,因而使挖掘过程的效果和效率都大打折扣。     

基于混沌遗传算法的网格工作流调度应用

动态网格环境中, 多QoS(服务质量)约束下的工作流调度问题是决定其任务执行成功与否及效率高低的关键。现有的网格工作流调度算法难以满足实际应用中的不同需求, 同时算法欠优化, 难以提供多种策略, 由此提出了一种基于期限与预算两个QoS约束的改进型混沌遗传算法。首先, 为避免算法出现收敛停滞将混沌机制引入遗传算法并对变异概率进行自适应处理。其次, 提出时间和预算的线性结合概念, 将目标函数转换为适应值函数。最终基于工作流调度中的平衡结构和非平衡结构测试了算法的有效性。     

一种新的几何约束系统参数取值范围的计算方法

在利用参数化CAD系统进行图形设计的过程中,通过修改图形对象的可变参数重新生成图形是最常见的一种操作。但用户在改变参数的过程中,由于事先并不知道有效的参数值,也没有任何引导信息,导致了用户只能盲目地不断输入参数值,通过反复输入参数值来满足约束关系的需要。该文将结构约束引入参数有效取值范围求解的范畴,并提出了确定一类常用的二维参数化CAD模型中参数的有效范围的计算方法和算法。算法复杂度为O(n2) 。     

一种链路分离路径算法的优化

DIMCRA算法能很好地解决多个加性约束下的链路分离路径问题的算法。论文对DIMCRA算法进行了理论分析,并证明了存在一类链路分离路径问题是该算法不能解决的。随后在算法中引入了组合差分的概念,对算法进行了优化,并通过实例仿真说明了改进后的算法能弥补原算法的不足。     

Navigation with constraints for an autonomous mobile robot

This paper describes a navigation planning algorithm for a robot capable of autonomous navigation in a structured, partially known and dynamic environment. This algorithm is applied to a discrete workspace composed of a network of places and roads. The environment specification associates temporal constraints with any element of the network, and recharge or relocalisation possibilities with places. A mission specification associates several constraints with each navigation task (energy, time, position uncertainty and distance).

The algorithm computes an optimal path for each navigation task according to the optimization criterion and constraints. We introduce the notion of efficient path applied to a new best first search algorithm solving a multiple constraints problem. The path determination relies on a state representation adapted to deal with environment constraints. We then prove that the complexity chracteristics of our algorithm are similar to those of the A* algorithm.

The planner described in this paper has been implemented on a Spare station for a Robuter mobile platform equipped with ultra-sonic range sensors and an active stereo vision system. It was developed for the MITHRA family of autonomous surveillance robots as part of project EUREKA EU 110.     

Model-free constrained data-driven iterative reference input tuning algorithm with experimental validation

This paper presents the design and experimental validation of a new model-free data-driven iterative reference input tuning (IRIT) algorithm that solves a reference trajectory tracking problem as an optimization problem with control signal saturation constraints and control signal rate constraints. The IRIT algorithm design employs an experiment-based stochastic search algorithm to use the advantages of iterative learning control. The experimental results validate the IRIT algorithm applied to a non-linear aerodynamic position control system. The results prove that the IRIT algorithm offers the significant control system performance improvement by few iterations and experiments conducted on the real-world process and model-free parameter tuning.     

基于角色的权限访问控制在CMS中的研究与应用

针对CMS（内容管理系统）的特点,在基于角色的权限访问控制的基础上,分析CMS中的访问主体与客体,涉及到的访问权限以及约束属性,提出一个带有附加主体、客体约束属性和约束机制的权限访问控制算法。该算法通过适用用户范围、信息状态、用户信用、用户级别四个方面对访问进行约束,使拥有同一角色的不同用户对信息资源的访问表现出各自不同的访问控制特征,从而,减少角色的数量,提高CMS中权限分配和访问控制的灵活性与安全性。     

一种多约束的密度聚类算法的研究

针对传统的密度聚类算法不能处理带有多约束条件的问题,在现有的密度聚类算法的基础上,提出了一个带有多约束条件限制的密度聚类算法。该算法将多约束条件引入到密度聚类分析中,并分析了多约束条件对聚类结果的影响。实验表明该算法在多约束条件下,可有效完成对数据点的聚类并且效果较好,为现实情况中处理多约束聚类提供了良好的理论支持。     

Signal and image approximation with level-set constraints

Summary We present a novel variational approach to signal and image approximation using filter statistics (histograms) as constraints. Given a set of linear filters, we study the problem to determine the closest point to given data while constraining the level-sets of the filter outputs. This criterion and the constraints are formulated as a bilevel optimization problem. We develop an algorithm by representing the lower-level problem through complementarity constraints and by applying an interior-penalty relaxation method. Based on a decomposition of the penalty term into the difference of two convex functions, the resulting algorithm approximates the data by solving a sequence of convex programs. Our approach allows to model and to study the generation of image structure through the interaction of two convex processes for spatial approximation and for preserving filter statistics, respectively.      

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

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

Constrained motion planning for robot manipulators using local geometric information

This paper proposes a new motion planning algorithm for robot manipulator systems with path constraints. The constraint function of a manipulator determines the subspace of its joint space, and a proposed sampling-based algorithm can find a path that connects valid samples in the subspace. These valid samples can be obtained by projecting the samples onto the subspace defined by the constraint function. However, these iteratively generated samples easily fall into local optima, which degrades the search performance. The proposed algorithm uses the local geometric information and expands the search tree adaptively to avoid the local convergence problem. It increases the greediness of the search tree when it expands toward an unexplored area, which produces the benefit of reducing computational time. In order to demonstrate the performance of the algorithm, it is applied to two example problems: a maze problem using PUMA 560 under predefined constraints and a closed-chain problem using two Selective Compliance Assembly Robot Arms. The results are compared with those obtained with an existing algorithm to show the improvement in performance.     

装配配合约束自动获取技术研究

装配配合约束获取对于装配设计、装配工艺规划等多个领域的研究具有重要意义;现有的装配配合约束获取方法容易产生约束的遗漏和约束无效性;通过对自动获取配合约束技术进行研究,在充分利用CAD模型几何拓扑信息的基础上。提出了几何约束识别和配合验证相结合的装配配合约束自动获取箅法;实践证明,该方法可以显著地提高约束信息的获取效率、正确性和有效性。     

基于线性约束条件下全局优化问题的定边界模拟退火算法

针对线性约束条件下全局优化问题,提出了定边界模拟退火算法(DBSA,参数确定范围[0,1])。应用凸集理论,将线性约束条件转化为和为1的等式约束,可证明二若等价。针对新的约束条件,对模拟退火算法可能解的选取方法进行相应改进。其次从应用上验证了DBSA的可行性,对比结果表明定边界模拟退火算法具有较快的运算速度和精度。     

Finding the Right Hybrid Algorithm – A Combinatorial Meta-Problem

Benchmark comparisons tend to overlook the most important challenge in solving combinatorial problems: how to design an appropriate algorithm. For example, an early version of Localizer incurred a factor 3 performance penalty when benchmarked against a C implementation of GSAT, but we would recommend implementing a new local search algorithm in Localizer rather than C every time. The ECLiPSe CLP language supports the experimental process of seeking the right hybrid algorithm for the problem at hand. It offers high-level modelling and control features, extensibility and a wide range of constraint solvers which can cooperate in the solving of a problem. We recently sought a new hybrid algorithm for a very unpromising class (SAT problems), and using ECLiPSe we were able to develop an algorithm which showed good performance on some very hard instances. We describe the process of exploring the space of hybrid algorithms for the problem class, and indicate the features of ECLiPSe that enabled us to find previously undiscovered algorithms. How to benchmark the solving of this meta-problem remains a topic of future research. We conclude by pointing out the advantages of an extensible platform, such as ECLiPSe, for developing sophisticated hybrid algorithms for large scale industrial combinatorial optimisation problems.     

基于图像退化模型的图像去雾算法

在雾、霾之类的恶劣天气下拍摄的图像,由于存在大气的散射作用,使得物体特征难以辨认,严重影响了图像的视觉效果,同时还妨碍了图像的特征提取. 因此,需要利用去雾技术对图像进行增强和修复,以改善视觉效果和方便后期处理. 本文针对暗原色先验去雾算法耗时长和处理效果不佳等问题,提出了一种改进的自适应边界约束去雾算法. 同时,引入了信息熵和平均梯度对其进行客观评价,对比实验结果表明该方法运算速度快,在细节处理上效果更好.     

Solving Systems of Difference Constraints Incrementally

Difference constraints systems consisting of inequalities of the form x _i - x _j b _i,j occur in many applications, most notably those involving temporal reasoning. Often, it is necessary to maintain a solution to such a system as constraints are added, modified, and deleted. Existing algorithms handle modifications by solving the resulting system anew each time, which is inefficient. The best known algorithm to determine if a system of difference constraints is feasible (i.e., if it has a solution) and to compute a solution runs in Θ (mn) time, where n is the number of variables and m is the number of constraints. This paper presents a new efficient incremental algorithm for maintaining a solution to a system of difference constraints. As constraints are added, modified, or deleted, the algorithm determines if the new system is feasible and updates its solution. When the system becomes infeasible, the algorithm continues to process changes until it becomes feasible again, at which point a feasible solution will be produced. The algorithm processes the addition of a constraint in time O(m + n log n) and the removal of a constraint in constant time when the original system is feasible. More precisely, additions are processed in time O( || Δ || + |Δ| log|Δ| ) , where |Δ| is the number of variables whose values are changed to compute the new feasible solution, and || Δ || is the number of constraints involving the variables whose values are changed. When the original system is infeasible, the algorithm processes any change in O(m + n log n) amortized time. The new algorithm can also be used to check for the existence of negative cycles in dynamic graphs. Received September 25, 1997; revised November 16, 1997.     

配对组合测试中参数约束问题研究

给出了配对组合测试参数约束分类方法及相关定义。重点对有2值型约束的情况进行了研究,得出有2值型约束存在时虽然所需覆盖的配对数减少,但测试集不一定减小的结论;给出有2值型约束时测试集的最小下限,并证明之。最后介绍了能够有效解决配对组合测试参数约束问题的HPC_IPO约束控制算法。     

An Efficient Bounds Consistency Algorithm for the Global Cardinality Constraint

Previous studies have demonstrated that designing special purpose constraint propagators can significantly improve the efficiency of a constraint programming approach. In this paper we present an efficient algorithm for bounds consistency propagation of the generalized cardinality constraint (gcc). Using a variety of benchmark and random problems, we show that on some problems our bounds consistency algorithm can dramatically outperform existing state-of-the-art commercial implementations of constraint propagators for the gcc. We also present a new algorithm for domain consistency propagation of the gcc which improves on the worst-case performance of the best previous algorithm for problems that occur often in applications.     

粒子群优化算法在桁架结构优化中的应用

介绍了粒子群优化（PSO）算法的一种改进算法：用于约束优化问题的启发式粒子群优化（HPSO）算法。针对HP-SO算法在桁架结构优化中速度较慢的问题,将HPSO算法的约束处理策略与另一种适用于粒子群算法的约束处理方法结合,并将改进后的算法应用到1个桁架结构截面优化设计算例中,同时与HPSO算法进行对比分析。对于此算例,改进算法和HPSO算法都运行了多次,从多次运行的统计分析中可以看出,改进算法的优化效果和稳定性好于HPSO算法,且结构分析的次数减少了一半左右,从而整个程序运行的速度比HPSO算法提高了将近一倍。