Arrêt de service programmé du vendredi 10 juin 16h jusqu’au lundi 13 juin 9h. Pour en savoir plus
Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

The cut tool for QCSP

Abstract :

Quantified Constraint Satisfaction Problems (QCSP) are a generalization of Constraint Satisfaction Problems (CSP) in which variables may be quantified existentially and universally. QCSP offers a natural framework to express PSPACE problems as finite two-player games or planning under uncertainty. State-of-the-art QCSP solvers have an important drawback: they explore much larger combinatorial spaces than the natural search space of the original problem since they are unable to recognize that some sub-problems are necessarily true. We introduce a new tool, inspired by the cut rule of Prolog as a tool under responsibility of the designer of the QCSP, to prune those parts of the search space which are by construction known to be useless. We use this new tool to restore on one hand the annihilator property of true for disjunction in QCSP solver and, on the other hand, to prune the search space in two-player games. It is a simple solution to use efficiently QCSP to design finite two-player games without restricting the QCSP language. This tool does not need to modify the QCSP solver but has only one requirement: be able to tell the QCSP solver that the current QCSP is solved. Our QCSP solver built over Ge Code, a CSP library, obtained very good results compared to state-of-the-art QCSP solvers.

Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-03352570
Contributeur : Okina Univ Angers Connectez-vous pour contacter le contributeur
Soumis le : jeudi 23 septembre 2021 - 12:18:48
Dernière modification le : mercredi 20 octobre 2021 - 03:19:09

Identifiants

Collections

Citation

Vincent Barichard, Igor Stéphan. The cut tool for QCSP. 26th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'14), 2014, Limassol, Cyprus. pp.883-890, ⟨10.1109/ICTAI.2014.135⟩. ⟨hal-03352570⟩

Partager

Métriques

Consultations de la notice

8