Dynamic Constraint Satisfaction Problems
Dynamic Constraint Satisfaction Problems
复制标题
DOI：
--
复制
发表时间：
1990-07
期刊：
影响因子：
--
通讯作者：
S. Mittal;Brian Falkenhainer
中科院分区：
文献类型：
--
作者：
S. Mittal;Brian Falkenhainer
约束满足（CSP）是一个强大且广泛使用的描述搜索问题的框架。 CSP 通常被定义为在给定对这些变量的一些约束的情况下找到对一组固定变量的一致赋值的问题。然而，对于许多综合任务（例如配置和模型组合），与解决方案相关且必须分配值的变量集会根据问题解决过程中做出的决策而动态变化。在本文中，我们将这个概念形式化为使用两种类型约束的动态约束满足问题。兼容性约束对应于 CSP 中传统的约束，即对变量值的约束。活动约束描述了变量可能会或可能不会被积极考虑作为最终解决方案的一部分的条件。我们提出了一种语言，用于根据变量值和所考虑的变量来表达四种类型的活动约束。然后，我们描述了一种实现的算法，该算法可以实现变量活动的约束和变量值的约束之间的紧密交互。该方法的实用性在配置和模型组合任务中得到了证明。
Constraint satisfaction (CSP) is a powerful and extensively used framework for describing search problems. A CSP is typically defined as the problem of finding consistent assignment of values to a fixed set of variables given some constraints over these variables. However, for many synthesis tasks such as configuration and model composition, the set of variables that are relevant to a solution and must be assigned values changes dynamically in response to decisions made during the course of problem solving. In this paper, we formalize this notion as a dynamic constraint satisfaction problem that uses two types of constraints. Compatibility constraints correspond to those traditionally found in CSPs, namely, constraints over the values of variables. Activity constraints describe conditions under which a variable may or may not be actively considered as a part of a final solution. We present a language for expressing four types of activity constraints in terms of variable values and variables being considered. We then describe an implemented algorithm that enables tight interaction between constraints about variable activity and constraints about variable values. The utility of this approach is demonstrated for configuration and model composition tasks.