Méthodes de recherche systématiques pour le raisonnement par contraintes centralisé et distribué

Abstract

La programmation par contraintes est l’une des orientations stratégiques en matière de recherche informatique. Le succès de la programmation par contraintes est dû principalement à son potentiel élevé à résoudre des problèmes réels. Dans cette thèse, nous avons proposé une approche basée sur la programmation par contraintes pour résoudre, de manière centralisée, les conflits entre les avions en cours de vol. La programmation par contrainte est également concernée par la résolution distribuée des problèmes de satisfaction de contraintes. Plusieurs problèmes dans l’intelligence artificielle distribuée ont pour objectif de trouver une combinaison cohérente des actions d’agents autonomes. La plupart de ces problèmes peuvent être formalisés sous forme de Problèmes de Satisfaction de Contraintes Distribués (DisCSP)s.Différents algorithmes ont été développés pour la résolution desDisCSPs. Parmi tous ces algorithmes, le Backtracking Asynchrone (ABT) est un algorithme central. Cependant, ABT nécessite un ordre total statique sur les agents. Etant donné que le changement de l’ordre des agents au cours de la recherche peut améliorer le temps de calcul d’une manière drastique, de nombreux algorithmes qui permettent le changement d’ordre ont été proposés. Néanmoins, quand la recherche d’une solution se fait d’une manière distribuée et asynchrone, le changement dynamique de l’ordre devient nettement plus complexe que dans le cas centralisé. Dans cette thèse, nous avons mis en évidence et corrigé quelques bugs dans des algorithmes existants qui permettent le changement d’ordre. Nous avons également proposé un nouvel algorithme appelé Agile-ABT qui permet plus de flexibilité par rapport à toutes les anciennes approches. Les expérimentations que nous avons menées confirme les bonnes performances de notre algorithme.