Au delà des QCSP pour résoudre des problèmes de contrôle

Résumé : Les problèmes de satisfaction de contraintes quantifiés (QCSP) sont souvent présent és comme les outils adéquats permettant de mod éliser et de résoudre des problèmes de jeu à deux joueurs ou de planification dans l'incertain ou plus généralement des problèmes o u l'objectif est de contrôler un système dynamique soumis à des événements incontrôlés. Ce papier montre que, pour de nombreux probl èmes de ce type, l'approche standard de type QCSP ou QCSP+ n'est pas la plus appropriée. Les raisons principales en sont que, dans le cadre QCSP/QCSP+, (1) les évolutions possibles du syst ème sont d épli ées sur un nombre fixé d' étapes, (2) la notion d'état du système n'est pas explicitement prise en compte et (3) les algorithmes recherchent des stratégies gagnantes à mémoire complète définies comme des arbres de politique plutôt que des stratégies sans mémoire définies comme des fonctions depuis les états vers les décisions. Ce papier propose un nouveau cadre à base de contraintes qui n'a pas ces défauts. Les expérimentations montrent des améliorations de plusieurs ordres de grandeur par rapport a des solveurs de QCSP/QCSP+.
Type de document :
Communication dans un congrès
Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00829639
Contributeur : Ist Inria Saclay <>
Soumis le : lundi 3 juin 2013 - 15:48:00
Dernière modification le : mercredi 28 mars 2018 - 14:06:01
Document(s) archivé(s) le : mardi 4 avril 2017 - 15:42:18

Fichier

paper_34.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00829639, version 1

Collections

Citation

Cédric Pralet, Gérard Verfaillie. Au delà des QCSP pour résoudre des problèmes de contrôle. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00829639〉

Partager

Métriques

Consultations de la notice

51

Téléchargements de fichiers

71