Traitement des problèmes de satisfaction et d’optimisation de contraintes distribués

Abstract

Ce travail se place dans le domaine de raisonnement par contraintes distribué (DCR). Il vise à développer des méthodes de résolution des problèmes de satisfaction et d’optimisation de contraintes distribués. Un premier algorithme (ABT-cf), conçu par la compilation des solutions locales dans le protocole ABT à multi-variables, permet de résoudre les problèmes de satisfaction de contraintes distribués (DisCSPs) avec problèmes locaux complexes. Une nouvelle technique de l’interchangeabilité a été appliquée à cet algorithme pour augmenter son efficacité. Un second algorithme (ABFS) qui améliore l’algorithme AFB-BJ, permet de résoudre les problèmes d’optimisation de contraintes distribués (DCOP). Cet algorithme est basé sur la transformation du graphe de contraintes en un arbre. Le troisième algorithme (DyBop) et sa version préliminaire DisDB&B sont deux algorithmes dynamiques. L’ordre dynamique est assuré par la mémorisation des nogoods valués. Tous ces algorithmes ont été implémentés dans la plate-forme DisChoco développée dans la cadre de ce travail, et qui a permis de réaliser plusieurs évaluations expérimentales. Celles-ci ont montré que ces algorithmes permettent d’obtenir un niveau de performances plus élevé qu’avec d’autres méthodes existantes.