Abstract
The Stochastic CSP (SCSP) is a framework recently introduced by Walsh to capture combinatorial decision problems that involve uncertainty and probabilities. The SCSP extends the classical CSP by including both decision variables, that an agent can set, and stochastic variables that follow a probability distribution and can model uncertain events beyond the agent’s control. So far, two approaches to solving SCSPs have been proposed; backtracking-based procedures that extend standard methods from CSPs, and scenario-based methods that solve SCSPs by reducing them to a sequence of CSPs. In this paper we further investigate the former approach. We first identify and correct a flaw in the forward checking (FC) procedure proposed by Walsh. We also extend FC to better take advantage of probabilities and thus achieve stronger pruning. Then we define arc consistency for SCSPs and introduce an arc consistency algorithm that can handle constraints of any arity.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bessière, C., Régin, J.C., Yap, R., Zhang, Y.: An Optimal Coarse-grained Arc Consistency Algorithm. Artificial Intelligence 165(2), 165–185 (2005)
Bordeaux, L., Cadoli, M., Mancini, T.: CSP Properties for Quantified Constraints: Definitions and Complexity. In: Proceedings of AAAI 2005, pp. 360–365 (2005)
Bordeaux, L.: Boolean and interval propagation for quantified constraints. In: Proceedings of the CP 2005 Workshop on Quantification in Constraint Programming, pp. 16–30 (2005)
Dubois, D., Fargier, H., Prade, H.: Possibility Theory in Constraint Satisfaction Problems: Handling Priority, Preference and Uncertainty. Applied Intelligence 6(4), 287–309 (1996)
Fiat, A., Woeginger, G.J. (eds.): Online Algorithms. LNCS, vol. 1442. Springer, Heidelberg (1998)
Littman, M.L., Majercik, S.M., Pitassi, T.: Stochastic Boolean Satisfiability. Journal of Automated Reasoning 27(3), 251–296 (2000)
Manandhar, S., Tarim, A., Walsh, T.: Scenario-based Stochastic Constraint Programming. In: Proceedings of IJCAI 2003, pp. 257–262 (2003)
Ruszczynski, A., Shapiro, A.: Stochastic Programming. In: Handbooks in OR/MS, vol. 10. Elsevier Science, Amsterdam (2003)
Verfaillie, G., Jussien, N.: Constraint Solving in Uncertain and Dynamic Environments: A Survey. Constraints 10(3), 253–281 (2005)
Walsh, T.: Stochastic Constraint Programming. In: Proceedings of ECAI 2002, pp. 111–115 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Balafoutis, T., Stergiou, K. (2006). Algorithms for Stochastic CSPs. In: Benhamou, F. (eds) Principles and Practice of Constraint Programming - CP 2006. CP 2006. Lecture Notes in Computer Science, vol 4204. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11889205_6
Download citation
DOI: https://doi.org/10.1007/11889205_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-46267-5
Online ISBN: 978-3-540-46268-2
eBook Packages: Computer ScienceComputer Science (R0)