协同设计中定量化约束求解方法

通过对约束满足与约束冲突的分析，提出了约束求解的定量化策略．基于变量不确定性，量化了约束满足程度与约束冲突程度，解决了约束求解过程中的优先权问题；给出了约束变化量及关联函数，为约束求解确立了具体的目标和实施方法，实现了约束求解过程的有序搜索．定量化约束求解策略不仅实现了对约束的有序及有效求解，而且真正地实现了在上游约束求解过程中定量地考虑下游约束求解问题．最后，利用随机仿真技术实现了基于变量不确定性的约束求解策略的验证．     

动态识别三维几何约束冲突的方法研究

基于装配几何特征的广义几何约束图,避免了传统几何约束图的超图性质和模糊性,为几何约束满足问题提供了一个清晰的分析模型。文中以此模型来分析产生约束冲突的原因。空间分析法定义和推导了约束满足空间约束满足条件,提出了自由空间和自由度的计算方法,并据此在动态满足三维几何约束的过程中识别约束冲突,明确指出产生约束冲突的原因。     

一种基于修改的约束满足算法

求解约束满足问题的修改算法从实始的有冲突的完整解出发，不断修改理有的变量赋值，从而得到无冲突的完整解。本文将启发式方法应用了修改型算法，提出了一种高效的基于修改的约束满足算法。     

几何设计约束的表示与满足问题研究

对于智能ＣＡＤ系统来说，具有解决几何设计约束的功能是重要的。本文提出了一种面向对象的几何设计约束表示方法，它可以通过两种方式来表达。文中给出了一个约束传播算法，用于解决约束满足问题。     

一种基于图分割的动态回溯算法

动态回溯算法在进行回溯时保留所有已赋值变量的值,从而可能与后面赋值的变量产生冲突,其在解决不具有明显子问题结构的约束满足问题时效率较低。为此,将图分割技术应用于动态回溯,通过图分割将变量分为若干集合,当发生回溯时,不保留全部变量的值,舍弃那些与引起冲突的变量在同一集合变量中的值。实验结果表明,该算法在求解没有明显子问题结构的约束满足问题时具有较高的效率。     

钢铁企业生产能力平衡模型及启发式算法

针对钢铁企业生产能力平衡配置问题,建立了非线性数学模型,形式化地描述了钢铁产品对资源和能力的竞合关系,提出了平衡下的多个优化目标。针对问题的模型及其特点,提出了基于约束满足技术的启发式算法,算法通过优化目标指导变量排序,在变量赋值过程中采用约束传播和回溯技术,缩减变量值域、解消约束冲突,提高了计算效率。基于企业实际生产数据的仿真实验结果验证了模型和算法的有效性。     

基于多AGENT的虚拟企业伙伴选择系统

伙伴选择是虚拟企业建立过程中的核心问题。在基于多agent的虚拟企业体系结构基础上,通过本体驱动的虚拟企业目标体系描述与分解,将虚拟企业伙伴选择问题表示为分布式约束满足和优化问题,并进一步以agent谈判的方式来求解该问题,最终得到优化的伙伴选择方案。本体驱动的虚拟企业目标描述与分解方法,为不同企业之间的谈判提供了通用词汇;用分布式约束满足和优化的方法对问题进行形式化描述,可以为企业之间的谈判提供论域和决策支持。分布式约束满足和优化方法的应用,为解决虚拟企业伙伴选择问题提供了一种新思路。     

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

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

约束分解技术回顾与展望

约束满足问题是一个强有力的知识表示框架,可以有效地解决许多问题。由于约束满足问题一般情况下是NP难度的问题,因此通过约束分解来降低计算的开销具有十分重要的意义。主要描述约束分解在约束满足问题中的地位、经典的分解技术和约束分解技术的发展历史,然后简要地分析这些分解技术。介绍了关于约束分解研究的最新状况,并描述、分析和总结其主要求解思想。最后根据存在的问题与不足提出了下一步的工作方向和研究思路。     

基于约束满足和遗传算法的排课算法

针对高校排课过程中存在诸多资源约束因素的问题,提出一种将遗传算法与约束满足算法相结合的排课算法,由约束满足算法确定排课任务的优先次序,遗传算法解决单个排课任务时间片分配的优化问题。算法中单个排课任务的局部最优解具有全局最优性。实验结果表明,该算法能够改进算法性能,提高排课效率。     

Disjunctions, independence, refinements

An important question in constraint satisfaction is how to restrict the problem to ensure tractability (since the general problem is NP-hard). The use of disjunctions has proven to be a useful method for constructing tractable constraint classes from existing classes; the well-known ‘max-closed’ and ‘ORD-Horn’ constraints are examples of tractable classes that can be constructed this way. Three sufficient conditions (the guaranteed satisfaction property, 1-independence and 2-independence) that each ensure the tractability of constraints combined by disjunctions have been proposed in the literature. We show that these conditions are both necessary and sufficient for tractability in three different natural classes of disjunctive constraints. This suggests that deciding this kind of property is a very important task when dealing with disjunctive constraints. We provide a simple, automatic method for checking the 1-independence property—this method is applicable whenever the consistency of the constraints under consideration can be decided by path-consistency. Our method builds on a connection between independence and refinements (which is a way of reducing one constraint satisfaction problem to another.)     

Ultraviolet: A Constraint Satisfaction Algorithm for Interactive Graphics

Ultraviolet is a constraint satisfaction algorithm intended for use in interactive graphical applications. It is capable of solving constraints over arbitrary domains using local propagation, and inequality constraints and simultaneous linear equations over the reals. To support this, Ultraviolet is a hybrid algorithm that allows different subsolvers to be used for different parts of the constraint graph, depending on graph topology and kind of constraints. In addition, Ultraviolet and its subsolvers support plan compilation, producing efficient compiled code that can be evaluated repeatedly to resatisfy a given collection of constraints for different input values.     

Fuzzy Constraint-Based Agent Negotiation

Conflicts between two or more parties arise for various reasons and perspectives. Thus, resolution of conflicts frequently relies on some form of negotiation. This paper presents a general problem-solving framework for modeling multi-issue multilateral negotiation using fuzzy constraints. Agent negotiation is formulated as a distributed fuzzy constraint satisfaction problem (DPCSP). Fuzzy constrains are thus used to naturally represent each agent's desires involving imprecision and human conceptualization, particularly when lexical imprecision and subjective matters are concerned. On the other hand, based on fuzzy constraint-based problem-solving, our approach enables an agent not only to systematically relax fuzzy constraints to generate a proposal, but also to employ fuzzy similarity to select the alternative that is subject to its acceptability by the opponents. This task of problem-solving is to reach an agreement that benefits all agents with a high satisfaction degree of fuzzy constraints, and move towards the deal more quickly since their search focuses only on the feasible solution space. An application to multilateral negotiation of a travel planning is provided to demonstrate the usefulness and effectiveness of our framework.     

Modeling Agent Negotiation Via Fuzzy Constraints in E-Business

In e-business, disputes between two or more parties arise for various reasons and involve different issues. Thus, resolution of these disputes frequently relies on some form of negotiation. This article presents a general problem-solving framework for modeling multi-issue multilateral agent negotiation using fuzzy constraints in e-business. Fuzzy constraints are thus used not only to define each agent's demands involving human concepts, but also to represent the relationships among agents. A concession strategy, based on fuzzy constraint-based problem-solving, is proposed to relax demands, and a trade-off strategy is presented to evaluate existing alternatives. This approach provides a systematic method for reaching an agreement that benefits all agents with a high satisfaction degree of constraints. Meanwhile, by applying the method, agents can move toward an agreement more quickly, because their search focuses only on the feasible solution space. An example application to negotiate an insurance policy among agents is provided to demonstrate the usefulness and effectiveness of the proposed framework.     

A Foundation of Solution Methods for Constraint Hierarchies

Constraint hierarchies provide a framework for soft constraints, and have been applied to areas such as artificial intelligence, logic programming, and user interfaces. In this framework, constraints are associated with hierarchical preferences or priorities called strengths, and may be relaxed if they conflict with stronger constraints. To utilize constraint hierarchies, researchers have designed and implemented various practical constraint satisfaction algorithms. Although existing algorithms can be categorized into several approaches, what kinds of algorithms are possible has been unclear from a more general viewpoint. In this paper, we propose a novel theory called generalized local propagation as a foundation of algorithms for solving constraint hierarchies. This theory formalizes a way to express algorithms as constraint scheduling, and presents theorems that support possible approaches. A benefit of this theory is that it covers algorithms using constraint hierarchy solution criteria known as global comparators, for which only a small number of algorithms have been implemented. With this theory, we provide a new classification of solution criteria based on their difficulties in constraint satisfaction. We also discuss how existing algorithms are related to our theory, which will be helpful in designing new algorithms.     

A note on some collapse results of valued constraints

Valued constraint satisfaction problem (VCSP) is an optimisation framework originally coming from Artificial Intelligence and generalising the classical constraint satisfaction problem (CSP). The VCSP is powerful enough to describe many important classes of problems. In order to investigate the complexity and expressive power of valued constraints, a number of algebraic tools have been developed in the literature. In this note we present alternative proofs of some known results without using the algebraic approach, but by representing valued constraints explicitly by combinations of other valued constraints.     

High-Order Consistency in Valued Constraint Satisfaction

k-consistency operations in constraint satisfaction problems (CSPs) render constraints more explicit by solving size-k subproblems and projecting the information thus obtained down to low-order constraints. We generalise this notion of k-consistency to valued constraint satisfaction problems (VCSPs) and show that it can be established in polynomial time when penalties lie in a discrete valuation structure.A generic definition of consistency is given which can be tailored to particular applications. As an example, a version of high-order consistency (face consistency) is presented which can be established in low-order polynomial time given certain restrictions on the valuation structure and the form of the constraint graph.     

A constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling

Scheduling activities in concurrent product development process is of great sig-nificance to shorten developements lead time and minimize the cost.Moreover,it can eliminate the unnecessary redesign periods and guarantee that serial activities can be executed as concurrently as possible,This paper presents a constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling.In the combined approack,the neural network is used to obtain a feasible starting time of all the activities based on sequence constraints ,the heuristic algorithm is used to obtain a feasible solution of the scheduling problem based on resource constrainsts.The feasible scheduling solution is obtained by a gradient optimization function .Sim-ulations have shown that the proposed combined approach is efficient and fasible with respect to concurrent activities scheduling.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

Review of: “Management by Motivation”By Saul W. Gellerman. (American Management Association,’1968.) [Pp. 286.] $0.

This paper examines the effects of different types of complexity facing novice designers in constraint satisfaction tasks. The nature of the complexity in a design task was varied by manipulating different aspects of the extrinsic constraints, which refer to restrictions concerning how design components can be assembled. We investigated the effect of the number of constraints (Study 1) and the number of different types of constraint (Study 2) in a simulated office design task. Results indicated that tackling a design task with a greater number of constraints, or more types of constraint, resulted in decrements in performance. Study 3 examined the effect of reasoning about constraints that involved a fixed location in the office layout and those that did not. It was found that having a higher proportion of constraints that referenced a fixed location led to better design performance. The theoretical and practical aspects of these results are discussed.

Practitioner summary: This paper identifies sources of constraint complexity facing the novice designer in an office design task. Three features of constraints proved problematic: the number of constraints, the number of types of constraint and whether the constraint involved a specific location. Training and decision support solutions are discussed.