Mon sujet de thèse
 

Directeur :      Pr Eric Gregoire (CRIL)

Responsable :  Dr Christophe Lecoutre (CRIL)

Titre :                Vers l'introduction de la flexibilité dans les CSPs.

Pour en savoir plus sur :

 L'équipe "Contraintes"

 

Composition :

Collaborations  :

  Le Sujet

Titre : Contribution à la repréentation et à la résolution de problèmes de satisfaction de contraintes..

Résumé :

La première partie de la thèse permet de traiter les problèmes de satisfaction de contraintes pour faciliter leur résolution. Avant de chercher à résoudre ce genre de problèmes, il est intéressant de tirer un maximum d'informations pour le simplifier et ainsi aider la résolution. Une première méthode consiste à réduire les domaines de définitions des variables : nous nous sommes intéressés aux contraintes à différences (et à somme) bornées définies sur des intervalles et nous montrons comment réduire les domaines à l'aide d'un algorithme de filtrage basé sur le calcul de plus courts chemins à destination inconnue. Une deuxième méthode est basé sur l'abstraction : les domaines et les contraintes deviennent abstraits, le problème défini est plus simple et permet de déduire la semi-décidabilité et certaines informations sur la famille de solutions.
Dans la deuxième partie de la thèse, nous étudions les problèmes de satisfaction et d'optimisation, c'est à dire les problèmes portant à la fois sur la satisfaction de contraintes et sur l'optimisation de critères. Nous définissons un cadre formel "hiérarchie floue" permettant de représenter et résoudre ce type de problèmes.  L'aspect hiérarchique permet d'établir les différentes priorités entre critères et contraintes. L'aspect floue permet de relâcher certains éléments du problème, comme les contraintes ou même l'aspect hiérarchique. Nous avons défini une méthode déclarative afin de fixer les différents paramètres de la hiérarchie floue. L'utilsateur doit simplement exprimer les différentes priorités et fixer quelques bornes pour chaque contrainte ou critère.
Enfin, nous appliquons tout d'abord la réduction d'intervalles puis la résolution à l'aide d'une hiérarchie floue à un problème particulier réel : la détermination du profil de réseaux d'assainissement.

Actuellement, nous souhaitons comparer la hiérarchie floue à d'autres cadres existants ainsi que fixer intégralement la méthode déclarative. Dans un deuxième temps, nous aimerions traiter une deuxième application qui puisse mettre en oeuvre le mécanisme d'abstraction défini comme l'ordonnancement.

Les applications

Détermination du profil de réseaux d'assainissement

 

 
 
 

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.

Une extension possible de cette application est de concevoir le réseau d'assainissement. Il suffit de donner quelques points de jonctions obligatoires et le système calcule une solution qui "respecte" les contraintes et les critères.
 

Autres applications


 Bibliographie

La notre :

 
Eufit'98 "A flexible approach to determine the profile of urban drainage networks" 
HydroInformatics'98 "Genetic algorithms to determine urban drainage networks"
JNPC'98 "Une approche souple pour résoudre des problèmes réels. Application à la détermination de profils de réseaux d'assainissement"
NTIC'98 "Une méthode déclarative pour déterminer le profil de réseaux d'assainissements"
ICUSD'99 "Comparison of interpolation methods to approximate the profile of urban drainage networks" 
CP'99 workshop on Soft Constraints "Fuzzy Hierarchies" 
RFIA'2000 "Un cadre d'abstration appliqué aux problèmes de satiasfaction de contraintes"

Les autres :

 
Bistarelli 97  Semiring Constraint Satisfaction Problems 
Borning Benson ... 92 Constraint Hierarchies
Caseau 91 Abstract interpretation of constraints on order-sorted domains
Davis 87 Constraint propagation with interval label.
Dechter 91 From local to global consistency
Ellman 93 Abstraction via approximate symetry
Fargier 94 Problèmes de satisfaction de contraintes flexibles : application à l'ordonnancement de production.
Freuder Wallace 92 Preference Logic Programming
Lhomme 94 Contribution à la résolution de contraintes sur les réels par propagation de contraintes. PhD Thesis.
Marriott 93 Frameworks for abstract interpretaion
Schiex Fargier ...  95 Valued Satisfaction Problem 
Yager 88 On ordered weighted averaging aggregation operators in multicriteria decisionmaking.
Zadeh L. 65. Fuzzy sets.

 Liens

 

 
 
 
 
 
 


22/12/1999© Sylvain Merchez