The Quantified CSP (QCSP) is a generalization of the CSP which allows for universally quantified variables. For each possible sequence of assignments to such variables, we have to find a way to set the values of the remaining, existentially quantified, variables so that all the constraints are satisfied. Such problems arise in areas such as planning under uncertainty, model checking, and adversary game playing. QCSPs are starting to attract interest following the development of numerous efficient solvers for the closely related area of QBF. Two approaches have been studied so far; the encoding of QCSPs into QBF, and the generalization of well-known search procedures for CSPs, like FC and MAC, to the quantified case. In this paper we introduce a new approach which utilizes repair-based techniques. We describe a framework for a QCSP solver in which complete and incomplete repair-based methods can be incorporated. We also evaluate such a solver that applies backtracking and local search methods based on the min-conflicts heuristic. Experimental results demonstrate that even simple repair-based techniques can outperform the state-of-the-art solver QCSP-Solve.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- Repair-Based Methods for Quantified CSPs
- Springer Berlin Heidelberg
Neuer Inhalt/© ITandMEDIA