Dynamic Flexible Constraint Satisfaction

摘要

Existing techniques for solving constraint satisfaction problems (CSPs) are largely concerned with a static set of imperative, inflexible constraints. Recently, work has addressed these shortcomings of classical constraint satisfaction in the form of two separate extensions known as flexible and dynamic CSP. Little, however, has been done to combine these two approaches in order to bring to bear the benefits of both in solving more complex problems. This paper presents a new integrated algorithm, Flexible Local Changes, for dynamic flexible problems. It is further shown how the use of flexible consistency-enforcing techniques can improve solution re-use and hence the efficiency of the core algorithm. Empirical evidence is provided to support the success of the present approach.