• Doctorant:
  • Hugues Wattez
  • Financement : Artois, Région HdF
  • Thèse soutenue le :
  • 9 déc. 2021

Description

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.

Jury

  • Directeurs
    • Frédéric Koriche, Université d’Artois, Lens
    • Christophe Lecoutre, Université d’Artois, Lens
  • Encadrante
    • Anastasia Paparrizou, CNRS, Lens
  • Présidente
    • Marie-José Huguet, INSA, Toulouse
  • Rapporteurs
    • Thomas Schiex, INRAE, MIA, Toulouse
    • Cyril Terrioux, Université d’Aix-Marseille
  • Examinateur
    • Rémy Bardenet, Université de Lille
  • Invités
    • Sébastien Tabary, Université d’Artois, Lens
    • Sonia Vanier, LIX, Université Paris1