Abstract
Because of the dynamism and uncertainty associated with many real life problems, these problems and their associated Constraint Satisfaction Problem (CSP) models may change over time; thus an earlier solution found for the latter may become invalid. Moreover, many approaches proposed in the literature cannot be applied when the required information about dynamism is unknown ([9], [4], [5], [11], [10], etc.). This fact has motivated us to consider dynamic situations where, in addition, only limited assumptions about changes can be made. Our analysis focuses on CSPs with ordered and discrete domains that model problems for which the order over the elements of the domain is significant. In these cases, a common type of change that problems may undergo is restrictive modifications over the bounds of the solution space. A discussion of these assumptions, their motivation and real life examples can be found in [3].
In this paper, we present an algorithm that meets the goal of combining solution stability (meaning that solutions can often be repaired using other similar values if they undergo a value loss) and robustness (meaning that solutions have a high likelihood of remaining solutions after changes). The desireability of this combination of features was noted in the survey [8]. Furthermore, in this work we have extended both concepts to apply to the type of CSP analyzed. The paper is organized as follows. Section 2 presents the new conceptions of robustness and stability. Section 3 describes our approach for finding solutions that simultaneously meet both these criteria. In Section 4 we present some experimental results. Section 5 gives conclusions.
This is a summary of the paper: L. Climent, R. J. Wallace, M. A. Salido, and F. Barber. Robustness and Stability in Constraint Programming under Dynamism and Uncertainty. Journal of Artificial Intelligence Research, 49:49-78, 2014. http://www.jair.org/media/4126/live-4126-7626-jair.pdf
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Climent, L., Wallace, R., Salido, M., Barber, F.: An algorithm for finding robust and stable solutions for constraint satisfaction problems with discrete and ordered domains. In: 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2012), pp. 874–879 (2012)
Climent, L., Wallace, R.J., Salido, M.A., Barber, F.: A constraint programming approach to solve scheduling problems under uncertainty. In: Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS 2013) in ICAPS 2013, pp. 28–37 (2013)
Climent, L., Wallace, R.J., Salido, M.A., Barber, F.: Finding robust solutions for constraint satisfaction problems with discrete and ordered domains by coverings. In: Artificial Intelligence Review (AIRE) (2013), doi:10.1007/s10462-013-9420-0
Fargier, H., Lang, J.: Uncertainty in constraint satisfaction problems: A probabilistic approach. In: Moral, S., Kruse, R., Clarke, E. (eds.) ECSQARU 1993. LNCS, vol. 747, pp. 97–104. Springer, Heidelberg (1993)
Fargier, H., Lang, J., Schiex, T.: Mixed constraint satisfaction: A framework for decision problems under incomplete knowledge. In: Proceedings of the 13th National Conference on Artificial Intelligence (AAAI 1996), pp. 175–180 (1996)
Hebrard, E.: Robust Solutions for Constraint Satisfaction and Optimisation under Uncertainty. PhD thesis, University of New South Wales (2006)
Sadeh, N., Fox, M.: Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence 86(1), 1–41 (1996)
Verfaillie, G., Jussien, N.: Constraint solving in uncertain and dynamic environments: A survey. Constraints 10(3), 253–281 (2005)
Wallace, R., Freuder, E.: Stable solutions for dynamic constraint satisfaction problems. In: Maher, M.J., Puget, J.-F. (eds.) CP 1998. LNCS, vol. 1520, pp. 447–461. Springer, Heidelberg (1998)
Walsh, T.: Stochastic constraint programming. In: Proceedings of the 15th European Conference on Artificial Intelligence (ECAI 2002), pp. 111–115 (2002)
Yorke-Smith, N., Gervet, C.: Certainty closure: Reliable constraint reasoning with incomplete or erroneous data. Journal of ACM Transactions on Computational Logic (TOCL) 10(1), 3 (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Climent, L., Wallace, R.J., Salido, M.A., Barber, F. (2014). Robustness and Stability in Constraint Programming under Dynamism and Uncertainty. In: O’Sullivan, B. (eds) Principles and Practice of Constraint Programming. CP 2014. Lecture Notes in Computer Science, vol 8656. Springer, Cham. https://doi.org/10.1007/978-3-319-10428-7_68
Download citation
DOI: https://doi.org/10.1007/978-3-319-10428-7_68
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-10427-0
Online ISBN: 978-3-319-10428-7
eBook Packages: Computer ScienceComputer Science (R0)