Robustness in Dynamic Constraint Satisfaction Problems

Abstract

[EN] Constraint programming is a successful technology for solving combinatorial problems modeled as constraint satisfaction problems (CSPs). Many real life problems are dynamic, which means that the initial description of the problem may change during its execution. These problems can be modeled as dynamic constraint satisfaction problems (DynCSPs), which are an important extension of the CSPs. In this paper, we focus our attention on the concept of robustness. Our aim is to find robust solutions which have a high probability of remaining valid faced with possible future changes in the constraints of the problem. We introduce the informed DynCSPs, proposing an approach to solve them by the weighted CSP (WCSP) modeling. Thus, the best solution for the modeled WCSP will be a robust solution for the original DynCSP. Furthermore, this technique has been evaluated in order to analyze the robustness of the solutions obtained.