Autonomous Constraint Solvers
Solveurs de Contraintes Autonomes
Résumé
Constraint programming is declarative: the user models the problem (in the form of constraints) without worrying about the solving part. The solving is delegated to a generic program called a constraint solver.
Constraint solvers use mechanisms from artificial intelligence to guide its choices (heuristics), and to efficiently reduce the search space (inference). Recent constraint solvers are equipped with several heuristics. Choosing the best heuristic to solve a given problem instance is currently delegated to the user.
The goal of this thesis is to make constraint solvers more autonomous. We want to remove any cognitive burden from the user regarding the solving process. While searching for solutions, the solver often restarts the search to avoid expensive dead-ends. We propose to automatically select the most promising heuristic after each restart.
In response to this sequential choice problem, we take inspiration from policies addressing the multi-armed bandit problem. Such policies are derived from reinforcement learning and allow to explore a set of actions while exploiting the most profitable one as often as possible.
After having defined how to incorporate this machine learning tool in a solver, we propose several applications to make modern constraint solvers more autonomous. First, we apply the policies proposed in the multi-armed-bandits literature to learn the best heuristic among a set of heuristics provided by the solver. Based on this first application, we propose a new policy that is more consistent with the structure of current solvers. Still using bandit policies, we propose to adapt the amount of randomization needed to perturb a given heuristic and make it more efficient. Finally, we extend these results to constraint optimization solvers.
La programmation par contraintes est déclarative : l'utilisateur modélise le problème (sous forme de contraintes) sans se soucier de la partie résolution. La résolution est déléguée à un programme générique appelé solveur de contraintes.
Les solveurs de contraintes utilisent des mécanismes issus de l'intelligence artificielle pour guider ses choix (heuristiques), et pour réduire efficacement l'espace de recherche (inférence). Les solveurs de contraintes récents sont équipés de plusieurs heuristiques. Le choix de la meilleure heuristique pour résoudre une instance de problème donnée est actuellement délégué à l'utilisateur.
L'objectif de cette thèse est de rendre les solveurs de contraintes plus autonomes. Nous voulons enlever toute charge cognitive à l'utilisateur concernant le processus de résolution. Pendant la recherche de solutions, le solveur redémarre régulièrement la recherche pour éviter les impasses coûteuses. Nous proposons de sélectionner automatiquement l'heuristique la plus prometteuse après chaque redémarrage.
En réponse à ce problème de choix séquentiel, nous nous inspirons des politiques traitant du problème du bandit multi-bras. De telles politiques sont issues de l'apprentissage par renforcement et permettent d'explorer un ensemble d'actions tout en exploitant, le plus souvent possible, l'action la plus prometteuse.
Après avoir défini comment incorporer cet outil d'apprentissage automatique dans un solveur, nous proposons plusieurs applications pour rendre les solveurs de contraintes modernes plus autonomes. Premièrement, nous appliquons les politiques proposées dans la littérature sur les bandits multi-bras pour apprendre la meilleure heuristique parmi un ensemble d'heuristiques fournies par le solveur. Sur la base de cette première application, nous proposons une nouvelle politique qui est plus cohérente avec la structure des solveurs actuels. Toujours en utilisant des politiques de bandit, nous proposons d'adapter la quantité d'aléa nécessaire pour perturber une heuristique donnée et la rendre plus efficace. Enfin, nous étendons ces résultats aux solveurs de contraintes sous optimisation.
Origine : Fichiers produits par l'(les) auteur(s)