Algorithms for stochastic constraint satisfaction problems

Abstract

This thesis consists of six chapters. Chapter1 includes a general introduction in the area of interest. The related work that has been done in CSPs and SCSPs is reviewed in Chapter 2. We also describe here the main algorithms that have been proposed for solving stochastic constraint satisfaction problems.In Chapter 3 we propose a generalized arc consistency (GAC) algorithm for SCSPs. This algorithm extends the GAC algorithm AC2001/3.1 with specialized features, so that SCSPs can be handled. We also explain how arc consistency reasoning can be performed when “chance” constraints are present in a problem. In Chapter 4 we introduce new search algorithms for solving stochastic constraint satisfaction problems. We first identify and correct a flaw in the forward checking (FC) algorithm given in [Walsh02]. We also describe an improved version of FC which exploits probabilities in a more “global” way and in this way results in stronger pruning. Then we introduce a Maintaining Arc Consistency (MAC) algorithm for SCSPs. In contrast with [Walsh02], where the given algorithms can only handle binary constraints, our MAC algorithm is able to handle constraints of any arity. The chapter ends with the presentation of some heuristics which increase the efficiency of the above search algorithms.A set of experiments is presented in Chapter 5. These experiments demonstrate the effect that the flaw has in the FC algorithm of [Walsh02] and depict the achieved improvement of our new FC algorithm. We also present experiments with FC that uses arc consistency as a preprocessing technique.Finally Chapter 6 concludes the thesis by summarizing the results reported here and gives some directions for future work.