Stochastic Constraint Programming

Abstract

To model combinatorial decision problems involving uncertainty and probability, we introduce stochastic constraint programming. Stochastic constraint programs contain both decision variables (which we can set) and stochastic variables (which follow a probability distribution). They combine together the best features of traditional constraint satisfaction, stochastic integer programming, and stochastic satisfiability. We give a semantics for stochastic constraint programs, and propose a number of complete algorithms and approximation procedures. Finally, we discuss a number of extensions of stochastic constraint programming to relax various assumptions like the independence between stochastic variables, and compare with other approaches for decision making under uncertainty.

Proceedings of the 15th Eureopean Conference on Artificial Intelligence

References in corpus (1)

• On the Complexity of Solving Markov Decision Problems

Cited by in corpus (15)

• Value Elimination: Bayesian Inference via Backtracking Search
• A constraint satisfaction approach to the robust spanning tree problem with interval data
• An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities
• Confidence-based Reasoning in Stochastic Constraint Programming
• Statistical Constraints
• Generalized Craig Interpolation for Stochastic Boolean Satisfiability Problems with Applications to Probabilistic State Reachability and Region Stability
• microPhantom: Playing microRTS under uncertainty and chaos
• Compiling Stochastic Constraint Programs to And-Or Decision Diagrams
• Stochastic Constraint Optimization using Propagation on Ordered Binary Decision Diagrams
• CDF-Intervals: A Reliable Framework to Reason about Data with Uncertainty
• Distributed Constraint Problems for Utilitarian Agents with Privacy Concerns, Recast as POMDPs
• The P-Box CDF-Intervals: Reliable Constraint Reasoning with Quantifiable Information
• Declarative Statistics
• Optimizing Probabilities in Probabilistic Logic Programs
• Constrained optimization under uncertainty for decision-making problems: Application to Real-Time Strategy games