BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Value Ordering Heuristics for Quantified Constraint Satisfaction -
  David Stynes\, University College Cork
DTSTART:20091030T140000Z
DTEND:20091030T143000Z
UID:TALK21266@talks.cam.ac.uk
CONTACT:Dr Fabien Petitcolas
DESCRIPTION:Constraint Satisfaction Problems (CSPs) are not suited to reas
 oning on problems containing uncertainty or adversarial situations\, in wh
 ich 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 gene
 ral\, PSPACE-complete. As such when the problem size is increased\, even t
 he most efficient QCSP solvers quickly become unable to solve the problem.
  In this talk\, we investigate the use of Value Ordering Heuristics to hel
 p address this issue. We show that value ordering can be used to improve t
 he efficiency of search when solving QCSPs. For cases where there is not e
 nough 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 u
 se value ordering to help us reason about what value to pick for the curre
 nt decision. We perform game-tree search augmented with constraint propaga
 tion during our limited time per decision\, and use the value ordering heu
 ristics to evaluate the states explored during the search to help choose w
 hat value to assign the current variable. We find that both on randomly ge
 nerated binary QCSPs and on Online Bin Packing problems we can achieve goo
 d performance with this approach\, and can also handle QCSP problem instan
 ces which are too large for current QCSP solvers to solve fully.
LOCATION:Small Lecture Room\, Microsoft Research\, Roger Needham Building\
 , 7 J J Thomson Avenue\, Cambridge CB3 0FB
END:VEVENT
END:VCALENDAR