GT RAP

Représentations et Algorithmes en Pratique

Activités du GT

Responsables

Description

Les progrès réalisés dans le cadre de la résolution pratique de problèmes NP-complets (tels que SAT ou CSP) permettent d’envisager la modélisation et la résolution de problèmes calculatoirement plus difficiles (FP, PSPACE, #P, …). Ainsi, des problèmes tels que la fusion ou la révision de croyances (FP), l’inférence probabiliste (#P) ou encore les jeux à deux joueurs (PSPACE) peuvent maintenant être modélisés et traités de manière empirique. Des problèmes considérés comme intraitables au niveau expérimental il y a à peine une dizaine d’années sont ainsi aujourd’hui largement accessibles. C’est dans ce contexte que ce groupe de travail s’inscrit. L’objectif principal est de proposer des représentations adaptées et des solutions algorithmiques à des problèmes d’intelligence artificielle. La production de programme pour la résolution d’applications réelles peut, de fait, améliorer la visibilité de recherches qui sont pour la plupart étudiées uniquement de manière théorique (il suffit d’observer la popularité de l’apprentissage pour se rendre compte de l’intérêt d’une telle démarche). Cela peut aussi conduire à un cercle vertueux. En effet, la prise en compte en pratique de nouveaux problèmes d’inférence ou de prise de décision peut bénéficier aux communautés produisant des encodages ou des solveurs (en faisant office de nouveaux défis). Et réciproquement, la résolution pratique de tels problèmes peut conduire à focaliser des recherches à visée théorique sur des points d’intérêt originaux et susciter de nouveaux questionnements.

 

Les principaux objectifs considérés dans ce groupe de travail sont les suivants :

  1. Identifier les problèmes pratiques d’inférence et de prise de décision qui peuvent être maintenant traités grâce à des techniques d’intelligence artificielle, les modéliser et déterminer des représentations adaptées 
  2. Développer des algorithmes pour les résoudre
  3. Proposer des protocoles expérimentaux permettant de comparer finement les algorithmes existants 
  4. Étudier les passerelles permettant de partager des informations entre des modèles ainsi qu’entre des solveurs s’appuyant sur des langages de représentation différents

 

1) De la théorie à la pratique

De nombreux travaux réalisés dans le cadre de l’intelligence artificielle ont consisté essentiellement en des développements de nature théorique. Par exemple, considérons la problématique de la révision de croyances. Bien que les avancées réalisées dans le cadre de la résolution pratique de SAT permettent d’envisager la réalisation de solveurs permettant d’implanter de nombreux opérateurs de révision, il existe peu de travaux identifiés dans la littérature décrivant une étude expérimentale approfondie. Ce manque d’expérimentations n’est pas le résultat d’un manque d’intérêt pour cela, mais résulte d’un déficit en applications concrètes. Cette situation peut paraître étrange étant donné que la problématique de la révision de croyances est très naturelle. Pour autant, la plupart des chercheurs travaillant sur ce sujet ont une faible connaissance de ce qui est possible de modéliser et surtout de résoudre aujourd’hui.

  

Ainsi, dans le cadre de ce groupe de travail nous souhaitons augmenter les interactions entre les différentes communautés afin de modéliser, représenter et résoudre en pratique de nouveaux problèmes au delà de NP.

 

2) Développement d’algorithmes

Le développement et l’évaluation d’algorithmes dédiés à la réalisation de tâches complexes d’inférence et de prise de décision sera au cœur des activités du groupe. Comme les tâches visées ont une complexité au delà de NP, le recours à des oracles SAT (implantés sous forme de solveurs) est naturel et permettra une modularité importante. En particulier, les différents outils logiciels qui seront produits par le groupe seront intégrés sous forme de bibliothèques et mis en ligne via un site dédié aux travaux du groupe. Pour ceux pour lesquels cela aura du sens, une diffusion sur des sites communautaires visibles au niveau international (tel beyondnp.org) sera réalisée. Sur le fond, dans la droite ligne des travaux actuels sur “incremental SAT”, il s’agira de capitaliser autant que possible les informations obtenues à chaque appel du solveur utilisé pour améliorer l’efficacité de la résolution globale du problème traité.

 

3) Comment mener à bien ses expérimentations

Réaliser une “bonne expérimentation” n’est pas un problème facile. Par exemple, bien qu’il y ait depuis de nombreuses années des compétitions permettant de comparer expérimentalement des solveurs SAT, il y a de façon récurrente de nombreuses discussions au sein du comité de programme de la conférence (SAT, Pseudo-Booléen, CSP, …)  au sujet de la façon de réaliser les expérimentations de façon correcte. Ainsi, même pour des domaines de recherche tel que SAT ou CSP, où il y a pléthore de problèmes modélisés, évaluer correctement une méthode reste une tâche complexe. Cela montre l’importance de définir des protocoles expérimentaux précis permettant de comparer finement les algorithmes proposés. Ce point est encore plus important pour des applications issues de l’intelligence artificielle où les requêtes ne se réduisent pas uniquement à un test NP/coNP.

 

Ainsi, sur le modèle de ce qui a déjà été réalisé dans le cadre de du projet ANR BRCP (https://www.irit.fr/~Helene.Fargier/BR4CP/benches.html), nous avons comme premier objectif de proposer des jeux d’essai, des requêtes et plus généralement des protocoles qui formaliseront les plans d’expérience à conduire.

 

4) Du partage d’informations entre représentations et solveurs hétérogènes

Aussi puissant que peut être un solveur, si la modélisation du problème traité et la représentation des données d’entrée n’est pas bonne, alors la résolution ne sera pas efficace. De plus, certains solveurs très efficaces sont peu utilisés car la représentation qu’ils prennent en entrée est difficile à construire. L’idée est donc de proposer aux utilisateurs de représenter les données d’entrée de manière simple et intuitive dans le langage le plus approprié. Ensuite, cette représentation sera encodée automatiquement en une autre représentation adaptée aux solveurs devant être testés. Le partage d’informations peut donc se faire à différents niveaux :

– entre les représentations (informations apprises via des calculs de cohérences, réduction de domaines, …) ;

– entre les solveurs (solutions partielles, nogoods, …).

 

Nous pouvons imaginer des transformations de représentations successives réduisant le problème jusqu’à obtenir un point fixe. Ensuite, différents solveurs peuvent être appliqués de manière séquentielle ou parallèle afin de partager des informations et ainsi accélérer la recherche.

 

Liste des thématiques concernées :

  • RCR. Représentation des connaissances et modélisation des raisonnements
  • PPC. Contraintes et SAT
  • SMA. Systèmes multi-agents et décision collective
  • IMG. Incertitude, modèles graphiques, réseaux Bayésiens