Description

Ce sujet se site à l’intersection de deux domaines importants de l’intelligence artificielle :

— la programmation par contraintes,

— l’apprentissage par renforcement.

De nos jours, la programmation par contraintes est devenue une technologie incontournable pour résoudre une grande variété de problèmes combinatoires, couvrant non seulement le problème de satisfaction de contraintes (CSP) mais aussi des problèmes plus complexes, intégrant l’optimisation et la prise de décision séquentielle sous contraintes. En programmation par contraintes, un problème est généralement résolu en utilisant deux idées principales : trouver une heuristique pour explorer l’espace combinatoire (c’est la partie ”recherche”) et trouver une méthode de filtrage permettant d’éliminer rapidement un grand nombre de valeurs impossibles ou sous-optimales (c’est la partie ”inférence). Avec les progrès considérables réalisés en programmation par contraintes, il existe aujourd’hui un grand nombre d’heuristiques [2] et de méthodes de filtrage [3, 6]. On pourra citer les heuristiques basées sur la pondération de contraintes, l’activité, l’impact ou les derniers conflits, et les méthodes de filtrage basées sur des propriétés (appelées cohérences locales) telles que la cohérence d’arc, l’inter-cohérence, ou la cohérence de chemin restreinte. Les solveurs modernes, tels qu’AbsCon ou Choco, contiennent des bibliothèques entières d’heuristiques et de méthodes de filtrage. Malheureusement, même si la modélisation d’un problème combinatoire reste une tâche relativement acces- sible à la plupart des utilisateurs, la résolution du problème faisant appel au choix judicieux d’heuristiques et de cohérences efficaces, relève aujourd’hui des experts en programmation par contraintes.

Dans la perspective de construire des solveurs autonomes, l’objectif du sujet est d’exploiter l’apprentissage par renforcement pour choisir automatiquement les heuristiques et cohérences appropriées pour un problème donné. De manière générale, la résolution autonome peut être vue comme un problème de bandits multi-bras (MAB) [7] : à chaque étape de la résolution, le solveur doit choisir la bonne décision (heuristique et cohérence), dont la performance peut être mesurée selon divers critères (ex : taille du sous-arbre exploré). Il existe aujourd’hui une grande variété d’algorithmes de bandits multi-bras, qui dépendent de la nature du problème de décision (”stochastique” ou ”adversariel”), de l’espace de décisions possibles (simple ou combinatoire), et du renforcement transmis à l’algorithme (semi-bandit ou bandit) [4]. La vitesse de convergence et la complexité temporelle d’un algorithme MAB dépendent naturellement du problème de décision sous-jacent.

Il a été démontré à IJCAI 2015 [1] que l’utilisation des bandits multi-bras stochastiques (en particulier l’algorithme standard UCB) pour le choix de méthodes de filtrage, a permis d’accélérer la résolution de nombreuses instances du problème de satisfaction de contraintes. Le but de cette thèse est d’explorer plus en avant l’intersection entre la résolution par contraintes et les bandits multi-bras. Nous étudierons plusieurs classes de problèmes (satisfaction, optimisation, décision séquentielle et jeux [5]) ainsi que plusieurs classes d’algorithmes de semi-bandits ou bandits (stochastiques ou adversariaux, simples ou combinatoires) pour apprendre à choisir de manière autonome les bonnes heuristiques et cohérences. La thèse comprend à la fois une partie théorique (analyse de convergence et complexité des bandits en résolution par contraintes) et une partie expérimentale (avec le solveur AbsCon).

Encadrement

— Frederic Koriche, professeur en informatique, dont le domaine de spécialité est l’apprentissage dans les modèles graphiques. Frederic Koriche est co-auteur d’un solveur de jeux à base de contraintes et de bandits (Woodstock) qui est aujourd’hui un des systèmes les plus performants en GGP (General Game Playing).

— Christophe Lecoutre, professeur en informatique, dont le domaine de spécialité est la programmation par contraintes. Christophe Lecoutre est auteur d’un livre ’Constraints Networks ; Techniques and Algorithms” édité chez Wiley, et développeur du solveur de contraintes ”AbsCon”.

— Anastasia Paparrizou, chercheure de recherche au CNRS, dont le domaine de spécialité est la programmation par contraintes. Anastasia Paparrizou est lauréate du prix de thèse ECCAI 2013 et du prix de thèse ACP (Association for Constraint Programming) 2015.

Références

[1] A. Balafrej and C. Bessière and A. Paparrizou, “Multi-Armed Bandits for Adaptive Constraint Propagation,” In International Joint Conference on Artificial Intelligence (IJCAI), pages 290- 296, 2015.

[2] F. Boussemart and F. Hemery and C. Lecoutre and L. Sais, “Boosting Systematic Search by Weighting Constraints,” In European Conference on Artificial Intelligence (ECAI), pages 146- 150, 2004.

[3] C. Bessiere and K. Stergiou and T. Walsh, “Domain filtering consistencies for non-binary constraints,” Artificial Intelligence 172(6-7), pages 800-822, 2008.

[4] S. Bubeck and N. Cesa-Bianchi, “Regret analysis of stochastic and nonstochastic multi-armed bandit problems,” Foundations and Trends in Machine Learning, vol 5(1), pages 1-122, 2012.

[5] F. Koriche and S. Lagrue and É. Piette and S. Tabary, “Constraint-Based Symmetry Detection in General Game Playing,” In International Joint Conference on Artificial Intelligence (IJCAI), pages 280-287, 2017.

[6] C. Lecoutre and C. Likitvivatanavong and R. Yap, “STR3 : A path-optimal filtering algorithm for table constraints,” Artificial Intelligence 220, pages 1-27, 2015.

[7] M. Loth and M. Sebag and Y. Hamadi and M. Schoenauer, “Bandit-based search for constraint programming,” In Principles and Practice of Constraint Programming (CP), pages 464–480, 2013.