De nombreuses tâches en intelligence artificielle, et plus généralement en informatique, nécessitent la résolution de problèmes difficiles d’un point de vue calculatoire.

L’axe « Contraintes » porte sur la modélisation et la résolution pratique de problèmes combinatoires sous contraintes. Deux formalismes sont principalement étudiés dans l’axe : SAT (Satisfiability Testing), où les variables sont booléennes et CSP (Constraint Satisfaction Problem) où les variables sont définies sur des domaines finis. Ces deux formalismes entrent dans le champ général de la programmation par contraintes (CP pour Constraint Programming). Parmi les problèmes étudiés figurent les problèmes de satisfaction (existence d’une solution), d’optimisation (recherche d’une « meilleure » solution), de comptage (calcul du nombre de solutions), d’énumération (des solutions). Les travaux réalisés dans l’axe vont de développements théoriques (étude de complexité, analyse de propriétés des langages et des algorithmes) jusqu’au développement de logiciels (appelés solveurs) permettant de résoudre en pratique les problèmes abordés.

Parmi les thèmes de recherche de l’axe « Contraintes », on trouve :

  • le développement de langages généraux de modélisation et des outils associés
  • la conception de mécanismes efficaces de parcours de l’espace de recherche
  • la conception de mécanismes d’inférences et d’apprentissages au sein de solveurs
  • la compilation en amont de problèmes combinatoires afin d’effectuer, a posteriori, de façon efficace, un ensemble de requêtes sur ces derniers.

Au sein de l’axe « Contraintes », le CRIL s’intéresse donc à différentes questions inter-corrélées qui vont de la représentation à la résolution de problèmes combinatoires. Des travaux portent sur l’extension de cadres existants et l’utilisation de techniques issues de SAT, CSP et de formalismes apparentés (pseudo-booléens, formules booléennes quantifiées) pour élargir les champs d’application. Par exemple, de nombreux outils développés dans l’axe sont utilisés pour traiter des problèmes fondamentaux pour l’IA explicable et robuste.

Le développement de solveurs open-source génériques et la résolution de problèmes réels (industriels) font également partie des activités conduites au sein de l’axe.

Rapport d’activités