Value Ordering Heuristics for Quantified Constraint Satisfaction

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

• David Stynes, University College Cork
• Friday 30 October 2009, 14:00-14:30
• Small Lecture Room, Microsoft Research, Roger Needham Building, 7 J J Thomson Avenue, Cambridge CB3 0FB.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Microsoft Research PhD Scholars
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Small Lecture Room, Microsoft Research, Roger Needham Building, 7 J J Thomson Avenue, Cambridge CB3 0FB
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.