约束编程及其在产品配置器中的应用

产品配置器技术是人工智能领域近十几年来发展起来的一个新的研究方向,而约束编程、约束满足问题等也是近三十年才发展起来的。本文介绍了产品配置器核心算法的最新发展,论述了约束编程在这一领域所做的贡献以及两者相结合的发展趋势。     

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

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

约束满足问题的局部一致性维护理论与方法

人工智能与计算机科学中的许多问题都可视为约束满足问题,为了简化问题的求解,常采用局部一致性方法减小搜索空间。本文首先介绍与分析了着眼于全局一致性的局部处理的理论与方法,以及尽可能消除回溯因素的局部一致性方法,最后给出了一种在减少局部一致性维护代价上优于已有方法的新算法。     

约束满足技术在板坯排序中的应用

热轧调度中的板坯排序问题是一类特殊的排序问题,具有约束条件复杂、NP难特点。为了简化问题,将板坯排序问题转化为一个约束满足问题处理。给出板坯排序问题的约束满足模型,设计了基于约束满足和启发式混合求解算法。用3组实际生产数据对算法性能进行验证,说明了算法的有效性。     

模糊约束满足在夜间车辆识别中的应用

根据夜间运动车辆识别中存在的无法提取有效的车辆特征,提出了一种改进后的模糊约束满足的夜间运动车辆分类方法。通过对夜间交通监控视频中行驶车辆的车灯光的预处理,调整模糊约束问题算法中各类型车辆的隶属函数参数,从而从构造的车辆运动轨迹图像快速地识别出运动车辆的类型。实验结果表明,引入车辆灯光信息后夜间车辆类型识别准确率得到了一定的提高。     

动态约束满足及其在资源调度问题中的应用

论文系统地论述了动态约束满足技术的基本理论与方法,建立了动态约束满足技术的基本分析框架,给出了动态约束满足在Job-Shop问题中的应用实例。     

基于MAS的分布式约束满足求解在供应链研究中的应用

简要介绍了多智能体系统(MAS)在供应链研究中的应用,给出了约束满足问题(Constraint Satisfaction Problem,CSP)和分布式约束满足问题(Distributed CSP)的定义以及其应用现状,提出了一个利用基于MAS的分布式约束满足求解来研究供应链问题的基本框架,并给出了其求解过程。     

基于非二元约束满足的配置问题求解方法

依据产品的可配置性,提出基于非二元约束的逻辑产品模型,给出基于动态变量序的一类配置求解算法。采用仿真实验比较各种算法的求解效率,指出各算法在不同配置约束密度下快速求解配置问题时的适用范围。基于逻辑产品模型,依据配置问题实际性质,采用相应配置求解算法,能够更快地生成符合客户要求的产品配置方案。     

Algorithms for Distributed Constraint Satisfaction: A Review

When multiple agents are in a shared environment, there usually exist constraints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. Various application problems in multi-agent systems can be formalized as distributed CSPs. This paper gives an overview of the existing research on distributed CSPs. First, we briefly describe the problem formalization and algorithms of normal, centralized CSPs. Then, we show the problem formalization and several MAS application problems of distributed CSPs. Furthermore, we describe a series of algorithms for solving distributed CSPs, i.e., the asynchronous backtracking, the asynchronous weak-commitment search, the distributed breakout, and distributed consistency algorithms. Finally, we show two extensions of the basic problem formalization of distributed CSPs, i.e., handling multiple local variables, and dealing with over-constrained problems.     

A New Approach for Weighted Constraint Satisfaction

We consider the Weighted Constraint Satisfaction Problem which is an important problem in Artificial Intelligence. Given a set of variables, their domains and a set of constraints between variables, our goal is to obtain an assignment of the variables to domain values such that the weighted sum of satisfied constraints is maximized. In this paper, we present a new approach based on randomized rounding of semidefinite programming relaxation. Besides having provable worst-case bounds for domain sizes 2 and 3, our algorithm is simple and efficient in practice, and produces better solutions than some other polynomial-time algorithms such as greedy and randomized local search.     

基于动态约束满足框架的强表达时态规划算法

智能规划已经成为人工智能领域最热门的研究主题之一。近年来,智能规划在现实领域的应用越来越广泛,这对规划器的处理能力和效率提出了很大的挑战。以一类强表达时态规划——基于约束区间规划为研究对象,基于动态约束满足框架设计和实现了一个基于约束区间的规划算法LP-TPOP;对算法的可靠性和完备性进行了证明;最后以一个规划实例演示了算法的运行过程。     

并发约束程序设计语言COPS及其执行模型

约束程序设计尤其是约束逻辑程序设计与并发约束程序设计在AI程序设计领域占据着越来越重要的位置。传统逻辑程序设计的基“计算即为定理证明”的计算风格虽获得了简洁优美的操作语义特性,但也付出了执行效率低的代价,当应用系统规模增大时,其性能严重下降以致崩溃。针对传统逻辑程序设计的这种可伸缩性问题,设计了一个基于并发约束程序设计概念的说明性语言COPS,旨在从语言设计与执行模型两方面降低说明性程序的不确定性,提高搜索与运行效率。在语言设计方面,通过引入确定性语言成分,避免不确定计算用于确定性目标所浪费的系统开销;在执行模型方面,在目标的并发穿叉执行与数据驱动的并发同步机制的基础上,实现“优先执行确定目标”策略与“最少假定”策略,作为约束传播的延伸,最大幅度地剪枝搜索空间,降低搜索复杂性。COPS提供的知识表示、推理与并发机制使其成为构造agent程序的理想语言。论文给出COPS语言的语法规范与执行模型的操作语义描述。     

A Glimpse of Constraint Satisfaction

Constraint satisfaction has become an important field in computer science. This technology is embedded in millions of pounds of software used by major companies. Many researchers or software engineers in the industry could have benefited from using constraint technology without realizing it. The aim of this paper is to promote constraint technology by providing readers with a fairly quick introduction to this field. The approach here is to use the well known 8-queens problem to illustrate the basic techniques in constraint satisfaction (without going into great details), and leave interested readers with pointers to further study this field.     

SC-PROLOG解释系统中的约束逻辑程序设计方法

约束逻辑程序设计（ＣＬＰ）方法是提高ＰＲＯＬＯＧ语言效率的一种崭新方法，本文针对ＳＣ┐ＰＲＯＬＯＧ解释系统的实现介绍其相应设计思想，从域变量含义入手，提出了域及约束的存储方法以及约束机制的实现算法，是对逻辑设计方法研究的一点体会     

Boosting Search with Variable Elimination in Constraint Optimization and Constraint Satisfaction Problems

There are two main solving schemas for constraint satisfaction and optimization problems: i) search, whose basic step is branching over the values of a variables, and ii) dynamic programming, whose basic step is variable elimination. Variable elimination is time and space exponential in a graph parameter called induced width, which renders the approach infeasible for many problem classes. However, by restricting variable elimination so that only low arity constraints are processed and recorded, it can be effectively combined with search, because the elimination of variables may reduce drastically the search tree size.In this paper we introduce BE-BB(k), a hybrid general algorithm that combines search and variable elimination. The parameter k controls the tradeoff between the two strategies. The algorithm is space exponential in k. Regarding time, we show that its complexity is bounded by k and a structural parameter from the constraint graph. We provide experimental evidence that the hybrid algorithm can outperform state-of-the-art algorithms in constraint satisfaction, Max-CSP and Weighted CSP. Especially in optimization tasks, the advantage of our approach over plain search can be overwhelming.     

Heavy-Tailed Phenomena in Satisfiability and Constraint Satisfaction Problems

We study the runtime distributions of backtrack procedures for propositional satisfiability and constraint satisfaction. Such procedures often exhibit a large variability in performance. Our study reveals some intriguing properties of such distributions: They are often characterized by very long tails or heavy tails. We will show that these distributions are best characterized by a general class of distributions that can have infinite moments (i.e., an infinite mean, variance, etc.). Such nonstandard distributions have recently been observed in areas as diverse as economics, statistical physics, and geophysics. They are closely related to fractal phenomena, whose study was introduced by Mandelbrot. We also show how random restarts can effectively eliminate heavy-tailed behavior. Furthermore, for harder problem instances, we observe long tails on the left-hand side of the distribution, which is indicative of a non-negligible fraction of relatively short, successful runs. A rapid restart strategy eliminates heavy-tailed behavior and takes advantage of short runs, significantly reducing expected solution time. We demonstrate speedups of up to two orders of magnitude on SAT and CSP encodings of hard problems in planning, scheduling, and circuit synthesis.