Robustness and stability in Constraint Programming under dynamism and uncertainty

Climent, Laura; Wallace, Richard J.; Salido, Miguel A.; Barber, Frederico

Robustness and stability in Constraint Programming under dynamism and uncertainty

Files

13954-61073-1-PB.pdf(466.9 KB)

Published version

Date

2014-01-28

Authors

Climent, Laura

Wallace, Richard J.

Salido, Miguel A.

Barber, Frederico

Publisher

AI Access Foundation

Abstract

Many real life problems that can be solved by constraint programming, come from uncertain and dynamic environments. Because of the dynamism, the original problem may change over time, and thus the solution found for the original problem may become invalid. For this reason, dealing with such problems has become an important issue in the fields of constraint programming. In some cases, there exist extant knowledge about the uncertain and dynamic environment. In other cases, this information is fragmentary or unknown. In this paper, we extend the concept of robustness and stability for Constraint Satisfaction Problems (CSPs) with ordered domains, where only limited assumptions need to be made as to possible changes. We present a search algorithm that searches for both robust and stable solutions for CSPs of this nature. It is well-known that meeting both criteria simultaneously is a desirable objective for constraint solving in uncertain and dynamic environments. We also present compelling evidence that our search algorithm outperforms other general-purpose algorithms for dynamic CSPs using random instances and benchmarks derived from real life problems.

Keywords

Constraint programming , Robustness , Dynamism

Citation

Climent, L., Wallace, R. J., Salido, M. A. and Barber, F. (2014) 'Robustness and Stability in Constraint Programming under Dynamism and Uncertainty', Journal of Artificial Intelligence Research, 49, pp. 49-78. doi: 10.1613/jair.4126