Min-domain retroactive ordering for Asynchronous Backtracking

Ordering heuristics are a powerful tool in CSP search algorithms. Among the most successful ordering heuristics are heuristics which enforce a fail first strategy by using the Min-domain property (Haralick and Elliott, Artif Intel 14:263–313, 1980; Bessiere and Regin, Mac and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Proc. CP 96, pp. 61–75, Cambridge, MA, 1996; Smith and Grant, Trying harder to fail first. In European Conference on Artificial Intelligence, pp. 249–253, 1998; Dechter, Constraint Processing. Morgan Kaufman, 2003). Ordering heuristics have been introduced recently to asynchronous backtracking (ABT), for distributed constraints satisfaction (DisCSP) (Zivan and Meisels, Dynamic ordering for asynchronous backtracking on discsps. In CP-2005, pp. 32–46, Sigtes (Barcelona), Spain, 2005). However, the pioneering study of dynamically ordered ABT, ABT_DO, has shown that a straightforward implementation of the Min-domain heuristic does not produce the expected improvement over a static ordering. The present paper proposes an asynchronous dynamic ordering which does not follow the standard restrictions on the position of reordered agents in ABT_DO. Agents can be moved to a position that is higher than that of the target of the backtrack. Combining the Nogood-triggered heuristic and the Min-domain property in this new class of heuristics results in the best performing version of ABT_DO. The new version of retroactively ordered ABT is faster by a large factor than the best form of ABT.     

Asynchronous Forward-checking for DisCSPs

A new search algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. Agents assign variables sequentially, but perform forward checking asynchronously. The asynchronous forward-checking algorithm (AFC) is a distributed search algorithm that keeps one consistent partial assignment at all times. Forward checking is performed by sending copies of the partial assignment to all unassigned agents concurrently. The algorithm is described in detail and its correctness proven. The sequential assignment method of AFC leads naturally to dynamic ordering of agents during search. Several ordering heuristics are presented. The three best heuristics are evaluated and shown to improve the performance of AFC with static order by a large factor. An experimental comparison of AFC to asynchronous backtracking (ABT) on randomly generated DisCSPs is also presented. AFC with ordering heuristics outperforms ABT by a large factor on the harder instances of random DisCSPs. These results hold for two measures of performance: number of non-concurrent constraints checks and number of messages sent. Research supported by the Lynn and William Frankel Center for Computer Sciences and the Paul Ivanier Center for Robotics and Production Management.     

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

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

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

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

动态Web Services的约束满足优化技术研究

Web Services合成是Web Services技术的重要方面,能够按要求提供选择新的服务。本文首先提出了Web Services服务约束的分类描述,进而分析了Web Services服务合成中如何按照服务约束指导服务选择,进而选择合适的服务集来满足客户的要求。该方法把动态Web Services合成转化为约束满足问题。     

一种动态分布式约束优化问题协同求解算法

多Agent协作过程中的许多问题都可在分布式约束优化问题(DCOP)框架下建模,但多局限于规划问题,且一般需Agent具有完全、准确收益函数.针对DCOP局限性,定义动态分布式约束优化问题(DDCOP),分析求解它的两个关键操作:Exploration和Exploitation,提出基于混沌蚂蚁的DDCOP协同求解算法(CA-DDCOP).该算法借鉴单只蚂蚁的混沌行为和蚁群的自组织行为,实现Exploration和Exploitation,根据玻尔兹曼分布,建立平衡Exploration和Exploitation的协同方法.通过多射频多信道无线AdHoc网络的信道分配验证该算法的有效性.     

A CSP technique-based interactive control panel layout

An interactive and iterative control panel layout method based on the constraint satisfaction problem (CSP) technique was developed to generate an ergonomically sound panel design. This control panel layout method attempts to incorporate a variety of relevant ergonomic principles and design constraints, and generate an optimal or, at least, a ‘satisfactory’ solution through an efficient search algorithm. The problem of seeking an ergonomically sound panel design should be viewed as a multi-criteria problem, and most of the design objectives should be understood as constraints. Hence, a CSP technique was employed in this study for dealing with the multi-constraints layout problem. The efficient search algorithm using ‘preprocess’ and ‘look_ahead’ procedures was developed to handle the vast amount of computational effort. In order to apply the CSP technique to the panel layout procedure, the ergonomic principles such as spatial compatibility, frequency-of-use, importance, functional grouping, and sequence-of-use were formalized as CSP terms. The effectiveness of the proposed panel layout method was evaluated by example problems, and the results clearly showed that the generated layouts properly considered various ergonomic design principles.     

Symmetry Definitions for Constraint Satisfaction Problems

We review the many different definitions of symmetry for constraint satisfaction problems (CSPs) that have appeared in the literature, and show that a symmetry can be defined in two fundamentally different ways: as an operation preserving the solutions of a CSP instance, or else as an operation preserving the constraints. We refer to these as solution symmetries and constraint symmetries. We define a constraint symmetry more precisely as an automorphism of a hypergraph associated with a CSP instance, the microstructure complement. We show that the solution symmetries of a CSP instance can also be obtained as the automorphisms of a related hypergraph, the k-ary nogood hypergraph and give examples to show that some instances have many more solution symmetries than constraint symmetries. Finally, we discuss the practical implications of these different notions of symmetry.     

Automatic Generation of Redundant Models for Permutation Constraint Satisfaction Problems

If we have two representations of a problem as constraint satisfaction problem (CSP) models, it has been shown that combining the models using channeling constraints can increase constraint propagation in tree search CSP solvers. Handcrafting two CSP models for a problem, however, is often time-consuming. In this paper, we propose model induction, a process which generates a second CSP model from an existing model using channeling constraints, and study its theoretical properties. The generated induced model is in a different viewpoint, i.e., set of variables. It is mutually redundant to and can be combined with the input model, so that the combined model contains more redundant information, which is useful to increase constraint propagation. We also propose two methods of combining CSP models, namely model intersection and model channeling. The two methods allow combining two mutually redundant models in the same and different viewpoints respectively. We exploit the applications of model induction, intersection, and channeling and identify three new classes of combined models, which contain different amounts of redundant information. We construct combined models of permutation CSPs and show in extensive benchmark results that the combined models are more robust and efficient to solve than the single models.     

The Impact of Search Heuristics on Heavy-Tailed Behaviour

The heavy-tailed phenomenon that characterises the runtime distributions of backtrack search procedures has received considerable attention over the past few years. Some have conjectured that heavy-tailed behaviour is largely due to the characteristics of the algorithm used. Others have conjectured that problem structure is a significant contributor. In this paper we attempt to explore the former hypothesis, namely we study how variable and value ordering heuristics impact the heavy-tailedness of runtime distributions of backtrack search procedures. We demonstrate that heavy-tailed behaviour can be eliminated from particular classes of random problems by carefully selecting the search heuristics, even when using chronological backtrack search. We also show that combinations of good search heuristics can eliminate heavy tails from quasigroups with holes of order 10 and 20, and give some insights into why this is the case. These results motivate a more detailed analysis of the effects that variable and value orderings can have on heavy-tailedness. We show how combinations of variable and value ordering heuristics can result in a runtime distribution being inherently heavy-tailed. Specifically, we show that even if we were to use an oracle to refute insoluble subtrees optimally, for some combinations of heuristics we would still observe heavy-tailed behaviour. Finally, we study the distributions of refutation sizes found using different combinations of heuristics and gain some further insights into what characteristics tend to give rise to heavy-tailed behaviour.     

Distributed AEC databases for collaborative design

The Architecture, Engineering and Construction (AEC) design process for a facility involves participation of many design specialists. These participants are architects, engineers (structural, mechanical and electrical) and contractors, who may be independent design professionals or design teams within an organization. From the viewpoint of information processing, two characteristic features distinguish the AEC design process from many other design domains. Firstly, there is a massive volume of design data involved in the design of each of its component specialties. Secondly, the specialization of the disciplines themselves warrant substantial autonomy. For design automation, this autonomy should be realized without sacrificing the collaborative nature of the multidisciplinary AEC design process. We propose autonomous AEC databases to deal with the first issue, and a global constraint maintenance mechanism for the second. Autonomous design databases can support the existing local applications in architectural, structural and mechanical engineering, and construction domains. However, a set of inter-disciplinary constraints needs to be enforced to ensure spatial and functional consistency of the design. A global constraint checking mechanism frees designers from the burden of keeping track of various design changes that may result in cross-functional conflicts. In this paper, we discuss the relevant issues for constraint management on distributed AEC databases. Although specific AEC examples will be used, the presentation is general enough to be applicable to other design domains, such as VLSI and manufacturing.     

基于层次约束满足的产品选择算法

将产品的选择看作一种层次约束满足问题,从而提出一种基于层次约束满足的多属性决策算法HCSMDA,该算法基于约束逻辑编程,可解决实际的产品选择问题,使得用户得到所需的产品.     

Generalised arc consistency for the AllDifferent constraint: An empirical survey

The AllDifferent constraint is a crucial component of any constraint toolkit, language or solver, since it is very widely used in a variety of constraint models. The literature contains many different versions of this constraint, which trade strength of inference against computational cost. In this paper, we focus on the highest strength of inference, enforcing a property known as generalised arc consistency (GAC). This work is an analytical survey of optimizations of the main algorithm for GAC for the AllDifferent constraint. We evaluate empirically a number of key techniques from the literature. We also report important implementation details of those techniques, which have often not been described in published papers. We pay particular attention to improving incrementality by exploiting the strongly-connected components discovered during the standard propagation process, since this has not been detailed before. Our empirical work represents by far the most extensive set of experiments on variants of GAC algorithms for AllDifferent. Overall, the best combination of optimizations gives a mean speedup of 168 times over the same implementation without the optimizations.     

资源独立工作流可满足性的最小增量模式回溯

工作流可满足性是业务安全规划的基本问题, 正在面临高资源配比(资源数n显著大于步骤数k)造成的性能挑战. 在资源独立约束下, 其最高效求解途径是模式空间上的增量回溯法IPB. 为克服结点真实性验证的性能瓶颈, 它增量计算模式k指派(二部)图及其(左完备)匹配, 分别需要O(kn)和O(k²)时间. 利用父子模式的原子差异增量计算完全指派图, 只需O(n)时间, 特别是其实际性能, 将随模式块规模增长迅速提高. 但该图的O(kn)规模导致了同样的增量匹配时间. 进而引入完备k核心匹配概念, 证明其存在性等价于左完备匹配, 且其增量计算时间为O(k²). 由此, 建立了时间复杂度更低的最小增量模式回溯法. 在含互斥和两种全局值势约束而授权比例约为1/4的扩展公开实例集上进行实验, 结果表明: 当n/k=10(及n/k=100), 而k变化时, 该方法较IPB有平均超过2(及5)倍、最低1.5(及2.9)倍的性能优势; 当k=18(及k=36), 而n/k=2~4096(及n/k=2~2048)时, 该方法有平均超过2.6(及3.6)倍优势; 而较2021年Minizinc挑战赛的冠军求解器Google OR-Tools CP-SAT, 该方法最低有超过3倍优势.     

智能规划中的可纳子目标排序

提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能.     

分布式系统上异步算法的终止

本文论述了一种检测分布式系统上异步算法终止的有效方法．     

Toward a Model for Backtracking and Dynamic Programming

We propose a model called priority branching trees (pBT) for backtracking and dynamic programming algorithms. Our model generalizes both the priority model of Borodin, Nielson and Rackoff, as well as a simple dynamic programming model due to Woeginger, and hence spans a wide spectrum of algorithms. After witnessing the strength of the model, we then show its limitations by providing lower bounds for algorithms in this model for several classical problems such as Interval Scheduling, Knapsack and Satisfiability.     

Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results

This paper summarizes the main existing approaches to propagate resource constraints in Constraint-Based scheduling and identifies some of their limitations for using them in an integrated planning and scheduling framework. We then describe two new algorithms to propagate resource constraints on discrete resources and reservoirs. Unlike most of the classical work in scheduling, our algorithms focus on the precedence relations between activities rather than on their absolute position in time. They are efficient even when the set of activities is not completely defined and when the time window of activities is large. These features explain why our algorithms are particularly suited for integrated planning and scheduling approaches. All our algorithms are illustrated with examples. Encouraging preliminary results are reported on pure scheduling problems as well as some possible extensions of our framework.     

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

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

基于组件的分布式约束管理系统研究

在分析约束管理系统分布性、异构性等特点以及可靠性、可扩展性和可重用性等要求的基础上,提出了基于组件技术设计与实现分布式约束管理系统的方法,并给出了系统的开发实例。