Value Ordering for Offline and Realtime-Online Solving of Quantified Constraint Satisfaction Problems

Standard Constraint Satisfaction Problems (CSPs) are not suited to reasoning on problems containing uncertainty or adversarial situations (e.g. games), in which the decisions are not all under the control of a single decision maker. We can describe these types of problems as online CSPs, where the problem variables must be instantiated in a fixed sequence, but where some of those variables are set externally. There exists an extension of CSP, the Quantified Constraint Satisfaction Problem (QCSP), which can be regarded as a model for these types of online CSP. A QCSP allows the variables to be universally or existentially quantified, and to solve a QCSP we must find a strategy which allows a solution to be reached no matter what combination of values the universally quantified variables may take. Finding a winning strategy to the QCSP guarantees being able to reach a solution in the online CSP. Unfortunately, solving the 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 dissertation, 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 QCSPs. For cases where the online CSP is also real time, i.e. the decisions must be made within strict time limits and we do not have enough time to fully solve the QCSP, 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 show that both on randomly generated binary QCSPs 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 to solve fully.

David Stynes - Thesis.pdf
PDF file

Details

TypePhdThesis
InstitutionNational University of Ireland, Cork
> Publications > Value Ordering for Offline and Realtime-Online Solving of Quantified Constraint Satisfaction Problems