EMERGENCE INS2I BAUTOM

Bandits as an AUTOnomous Machine (BAUTOM)

La programmation par contraintes a développé un large éventail de méthodes efficaces et polyvalentes pour résoudre de nombreux problèmes du monde réel à grande échelle, pouvant être exprimés et résolus comme des problèmes de satisfaction de contraintes (CSP). Les domaines qui bénéficient de cette technologie sont le transport, la gestion des réseaux, les télécommunications, la bioinformatique et la finance [1]. Par conséquent, des organisations et des industries du monde entier exploitent déjà la programmation par contrainte pour résoudre des problèmes difficiles de conception et de configuration, de planification et d’ordonnancement, de raisonnement temporel et spatial, etc. Toutefois, la programmation par contraintes(CP) souffre d’un goulot d’étranglement qui limite son utilisation : la nécessité d’un expert en programmation par contraintes de régler le solveur de manière à ce qu’il devienne plus efficace pour le problème en question. Actuellement, un expert en contraintes doit choisir parmi diverses techniques de résolution et les affiner pour construire un programme efficace. Cette proposition vise à faciliter le travail d’un expert avec l’apprentissage automatique(ML). L’apprentissage par renforcement sera utilisé pour changer et adapter les configurations possibles du solveur, dynamiquement pendant la recherche. Jusqu’à présent, les solveurs sont utilisés comme des boîtes noires (sauf pour les experts), où un utilisateur ne peut pas intervenir ou comprendre. Grâce à l’utilisation de l’apprentissage, plusieurs explications du comportement et du fonctionnement du solveur seront extraites et ainsi expliquées. L’automatisation de la configuration du solveur a fait l’objet d’une grande attention, car elle peut dispenser l’utilisateur de choisir la configuration appropriée pour résoudre son problème. Il existe plusieurs approches différentes qui utilisent des méthodes d’apprentissage machine (ML) dans la résolution adaptative des contraintes ( voir [2, 3]). Deux approches principales ont été étudiées. Dans le premier cas, une stratégie spécifique (par exemple, un algorithme de recherche ou un solveur spécifique) est sélectionnée automatiquement parmi un ensemble de stratégies disponibles, soit pour une classe entière de problèmes, soit pour une instance spécifique. De telles méthodes, appelées portfolios, ont été principalement proposées pour SAT (par exemple, SATzilla [4]) et, dans une moindre mesure, pour les CSP (par exemple, CPHydra [5]). Dans le second cas, l’utilisation du ML permet de synthétiser une nouvelle stratégie (par exemple, une combinaison d’algorithme de recherche et d’heuristique) [3]. De telles tentatives se sont principalement concentrées sur l’apprentissage de stratégies de combinaison d’heuristiques, résultant par exemple de nouvelles heuristiques hybrides d’ordonnancement de variables. Dans [6], Xu et al. ont proposé l’utilisation de l’apprentissage par renforcement pour la sélection dynamique d’une heuristique d’ordre variable à chaque point de la recherche CSP. Un autre travail récent utilise ML pour décider avant la recherche si l’apprentissage paresseux sera activé ou désactivé [7]. Une technique d’apprentissage par renforcement, appelée bandits à bras multiples (MAB), a été initialement proposée pour modéliser les problèmes d’allocation de ressources, où, étant donné un budget fixe, l’objectif est d’allouer des ressources entre des tâches/projets, dont les résultats/récompenses sont inconnus ou partiellement connus au moment de l’allocation [8]. Le problème nécessite de trouver un équilibre entre la maximisation de la récompense totale basée sur les connaissances acquises et l’essai de nouvelles actions pour accroître davantage les connaissances, appelé compromis entre exploitation et exploration dans l’apprentissage par renforcement. La prise de décisions séquentielles dans la recherche CP, tout en maximisant les performances du solveur, peut être représentée comme un problème MAB. Récemment, les bandits à bras multiples(MAB) ont été utilisés pour apprendre les bonnes heuristiques d’ordre de variables et de valeurs pendant la résolution CSP [9,10].

Ce projet de recherche vise à proposer des techniques pour améliorer et automatiser la résolution de contraintes en fournissant un cadre autonome qui dirigera la recherche par l’utilisation de bandits. Plus précisément, le solveur apprendra pendant la recherche quelle méthode de branchement utiliser ou avec quel critère se brancher, devenant ainsi plus robuste que de choisir une configuration fixe tout au long de la recherche. En même temps, le mécanisme d’apprentissage lui-même nous donnera un retour sur les opérations internes et le comportement du solveur, ce qui nous aidera à expliquer et à comprendre les mécanismes de la boîte noire du solveur.

Références

[1] M. Wallace. Practical applications of constraint programming. Constraints, 1:139–168, 1996.

[2] S. Minton. Automatically Configuring Constraint Satisfaction Programs: A Case Study. Constraints, 1(1/2):7–43, 1996.

[3] S. Epstein, S. Petrovic. Learning to Solve Constraint Problems. In ICAPS’07 Workshop on Planning and Learning, 2007

[4] L. Xu, F. Hutter, H. H. Hoos, K. Leyton-Brown. Satzilla: Portfolio-based algorithm selection for SAT. J. Artif. Intell. Res. (JAIR), 32:565–606, 2008.

[5] E. O’Mahony, E. Hebrard, A. Holland, C. Nugent, B. OSullivan. Using case-based reasoning in an algorithm portfolio for constraint solving. In Proc. of AICS’08, 2008.

[6] Y. Xu, D. Stern, H. Samulowitz. Learning Adaptation to solve Constraint Satisfaction Problems. In Proc.of LION’09, 2009.

[7]I.P. Gent, C. Jefferson, L. Kotthoff, I. Miguel, N.C.A. Moore, P. Nightingale, K.E. Petrie. Learning when to use lazy learning in constraint solving. In Proc. of ECAI’10, pages 873–878, 2010.

[8] J. C. Gittins. Multi-Armed Bandit Allocation Indices, volume 10. John Wiley and Sons, 1989.

[9] M. Loth, M. Sebag, Y. Hamadi, M. Schoenauer. Bandit-based search for constraint programming. In Proc. of CP’13, pages 464–480, 2013.

[10] A. Balafrej and C. Bessiere and A. Paparrizou, Multi-Armed Bandits for Adaptive Constraint Propagation. In proc of IJCAI’15, pages 290- 296, 2015.

[11] W. Xia and R. H. C. Yap, Learning Robust Search Strategies Using a Bandit-Based Approach. In Proc. of AAAI’18, pages 6657-6665, 2018.