Titre

Problèmes de satisfaction de contraintes : étude de mécanismes d'abstraction et de construction de hiérarchies

Soutenue le 15 Décembre 2000

Jury

Président	Michel Cayrol	Professeur à l'Université Paul Sabatier de Toulouse
Rapporteurs	Marie-Catherine Vilarem	Professeur à l'Université de Montpellier II
	Gérard Ferrand	Professeur à l'Université d'Orléans
Examinateurs	Frédéric Boussemart	Maîtres de Conférences à l'Université d'Artois
	Jean-Jacques Chabrier	Professeur à l'Université de Bourgogne
	Eric Grégoire	Professeur à l'Université d'Artois
	Gilles Goncalves	Professeur à l'Université d'Artois
	Christophe Lecoutre	Maitres de Conférences à l'Unuversité d'Artois
	Pierre Marquis	Professeur à l'Université d'Artois

Résumé

De nombreux problèmes issus de l'Intelligence Artificielle et de la Recherche Opérationnelle peuvent s'exprimer naturellement sous forme de contraintes. Cette thèse est une étude de deux aspects importants concernant les problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem).

Dans une première partie, nous nous sommes intéressés à la définition d'un cadre formel permettant de construire des abstractions de CSPs. Notre principal objectif a été de rendre aussi générale que possible notre proposition. Cela se traduit par la possibilité d'intégrer aussi bien les formes classiques d'abstraction de CSPs (introduites dans la littérature), que des formes originales identifiées dans cette thèse. Ces dernières correspondent à la notion de regroupement dit général de valeurs et de variables. L'origine de la généralité du cadre est liée à l'utilisation de relations d'approximation comme liens d'abstraction. Afin de prouver expérimentalement l'intérêt des formes originales d'abstraction, nous avons développé le prototype AbsCon.

Dans une seconde partie, nous nous sommes intéressés à la modélisation de CSPs prenant en compte des préférences (ou priorités). Nous proposons à cet effet un modèle de hiérarchie " flexible " qui permet d'évaluer et de classer l'ensemble des instanciations possibles (ou solutions potentielles). Nous calculons une évaluation globale qui intègre pour chaque niveau de la hiérarchie un degré de satisfaction et un degré de tolérance. Le degré de tolérance d'un niveau permet de prendre plus ou moins en compte les niveaux suivants de la hiérarchie. Le modèle que nous proposons est directement construit à partir de l'expression des contraintes, ce qui le rend naturellement déclaratif. Nous illustrons notre approche à l'aide d'une application réelle : la détermination du profil de réseaux d'assainissement.

Mots-Clés

Problèmes de satisfaction de contraintes, abstraction, relation d'approximation, hiérarchies floues, contraintes floues.

Applications

Suite à de nouvelles directives européennes, les collectivités locales doivent en effet s'organiser pour connaître leur réseau d'assainissement et effectuer les travaux éventuels de mise en conformité. En général, la structure du réseau est disponible alors que les cotes radiers (profondeurs) des différentes jonctions ne le sont pas. Les bureaux d'études effectuent alors la plupart du temps un relevé partiel des cotes radiers du réseau et calculent les données manquantes par interpolation linéaire.

A partir de données connues, de contraintes de construction et de critères empiriques, nous proposons de créer une image plus précise du réseau réel. Pour cela, nous procédons en trois étapes : nous fixons tout d'abord le domaine des variables du problème en utilisant des techniques de propagation d'intervalles. Puis, nous construisons une hiérarchie floue. Pour finir, nous utilisons les algorithmes génétiques pour parcourir l'espace de recherche du problème et extraire ainsi une solution dite "optimale", c'est à dire une solution qui sera la plus proche possible du réseau réel en terme de comportement hydraulique lors de simulations.