Approches complètes pour la résolution des problèmes DisCSPs et DCOPs

Abstract

Notre travail de recherche s’articule autour de l’´etude de la technologie contrainte à laquelle nous avons apport´e plusieurs contributions. Dans un premier temps, nous avons étudié le formalisme des Problèmes de Satisfaction de Contraintes Distribués (DisCSP) par la suite nous avons développé plusieurs algorithmes `a aspect différent. Dans un deuxième temps, nous nous sommes intéressés aux Problèmes d’Optimisation de Contraintes Distribuées (DCOP) dans le but de proposer des techniques originales. Les travaux que nous avons apport´e dans cette thèse peuvent se résumer comme suit. D’une part nous avons propos´e trois contributions dans le cadre des DisCSPs. ¶ AFC-ng (based-nogood Asynchronous Forward-Checking) : C’est un algorithme qui consiste `a intégrer le concept de no good dans le protocole AFC d’origine. Ce mécanisme nous a permis de réduire considérablement l’arbre de recherche `a travers un apprentissage dynamique des agents. • AILFC (Asynchronous Inter Level Forward-Checking) : Dans cette méthode nous exploitons les caractéristiques intrinsèques du graphe de contraintes, ce dernier est transformer en une structure pseudo-arborescente. Cette approche nous a permis d’améliorer les performances, `a travers une recherche asynchrone et parallèlement concurrente. ¸ AMAC (Asynchronous Maintenance of Arc-Consistency AMAC) : Cette contribution consiste `a la propagation des effets d’arc-inconsistance `a travers les agents voisins. Cet algorithme contribue `a la réduction de l’espace de recherche de manière `a ce que les inconsistances causées par les suppressions potentielles des valeurs soient propagées. D’autre part nous avons réalisé trois approches de résolution des problèmes DCOPs. ¶ ABFS (Asynchronous Breadth-First Search DCOP) : Cet algorithme consiste `a transformer le graphe de contraintes du probl`eme `a résoudre en un arbre Breadth-First Search (BFS), le parcours des agents en largeur-d’abord a permis la réduction de l’espace de recherche et l’amélioration de la solution. • DisDB&B (Distributed Dynamic Branch and Bound) : Une nouvelle méthode pour l’ordonnancement dynamique des agents et c’est aussi une approche de base pour l’apprentissage distribué des no goods values. ¸ DyBop (Dynamic Backtracking for DCOP) : Une version Asynchrone de l’algorithme DisDB&B. Cette technique est basée sur l’intégration du mécanisme “forward checking”, permettant l’amélioration des bornes inférieures. Tous ces algorithmes ont ´et´e implémentés dans la plate-forme DisChoco, ce qui a permis de réaliser plusieurs évaluations expérimentales. Celles-ci ont montré que ces algorithmes permettent d’obtenir un niveau de performances beaucoup plus élevé que les méthodes déjà existantes.