Contraintes quantifiées : satisfaction et optimisation
Jérémie Vautard (GREYC)Les problèmes de satisfaction de contraintes quantifiées (QCSP) sont une extension des problèmes de satisfaction de contraintes dans laquelle certaines des variables peuvent être quantifiées universellement. Un tel formalisme permet de représenter de manière compacte des jeux à deux joueurs (“Existe-t- il un coup tel que pour tout coup de mon adversaire, il existe un coup tel que pour tout coup de mon adversaire ….. tel que je gagne ?”) ou, plus généralement, toute une classe de problème dans lesquels certains paramètres ne sont pas contrôlables (par exemple, la réalisation d’un projet en présence d’un ennemi ayant pour objectif de l’empêcher). Après avoir présenté les limitations du formalisme “classique” des QCSP, j’exposerai mes travaux sur deux extensions de ce cadre : d’une part, les QCSP+, permettant de modéliser aisément des problèmes non-triviaux ; et d’autre part la version “optimisation” de ces problèmes : les QCOP+, permettant de représenter et de résoudre des problèmes d’optimisation multi-niveaux non-linéaires. Enfin, je présenterai plusieurs pistes pour des travaux futurs.