• Thèse soutenue le :
  • 2010-12-03

Vendredi 3 décembre 2010, 14h30, salle des thèses de la faculté Jean-Perrin

Résumé

La modélisation et la résolution de problèmes sous contraintes constituent un domaine majeur en IA. Par la nature diverse des contraintes, différents formalismes de représentation ont été proposés pour les exprimer de manière simple et compacte tout en garantissant une efficacité des outils de résolutions associés. Les formules propositionnelles, les réseaux de contraintes discrets (RCD) et qualitatives (RCQ) sont des cadres de modélisation répondant à ces critères. Pour les informations temporelles ou spatiales, les RCQ constituent un modèle de choix avec de nombreuses applications comme l’ordonnancement de tâches, la planification temporelle ou spatiale, les systèmes d’informations géographiques.

Nos contributions visent à étudier les liens des RCQ vers les RCD et les formules propositionnelles, afin d’adapter les outils issus des divers domaines et de proposer de nouvelles approches. Tout d’abord, nous nous concentrons sur l’aspect structurel des RCQ, en adaptant la méthode de la composition faible dans les différents cadres. Nous exploitons ensuite les propriétés des classes traitables de certains formalismes qualitatifs, afin de définir une transformation vers la logique propositionnelle. En exploitant la transformation vers les RCD, nous proposons une méthode incomplète facilitant la preuve de l’incohérence des RCQ par la relaxation de la propriété de composition faible, puis nous complétons l’approche en exploitant les classes traitables. Enfin, ces études nous conduisent à proposer une nouvelle forme de substituabilité locale, dont les détections statique et dynamique permettent d’obtenir une amélioration algorithmique dans le cadre des RCD.

Mots-clés : Intelligence Artificielle, problème CSP, problème SAT, Raisonnement Qualitatif, Transformation, Classes traitables, Relaxation, Substituabilité.

Composition du jury

  • Belaïd Benhamou, Maître de conférence HDR, LSIS - Université Aix-Marseille, Rapporteur
  • Maroua Bouzid, Professeur des universités, GREYC - Université de Caen Basse-Normandie, Rapporteur<
  • Pierre Marquis, Professeur des universités, CRIL - Université d’Artois, Examinateur
  • Frédéric Saubion, Professeur des universités, LERIA - Université d’Angers, Examinateur
  • Christine Solnon, Maître de conférence HDR, LIRIS - Université Lyon 1, Examinateur
  • Jean-François Condotta, maître de conférence, CRIL - Université d’Artois, Co-directeur de thèse
  • Christophe Lecoutre, Professeur des universités, CRIL - Université d’Artois, Co-directeur de thèse
  • Lakhdar Saïs, Professeur des universités, CRIL - Université d’Artois, Directeur de thèse