Abstract

Constraint Satisfaction Problems (CSPs) are not suited to reasoning on problems containing uncertainty or adversarial situations, in which the decisions are not all under the control of a single decision maker. Quantified Constraint Satisfaction Problems(QCSPs), are an extension of CSPs which can express this uncertainty, but solving a QCSP is, in general, PSPACE -complete. As such when the problem size is increased, even the most efficient QCSP solvers quickly become unable to solve the problem. In this talk, we investigate the use of Value Ordering Heuristics to help address this issue. We show that value ordering can be used to improve the efficiency of search when solving QCS Ps. For cases where there is not enough time to fully solve the QCSP , as we have only a limited time window in which to make each decision, we investigate an approach in which we use value ordering to help us reason about what value to pick for the current decision. We perform game-tree search augmented with constraint propagation during our limited time per decision, and use the value ordering heuristics to evaluate the states explored during the search to help choose what value to assign the current variable. We find that both on randomly generated binary QCS Ps and on Online Bin Packing problems we can achieve good performance with this approach, and can also handle QCSP problem instances which are too large for current QCSP solvers to solve fully.