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+.
Domaines
Intelligence artificielle [cs.AI]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...