COALA

COntraintes, ALgorithmes et Applications

Mots clés

Responsable

Philippe JEGOU

Membres permanents

Stephane Grandcolas Djamal Habet Laurent Henocque Philippe Jegou
Richard Ostrowski Cyril Pain-Barre Lionel Paris Nicolas Prcovic
Cyril Terrioux Laurent Oxusoff

Membres non permanents

Estelle Chauveau Nabil Adrar

Intérêts scientifiques

Dans la continuité des travaux développés au sein de l’équipe INCA, la nouvelle équipe COALA positionne son activité principalement dans l’algorithmique associée à la résolution des problèmes de satisfaction de contraintes (SAT et CSP principalement). Cette activité, historiquement liée aux fondements de l’Intelligence Articifielle, mais également à ceux de la Programmation par Contraintes, a pour objectif l’étude des systèmes à base de contraintes, la mise en évidence de fragments polynomiaux (classes polynomiales), l’élaboration de méthodes et d’algorithmes pour la résolution de problèmes combinatoires, et la conception de solveurs efficaces en pratique. Ces travaux, qui vont naturellement de pair avec une mise en application sur des problèmes réels, portent principalement sur la résolution du problème général de la satisfiabilité (SAT) et des problèmes de satisfaction de contraintes (au sens CSP à domaines finis et qui est une extension de SAT). Nous nous intéressons également à leurs extensions à l’optimisation, avec Max-SAT (qui consiste à maximiser le nombre de clauses satisfiables) d’une part, et les CSP Pondérés ou WCSP (pondération sur les contraintes) d’autre part, ainsi qu’aux questions de dénombrement (#SAT et #CSP). Afin de bien cerner la dfifficulté des problèmes abordés, il est essentiel de rappeler ici certains résultats de complexité : SAT et CSP sont NP complets, Max-SAT et WCSP NP-difficiles tandis que #SAT et #CSP sont #P-complets. À l’origine, cette activité avait pour objectif de doter les systèmes de raisonnement de l’Intelligence Artificielle d’outils de résolution efficaces à la fois en théorie et en pratique. Ils ont désormais des retombées bien au-delà dans de nombreux domaines d’applications, notamment par la place prépondérante prise depuis plusieurs années maintenant par la Programmation par Contraintes. Si le thème central des recherches développées ici concerne l’algorithmique des problèmes de satisfaction de contraintes, on peut cependant évoquer deux autres domaines abordés. D’une part la Théorie (Algorithmique) des Graphes dans la mesure où nos travaux s’appuient très souvent sur les propriétés graphiques associées à l’expression des CSP sous la forme de “réseaux de contraintes” (ce sont des (hyper)graphes étiquetés). D’autre part, la Théorie de la Complexité au niveau de la mise en évidence de nouvelles classes polynomiales, c’est-à-dire d’ensembles infinis d’instances dont la reconnaissance et la résolution admettent des algorithmes de complexité polynomiale.

Nos travaux se déclinent ainsi en plusieurs axes et activités et qui constituent les thèmes de recherches qui seront abordés lors du prochain contrat :
– Classes polynomiales et méthodes de résolution pour CSP, WCSP et #CSP
– Méthodes complètes et incomplètes pour SAT et ses extensions à l’optimisation
– Problèmes connexes et applications
– Conception de Solveurs

L’équipe coordonne le projet ANR Demograph (Décomposition de Modèles Graphiques : http://www.lsis.org/demograph/ qui a débuté en 2017 pour une durée de 4 ans. Enfin, pour mieux appréhender nos axes de recherche, il est utile de préciser que nous avons publié ces dernières années (depuis 2015) dans des journaux tels que Artificial Intelligence, Constraints, Annals of Mathematics and Artificial Intelligence et JSAT, ainsi que dans des conférences telles que IJCAI, AAAI, CP et ECAI.

Voir aussi dans «Calcul»

ACRO CANA DALGO
Tutelles