• Sylvain Merchez
    • PhD defended on :
    • Dec 15, 2000

    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.