University of Cambridge > > Microsoft Research PhD Scholars > Value Ordering Heuristics for Quantified Constraint Satisfaction

Value Ordering Heuristics for Quantified Constraint Satisfaction

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Dr Fabien Petitcolas.

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.

This talk is part of the Microsoft Research PhD Scholars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2022, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity